10.3 Convolutional Codes

Besides block codes, convolutional codes are the second code group in channel coding. Convolutional codes are also using a linear mapping of a set of message words on a set of code words. Conceptual message and code words are of infinite length and therefore information or code sequences are considered. The decoding methods allow processing of soft input, i.e. for correction the knowledge about the validity of a detected symbol value can be taken into consideration. In contrast to the algebraic decoding of block codes decoding for convolutional codes is based on the optimum estimation of the received sequence.

If we assume binary data for convolutional coding, a message sequence is separated in blocks of m bits and by a coder coded on n bits. Then an n bit code word not only depends on the momentary information sequence at the coder but in addition on k previous sequences, the coder has a memory of order k.
The convolutional coder can be assumed as a digital LTI system with m inputs and n outputs. The code bits depend on the momentary message bit and on the state of the memory. For every step the input data of length m bit is written in a serial shift register of length (k+1)·m and together with the remaining k·m bit of the register linked to n code bit. The output data result in a combination of different taps of the register (mostly XOR connections (addition modulo 2)) (cf. Figure 10-10). We assume that the shift register at the beginning of the coding only contains zeros. For convolutional codes the input bits always affect more than one output bit, i.e. convolutional codes in contrast to block codes have a memory. There are 2k·m different memory contents. The constraint length of the code Lcode is (k+1)·m and therefore equals the length of the memory plus the momentary character.
With this type of coding convolutional codes are suitable for correcting single bit errors.

Here, the code rate CR is defined as quotient of m input bits taken at a time to n output bits of the same time:
\( CR=\frac{m}{n}=\frac{\text{number of incoming signals}}{\text{number of generator polynomials}}=\frac{\text{number of message bits}}{\text{number of code bits}} \)     (10-7)

A generator polynomial describes the circuit of the taps of the shift registers as shown in Figure 10-10.

A block diagram is shown. The upper line gives the generator polynomial G1 of z equals 1 plus z plus z squared. The lower line is generator polynomial g2 of z equals 1 plus 0 plus z squared. In the middle the information bits are given as input xi is split in three streams. The middle one leads to a delay unit T with xi-1. After this the signal is added to the upper stream and in parallel fed to a second delay unit T with xi-2. The resulting signal is added to both upper and lower line. At the end there is a switch, switching between the upper and the lower line to give the code bits c from the two streams c1 and c2.
Figure 10-10: Block diagram of a convolutional coders with m = 1, n =2 and k =2.

There are different possibilities to describe convolutional codes. In the following the state-chart and the trellis diagram are explained.

Tab. 10-4: State chart.
State A
 B
 C
 D
Memory content at moment t (xt-1 xt-2) 0 0
 1 0
 0 1
 1 1
Input bit xt 0 1
 0 1
 0 1
 0 1
New state at moment t+1 A B
 C D
 A B
 C D
Resulting code bits (c1 c2) 00 11
 10 01
 11 00
 01 10

For the circuit in Figure 10-10 the state chart in Tab. 10-4 and Figure 10-11 results.

State chart
A convolutional coder can be dealt with as a Mealy automat (Figure 10-11). Therefore, the dependence of the output signal from the actual state and from the input signal are described by giving possible changes of state and resulting output values. In contrast to the Trellis diagram no information about the timing of the coding is contained.
A state diagram with four nodes is given. The nodes are arranged in a diamond: on top is state 00, on the left 10, on the right 01 and at the bottom 11. From 00 an arrow 0/00 returns to 00, an arrow 1/11 leads to 10. From 10 an arrow 0/10 leads to 01, and an arrow 1/01 leads to 11. From 01 an arrow 0/11 leads to 00 and an arrow 1/00 to 10. Fromm 11 the arrow 1/10 returns to 11 and arrow 0/01 leads to 01.

Figure 10-11: State chart. 

Trellis diagram
A trellis diagram consists of nodes and edges. Every node represents one of the 2k·m states which the memory of the coder can take. Every edge is a valid change from one state to a valid successor state. The edges are labeled with the output bits and the input bits separated by a slash. The edges may also be marked in colors or graphically. The trellis diagram is the basis of the description of the Viterbi decoder (Figure 10-12, Figure 10-13).

The Viterbi algorithm searches the code sequence c which has the minimum Hamming distance from the received sequence e.
\( \lambda_i= \begin{cases} 0 & \text{ for } c_i \neq e_i \\ 1 & \text{ for } c_i=e_i \end{cases} \)

For every valid sequence Λ = Σ λi is calculated. The sequence with the largest Λ is that which is sent with highest probability, i.e. the sequence with the highest number of correctly receives bits.

Example: Decoding after Viterbi
Given is the generator polynomial in Figure 10-10 G1(z) = z² + z + 1 and G2(z) = z² + 1. Hence, the following assignment of the register and the following coding results as in Tab. 10-5. The message is added to the left of the register. The output follows the example in Figure 10-12 on the right.

Tab. 10-5
Message 1
 0
 1
 1
 0 0 0
Register (x xt-1 xt-2) 100 010 101 110 011 001 000
Coded bits (G1 G2) 11
 10
 00
 01
 01 11 00

On the left there is a column with states 00, 10, 01, 11. In the top lone the input is given as 1011000. On the very right the example connections for dedicated output are given, dotted for 0 from 00 to 00, from 10 to 01, from 01 to 00, and from 11 to 01, and solid for 00 to 10, 10 to 11, 01 to 10, and 11 to 11. In the middle this is used to span a tree, starting at 00 input 1 leads to 10 solid, dotted option to 00. The next input zero starts at 10 and goes to 01 dotted, but the other options are 00 to 00 dotted, 00 to 10 solid, and 10 to 11 solid. Now all states are activated and we always have all options from the very right. Input 1 will go from 01 to 10, another 1 from 10 to 11, a zero from 11 to 01, a zero from 01 to 00. As this is the second to the last step only the following connections exist here: 00 to 00 dotted, 10 to 01 dotted, and 11 to 01 dotted. The final step with input 0 shows 00 to 00 and 01 to 00 dotted.

Figure 10-12: Trellis diagram.

For decoding the single nodes are labeled with the distances. If different distances arrive at a node, then the paths that do not have the minimum distance are not considered anymore (light grey paths in Figure 10-13). The paths that remain are called survivors.

It is the same as figure 10-12 but the states are labeled with their distances from the code word. For decoding we search for a path with distance 0. This is 00 – 10 – 01 – 10 – 11 – 01 – 00 – 00.

Figure 10-13: Trellis diagram labeled with distances.

You have completed 7% of the lesson
7%