Galileo Signal - A Software-Defined GPS and Galileo Receiver: A Single-Frequency Approach - page 42

Direction of data flow from SV

MSB Data Data

Direction of data
flow from SV

Data

Data Data

LSB Data

MSB LSB

FIGURE 3.9. Ordering principle for data.

The concatenation of the input frame and the checksum then corresponds to the
polynomial T C since multiplying by x r corresponds to shifting the

input frame r bits to the left. The algorithm chooses the checksum C such that
T is divisible by a predefined polynomial P of degree r , called the generator
polynomial .
The algorithm divides Mx r by P and sets the checksum equal to the binary
vector corresponding to the remainder. That is, if Mx r

Mx r = +

= QP + R ,where R is a

polynomial of degree less than r ,then C R and the checksum is the binary vec-

tor corresponding to R . If necessary, the algorithm preceds zeros to the checksum
so that it has length r .
The MATLAB CRC generator does the following:
1. Left-shift the input frame by r bits and divide the corresponding polynomial
by P .
2. Set the checksum equal to the binary vector of length r corresponding to
the remainder from step 1.
3. Append the checksum to the input data frame. The result is the output
frame.
The CRC algorithm uses binary vectors to represent binary polynomials, in
descending order of powers. For example, the vector

=

[ 1101 ] represents the

polynomial x 3 x 2 + + 1.

T , corresponding to

Example 3.1 Suppose the input frame is [ 1100110 ]

x 6 x 5 x 2

the polynomial M = + + + x , and the generator polynomial is P =

x 3 x 2 3. By polynomial division Mx 3 x 6 x 3 x .

Remember that any binary number added to itself in a modulo-2 field yields zero.
The remainder is R

+ + 1, of degree r = = ( + + x ) P +

T . Note that an

= x so that the checksum is then [ 010 ]

extra 0 is added on the left to make the checksum have length 3.

3.3.3 Forward Error Correction and Block Interleaving
The starting point is a digital information source (transmitter) that sends a data
sequence comprising k bits of data to an encoder. Employing forward error-
correction coding, the encoder inserts redundant bits, thereby outputting a longer
sequence of n code bits called a codeword . At the receiving end, codewords are
used by a suitable decoder to extract the original data sequence.