5
Concatenated Codes and Iterative Decoding
5.1. Introduction
Since the works of Shannon in 1948 [SHA 48], researchers have proposed different error correcting codes with a reasonable complexity and if possible a high minimum distance. The idea of combining a few simple codes to obtain a stronger code was proposed in 1954 by Elias [ELI 54]. In his thesis in 1963, Gallager introduced the low density parity check codes (LDPCs) which were then forgotten for a few decades. In fact, this idea enables us to obtain codes with characteristics close to random coding but with a much simpler coding and decoding structure. In 1966, Forney [FOR 66] introduced the serial concatenation of a convolutional code and a linear block code. This structure has been a standard for decades in communication systems. However, all these structures were based on decoding algorithms performing only hard decisions.
Battail [BAT 87, BAT 89] showed the importance of soft input soft output decoding and the use of random coding as a criterion to build good codes. In 1993, Berrou, Glavieux and Thitimajshima [BER 93] proposed a new class of error correcting codes called turbo codes or parallel concatenated convolutional codes. While concatenation of codes, soft output decoding and iterative decoding had been previously proposed, this discovery permitted significant progress in the research of codes with performance close to the Shannon capacity (a few tenths of dB for frames of several thousand bits). This work on and rediscovery of LDPC significantly modified the field of error correcting codes.
In this chapter, we will start by giving the principles of soft input soft output decoding including the sum-product and forward-backward algorithm for convolutional codes. Then, we will describe the LDPC codes, their encoders and their iterative decoders for erasure channel, binary symmetric channel and additive white Gaussian noise channel. We will then study the parallel concatenated convolutional codes or turbo codes and the structure of the associated iterative decoder. Finally, we will briefly introduce other classes of concatenated codes such as the parallel concatenated block codes (PCBCs), product codes and serial concatenation of convolutional codes.
5.2. Soft input soft output decoding
5.2.1. Introduction
5.2.1.1. A posteriori and intrinsic probabilities
In Chapter 3, we introduced the maximum a posteriori (MAP) decoder which gives the received sequence y searches among all the possible transmitted sequences x, the estimated sequence 
for which the conditional probability Pr(x|y) is the highest.
In this section, we will focus on soft input soft output decoders that calculate for each bit, the conditional a posteriori probability APP(xi = a) as follows:
where ∝ means “proportional to”. Since the term p(y) is independent of a, it can be considered as a constant. We will often use this notation in this chapter.
Σx:xi=a means that the sum is performed over all codewords x for which the bit in position i is xi = a.
Since in this chapter we will restrict ourselves to the case of bipodal modulation, a can take the values +1 or −1.
If we assume that the conditional probabilities p(yj|xj) and the a priori probabilities Pr(xj) are independent, we can then write:
Finally, by taking out the a priori probability Pr(xi = a) and the conditional probability p(yi|xi) of the sum sign, we obtain the following classical relation:
with the extrinsic probability EXTR(xi = a):
So, the a posteriori probability APP(xi = a) is the product of three terms: the a priori probability Pr(xi = a), the conditional probability p(yi|xi) and the extrinsic probability EXTR(xi = a).
It is important to note that the computation of EXTR(xi = a) uses all the available information Pr(xj) and p(yj|xj) except Pr(xi = a) and p(yi|xi). We will see that this is a fundamental property for the iterative decoding of concatenated codes.
5.2.1.2. Log-likelihood ratio (LLR)
In relation [5.3], it is often more convenient to use the LLR instead of the probabilities. When a can take the values +1 or −1, relation [5.3] can be written as1:
This relation can simply be written as:
with:
LAPRI(xi), LINT(xi), LEXTR(xi) and LAPP(xi) are the a priori, intrinsic, extrinsic and a posteriori LLR, respectively.
Finally, we can also express p(yi|xi = +1) and p(yi|xi = −1) as a function of LINT(xi). From the definition of LINT(xi), we have :
By multiplying and dividing by 1 + exp(LI N T(xi)), this relation can be rewritten as:
Furthermore, we have:
Finally, we obtain the following relations:
5.2.1.3. Application to the additive white Gaussian noise channel
We consider a coded sequence x. This sequence is transmitted over an additive white Gaussian noise channel using a bipodal modulation. The received sample yi after matched filtering is equal to:
with xi = ±1 and ni is the noise sample with variance σ2 (to simplify the notation, we have normalized the expression by dividing by the term 
. Since the noise is Gaussian, the conditional probability p(yi|xi) can be written as:
Let us calculate the intrinsic information LINt(xi):
So, for the additive white Gaussian noise channel, the received signal yi is proportional to the intrinsic information LINt(xi). This property partially justifies the use of the LLR for the soft input soft output decoding.
We can write expression [5.14] as follows:
with 
and nIi is the noise term with a centered Gaussian distribution of variance 
. So, for a given value xi = +1, the variance of the LLR is the double of its mean 
. This property will be useful to evaluate the performance of the concatenated codes.
5.2.1.4. Case of the parity check code (3,2)
The factor graph2 associated with this code is given in Figure 5.1.
From the received samples y0, y1 and y2, we can compute the conditional probabilities p(y0|x0 = −1), p(y0|x0 = 1), p(y1|x1 = −1), p(y1|x1 = 1), p(y2|x2 = −1) and p(y2|x2 = 1). By applying relation [5.3], we obtain for
Figure 5.1. Factor graph of the parity check code (3,2)
with:
5.2.1.5. Case of the repetition code (3,1)
The factor graph associated with this code is given in Figure 5.2.
Figure 5.2. Factor graph of the repetition code (3,1)
From the received samples y0, y1 and y2, we can compute the conditional probabilities p(y0|x0 = −1), p(y0|x0 = +1), p(y1|x1 = −1), p(y1|x1 = +1), p(y2|x2 = −1), p(y2|x2 = +1). By applying lation [5.3], we btain for APP(x0 = a)
with
5.2.2. Sum-product algorithm
5.2.2.1. Introduction
The sum-product algorithm allows an efficient calculation of all the extrinsic probabilities EXTR(xi = a) and a posteriori probabilities APP(xi = a). Different signal processing algorithms can also be described using this algorithm. This algorithm is also known as the belief propagation algorithm in the field of artificial intelligence. The sum-product algorithm is applied on the factor graph of the code. The messages that are propagated on the branches of the graph can be probabilities or LLR.
5.2.2.2. Basic rules
From the results obtained with the parity check code (3,2) and the repetition code (3,1), we can determine the two decoding rules of the sum-product algorithm applied on a factor graph composed of binary variable nodes and control node defined by parity check equation (modulo 2 addition).
The first decoding rule allows the computation of the extrinsic information or message from a binary variable node toward a control node. Let the binary variable node of degree 3 described in Figure 5.3(a).
Figure 5.3. Message flows for the calculation of μc→T(c) and μT→c(c)
Let μTi→c(c) be the message from the control node Ti toward the binary variable node c. This message is the probability density of the binary variable c conditioned by the information obtained from the node Ta. The message μTi→c(c) is a vector (pi0, pi1) with pi0 + pi1 = 1. From the computation of the extrinsic information of the repetition code (3,1), we can calculate the message μc→T(c). The first rule is the following:
where the term pa1pb1 + pa0pb0 at the denominator is a normalization term.
We assume that the control node T is of degree 3 as shown in Figure 5.3(b). Let μci→T(ci) = (pi0, pi1) be the message from the variable node ci toward the control node T. From the computation of the extrinsic information of the parity check code (3,2), we can derive the expression of the message μT→c(c). The second rule is the following:
We can also use the LLR to compute the messages μc→T(c) and μT→c(c). Let us define:
From the first decoding rule, we obtain:
The second decoding rule can be written as:
by using the relation tanh (u/2) = (exp(u) − 1)/(exp(u) + 1) [BAT 79, HAG 96].
When the degree of the nodes is higher than 3, the decoding rules become:
where n(c) is the set of the control node connected to the variable node c and n(c)T means “the set n(c) except the control node T”.
where n(T) is the set of variable nodes connected to the control node T and n(T)c means “the set n(T) except the variable node c”.
The minimum-sum algorithm is a simplified version of the sum-product algorithm. It can be derived from the sum-product algorithm by replacing equation [5.26] by the following approximation:
where:
and:
We will use the operator 
in order to simplify the notation in the remaining of this chapter.
When the degree of the control node is higher than 3, relation [5.28] becomes using the operator:
In Figure 5.4, we have compared the level curves of the messages μT→c(c) computed using the sum-product algorithm (a) and the minimum-sum algorithm (b) for degree 3 control node. These curves have been plotted for μT→c(c)=0.5, 1, 1.5, 2, 2.5 and 3. For the high values of μci→T(ci), the two algorithms give the same result.
5.2.2.3. Application of the sum-product algorithm on factor graphs without cycle
The application of the sum-product algorithm on graph factors without cycle consists of performing the two rules starting from the leaves of the graph. The algorithm is finished as soon as each branch has been computed twice: once from variable node to control node and once from control node to variable node.
Figure 5.4. Level curves of μT→c(c) as a function of μca→T(ca) and μcb→T(cb) a) sum-product algorithm and b) minimum-sum algorithm
EXAMPLE 5.1.– Let us consider the linear block code (7,4) defined by the following parity check matrix:
The three parity bits are obtained as follows:
The Tanner graph of this code is given in Figure 5.5.
Figure 5.5. Tanner graph of the considered code (7,4)
Compared to the Hamming code (7,4), the minimum distance of this code is only 2.
Let x = [+1 −1 − 1 + 1 + 1 + 1 − 1] be the sequence associated with the binary codeword c = [1001110]. The sequence x is transmitted over an additive white Gaussian noise with variance σ2 = 0.75 and we assume that the received sequence is as follows: y = [+1.2 − 0.4 − 1.5 − 0.4 + 1.2 − 0.75 − 1.5].
Using the conditional probabilities p(yi|xi = −1) and p(yi|xi = +1) computed directly from the received samples yi, we can apply the sum-product on the factor graph of the code.
The different steps are described in Figure 5.6. We start by propagating the conditional probabilities toward the control T0,T1 and T2 (a). After that, using the second rule, we compute the messages from the variable node c0 (b). Then, we propagate the messages toward the control nodes using the first rule (c). Finally, using the second rule, we obtain the extrinsic probabilities EXTR(xi = a) associated with the variable nodes c0, c1, c2, c3, c4, c5 and c6 (d).
For example, for the bit c1, we have EXTR(x1 = +1) = 0.46 and EXTR(x1 = −1) = 0.54. The a posteriori probabilities can be computed using relation [5.3]:
After normalization, we finally obtain:
By directly using the intrinsic LLR LINT(xi) with 
, we can also apply the sum-product or the minimum-sum algorithm to the factor graph of the code (7,4). The different steps of the minimum-sum algorithm are given in Figure 5.7.
We have:
Figure 5.6. Sum-product algorithm applied to the factor graph of the code (7, 4)
Figure 5.7. Minimum-sum algorithm for the code (7, 4)
We obtain the following extrinsic LLR LEXTR(xi):
The a posteriori LLR, LAPP(xi) can then be computed using the relation LAPP(xi) = LAPRI(xi) + LINT(xi) + LEXTR(xi). Finally, we have:
since LAPRI(xi) = 0 in the absence of a priori information.
While these algorithms are not really decoding algorithms (since the aim of these algorithms is to provide the reliability of the decoded bits), if we apply a thresholding on the obtained a posteriori LLR, we obtain the transmitted codeword:
5.2.3. Forward-backward algorithm
The forward-backward algorithm or BCJR algorithm3 [BAH 74] estimates the a posteriori probabilities of the state and transitions of a Markov’s chain observed through a discrete memoryless noisy channel.
A binary convolutional encoder of rate k/n can be seen as a Markov’s source with one memory and with S = 2M internal states, where M is the number of memory elements of the coder.
Let
and 
be the input and output of the convolutional encoder, respectively, at time t and 
be the associated sequence transmitted. At the output of the discrete memoryless noisy channel, the decoder receives the vector 
at time t.
The forward-backward algorithm estimates the joint a posteriori probabilities σt(m′, m) of a convolutional encoder observed through a discrete memoryless noisy channel:
where st is the state at time t with st = m, m ∈ {0, 1, … , S − 1} and 
is the received sequence from time 0 until T − 1.
From these probabilities, we can determine the a posteriori probabilities (APP). We have:
We calculate σt(m′, m) by using the following relation:
with:
The quantities αt(m), γt(m′, m) and βt+1(m) represent the impact of the received sequence before time t, at time t and after time t, respectively, on the joint probability σt(m′, m) as shown in Figure 5.8.
The calculation of the branch metric γt(m′, m) is given as follows:
where the a posteriori probability on the output sequence conditionally to the input sequence is equal to:
and 
is the probability of transition of the channel. The probability Pr(xt = x|st = m′, st+1 = m) is equal to 0 or 1 depending on xt(m′, m):
Figure 5.8. Quantities αt(m), γt(m′, m) and βt+1(m) on the trellis of a convolutional code
The computation of the probabilities αt(m) is performed recursively:
The same principle is applied for the calculation of the probabilities βt(m):
Using [5.38] and [5.42], we obtain:
Finally, from [5.43] and [5.44], expression [5.47] can be written as:
The final expression of the a posteriori probabilities 
and extrinsic probabilities 
is a function of the structure of the convolutional encoder.
We can describe the forward-backward algorithm using four phases:
- – initialization: the starting state and the final state of the encoder are equal to the state zero:
- – computation of the γ and forward procedure: the γ are calculated for all the branches using relation [5.42] and simultaneously the probabilities αt(m) are calculated from [5.45];
- – return procedure: when the sequence
is received, the probabilities βt(m) are calculated using relation [5.46]; - – calculation of the a posteriori probabilities: finally, the a posteriori probabilities are obtained using relation [5.38].
5.2.3.1. Non-systematic convolutional codes
By introducing the a priori probability 
on 
, Pr(st+1 = m|st = m′) can be written as:
where xi(m′, m) is the value of the output associated with the branch (m′, m). If the a priori probability is not available at the input of the decoder, then 
and p(m|m′) is equal to 2n. We have:
with:
5.2.3.2. Systematic convolutional codes
In the case of systematic convolutional codes, we have the following expressions:
with:
5.2.3.3. Systematic convolutional codes with rate 1/2
Let 
be the transmitted word on the channel at time t and 
the received samples at the output of the memoryless channel. Thus, we have:
with:
When we have no a priori information on 
, the extrinsic information 
is given by:
5.2.3.4. Example
Let us consider the recursive systematic convolutional encoder with rate 1/2 
. The associated trellis is given in Figure 5.9.
Figure 5.9. Trellis of the coder 
We suppose that the information word, codeword and received word are the ones given in Table 5.1.
Table 5.1. Table of the transmitted and received symbols
The variance of the additive white Gaussian noise is equal to σ2 = 1. After multiplication of the received samples by 2/σ2 = 2, we obtain the intrinsic information LINT given in Table 5.2.
Table 5.2. Table of the intrinsic information
Calculation of the branch metric γ
For a systematic convolutional code of rate 1/2, the calculation of the branch metric is given by:
Let us calculate p(yt | xt) for an additive white Gaussian noise channel with xt = ±1:
The third line is obtained using the relation 
.
In our example, in the absence of a priori information, the 2n = 4 branch metrics 
where p and q are, respectively, the bits associated with 
and 
. They are given in Table 5.3 using relation [5.58].
To simplify the calculation of the branch metrics 
, we can use equation [5.61]. The obtained metrics are given in Table 5.4. We can see that Tables 5.3 and 5.4 are the same up to a normalization coefficient.
Calculation of α
The final results are given in Figure 5.10
Figure 5.10. Calculation of α
Calculation of ß
The final results are given in Figure 5.11.
Figure 5.11. Calculation of β
Calculation of 
We use the following relation:
Finally, after calculation, we obtain the a posteriori information given in Table 5.5.
Table 5.5. Calculation of the a posteriori information
5.2.3.5. Example of max log MAP decoding
In practice, the use of probability logarithms allows us to simplify the calculation.
Calculation of branch metrics ln γ
The branch metrics ln 
are obtained directly from the information LINT.
Table 5.6. Calculation of ln γ
Similarly, instead of calculating α and β, we will calculate ln α and ln β.
Calculation of ln α
The final results are presented in Figure 5.12
Figure 5.12. Calculation of ln α
Calculation of ln ß
The final results are given in Figure 5.13.
Figure 5.13. Calculation of ln β
Calculation of 
We are using the relation:
Finally, after calculation, we obtain the a posteriori information given in Table 5.7.
Table 5.7. Calculation of the a posteriori information
We can observe that the max log MAP decoder gives slightly different results compared to the MAP decoder. This difference is due to the “max” approximation. However, we usually prefer to use the max log MAP decoder since it is simpler to implement.
5.2.3.6. Complexity of the forward-backward algorithm
In order to evaluate the complexity of the forward-backward algorithm, we will consider the decoding of a convolutional code with no a priori information available on the information bits.
The number of multiplications and additions is given for one elementary trellis of the code. For a block of length K, we will have to multiply the results by K to obtain the number of operations per block:
- – calculation of γ: we calculate and memorize the 2n possible values of the expression
. Each calculation requires n – 1 elementary multiplications. The total number of multiplications for the calculation of γ is 2n × (n – 1); - – calculation of α: there are 2k branches leaving and arriving at each node. For each node, the calculation of α requires 2k elementary multiplications and one addition of 2k elements, i.e. 2k – 1 elementary additions. Since there are 2M nodes, the calculation of α requires consequently 2k+M multiplications and 2M × (2k − 1) elementary additions;
- – calculation of β: same complexity as the calculation of α;
- – calculation of
: each calculation requires one addition of 2M−1 × 2k terms and 2k × 2M multiplications. Since there are two values to calculate 
and 
, for the calculation of APP we need 
elementary additions and 2 × 2M × 2k multiplications.
5.2.3.7. Link between the forward-backward algorithm and the sum-product algorithm
In this section, we will show that the forward-backward algorithm is equivalent to the application of the sum-product algorithm on the graph factor of the convolutional encoder.
Let us consider the communication system composed of a recursive systematic convolutional encoder of rate 1/2 with termination that can be seen as a systematic linear block (2K, K) and a discrete memoryless stationary channel with conditional probability density p(y/x) as shown in Figure 5.14.
Let x = (xS, xP) be the transmitted sequence associated with the input sequence u with 
and 
. Let y = (yS, yP) be the received sequence.
Figure 5.14. Communication system
We have seen that the a posteriori probability 
is given by:
Assuming that the distribution of the transmitted sequence is uniform, the probability that a given sequence x has been transmitted is 1/2K.
Like for the Tanner Wiberg Loeliger (TWL) graphs, the local function 
at position i is defined from the state and output equation of the convolutional encoder:
A given sequence x implies that the product of the K relative local functions is equal to 1. We also have:
The factorization of Pr(x)p(y |x) is then the following:
An example of a factor graph for a recursive convolutional encoder of rate 1/2 is given in Figure 5.15.
Figure 5.15. Example of a factor graph for a recursive convolutional encoder of rate 1/2 used for the forward-backward algorithm
Since there is no cycle in the factor graph of the convolutional encoder, we can directly apply the sum-product algorithm to compute the probabilities APPs.
We will use the example given in Figure 5.15 to illustrate the application of the sum-product algorithm over this graph:
- – initialization and calculation of the branch metrics γ: the sum-product algorithm starts at the leaves of the tree. Each factorization node
and 
transmits a message toward the corresponding variable node 
and 
, respectively. Since the degree of the variable nodes is 2, the messages are directly transmitted toward the associated control nodes. These messages 
and 
correspond to 
and 
, respectively, in the forward-backward algorithm. The state variable nodes s0 and sK at the extremity of the graph send trivial messages μs0→T0(s0) and μsK→TK−1(sK) to the control nodes T0 and TK−1, respectively. These messages are denoted by α(s0) and β(sK) in the forward-backward algorithm; - – forward procedure: since the control node T0 has received the messages from three of its four branches, it can transmit the message α(s1) toward its neighbor state variable node s1. This message is transmitted toward the following control node T1. This procedure is repeated until the last variable node sK receives the message α(sK). The computation of α(si+1) is the following:
- – return procedure: the same procedure as the forward procedure is applied starting from the control node TK−1. The calculation of β(si) is the following:
- – calculation of the extrinsic probabilities: finally, the messages
are transmitted from the control nodes Ti toward the variable nodes ui
For each of these sums, 
except when the trellis branch is valid;
— calculation of the a posteriori probabilities: the calculation of 
is obtained from 
and 
as follows:
The messages α(si) and β(si) can be interpreted in terms of probabilities. For each value of si ∈ Si, α(si) is proportional to the conditional probability that the path associated with the transmitted sequence passes by the state si conditionally to the past observation y0, … , yi−1:
For each value of si+1 ∈ Si+1, β(si+1) is proportional to the conditional probability that the path associated with the transmitted sequence passes by the state si+1 conditionally to the future observation yi+1, yi+2, ….
Figure 5.16. Message passing when performing the forward-backward algorithm
We obtain the same expressions α(si) and β(si+1) as the ones computed previously using the forward-backward algorithm.
5.3. LDPC codes
LDPC codes were introduced by Gallager in 1963 [GAL 63], but it is only in 1996 after the works of MacKay and Neal [MAC 99] that the scientific community realized that these codes could almost reach the Shannon capacity and could also be interesting in practice due to their good performance complexity tradeoff.
5.3.1. Definition
A (N, dc, dT) LDPC code is a linear binary block code4 defined by its parity check matrix H of dimension M × N. This matrix is a low-density matrix, i.e. the number of “1” on each line is small compared to the size of the information word. Each line of the matrix H contains dT “1” and each column contains dc “1” and “0” everywhere else. Each line of H describes one of the M parity check equations. We have:
The associated Tanner graph is bipartite. This graph is regular since the variable nodes have the same degree dc and the control nodes have the same degree dT. The Tanner graph of an LDPC code is given in Figure 5.17.
Figure 5.17. Tanner graph of a (N, dc, dT) regular LDPC code
The rate 
of an LDPC code is:
Inequality [5.74] becomes an equality if all the lines of the matrix H are independent. In this case, the size of the information word is equal to 
.
EXAMPLE 5.2.– Let us consider the (12,3,4) LDPC code the Tanner graph of which is given in Figure 5.18.
Figure 5.18. Tanner graph of a (12, 3, 4) regular LDPC code
The parity check matrix of this code is the following:
Since the lines of H are independent, the rate of this code is 
, and the length of the information word is K = 3.
Gallager proved that the average minimum distance calculated over an ensemble of LDPC codes increases linearly with K when dc > 2 and consequently, the LDPC codes with dc > 2 are asymptotically good (they reach the Gilbert–Varshamov bound given by equation [3.36]). On the opposite, for dc = 2, the minimum distance increases only linearly with the logarithm of K (distance in 
(log K)).
Different works have shown that irregular LDPC codes reach the Shannon limit when the size of the codewords is very high [LUB 98]. The variable nodes and the control nodes of irregular LDPC codes are defined using node degree distribution functions.
Let 
and 
be the node degree distribution function of the variable and control nodes, respectively. λi (ρi) corresponds to the percentage of variable (control) nodes of degree i. The rate R of the irregular LDPC code is given by:
For a code of length N, the number of parity check equations M is equal to:
The functions λ(x) and ρ(x) are obtained using optimization methods such as linear programming and genetic algorithms. For the decoding, the variable nodes with the higher degree are better protected than the other variable nodes.
One of the main properties of the LDPC codes is its girth. The girth is the length of the smallest cycle in the bipartite graph. It has a major impact on the minimum distance of the code. Furthermore, the decoding algorithm on the graph becomes suboptimal if the girth is small. Consequently, we should avoid short cycles and maximize the girth of the graph. An example of code with girth equal to 4 is given in Figure 5.19.
Figure 5.19. Bipartite graph with girth of 4
The design of a parity check matrix with the highest girth is a difficult combinatorial problem. There are two different classes of parity check matrices H for the LDPC codes: the non-structured matrices and structured matrices.
The non-structured parity check matrices give the best performance since they require no additional constraints. These matrices are usually obtained using heuristic techniques such as the progressive edge growth (PEG) algorithm proposed by Hu et al. [HU 05], the improved progressive edge growth (IPEG) algorithm [XIA 04] and the bit filling algorithm of Campello et al. [CAM 01].
The structured matrices have the great advantage of allowing a simple and flexible hardware implementation. Different methods have been proposed such as the use of finite geometry [KOU 01] and algebraic combinatorial [JOH 01]. However, the most popular approach is to build quasi-cyclic (QC) parity check matrices [CHE 04, FOS 04].
The parity check matrix of the QC-LDPC code is composed of square circular submatrices of dimension Z × Z. Each submatrix is an identity matrix with a cyclic shift or an all-zero matrix. If we denote by I0 the identity matrix of dimension Z × Z, the matrix Ij with j right cyclic shifts can be written as follows:
The parity check matrix H of a QC-LDPC code can be divided into two matrices H = (H1 H2). The matrix H1 of dimension M × N–M is composed of circular submatrices or all-zero submatrices. The matrix H2 of dimension M × M is doubly diagonal and lower triangular. The parity check matrix H of the QC-LDPC code of size N = 648 and M = 324 rate R = 1/2 and Z = 27 used in the IEEE 802.11n and 802.11ac standards is given as an example in Figure 5.20. The all-zero submatrices are depicted using the symbol “-”.
Among the other classes of LDPC, we can cite the convolutional code LDPC (LDPC-CC) [JIM 99], the spatially coupled (SC-LDPC) [COS 14] and the LDPC codes built from protographs [THO 03].
Figure 5.20. Parity check matrix of a (638,324) QC-LDPC code
5.3.2. LDPC encoding
We will show that the low density of the parity check matrix allows a simple hardware implementation for the decoding. However, when the parity check matrix is not structured, the complexity of the encoding is proportional to MK (order of complexity 
(MK). It is consequently important to modify the generator matrix to have an encoding complexity linear with the codeword size (order of complexity 
(N)). In practice, the method proposed by Richardson and Urbanke is generally used [RIC 01b]. The aim of this method is first to modify the parity check matrix H in order to obtain the structure given in Figure 5.21.
Figure 5.21. Parity matrix H with a lower triangular form
Let us suppose that by applying column and line permutations, we are able to write the matrix H with the following form:
where A, B, C, D, E, T are the low- density matrices and T is a lower triangular matrix with a diagonal composed of 1. Different heuristic techniques have been proposed in [RIC 01b] to minimize the value of g. By multiplying right this matrix H with the matrix:
we obtain :
We know that for a linear code, we have the relation cHT = 0 for all codewords that can also be written as HcT = 0. If we assume that the code is systematic, we can write the codeword c using the form c = [u p1 p2] where u is the information word and [p1 p2] is the sequence composed of the M parity bits with p1 and p2 of length g and M − g, respectively. From the relation HcT = 0 and the modified parity check matrix given in [5.81], we obtain the following two equations:
By denoting ϕ = D − ET−1B and guaranteeing that the matrix ϕ of dimension g × g is non-singular, we can calculate 
and 
as follows:
In [RIC 01b], the authors have shown that once the preprocessing phase is performed, the encoding complexity using relations [5.84] and [5.85] is proportional to the length of the codeword N (order of complexity 
(N)).
Another solution consists of finding iteratively the parity bits by solving the system of equations HcT = 0 from the bipartite graph of the code [HAL 02]. This approach is similar to the decoding of erasure codes given in Chapter 3.
For the QC-LDPC codes, the encoding is straightforward since by writing c = [u p] where u is the information word, p is the sequence composed of the M parity bits and using the relation HcT = 0, we obtain the following relation:
Since H1 is a low-density matrix and 
has a regular structure, the complexity of the operation [5.86] is linear.
5.3.3. Iterative decoding of the LDPC codes
The complexity of the maximum likelihood decoder for LDPC codes increases exponentially with the size of the information word K. Fortunately, there are decoders with close to the optimal performance and with a reasonable complexity: this is the class of the iterative decoders. In this section, we will study the iterative decoding of LDPC on erasure channel, binary symmetric channel and additive white Gaussian noise. We will only consider regular LDPC codes, but the extension to irregular LDPC codes is strai ghtforward.
5.3.3.1. Iterative decoding of LDPC codes over erasure channel
We have already studied in section 3.4.5 the peeling decoding algorithm that performs successive corrections of the channel erasures. This algorithm can also be used for LDPC codes. In this section, we will focus on a slightly different class of decoding algorithms: the iterative decoding algorithm using message exchanges.
Let us define the alphabet 
and the received symbol 
associated with the variable node cn. The symbol X corresponds to an erased symbol and we have Pr(rn = X) = 
for an erasure channel. We define 
the message transmitted from the variable node cn toward the control node Tm and 
the message transmitted from the control node Tm toward the variable node cn at iteration l.
The iterative decoding algorithm over the graph consists of propagating messages between the variable nodes and the control nodes iteratively. One iteration is composed of two phases:
- – calculation of messages variable node toward control node: each variable node v receives dc messages from the neighbor control nodes and the message received at the output of the channel, calculates the dc messages and sends them to the neighbor control nodes;
- – calculation of the messages control node toward variable node: each control node c receives dT messages from the neighbor variable nodes, calculates the dT messages and sends them to the neighbor variable nodes.
In the two phases, each message is calculated from all incoming messages except the one of the considered branch.
For the erasure channel, the phases are the following:
- – calculation of the messages variable node toward control node:
- - at iteration 0
- - at iteration l with
if the received message cn and all the messages 
are erased (Tm′ are the control nodes connected to cn except Tm). Otherwise, 
will be equal to one of the not erased incoming messages 
;
- - at iteration 0
- – calculation of the messages control nodes toward variable nodes:
- - we have
if one of the messages 
is erased (cn′are the variable nodes connected to Tm except cn). Otherwise, 
mod 2.
- - we have
These two phases are repeated until convergence. It happens if all the erased symbols have been recovered or if the messages remain unchanged after one iteration. In this case, the iterative decoding algorithm has failed because the errors are confined in subsets of variable nodes called the stopping sets. A stopping set is a set of variable nodes in the graph, for which the corresponding subgraph does not contain any control node of degree 1. We recommend [RIC 08] for a detailed study of the properties of the stopping sets.
It is possible to predict the performance of this iterative algorithm when the size of the codeword is high enough to assume that the associated Tanner graph is a tree. Richardson and Urbanke [RIC 01a] proved that when the size of the information word K is large, the messages are propagating on a tree with a probability of 
. Consequently, under this condition, the cycles do not impact the convergence of the algorithm. In this case, the messages entering in the variable nodes and the messages entering in the control nodes are independent. Let us define 
and 
the erasure probabilities at the variable nodes and control nodes, respectively, at iteration l. For the regular LDPC code, we have the following recursive relations:
In the case of a regular LDPC code with dc = 6, dT = 3 and an erasure probability = 0.4, the first values of 
are 0.4000, 0.3402, 0.3062, 0.2818, 0.2617, 0.2438, 0.2266 and 0.2093. Figure 5.22 shows the evolution of the erasure probability for a regular code with dc = 6, dT = 3. We have plotted the function 
for = 0.4. This zigzag curve gives the values of 
when l = 1, 2, …. We obtain the values calculated previously and we can check that the probability tends toward 0 (after about 15 iterations). The limit value of corresponds to the case where the function 
is tangent to the straight line. For this code, we can show that lim = 0.4294 as illustrated with the dash curve in Figure 5.22.
In the case of an irregular LDPC defined by the functions λ (x) and ρ(x), the relation [5.88] becomes:
Figure 5.22. Graphical illustration of the evolution of the erasure probability as a function of the iterations for a regular LDPC code with dc = 6, dT = 3 . For a color version of the figure, see www.iste.co.uk/leruyet/communications1.zip
For example, for the irregular LDPC code defined by λ(x) = 0.409x + 0.202x2 + 0.0768x3 + 0.1971x6 + 0.1151x7 and ρ(x) = x5 of rate R ≈ 0.5, we obtain lim = 0.481 which is close to the Shannon limit (C = 0.5). Figure 5.23 gives the evolution of the erasure probability for this code with = 0.46.
5.3.3.2. Iterative decoding of LDPC codes over binary symmetric channels
In this section, we will describe the iterative algorithm A initially proposed by Gallager [GAL 63]. We consider the transmission of a codeword on a binary symmetric channel. Let rn be the received bit (0 or 1) associated with the variable node cn.
Figure 5.23. Graphical illustration of the evolution of the erasure probability as a function of the iterations for a irregular LDPC code. For a color version of the figure, see
www.iste.co.uk/leruyet/communications1.zip
The two phases of algorithm A are the following:
- – calculation of the messages variable node toward control node
for each branch (cn, Tm) :
- - at iteration 0,
, - - at iteration l with l > 0:
- if all the bits
(Tm′ are the control nodes connected to cn except Tm) then 
- else,
- - at iteration 0,
- – calculation of the messages control node toward variable node
for each branch (cn, Tm) :
mod 2 (cn′ are the variable nodes connected to Tm except cn)
The bits 
are an estimation of the bit cn at iteration l. In algorithm A, in order to have 
, it is necessary that all the bits 
are equal to b. Gallager proposed a second version of the algorithm called algorithm B in which this constraint is relaxed: if the number of bits 
is higher than a threshold S, then 
. The thresold S is chosen to minimize the binary error rate.
5.3.3.3. Iterative decoding ofLDPC codes over additive white Gaussian noise channel
Let us consider a bipodal modulation and an additive white Gaussian channel (y = x + n) with xi = ±1 and ni is a sample of white Gaussian noise with variance σ2.
We assume that the size of the codewords is high enough and we will restrict ourselves to the (dc, dT) regular LDPC codes. By optimizing the construction of the parity check matrix, the cycles in the Tanner graph will be high enough and will not impact the exchange of the extrinsic information during the iterative decoding.
We will use the factor graph of the LDPC code as shown in Figure 5.24 to describe the iterative decoding algorithm. This factor graph can be deduced from the Tanner graph of the LDPC.
The iterative decoding consists of applying a soft input soft output algorithm such as the sum-product algorithm on the factor graph of this code. As mentioned previously, the messages propagate on a graph with the probability 
. When the local graph used for the decoding is a graph, we can easily analyze the decoding algorithm since the messages arriving at each node are independent (each variable node appears only once in the local tree).
In Figure 5.25, we show an example of a local tree for a (dc, dT) LDPC code. On this tree, we can observe that each control node is defined by a single (dT, dT – 1) parity check code.
The application of the sum-product on this graph consists of propagating the messages between the variable nodes and control nodes iteratively
Figure 5.24. Factor graph of the (N,dc, dT) regular LDPC code
Using the two basic rules previously described when the messages are LLR, we obtain the following relations for the calculation of the messages 
and 
as shown in Figure 5.26:
– calculation of the messages variable node toward control node 
:
At the first iteration, since no a priori from the previous decoding is available, only the information coming from the transmission channel μ0 is used for the calculation of μc→T(c). μ0(c) is the LLR of the received symbol:
– calculation of the messages control node toward variable node 
Figure 5.25. Example of local tree for a (dc, dT) LDPC code
Finally, the calculation of the a posteriori information APP(x) associated with the bit c is performed by summing the information coming from the control nodes and channel:
The performance of a (4320, 3557) code LDPC with Dc = 17 and dT = 3 over an additive white Gaussian noise channel is given in Figure 5.27. We can observe that a significant number of iterations are required to reach the convergence of the iterative decoder (here about 20 iterations).
Figure 5.26. Message exchange for the calculation of 
and 
When the size of the frame tends to infinite, it is possible to determine analytically the minimum ratio Eb/N0, i.e. the ratio Eb/N0 from which the iterative decoding algorithm converges with a zero error probability. We can show that the probability density of the messages calculated using the sum-product algorithm is close to a Gaussian density. Under the Gaussian hypothesis, the probability density of the messages can be fully described using its mean and variance. Furthermore, we have seen that if the messages are LLR, it is possible to only consider the evolution of the mean of the messages since the variance is twice the mean due to the symmetry relation. From equation [5.90], we obtain:
where 
and 
are the means of the messages 
and 
, respectively.
can be calculated using the expectation of each of the terms in [5.91]:
Figure 5.27. Bit error rate versus Eb/N0 for the (4320, 3557) regular LDPC code with Dc = 17 and dT = 3
Let us define the function 
(x):
(x) is the mean of tanh
where u is a Gaussian random variable of mean x and variance 2x.
Using the function (x), we obtain the following relation:
In Figure 5.28, we have compared the evolution of the mean and variance of the message 
obtained using the Gaussian approximation and the density probability evolution.
Figure 5.28. Comparison of the mean and variance calculated using the Gaussian approximation and using the density probability evolution. For a color version of the figure, see www.iste.co.uk/leruyet/communications1.zip
We can observe that the curves obtained using the two approaches are very closed. The Gaussian approximation gives slightly pessimistic results.
5.3.4. Applications
In 2003, an LDPC code was selected in the standard for the satellite transmission of the digital television (digital video broadcast) DVB-S2 and also for the DVB-T2 and DVB-C2 standard. For the DVB-S2 standard, the length of codewords is N = 64800 bits (normal frame) with 11 different rates varying from 1/4 to 9/10 or N = 16200 bits (short frame) with 10 different rates varying from 1/4 to 8/9. The LDPC code is irregular and can be encoded as an irregular repeat-accumulated (IRA) code that we will study in section 5.5.
In 2008, an LDPC code was selected for the 1 Gbit/s ITU-T G.hn/G.9960 standard (ITU-T standard for power line transmission, twisted pair and coaxial cables). The length of the codes varies from N = 336 to 5184 bits and the rates are 1/2, 2/3 and 5/6. A (2048, 1723) LDPC code is also defined in the IEEE 802.3an standard for the Ethernet 10GBase-T, sending the data at 10 gigabits per second on a cable composed of four twisted pairs. Since 2009, the LDPC codes are also an option for the 802.1 In and 802.1 lac standard. In the 802.1 lac standard, four QC-LDPC codes of rate 1/2, 2/3, 3/4 and 5/6 are defined with N = 648, 1296 and 1944 bits. In Figure 5.20, we describe the parity check matrix H of this code for the case R = 1/2 and N = 648.
5.4. Parallel concatenated convolutional codes or turbo codes
5.4.1. Introduction
The discovery of parallel concatenated convolutional codes or turbo codes in 1993 by Berrou, Glavieux and Thitimajshima [BER 93] significantly modified the field of channel coding. The main breakthroughs of the turbo codes are the following:
- – the concatenation of simple codes and the use of an interleaver allowing us to mimic the random coding;
- – the use of soft input soft output decoding and iterative decoding.
In this section, we will introduce the structure of the turbo coder and the associated iterative decoder. Finally, we will study the theoretical performance of these codes, and give the criteria and design methods of the interleavers.
5.4.2. Structure of the encoder
The structure of the encoder associated with parallel concatenated convolutional codes or turbo codes is given in Figure 5.29. This encoder is composed of two binary systematic recursive convolutional (RSC) encoders of rate k/n and an interleaver of K bits. The length of the input or information sequence is K bits.
Figure 5.29. Parallel concatenated convolutional encoder
The turbo code is a (N, K) binary linear block code with 
K if we neglect the termination bits. The overall rate of the code is equal to:
The interleaving function applied to the K information bits modifies the order of these bits.
An interleaver E of size K is defined by its permutation matrix П of dimension K × K; we have the following relation between the input sequence u and the output sequence v of the interleaver E:
If aij = 1, then the bit ui is associated with the bit υj.
The initial structure proposed by Berrou et al. was composed of two RSC encoders of rate R = 1/2. The overall rate is then equal to RT = 1/3. The TWL graph of this turbo encoder is given in Figure 5.30.
Figure 5.30. TWL graph of a turbo encoder
As for the convolutional codes, it is possible to puncture the output of the turbo encoder to increase the overall rate.
The aim of the termination is to avoid codewords with low weight by adding M bits at the end of the input sequence to bring back the internal state of the convolutional encoder at the zero state assuming M is the number of memory elements of the convolutional encoder. The principal techniques of termination for turbo codes are the following:
- – termination of only the first encoder by adding M bits. The K + M bits will be interleaved and the interleaver should avoid the edge effect due to the absence of termination for the second convolutional encoder;
- – termination of both convolutional encoders separately [HOK 99a]. This is the solution used in the Universal Mobile Telecommunications System (UMTS) standard;
- – termination of both convolutional encoders jointly. For a given interleaver, it is possible by adding a number of bits between M and 2M to jointly bring back the internal state of the two trellis to the zero state [VAN 00];
- – another solution is to constraint the ending state to be equal to the starting state. The end of the trellis is then connected to its beginning. This technique is called tail-biting and avoids the rate decrease due to the addition of termination bits.
In this section, we will show that the parity check matrix of turbo codes are low-density parity check codes similarly to the LDPC codes.
Since the turbo code is a linear block code, we have the following relation between the information word u of length K bits and the codeword x of length N bits:
where G is the generator matrix of dimension K × N. The associated parity check matrix H is a matrix of dimension (N − K) × N with xHT = 0.
In Chapter 4, we introduced the parity check matrix of the convolutional code of rate R = 1/2. The second form is obtained using the parity check equation [4.8] and can be written as follows:
We have the following relation between u and x1, H2 and H1:
For the second convolutional code of the concatenated scheme, we have the relation:
The parity check matrix H of the turbo code can then be deduced from H as follows:
An example of parity check matrix H for a turbo code is shown in Figure 5.31 from matrix [4.24]. The circle means that the columns inside this submatrix are permutated according to the interleaver E.
Figure 5.31. Parity check matrix of a turbo coder composed of two RSC coders (7,5) with RT = 1/3
Under the condition that K is much higher than the number of memory elements M of the convolutional encoders, this structure is irregular and H is a low-density parity check matrix. Consequently, the turbo codes belong to the class of irregular LDPC.
5.4.3. Performance study of turbo codes
Since the turbo codes can be seen as linear block codes, their theoretical performance can be determined from the functions Input Output Weight Enumerator Function (IOWEF) or Input Redundancy Weight Enumerator Function (IRWEF) of the code. These functions allow us to determine the coefficients Bd of the upper bound [3.111]. At high-to-moderate signal-to-noise ratio, only the first term of the function has a real impact on the expression of the bit error rate and we have:
where dmin is the minimum distance of the turbo code. Since the minimum distance of the turbo code is not so high, we can observe a floor effect at high signal-to-noise ratio as shown in Figure 5.38.
In [BEN 96b], Benedetto and Montorsi introduced a uniform interleaver in order to study the average performance of turbo codes. A uniform interleaver is not an interleaver stricto sensu but rather a probabilistic tool: it associates an input sequence of weight w with the 
different sequences of weight w, each with the same probability 
This interleaver allows us to compute the average weight enumerator of the turbo codes and more generally of the concatenated convolutional codes. We previously introduced the weight enumerator function IRWEF AC(W, Z) of a (N, K) linear binary block encoder. The IRWEF function of an RSC encoder C of rate k/n the sequence of which is terminated and of length K bits is the following:
is the number of codewords of C the input sequence weight of which is equal to w and the parity check sequence weight of which is equal to z. wmin is the minimum weight of the input sequences and zmin is the minimum weight of the parity check bits. The calculation of the weight enumerator function Ac(W, Z) for a terminated convolutional code is developed in Appendix B.
In the case of the terminated RSC coders, we have wmin = 2. Thus, the relation between dfree the free distance of the RSC encoder and zmin is the following:
The coefficients of the average weight enumerator function IRWEF ACP (W, Z) for a turbo code composed of two RSC encoders and an interleaver can be written5 as:
Using the union bound, we can then obtain an upper bound on the bit error rate of the maximum likelihood decoder over additive white Gaussian noise.
Benedetto and Montorsi [BEN 96a] have shown that for parallel concatenated convolutional codes or turbo codes, the use of systematic recursive convolutional encoders gives an interleaver gain equal to 1/K. If we only consider the input sequence of weight w = wmin = 2, from relation [3.107], the binary error rate can be bounded by:
We define the effective free distance dfree,eff of the concatenated code as follows:
In the case of non-recursive convolutional encoders, since wmin = 1, there is no interleaver gain. To maximize zmin and consequently dfree,eff, we must choose a primitive polynomial at the denominator. For a given number of memory elements M and rate R, we just have to determine the polynomial at the numerator. In [BEN 98], an exhaustive search of the best RSC constituent encoders for turbo codes has been performed based on the effective free distance.
In Figure 5.32, we show the average performance Pe = f(Eb/No) of a turbo code of global rate Rt = 1/3 composed of two RSC encoders (7,5) and RSC (15,17) and for two sizes of the uniform interleavers (100 and 1,000 bits) by using the union bound. We can check that the interleaver gain is 1/K.
Figure 5.32. Comparison of the average performance of average turbo codes with rate Rt = 1/3 composed of RSC (7,5) encoders (dashed lines) and RSC (15,17) encoders (continuous line) and a uniform interleaver of size K = 100 and K = 1000
We know that the codewords with low weight are mainly generated by input sequences with low weight. In Figures 5.33 and 5.34, we have compared the impact of these sequences on the average performance of a turbo code composed of two RSC (15,17) encoders and a uniform interleaver of size K = 100 and 1,000. The global rate is Rt = 1/3. Only the input sequences with weight w < 4 impact the performance at average to high signal-to-noise ratio. It should be said that when the size of the interleaver increases, the input sequences of weight w = 2 become increasingly important.
Figure 5.33. Contribution of the input sequences of low weight on the bit error rate of a turbo coder of rate Rt = 1/3 composes of RSC (15,17) encoders and a uniform interleaver of size K = 100. For a color version of the figure, see www.iste.co.uk/leruyet/communications1.zip
Figure 5.34. Contribution of the input sequences of low weight on the bit error rate of a turbo coder of rate Rt = 1/3 composes of RSC (15,17) encoders and a uniform interleaver of size K = 1000. For a color version of the figure, see www.iste.co.uk/leruyet/communications1.zip
5.4.4. Iterative decoding of turbo codes
In the previous section, we have seen that the sum-product algorithm allows us to compute exactly and efficiently the a posteriori probabilities 
a) when there is no cycle in the graph. However, in most of the applications such as the concatenated codes (LDPC codes, product codes, turbo codes, etc.), the graph is not exactly without cycle. However, it is still possible to apply the sum-product algorithm without taking into account these cycles as we have already done for the iterative decoding of the LDPC codes.
Since the complexity of the exact calculation of 
increases exponentially with the length of the information sequence, the interest of concatenated codes is that we can perform a suboptimal decoding using iterative decoding. In the case of the turbo codes, the aim of iterative decoding is to exploit the structure of the graph of the turbo code composed of two elementary graphs without cycle to factorize the a posteriori probability 
. Consequently, we will avoid calculating globally the a posteriori probability.
The iterative decoder consists of decoding alternatively the two constituent codes of the concatenated code. For each elementary code, we will perform a soft input soft output decoding. In this case, the preferred algorithm is the forward-backward algorithm since the constituent codes are convolutional codes. The simplified structure of the iterative decoder is given in Figure 5.35.
Figure 5.35. Structure of the iterative decoder
During the decoding, the extrinsic information calculated by the first decoder after interleaving becomes the a priori information for the second decoder. After the decoding of the second code, the extrinsic information is then after deinterleaving transmitted to the first decoder as a priori information. This process corresponds to an iteration and is repeated a few times. An example of a factor graph for a turbo code of rate 1/3 is given in Figure 5.36.
Figure 5.36. Example of factor graph for a turbo code of rate 1/3
This graph has many cycles, and in the case of short-to-medium information sequences (K ≤ 2000) it is important to reduce their impact in order to improve the performance of the iterative decoding. In [MCE 98] and [KSC 01], the authors have shown that performing the iterative decoding is equivalent to applying the sum-product algorithm on the factor graph of this code.
We will now describe the different calculations performed during the decoding. Let u = xs be the information sequence and c1 and c2 be the redundancy sequences. yS, y1 and y2 are the associated received sequences. From the N = Kn/k observations related to the first coder and the a priori probabilities 
calculated during a previous decoding, the first decoder calculates the following extrinsic probabilities 
for the K information bits and at each iteration 
is the extrinsic probability. 
is the a priori probability on the i-th bit of the input sequence u.
is obtained as follows:
Similarly, the second decoder calculates 
Finally, we calculate 
to perform the final decision after the last iteration lT:
To calculate these probabilities, we apply the forward-backward algorithm. A few iterations are usually enough to reach the convergence of the iterative decoding. The required number of iterations is a function of the ratio Eb/No. The final decision is taken by keeping the sign of the a posteriori information obtained at the end of the last iteration.
As for the LDPC codes, instead of calculating the probabilities 
, we can calculate the log likelihood ratios (LLR). The LLR LAPP 
will be equal to:
LINT is the intrinsic information. In practice, it is necessary to estimate the noise variance σ2.
To illustrate the good performance of the turbo codes, we show in Figure 5.37 the curves BER = f(EB/No) of a turbo code with rate RT = 1/2 composed of two RSC convolutional encoders 
and an optimized S-random interleaver of size K = 1024. A puncturing pattern is applied to obtain the rate RT = 1/2. The curves are given for l = 2, 5, 10 and 15 iterations. We can see that after five iterations, the gain becomes negligible (less than 0.2 dB).
In Figure 5.38, we show the curves BER = f(EB/No) of a turbo code with rate RT = 1/2 composed of two RSC encoders 
with puncturing and a pseudo random interleaver of size K = 65536 [BER 93]. We can see that after 18 iterations, we have a Bit Error Rate (BER) of 10–5 for Eb/No = 0.7 dB, i.e. 0.7 dB from the Shannon limit. The floor effect is due to the low minimum distance of this code. This floor effect can be reduced after the interleaver optimization of the interleaver.
Figure 5.37. BER = f(Eb/No) for a turbo code of rate 1/2 composed of two RSC encoders 
and an S-random interleaver of size K = 1024
To conclude, the association of turbo codes and iterative decoding gives very good performance with a reasonable complexity.
5.4.5. EXIT charts
Another classical tool to study the behavior of the turbo code as well as any scheme performing iterative decoding is the EXtrinsic Information Transfer (EXIT) charts introduced by Brink [BRI 99, HAG 04]. The principle is to assimilate the soft input soft output decoder to a nonlinear operator the input of which is LAPRI(x) and the output LEXTR(x) for a given signal-to-noise ratio. There are other approaches such as the measure of the variance to characterize the performance of the concatenated codes, but the measure of the average mutual information I(x;LAPRI(x)) and I(x; LEXTR(x)) is the more common.
Figure 5.38. Curves BER = f(EB /N0) for a turbo code of rate 1/2 composed of two RSC encoders 
and a pseudo random interleaver of size K=65536
The measures performed on the LLR LAPRI (x) show that they are well approximated by Gaussian distribution. From relation [5.15], we have:
where 
and nA is a Gaussian noise sample with variance 
. From the definition of the average mutual information given by relation [1.111], we obtain:
Relation [5.114] is obtained by exploiting the Gaussian property of the distribution pA(z|x). The average mutual information I(x; LEXTR(x)) is generally non-Gaussian and consequently it is not possible to use this relation. Consequently, I(x; LEXTR(x)) is calculated as follows:
where pE(z|x) is the empirical distribution measured at the output of the soft input soft output decoder. So, for a given ratio Eb/No, we can obtain the EXIT chart associating the average mutual information at the input IA and the average mutual information at the output of the decoder IE:
In Figure 5.39, we show the EXIT charts obtained using a systematic recursive convolutional encoder (13,15) of rate R = 1/2, a Binary Phase Shift Keying (BPSK) modulation and different values of ratio Eb/No.
Within the iterative decoding, the extrinsic information is exchanged between the elementary decoders. Using the EXIT chart and starting at point (0,0), we can predict the evolution of the average mutual information as a function of the iterations. We just have to plot on the same figure the EXIT chart of each of the elementary decoders. When the two constituent codes are the same, we just have to add a second curve corresponding to the second decoder obtained by symmetry with the diagonal. In Figure 5.40, we provide an example of the evolution of the average mutual information as a function of the iterations for a turbo code composed of two systematic recursive convolutional encoders (13,15) of rate R = 1/2 and for the ratio Eb/No = 0.5 dB. If the two curves do not intersect, the EXIT chart allows us to predict that the iterative decoding will converge and that the bit error rate will be very low. Using the EXIT charts, we can find the value of the signal-to-noise ratio limit which corresponds to the closing of the tunnel between the two curves.
Figure 5.39. EXIT charts for an RSC encoder (13,15) of rate R = 1/2
Figure 5.40. Evolution of the average mutual information as a function of the iterations for a turbo code
5.4.6. Criteria and interleaver design
Interleavers have often been used in the past in digital communication systems, particularly when the channel is bursty or frequency selective. We also use an interleaver as part of the concatenated codes composed of a convolutional code as inner code and a block code as outer code. In these structures, the unique role of the interleaver is to disperse the burst errors generated at the output of the Viterbi decoder. For turbo codes, the interleaver is one of the key elements and its role is quite different. In this section, we will present the criteria for the design of an interleaver and some interleaver constructions such as the quadratic polynomial permutation (QPP) interleaver.
5.4.6.1. Definitions
An interleaver E is a component defined by its permutation function. An interleaver associates an input sequence u = [uo,u1 …, uk–1] with an output sequence v = [vo, v1, … , vk–1] The permutation function can then be described from a permutation vector p of length K:
We have the following relation between ui and vp(i):
Another description of the permutation function is obtained from the permutation matrix Π of dimension K × K:
If aij=1, then the bit ui is associated with the bit vj. We then have the relation between the input sequence u and the output sequence v of the interleaver:
For each pair of positions (i, j), a primary cycle is a cycle composed of the two branches of the interleaver (i,p(i)) and (j,p(j)) using the TWL representation of the turbo codes. An example of primary cycle is given in Figure 5.41.
The dispersion factors S and L give us information on the capability of the interleaver to minimize the correlation of the intrinsic information during the iterative decoding.
Figure 5.41. Example of primary cycle
A block interleaver has a dispersion factor S [DOL 95] if:
Consequently, two bits separated by at least S − 1 bits at the input of the interleaver will be separated by at least S − 1 bits at the output. This factor is used for the construction of the so-called S-random interleaver.
Another dispersion factor is the dispersion factor L [LER 00]. Let l(i, j) be a distance associated with the input bits at position i and j:
The dispersion factor L for the interleaver E is defined as follows:
L corresponds to the length of the shortest primary cycle.
We have seen that to improve the convergence of the iterative decoding, the a priori information should be the least possible correlated with the information intrinsic. The iterative decoding suitability (IDS) [HOK 99b] factor evaluates this correlation at the first iteration. At the first iteration, the first decoder calculates the extrinsic information 
to simplify the notation) directly from 
and y1 since no a priori information is available.
Let 
be the correlation between 
and 
. It has been shown in [HOK 99b] that this function is exponentially decreasing. The correlation at the output of the second decoder can be approximated as follows:
is the correlation matrix between Le2 and yS, and 
is one of its elements.
Let Vk be defined as follows:
with:
A low value of Vk means that the extrinsic information 
at the first iteration is of good quality. Similarly, we can compute 
with respect to the deinterleaver by replacing Π by ΠT in equation [5.124]. Finally, the IDS factor is the mean of all the values Vk and :
A low value of the IDS factor means that Le2 is uniformly correlated to the input sequence yS. In practice, the IDS factor is close to the dispersion factor L.
An interleaver is said to be conflict-free within the window of length W, if it satisfies (and also its associated deinterleaver) the following relation:
where 0 ≤ v < W, 0 ≤ u1 < M, 0 ≤ u2 < M, u1 ≠ u2 This property allows us to process the information frame into p windows of length W with K = pW. The values of each term in inequality [5.128] correspond to the indices of the windows. For any given position v of each window, the access to the memory banks will be unique.
5.4.6.2. Criteria
The three main criteria for the construction of the interleaver are the following:
- – The first criterion for the interleaver design is related to the weight distribution of the turbo codes. The interleaver should be built in order to avoid permutations generating low-weight codewords and consequently allow us to increase the minimum distance of the turbo codes. Due to the parallel structure of the turbo codes, the Hamming’s weight of a codeword is the sum of the Hamming’s weight of the sequences u, c1 and c2. Consequently, the interleaver should interleave the input sequences u generating low-weight sequences c1 into sequences v that will generate high-weight sequences c2.
- – The second criterion is related to the iterative decoding. An interleaver should be designed in order that, at each iteration, the a priori information is the least possible correlated with the intrinsic information received from the transmission channel. This criterion is satisfied if the cycles in the TWL graph are large enough.
- – A third criterion is related to the complexity and speed of the iterative decoder. Indeed, the interleaver can facilitate the parallelization of the processing to increase the decoding speed. The size of the memory required to generate the function of interleaving and deinterleaving is also an important issue.
5.4.6.3. Interleaver design
The design of an interleaver is an optimization problem. The main difficulty comes from the fact that we have to take into account different optimization criteria. Hopefully, these criteria are not contradictory. If an optimal solution is difficult to obtain, good solutions can be founded by using heuristic algorithms. We can classify the interleaver constructions into the following classes:
– the algebraic constructions: the simplest algebraic interleavers are the line-column interleaver and helical interleaver [BAR 95]. More efficient algebraic interleavers have been proposed in [TAK 98]. The QPP interleaver [SUN 05] also belongs to this class;
– the semi-algebraic constructions: among this class, we can cite the dithered relative prime (DRP) interleaver [CRO 05] and almost regular permutation (ARP) interleaver [BER 04] ;
– the constructions element-by-element: the permutation matrix is built line-by-line. The S-random interleaver [DOL 95] and its derivatives [SAD 01] and the L-random intereleaver [LER 00] belong to this class.
In the remaining part of this section, we will briefly introduce the QPP interleaver that has often been selected in the standards.
A polynomial P(x) = f1x + f2x2 is called a permutation polynomial over ℤk if it allows us to build an interleaver of size K. The polynomials used for the construction of QPP interleaver of size K are defined as follows:
where f1 and f2 are the two integers that should satisfy different conditions given in [SUN 05] in order that P(x) be a permutation polynomial. The values of f1 and f2 are then chosen to maximize the minimum distance of the turbo code. The QPP intereavers are conflict-free and allow us to parallelize the encoding and decoding operations. The ARP and QPP have often been proposed during the definition of the standards. In Figure 5.42, we show an example of an L-random interleaver of size K = 320 bits and a QPP interleaver of size K = 280 with f1 = 103 and f2 = 210 (interleaver of the LTE standard).
If the QPP seems to be close to the L-random interleaver, it is much more structured and facilitates the implementation and parallelization of the process.
5.4.7. Applications
The Consultative Committee for Space Data Systems (CCSDS) standard for spatial communications was one of the first standards to include the turbo codes. The constituents’ encoders are 16 state convolutional encoders and the length of the frame varies from 1,784 to 8,920 bits (with a possible extension until 16,384 bits). The supported rates are 1/2, 1/3, 1/4 and 1/6.
Figure 5.42. Interleavers a) L-random K = 320 and b) QPP K = 280
The 3rd Generation Partnership (3GPP) group proposed the UMTS and High Speed Packet Access (HSPA) standards, and more recently the long term evolution (LTE) standard for the fourth generation of wireless mobile networks. These standards use binary turbo codes. In the UMTS standard, the constituent encoders are eight state convolutional encoders (1 and 15/13) and the length of the information frame is 40 ≤ K ≤ 5114 bits. The constituent encoders for the CDMA2000 standard are eight state convolutional encoders (1, 15/13 and 17/13) with rate 1/3. The length of the frame varies from 378 to 20,730 bits and the supported rates are 1/2, 1/3, 1/4 and 1/5.
For the LTE standard, the encoders are eight state convolutional encoders (1 and 15/13). The standard defines 188 different QPP interleavers in order to support information frames of length varying from 40 to 6,144 bits. These interleavers allow parallelism of p = 8 for K < 2048 and p = 64 for K ≥ 2048.
In the Digital Video Broadcating - Return Channel Satellite (DVB-RCS) standard, the constituent codes are duo-binary (2 bits per symbol) eight state convolutional codes. The length of the frame can range from 16 to 256 octets and the rate can be chosen between the following values: 1/3, 2/5, 1/2, 2/3, 3/4, 4/5 or 6/7.
The Homeplug Alliance group has proposed the HomePlug AV and HomePlug AV2 standards for power line communications. These standards use a eight state convolutional code with rate 2/3. The length of the information frame is equal to 16, 136 or 520 octets. The rate is equal to 1/2 or 16/21. IEEE has used the same scheme for the IEEE 1901 standard.
5.5. Other classes of concatenated codes
5.5.1. Parallel concatenated block codes
5.5.1.1. Structure
The structure of the PCBCs is given in Figure 5.43. The information symbols are arranged in the form of an array of dimension kVkH. To this array, we have added two arrays of dimension kV(nH − kH) and (nV − kV)kH. The PCBC code is a systematic linear block code (N, K) with N = kV nH + nVkH − kVkH and K = kVkH. The global rate of the PCBC code is then equal to:
Figure 5.43. Code PCBC
Each of the kV lines corresponds to a systematic linear block code CH (nH, kH) Furthermore, each column corresponds to a systematic linear block code CV (nV, kV)
The minimum distance of this code is equal to the sum dV + dH −1 where dV and dH are the minimum distances of the constituent codes CV and CH, respectively.
The TWL graph of the PCBC codes is presented in Figure 5.44.
In this section, we will only consider the case of binary PCBC codes. These codes can be easily decoded by applying iterative decoding. The constituent codes are mainly the parity check codes, Hamming codes or Bose Chaudhuri Hocquenghem (BCH) codes.
5.5.1.2. Iterative decoding
In order to have an efficient iterative decoding, the TWL graph of the code should not have short cycles. The role of the line-column interleaver is to avoid these cycles.
The different phases of the iterative decoding are as follows:
– phase 1 : initialization of the a priori information 
for the horizontal decoding;
– phase 2: horizontal decoding. Calculation of the extrinsic information 
associated with the information bits ui;
– phase 3: the extrinsic information calculated becomes the a priori information 
for the vertical decoding:
– phase 4: vertical decoding. Calculation of the extrinsic information 
associated with the information bit ui;
– phase 5: if the fixed number of iterations (horizontal and vertical decoding) is reached, we terminate the decoding by phase 6, otherwise 
and return to phase 2;
– phase 6: calculation of the a posteriori information LAPP(xi) = LAPRI(xi) + LINTR(xi)) + .
Figure 5.44. TWL graph of the PCBC codes
The sum-product or minimum-sum algorithm is applied on the TWL graph of the constituent codes. Another solution is to use the Chase algorithm [PYN 94, CHA 72]. This algorithm performs a soft input soft output algorithm from a soft input hard output algorithm such as the Berlekamp-Massey algorithm.
5.5.2. Serial concatenated convolutional codes
The structure of a serial concatenated convolutional encoder is given in Figure 5.45. This encoder is composed of two systematic recursive convolutional encoders C1 and C2 of rate k1/n1 and k2/n2, respectively, and an interleaver of size Kn1/k1 bits. The length of the input sequence is k bits.
Figure 5.45. Serial concatenated convolutional encoder
This code is a (N, K) binary linear block code with 
if we neglect the termination bits. The global rate is:
For example, if we choose a code C1 of rate 1/2 and a code C2 of rate 2/3, we obtain a global rate Rt = 1/3. As for turbo code, we perform iterative decoding.
5.5.3. Repeat-accumulate codes
The repeat-accumulate (RA) code is a class of low complexity concatenated codes. The RA encoder is composed of a repetition encoder of rate 1/k, an interleaver and a rate 1 convolutional encoder with only one memory element and also called an accumulator as shown in Figure 5.46. Some LDPC codes can be seen as IRA codes.
5.5.4. Product codes
Product codes were introduced in 1954 by Elias [ELI 54]. The structure of these codes is given in Figure 5.47.
Figure 5.46. RA coder RT = 1/2
Figure 5.47. Product code
The product code is a (N, K) systematic linear code with N = nVnH and K = kVkH. The global rate of the product code is:
Each of the nV lines corresponds to a systematic linear block code CH (nH, kH) Furthermore, each column corresponds to a systematic block code CV (nV, kV). The main difference between product code and PCBC code is the presence of (nH − kH) × (nV − kV) additional redundancy bits for the protection of the parity bits of the line constituents codes (also called check on check bits). Similarly to PCBC, iterative decoding is applied to almost reach the performance of the maximum likelihood decoder6.
The minimum distance of these codes is equal to the product dV × dH where dV and dH are the minimum distance of the codes CV CH, respectively. The constituent codes are parity check codes, Hamming codes or BCH codes.
These codes have been selected for the WIMAX IEEE 802.16 standard. The constituent codes are parity check codes (8,7), (16,15) and (32,31) and also extended Hamming codes (16,11), (32,26) and (64,57).
5.6. Exercises
5.6.1. Exercise 1: soft input soft output decoding of a two-state convolutional code
Let us consider the recursive systematic convolutional encoder defined by the generator matri 
1) Determine the hardware structure of this coder. Express the output 
from 
and 
2) Determine the elementary trellis diagram of this code.
The Tanner graph associated with this code is given as follows:
3) Justify this graph.
We consider a transmission of four bits: three information bits and one termination bit to bring back the internal state to the zero state at time 4. We transmit the following vector:
The received intrinsic information 
is as follows:
4) Recall the mathematical expression of the a posteriori information (LLR).
5) Draw the trellis diagram by taking into account the termination.
6) Apply the forward-backward algorithm (log max version) to determine the a posteriori and extrinsic information associated with the symbol 
7) Find the results obtained using the forward-backward algorithm by using the minimum-sum algorithm over the Tanner graph of the code.
We consider a turbo code composed of the two previous RSC encoders and an interleaver of size 4 bits.
8) Draw the TWL graph used for the iterative decoding.
9) Explain the principle of the iterative decoding.
10) Justify why the constituent encoder should be an RSC encoder.
5.6.2. Exercise 2: soft input soft output decoding of a (4,3) linear block code
We consider the (4,3) systematic linear binary block code defined by the parity check equation: u1 + u1 + u3 + c4 = 0.
We use this code for a transmission over an additive white Gaussian noise channel of variance σ2. Before the transmission, the coded bits are converted into a bipodal signal bit 0 ⇒ − 1 and bit 1 ⇒ +1.
Let us consider the trellis and Tanner graph associated with this code:
The variable C5 in the Tanner graph is a hidden variable (variable without intrinsic information) added to have two parity check nodes of degree 3 instead of one parity check node of degree 4.
We transmit the word x = [+1 − 1 − 1 + 1] and receive the word y = [+0.4 − 0.2 + 0.2 + 1.4]. The variance of the noise is equal to σ2 = 2.
1) Apply the forward-backward algorithm (log max version) on this trellis to determine LAPP(xi). Deduce LEXTR(xi)
2) Use the minimum-sum algorithm to determine LAPP(xi). Deduce
LEXTR(xi).
3) Let us assume that we also have the following a priori information available: LAPRI = [+0.3 − 0.5 − 0.4 − 0.2] (obtained, for example, from another soft input soft output decoder). Solve questions 1) and 2) again.