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.
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.
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:
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.
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
with:
The factor graph associated with this code is given in Figure 5.2.
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
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.
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).
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.
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.
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.
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:
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:
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):
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:
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:
In the case of systematic convolutional codes, we have the following expressions:
with:
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:
Let us consider the recursive systematic convolutional encoder with rate 1/2 . The associated trellis is given in Figure 5.9.
We suppose that the information word, codeword and received word are the ones given in Table 5.1.
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.
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
Calculation of ß
The final results are given in Figure 5.11.
Calculation of
We use the following relation:
Finally, after calculation, we obtain the a posteriori information given in Table 5.5.
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.
Similarly, instead of calculating α and β, we will calculate ln α and ln β.
Calculation of ln α
The final results are presented in Figure 5.12
Calculation of ln ß
The final results are given in Figure 5.13.
Calculation of
We are using the relation:
Finally, after calculation, we obtain the a posteriori information given in Table 5.7.
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.
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:
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.
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.
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:
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, ….
We obtain the same expressions α(si) and β(si+1) as the ones computed previously using the forward-backward algorithm.
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.
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.
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.
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.
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].
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.
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.
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.
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:
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:
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:
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.
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.
www.iste.co.uk/leruyet/communications1.zip
The two phases of algorithm A are the following:
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.
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
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
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).
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]:
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.
We can observe that the curves obtained using the two approaches are very closed. The Gaussian approximation gives slightly pessimistic results.
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.
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:
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.
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.
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.
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:
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.
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.
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.
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.
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.
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.
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.
To conclude, the association of turbo codes and iterative decoding gives very good performance with a reasonable complexity.
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.
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.
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.
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.
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.
The three main criteria for the construction of the interleaver are the following:
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.
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.
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.
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:
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.
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)) + .
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.
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.
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.
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.
Product codes were introduced in 1954 by Elias [ELI 54]. The structure of these codes is given in Figure 5.47.
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).
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.
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.