4
Convolutional Codes
4.1. Introduction
Convolutional codes are the second main class of error correcting codes. They were introduced by Elias in 1955 [ELI 55] and were first used for spatial communications. After the discovery of Viterbi’s algorithm in 1967, they were applied in almost all communication systems.
In this chapter, we will first study the convolutional codes and their encoders. Then, we will introduce Viterbi’s algorithm currently used for the decoding of these codes.
For a deeper development of convolutional codes, we recommend the books [PIR 88] and [JOH 99]. In this chapter, we will restrict ourselves to binary codes.
4.2. Mathematical representations and hardware structures
4.2.1. Definitions
A convolutional code is a code that transforms a semi-infinite sequence of information words into another semi-infinite sequence of codewords.
Let u be the input sequence or sequence of information words of dimension k of a binary convolutional encoder of rate 
, u = u0, u1, u2, … where ui = 
is the ith information word of the sequence, and let c be the output sequence or sequence of codewords of dimension n, c = c0, c1, c2, … where 
is the ith codeword of the sequence as shown in Figure 4.1.
Figure 4.1. Convolutional encoder
It is usually simpler to describe these sequences using the delay operator D. Thus, we have:
with:
where 
is the finite field with two elements. The set of the causal Laurent series with the form:
is an ideal1 denoted by 
subset of the field of the Laurent series 
. It should be said that some authors prefer to consider the sequences u(D) and c(D) as Laurent series.
DEFINITION 4.1.– A binary convolutional encoder of rate k/n is an implementation using a linear circuit of the association ϕ of a sequence of information words composed of k bits u(D) with a sequence of codewords composed of n bits c(D):
with:
G(D) is the generator matrix used by the encoder of dimension k × n and rank k:
The elements gi,j(D) of the generator matrix G(D) are polynomials in D or rational functions in D.
For a given generator matrix, different encoder structures can be considered. There are two classes of convolutional encoders: non-recursive and recursive encoders.
In the case of non-recursive encoders, the n output bits are a function of the k current input bits and a finite number of previous input bits. This encoder can be seen as a finite response system over 
. The elements gi,j(D) of the matrix generator are polynomials in D.
DEFINITION 4.2.– A convolutional code is the set of all the possible output sequences c(D) of the convolutional encoder.
There exists a set of generator matrices G(D) and encoders corresponding to a given convolutional code.
DEFINITION 4.3.– Two generator matrices G(D) and G′(D) are equivalent if they generate the same convolutional code. Two convolutional encoders are equivalent if their generator matrices are equivalent.
For a given encoder, let Mi be the number of memory elements associated with the ith binary input sequence:
The total number of memory elements is equal to 
EXAMPLE 4.1.– Let us consider the example of the non-recursive convolutional coder k = 1, n = 2 M = 2 of rate 1/2 given in Figure 4.2.
Figure 4.2. Non-recursive convolutional coder of rate 1/2 M=2 g1=7, g2=5
Its generator matrix is the following :
Since the maximum degree of the polynomials is two, the hardware structure of this encoder will require only M = 2 memory elements.
We can describe the polynomial generators of the convolutional encoder using the octal notation:
In this example, we have the following relations:
Equations [4.5] and [4.6] can at time i be written as follows:
EXAMPLE 4.2.– Let us consider a non-recursive convolutional encoder k = 1, n = 2 M = 6 of rate 1/2 given in Figure 4.3.
Figure 4.3. Non-recursive convolutional encoder of rate 1/2 M=6 g1=133, g2=171
The generator matrix is the following:
This encoder has been used very often in spatial communications and telecommunications.
For the recursive convolutional encoder, the n output bits can be a function of an infinite number of input bits. Consequently, the recursive convolutional coder can be seen as a system with an infinite impulse response (IIR) in . The elements gi,j(D) of the generator matrix are rational functions.
A binary convolutional encoder of rate k/n is systematic if the k input bits are replicated at the output of the coder. This generator matrix is written as follows:
EXAMPLE 4.3.– Let us consider the example of the systematic recursive convolutional encoder k = 1, n = 2 M = 2 given in Figure 4.4.
Figure 4.4. Systematic recursive convolutional encoder 1/2 M = 2
The generator matrix of this systematic recursive convolutional encoder is the following:
Consequently, we have:
The equality in [4.7] of each power of D implies that the we have the following parity check equation for each position i:
The encoders of the first and third examples are equivalent.
Recursive convolutional encoders have rarely been used in the past, but the work of Battail [BAT 93] has shown that they imitate the random encoder if the denominator polynomial was primitive. These codes are the constituent codes of the so-called turbo codes as we will show in Chapter 5.
4.2.2. Matrix representation of convolutional codes
Compared to linear block encoders, a convolutional encoder is composed of memory elements that memorize a state vector of dimension M bits. So, the codeword ci is not only a linear function of the information word ui but also of the internal state of the encoder at time i, si.
The relations between ui, si, si+1 and ci are the following:
While a binary linear block encoder for a (N, K) code is defined by a matrix G of dimension K × N, a convolutional encoder of rate k/n is defined by four matrices 
These equations correspond to the state equation and output equation that are used to describe a time invariant discrete linear system [KAI 80].
For the first example, we have the following relations:
The state and output equations are given by:
From the state and output equations [4.9], we have the following relations using the delay operator D:
where u(D) and c(D) are defined in [4.1] and [4.2], respectively, and:
We can observe that we obtain the classical relation between the generator matrix G(D) and the matrices 
Another matrix representation is obtained after serializing the input and output bits of the convolutional encoder:
Relation [4.3] becomes:
where G is a semi-infinite matrix, the elements of which are binary.
We have described the matrix G only for the convolutional encoders with k = 1 (rate 1/n) given in Figure 4.5. The general case can be obtained without difficulty.
Figure 4.5. Generic non-recursive convolutional encoder of rate 1/n
The matrix G has the following form:
with 
.
For the first example, the generator matrix is the following:
As with block codes, we can introduce the semi-infinite parity check matrix H given by:
Each sequence c should satisfy the relation:
For the first example, the parity check matrix is the following:
4.3. Graphical representation of the convolutional codes
4.3.1. State transition diagram
The state transition diagram allows us to easily describe the behavior of the convolutional encoder. For a convolutional encoder composed of M memory elements, we define the internal state at time i by the vector si of dimension M:
is the state at time i of the j-th memory element.
The state transition diagram is an oriented graph composed of 2M vertices. Each vertex is associated with an internal state of the encoder.
EXAMPLE 4.4.– The state transition diagram of the non-recursive convolutional encoder of rate 1/2 defined using the generator matrix G(D) = (1 + D + D2, 1 + D2) is given in Figure 4.6.
In this example, we have M = 2 and consequently 2M = 4 internal states as shown in Table 4.1.
Each branch is labeled by its respective output bits (here, 
and 
). By convention, the branches with dash line and continuous lines correspond to an input bit equal to “0” and “1”, respectively.
Figure 4.6. State transition diagram for the non-recursive convolutional code g1 = 7, g2 = 5
Table 4.1. Description of the internal states
| Internal state |  |
 |
