 Concatenated error correction code

In coding theory, concatenated codes form a class of errorcorrecting codes that are derived by combining an inner code and an outer code. They were conceived in 1966 by Dave Forney as a solution to the problem of finding a code that has both exponentially decreasing error probability with increasing block length and polynomialtime decoding complexity.^{[1]} Concatenated codes became widely used in space communications in the 1970s.
Contents
Background
The field of channel coding is concerned with sending a stream of data at the highest possible rate over a given communications channel, and then decoding the original data reliably at the receiver, using encoding and decoding algorithms that are feasible to implement in a given technology.
Shannon's channel coding theorem shows that over many common channels there exist channel coding schemes that are able to transmit data reliably at all rates R less than a certain threshold C, called the channel capacity of the given channel. In fact, the probability of decoding error can be made to decrease exponentially as the block length N of the coding scheme goes to infinity. However, the complexity of a naive optimum decoding scheme that simply computes the likelihood of every possible transmitted codeword increases exponentially with N, so such an optimum decoder rapidly becomes infeasible.
In his doctoral thesis, Dave Forney showed that concatenated codes could be used to achieve exponentially decreasing error probabilities at all data rates less than capacity, with decoding complexity that increases only polynomially with the code block length.
Description
Let C_{in} be a [n, k, d] code, that is, a block code of length n, dimension k, minimum Hamming distance d, and rate r = n/k, over an alphabet A:
Let C_{out} be a [N, K, D] code over an alphabet B with B = A^{k} symbols:
The inner code C_{in} takes one of A^{k} = B possible inputs, encodes into an ntuple over A, transmits, and decodes into one of B possible outputs. We regard this as a (super) channel which can transmit one symbol from the alphabet B. We use this channel N times to transmit each of the N symbols in a codeword of C_{out}. The concatenation of C_{out} (as outer code) with C_{in} (as inner code), denoted C_{out}∘C_{in}, is thus a code of length Nn over the alphabet A:^{[1]}
It maps each input message m = (m_{1}, m_{2}, ..., m_{K}) to a codeword (C_{in}(m'_{1}), C_{in}(m'_{2}), ..., C_{in}(m'_{N})), where (m'_{1}, m'_{2}, ..., m'_{N}) = C_{out}(m_{1}, m_{2}, ..., m_{K}).
The key insight in this approach is that if C_{in} is decoded using a maximumlikelihood approach (thus showing an exponentially decreasing error probability with increasing length), and C_{out} is a code with length N = 2^{nr} that can be decoded in polynomial time of N, then the concatenated code can be decoded in polynomial time of its combined length n2^{nr} = O(N⋅log(N)) and shows an exponentially decreasing error probability, even if C_{in} has exponential decoding complexity.^{[1]} This is discussed in more detail in section Decoding concatenated codes.
In a generalization of above concatenation, there are N possible inner codes C_{in,i} and the ith symbol in a codeword of C_{out} is transmitted across the inner channel using the ith inner code. The Justesen codes are examples of generalized concatenated codes, where the outer code is a ReedSolomon code.
Properties
1. The distance of the concatenated code C_{out}∘C_{in} is at least dD, that is, it is a [nN, kK, D'] code with D' ≥ dD.
Proof: Consider two different messages m^{1} ≠ m^{2} ∈ B^{K}. Let Δ denote the distance between two codewords. Then
Thus, there are at least D positions in which the sequence of N symbols of the codewords C_{out}(m^{1}) and C_{out}(m^{2}) differ. For these positions, denoted i, we have
Consequently, there are at least d⋅D positions in the sequence of n⋅N symbols taken from the alphabet A in which the two codewords differ, and hence
2. If C_{out} and C_{in} are linear block codes, then C_{out}∘C_{in} is also a linear block code.
This property can be easily shown based on the idea of defining a generator matrix for the concatenated code in terms of the generator matrices of C_{out} and C_{in}.
Decoding concatenated codes
A natural concept for a decoding algorithm for concatenated codes is to ﬁrst decode the inner code and then the outer code. For the algorithm to be practical it must be polynomialtime in the final block length. Consider that there is a polynomialtime unique decoding algorithm for the outer code. Now we have to find a polynomialtime decoding algorithm for the inner code. It is understood that polynomial running time here means that running time is polynomial in the final block length. The main idea is that if the inner block length is selected to be logarithmic in the size of the outer code then the decoding algorithm for the inner code may run in exponential time of the inner block length, and we can thus use an exponentialtime but optimal maximum likelihood decoder (MLD) for the inner code.
In detail, let the input to the decoder be the vector y = (y_{1}, ..., y_{N}) ∈ (A^{n})^{N}. Then the decoding algorithm is a twostep process:
 Use the MLD of the inner code C_{in} to reconstruct a set of inner code words y' = (y'_{1}, ..., y'_{N}), with y'_{i} = MLD_{Cin}(y_{i}), 1 ≤ i ≤ N.
 Run the unique decoding algorithm for C_{out} on y'.
Now, the time complexity of the first step is O(N⋅exp(n)), where n = O(log(N)) is the inner block length. In other words, it is N^{O(1)} (i.e., polynomialtime) in terms of the outer block length N. As the outer decoding algorithm in step two is assumed to run in polynomial time the complexity of the overall decoding algorithm is polynomialtime as well.
Remarks
The decoding algorithm described above can be used to correct all errors up to less than dD/4 in number. Using minimum distance decoding, the outer decoder can correct all inputs y' with less than D/2 symbols y'_{i} in error. Similarly, the inner code can reliably correct an input y_{i} if less than d/2 inner symbols are erroneous. Thus, for an outer symbol y'_{i} to be incorrect after inner decoding at least d/2 inner symbols must have been in error, and for the outer code to fail this must have happened for at least D/2 outer symbols. Consequently, the total number of inner symbols that must be received incorrectly for the concatenated code to fail must be at least d/2⋅D/2 = dD/4.
The algorithm also works if the inner codes are different, e.g., for Justesen codes. The generalized minimum distance algorithm, developed by Forney, can be used to correct up to dD/2 errors.^{[2]} It uses erasure information from the inner code to improve performance of the outer code, and was the first example of an algorithm using softdecision decoding.^{[3]}^{[4]}
Applications
Although a simple concatenation scheme was implemented already for the 1971 Mariner Mars orbiter mission,^{[5]} concatenated codes were starting to be regularly used for deep space communication with the Voyager program, which launched their first probe in 1977.^{[6]} Since then, concatenated codes became the workhorse for efficient error correction coding, and stayed so at least until the invention of turbo codes and LDPC codes.^{[5]}^{[6]}
Typically, the inner code is not a block code but a softdecision convolutional Viterbidecoded code with a short constraint length.^{[7]} For the outer code, a longer harddecision block code, frequently Reed Solomon with 8bit symbols, is selected.^{[1]}^{[5]} The larger symbol size makes the outer code more robust to burst errors that may occur due to channel impairments, and because erroneous output of the convolutional code itself is bursty.^{[1]}^{[5]} An interleaving layer is usually added between the two codes to spread burst errors across a wider range.^{[5]}
The combination of an inner Viterbi convolutional code with an outer ReedSolomon code (known as an RSV code) was first used on Voyager 2,^{[5]}^{[8]} and became a popular construction both within and outside of the space sector. It is still notably used today for satellite communication, such as the DVBS digital television broadcast standard.^{[9]}
In a more loose sense, any (serial) combination of two or more codes may be referred to as a concatenated code. For example, within the DVBS2 standard, a highly efficient LDPC code is combined with an algebraic outer code in order to remove any resilient errors left over from the inner LDPC code due to its inherent error floor.^{[10]}
A simple concatenation scheme is also used on the Compact Disc, where an interleaving layer between two ReedSolomon codes of different sizes effectively spreads errors across different blocks.
Turbo codes: A parallel concatenation approach
The description above is given for what is now called a serially concatenated code. Turbo codes, as described first in 1993, implemented a parallel concatenation of two convolutional codes, with an interleaver between the two codes and an iterative decoder that would pass information forth and back between the codes.^{[6]} This construction had much higher performance than all previously conceived concatenated codes.
However, a key aspect of turbo codes is their iterated decoding approach. Iterated decoding is now also applied to serial concatenations in order to achieve higher coding gains, such as within serially concatenated convolutional codes (SCCCs). An early form of iterated decoding was notably implemented with 2 to 5 iterations in the "Galileo code" of the Galileo spacecraft.^{[5]}
See Also
 Justesen code
 Zyablov bound
 Singleton bound
 GilbertVarshamov bound
References
 ^ ^{a} ^{b} ^{c} ^{d} ^{e} G. D. Forney (1967). Concatenated codes. Cambridge, Massachusetts: MIT Press.
 ^ Forney, G. David (April 1966). "Generalized Minimum Distance Decoding". Transactions on Information Theory (IEEE) 12 (2): 125−131.
 ^ Yu, Christopher C.H.; Costello, Daniel J. (March 1980). "Generalized Minimum Distance Decoding for Qary Output Channels". Transactions on Information Theory (IEEE) 26 (2): 238−243.
 ^ Wu, Yingquan; Hadjicostis, Christoforos (January 2007). "SoftDecision Decoding of Linear Block Codes Using Preprocessing and Diversification". Transactions on Information Theory (IEEE) 53 (1): 387−393.
 ^ ^{a} ^{b} ^{c} ^{d} ^{e} ^{f} ^{g} Robert J. McEliece; Laif Swanson (20 Aug. 1993). ReedSolomon Codes and the Exploration of the Solar System. JPL.
 ^ ^{a} ^{b} ^{c} K. Andrews et al., The Development of Turbo and LDPC Codes for DeepSpace Applications, Proceedings of the IEEE, Vol. 95, No. 11, Nov. 2007.
 ^ J. P. Odenwalder (1970). Optimal decoding of convolutional codes. U.C.L.A., Systems Science Dept. (dissertation).
 ^ R. Ludwig, J. Taylor, Voyager Telecommunications Manual, JPL DESCANSO (Design and Performance Summary Series), March 2002.
 ^ Digital Video Broadcasting (DVB); Framing structure, channel coding and modulation for 11/12 GHz satellite services, ETSI EN 300 421, V1.1.2, August 1997.
 ^ Digital Video Broadcasting (DVB); Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other broadband satellite applications (DVBS2), ETSI EN 302 307, V1.2.1, April 2009.
Further reading
 Shu Lin, Daniel J. Costello, Jr. (1983). Error Control Coding: Fundamentals and Applications. Prentice Hall. pp. 278–280. ISBN 013283796X.
 F.J. MacWilliams; N.J.A. Sloane (1977). The Theory of ErrorCorrecting Codes. NorthHolland. pp. 307–316. ISBN 0444851933.
External links
 Concatenated codes at Scholarpedia, curated by Dave Forney.
 University at Buffalo Lecture Notes on Coding Theory – Dr. Atri Rudra
Consultative Committee for Space Data Systems Data compression Error Correction Telemetry command uplink Telemetry downlink Spacecraft Monitoring & Control • Beacon mode serviceTelemetry general Telemetry modulation systems BPSK • QPSK • OQPSK • Proposed: GMSKFrequencies Networking, interoperability and monitoring Categories:
Wikimedia Foundation. 2010.