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

G 1

Input D D D D D D

G 2

FIGURE 3.10. Viterbi convolutional coding scheme.

( , )

In general, codes are designated with the notation n k according to the num-

/

ber of n output code bits and k input data bits. The ratio k n is called the rate of

the code and is a measure of the fraction of information contained in each code bit.
Figure 3.10 describes the Viterbi convolutional coding scheme used for Galileo.
The Viterbi convolutional coding of all data channels is characterized by the fol-
lowing values: coding rate = 1 / 2, constraint length 7, generator polynomials

G 1 133 (octal), and encoding sequence G 1 and then G 2 .

That is, there are taps at seven points along the encoder shift register, and it gen-
erates two encoded channel symbols for each input data bit. Note that G 1 =

= 171 (octal), G 2 =

171

(octal) is 001111001 in binary and G 2 = 133 (octal) is 001011011 in binary.

6, and 7, numbered from right to left, are
connected to modulo-2 adders and for G 2 the taps 1

We observe that for G 1 the taps 1 , 4 , 5 ,

5, and 7 are connected
to modulo-2 adders. The error-correcting power is related to the constraint length,
increasing with longer lengths of shift register.
After the Viterbi convolutional encoding block follows an interleaving proce-
dure. The purpose of interleaving is to increase the efficiency of the convolutional
coding by spreading the burst errors in order to improve the correction capacity
of the specific convolutional decoding algorithm applied in the receiver.
Normally interleaving is implemented by using a two-dimensional buffer ar-
ray. The data enter the buffer array row by row and are then read out column
by column. The result of the interleaving process is ideal if a burst of errors in
the communication channel after de-interleaving becomes spaced single-symbol
errors, which are easier to correct than consecutive ones.

, 2 , 4 ,

Example 3.2 Below we illustrate how an input data stream is read, column by
column, into an array and then read out, row by row, to achieve the bit interleaving
operation:

- Data input

x 16 x 15 x 14 x 13 x 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1

- Interleaving array

x 1 x 5 x 9 x 13

x 2 x 6 x 10 x 14

x 3 x 7 x 11 x 15

x 4 x 8 x 12 x 16