|---|---|---|
| a | 0 | 0 |
| b | 0 | 1 |
| c | 1 | 0 |
| d | 1 | 1 |
4.3.2. Trellis diagram
From a state transition diagram, it is possible to build a bipartite graph also called an elementary trellis. Each branch b of the bipartite graph connects a starting state s−(b) to an arrival state s+(b).
EXAMPLE 4.5.– The elementary trellis for a non-recursive convolutional encoder of rate 1/2 defined by the generator matrix G(D) = (1 + D + D2, 1 + D2) is given in Figure 4.7.
At each node 2k branches arrive and leave. The total number of branches is equal to 2k+M ; (2k+M = 8 in this example since k = 1 and M = 2).
Figure 4.7. Elementary trellis of a non-recursive convolutional encoder g1 = 7, g2 = 5
The trellis diagram is a state transition diagram of which the horizontal axis is the time. It is obtained by concatenating an infinite number of elementary trellis. The trellis diagram for the non-recursive convolutional coder of rate 1/2 defined by the generator matrix G(D) = (1 + D + D2, 1 + D2) starting at state a is given in Figure 4.8.
Figure 4.8. Trellis diagram for the non-recursive convolutional coder g1 = 7, g2 = 5
On each branch, we labeled the value of the output bits 
and 
. In this trellis diagram, the continuous lines correspond to ui = 1, while the dash lines correspond to ui = 0. We can see that after a transitory duration, the trellis diagram is indeed the concatenation of the elementary trellis.
4.3.3. TWL graphs
Tanner, Wiberg and Loeliger (TWL) graphs [WIB 95] or extended Tanner graphs are used to describe the convolutional coders and also the concatenated convolutional coders.
In addition to the binary variable nodes and the parity check nodes, we add a third family of nodes called state variable node or hidden variable node. The hidden variable nodes are symbolized by a double circle.
Furthermore, the parity check nodes can be replaced by local functions. These local functions are symbolized by black squares in these graphs.
The TWL graph of a systematic convolutional coder of rate 1/2 is given in Figure 4.9.
Figure 4.9. TWL graph of a systematic convolutional coder of rate 1/2
The local function 
at position i is defined by the state and output equations [4.9] of the convolutional encoder. We have:
The local function 
corresponds to the elementary trellis of the convolutional encoder that governs the relationship between 
and ui.
4.4. Free distance and transfer function of convolutional codes
The free distance of a convolutional code is the minimum distance between the two output sequences associated with two paths that diverge from the same state and converge again. The determination of the free distance of a convolutional code can be obtained from the trellis diagram. To obtain the free distance, we take the all-zero path associated with the all-zero input sequence u = [0, 0,… ] as the reference path. This path is shown in bold line on the trellis diagram given in Figure 4.10. On each branch, we have given the Hamming distance of the two output bits 
and 
.
Figure 4.10. Trellis diagram of the non-recursive convolutional code g1 = 7, g2 = 5
From this trellis diagram, we can observe that there is only one path leaving the reference path at time i = 0 at the distance 5 from the reference path. This is the path (a,c,b,a). Consequently, the free distance of this convolutional code is equal to 5. It should be noted that there exist also two paths (a, c, d, b, a) and (a, c, b, c, b, a) at the distance 6 from the reference path.
The transfer function of a convolutional code gives its distance properties. This function can be obtained from the state diagram of the convolutional encoder.
In order to determine the transfer function, we have to modify the state diagram as follows: first, all the branches are labeled with DwOWwI where wI and wO are the Hamming weight of the information bits and output bits, respectively. In our example, one information bit and two output bits are associated with each branch. We suppress the branch going back to the state a since it does not impact the distance properties of the code. Finally, we separate the node a into two distinct nodes a and e corresponding to the input and output nodes of the modified state diagram, respectively. The modified state diagram for the non-recursive convolutional encoder of rate 1/2 defined by the generator matrix G(D) = (1 + D + D2, 1 + D2) is given in Figure 4.11.
Figure 4.11. Modified state diagram of a non-recursive convolutional code g1 = 7, g2 = 5
From this state diagram, we can compute the transfer function of this convolutional code. We have the four following equations:
By solving this system of equations, we obtain the following Input Output Weight Enumerator Function (IOWEF) function T(W,D), defined in Chapter 32:
where Bw,d is the number of paths that diverge from the state 0 and converge again to this state, with information sequences of weight w and output sequences of weight d. By setting L = 1 and W = 1, we obtain the transfer function T(D):
The transfer function T(D) informs us about the free distance of the code (here 5) and the number of associated sequences (here only one sequence). This function is also used to evaluate the performance of the convolutional code.
Let the sequence c0 corresponding to the all-zero reference paths and cd be a sequence of weight d. Using the union bound, we can bound the bit error rate over additive white Gaussian noise channel considering soft input decoding as follows:
where:
and:
which is the pairwise error probability obtained using relations [3.97] and [3.102]. The set of pairs 
gives the spectrum distance of the convolutional code. By replacing [4.30] into [4.28], we finally obtain the following upper bound:
For the previous example, we can show that 
In Table 4.2, we give the best convolutional codes with rate 1/2 [LIN 83].
Table 4.2. List of the best convolutional codes of rate 1/2
| Number of memory elements | Code | dfree |
|---|---|---|
| 1 | (2, 3) | 3 |
| 2 | (5, 7) | 5 |
| 3 | (15, 17) | 6 |
| 4 | (23, 35) | 7 |
| 5 | (53, 75) | 8 |
| 6 | (133, 171) | 10 |
| 7 | (345, 237) | 10 |
| 8 | (561, 753) | 12 |
| 9 | (1161, 1545) | 12 |
| 10 | (2335, 3661) | 14 |
| 11 | (4335, 5723) | 15 |
| 12 | (10533, 17661) | 16 |
4.5. Viterbi’s algorithm for the decoding of convolutional codes
The first method used for the decoding of the convolutional codes was sequential decoding [JEL 69, JOH 99]. However, from 1970, sequential decoding has been replaced by maximum likelihood decoding using the Viterbi algorithm [VIT 67, FOR 73]. Indeed, the regular structure of the trellis is particularly suitable for the application of the Viterbi algorithm as we will now see.
We have shown in Chapter 3 that the search for the maximum likelihood sequence 
is equivalent to the search for the maximum likelihood path (or sequence of states). Thus, the sequence can be directly obtained. We have also seen that the general principle of the Viterbi algorithm is to eliminate, at each section of the trellis diagram, the paths (and associated sequences) that cannot be the maximum likelihood path. At each trellis node, we only keep one path.
We will illustrate the Viterbi algorithm by using the convolutional encoder previously considered. We assume that the decoder is hard input, i.e. the metrics are Hamming distances. We suppose that at time i = 0, the convolutional encoder is in state a and that the input sequence is 1001. The sequence at the output of the decoder is consequently 11 10 11 11. Let us assume that the received sequence is 11 00 11 11 (i.e. one error on the third bit).
At each time, we compute for each branch the Hamming distance between the couple of received bits and the couple of bits associated with the considered branch. Then, we compute the 2k+M cumulated metrics. The trellis diagram for this example is given in Figure 4.12.
Then for each node, we will select only one path called the survivor path: the survivor path is the path the minimum Hamming distance from the received sequence.
EXAMPLE 4.6.– At time i = 3, two paths converge toward the state a:
- – the path (a, c, b, a) is at distance 0+1+0 = 1 from the received sequence;
- – the path (a, a, a, a) is at distance 2+0+2 = 4 from the received sequence.
Figure 4.12. Viterbi decoding for a non-recursive convolutional encoder g1 = 7, g2 = 5
The survivor path for this node will be the path (a, c, b, a). At time i = 4, we have only four survivor paths:
- – the path (a, a, c, b, a) with the ending state a with distance 2;
- – the path (a, a, a, c, b) with the ending state b with distance 3;
- – the path (a, c, b, a, c) with the ending state c with distance 1;
- – the path (a, c, d, d, d) with the ending state d with distance 3.
Consequently, the maximum likelihood sequence is the one corresponding to the survivor path with the ending state c at i = 4, i.e. the path (a, c, b, a, c). This path corresponds to the sequence of codewords 11101111 and the sequence of information words 1001: the Viterbi decoder has been able to correct the error due to the channel.
The Viterbi algorithm can also be performed for soft input decoding by replacing the Hamming distance by the Euclidean distance. As seen in Chapter 3, soft decoding achieves a gain of about 2 dB compared to hard decoding. In practice, it is necessary to quantize the input using 2b levels, with b = 3 or b = 4.
4.5.1. Complexity of the Viterbi decoder
For a convolutional encoder of rate k/n composed of M memory elements, we have 2M internal states: the Viterbi algorithm requires us to memorize at each time 2M survivor paths and their associated cumulated metrics. At each time, 2k paths converge toward each node; for each of these paths, we will have to compute the cumulated metric in order to find the survivor path. Consequently, the number of cumulated metrics that must be performed at each time is 2k+M. This calculation increases exponentially with k and M, which limits the use of the Viterbi algorithm to the small values of k and M.
In practice, it is not necessary to wait for the end of the full received sequence to start the decoding: indeed, we can show that after a given time (about 5M), all the survivor paths converge to the same path. Consequently, we can at time i estimate the symbol emitted at time i − 5M.
4.6. Punctured convolutional codes
It is possible from a convolutional code of rate k/n to construct convolutional codes with higher rates by suppressing some of the output symbols of the original encoder [YAS 84, CAI 79]. This technique, called puncturing, allows us to modify the rate of the convolutional code without changing the structure and complexity of the decoder. To illustrate puncturing, we will consider the example of a convolutional coder of rate 2/3 obtained from the convolutional encoder of rate 1/2 considered previously. Puncturing is obtained by removing one symbol every four symbols at the output of the encoder of rate 1/2. At the reception, we insert a zero symbol instead of the missing symbol.
The trellis diagram of this punctured convolutional encoder of rate 2/3 is given in Figure 4.13.
Figure 4.13. Trellis diagram of a punctured convolutional encoder
The free distance of the convolutional code of rate 1/2 and M = 2 is equal to 5; it is reduced to 3 after puncturing with rate 2/3.
4.7. Applications
Convolutional codes were used for spatial communications as early as 1969. The Pioneer 9 mission in 1969 (Sun), Pioneer 10 mission in 1972 (Jupiter), Pioneer 11 mission in 1973 (Saturn) and Pioneer 12 mission in 1978 (Venus) used a convolutional code of rate 1/2 of length M = 31 using a soft input sequential decoding. From 1977, sequential decoding was replaced by the Viterbi decoder and the convolutional code (163,171) of rate 1/2 has become a de facto standard. From 1987, the Consultative Committee for Space Data Systems (CCSDS) standard has often been used for spatial communications. The channel coding defined in this standard is composed of a Reed-Solomon code (255,223) as external code, an interleaver and a convolutional code (163,171) of rate 1/2 and M = 6 as inner code. This scheme was used, for example, for the Voyager 1 and 2 missions in 1979 (Jupiter and Saturn). In 1990, for the Galileo mission (Jupiter), the Jet Propulsion Laboratory (JPL) developed a convolutional code of rate 1/4, M = 14 (8,192 internal states) with a free distance of 35 and its associated Viterbi decoder (Big Viterbi Decoder (BVD)).
For the digital video broadcasting systems by satellite (DVB-S) and terrestrial (DVB-T), the coding scheme is close to the CCSDS standard. It is composed of a Reed-Solomon code (204,188,17), a convolutional interleaver and a convolutional code (163,171) of rate 1/2, M = 6, with puncturing 3/4, 4/5, 5/6 and 7/8. The digital audio broadcast (DAB) uses a non-recursive convolutional of rate 1/4 M = 6, with a large choice of puncturing patterns.
For the second generation of radiocommunication systems, the Global System for Mobile Communications (GSM) standard uses a convolutional code of rate 1/2 with M = 4, while the IS95 standard uses a convolutional code of rate 1/2 with M = 8 as for the Globalstar cellular satellite system.
Convolutional codes are also used in the concatenated convolutional codes as we will study in Chapter 5.
4.8. Exercises
4.8.1. Exercise 1: systematic recursive convolutional code
- 1) Draw the structure of the recursive convolutional coder defined by the following generator matrix :
- 2) Determine the state diagram and elementary trellis of this code.
- 3) Find the free distance of this code.
4.8.2. Exercise 2: non-recursive code and Viterbi decoding
Let us consider the non-recursive convolutional coder of rate R = 1/2 defined by the generator matrix G(D) = (1 ; 1 + D).
- 1) Draw the hardware structure of the encoder.
- 2) Determine the associated trellis diagram.
- 3) Find the free distance of this code.
- 4) We have the input sequence u = [1111]. Determine the transmitted sequence. The binary received sequence is 11 01 10 10. Assuming that the initial state is the zero state, perform the hard input Viterbi algorithm to estimate the input sequence.
- 5) The signal is converted into a bipodal signal before transmission bit 0 ⇒ −1 and bit 1 ⇒ +1. Let us assume that the received sequence is: +2.0 +1.3 −0.3 +0.2 +1.6 −1.0 +0.5 −2.0, perform the soft input Viterbi algorithm to estimate the input sequence (for the metric calculation, we can use the Euclidean or Manhattan distances).
- 6) We perform puncturing to obtain a convolutional code of rate R=2/3 with the puncturing pattern
The received sequence is then +2.0 +1.3 −0.3 X +1.6 −1.0 +0.5 X. Perform the soft input Viterbi algorithm to estimate the input sequence.