Incoding theory,concatenated codes form a class oferror-correcting codes that are derived by combining aninner code and anouter code. They were conceived in 1966 byDave Forney as a solution to the problem of finding a code that has both exponentially decreasing error probability with increasing block length andpolynomial-time decodingcomplexity.^[1]Concatenated codes became widely used in space communications in the 1970s.

The field ofchannel coding is concerned with sending a stream of data at the highest possible rate over a givencommunications 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${\displaystyle R}$ less than a certain threshold${\displaystyle C}$, called thechannel capacity of the given channel. In fact, the probability of decoding error can be made to decrease exponentially as the block length${\displaystyle 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${\displaystyle N}$, so such an optimum decoder rapidly becomes infeasible.

In hisdoctoral 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.

LetC_in be a [n,k,d] code, that is, ablock code of lengthn,dimensionk, minimumHamming distanced, andrater =k/n, over an alphabetA:

${\displaystyle C_{in}:A^k\to A^n}$

LetC_out be a [N,K,D] code over an alphabetB with |B| = |A|^k symbols:

${\displaystyle C_{out}:B^K\to B^N}$

The inner codeC_in takes one of |A|^k = |B| possible inputs, encodes into ann-tuple overA, transmits, and decodes into one of |B| possible outputs. We regard this as a (super) channel which can transmit one symbol from the alphabetB. We use this channelN times to transmit each of theN symbols in a codeword ofC_out. Theconcatenation ofC_out (as outer code) withC_in (as inner code), denotedC_out${\displaystyle \circ }$C_in, is thus a code of lengthNn over the alphabetA:^[1]

${\displaystyle C_{out}\circ C_{in}:A^{kK}\to A^{nN}}$

It maps each input messagem = (m₁,m₂, ...,m_K) to a codeword (C_in(m'₁),C_in(m'₂), ...,C_in(m'_N)),where (m'₁,m'₂, ...,m'_N) =C_out(m₁,m₂, ...,m_K).

Thekey insight in this approach is that ifC_in is decoded using amaximum-likelihood approach (thus showing an exponentially decreasing error probability with increasing length), andC_out is a code with lengthN = 2^nr that can be decoded in polynomial time ofN, then the concatenated code can be decoded in polynomial time of its combined lengthn2^nr =O(N⋅log(N)) and shows an exponentially decreasing error probability, even ifC_in has exponential decoding complexity.^[1] This is discussed in more detail in sectionDecoding concatenated codes.

In a generalization of above concatenation, there areN possible inner codesC_in,i and thei-th symbol in a codeword ofC_out is transmitted across the inner channel using thei-th inner code. TheJustesen codes are examples of generalized concatenated codes, where the outer code is aReed–Solomon code.

1. The distance of the concatenated codeC_out${\displaystyle \circ }$C_in is at leastdD, that is, it is a [nN,kK,D'] code withD' ≥dD.

Proof:Consider two different messagesm¹ ≠m² ∈B^K. Let Δ denote the distance between two codewords. Then

${\displaystyle \mathrm{\Delta }(C_{out}(m^1),C_{out}(m^2))\ge D.}$

Thus, there are at leastD positions in which the sequence ofN symbols of the codewordsC_out(m¹) andC_out(m²) differ. For these positions, denotedi, we have

${\displaystyle \mathrm{\Delta }(C_{in}(C_{out}(m^1{)}_i),C_{in}(C_{out}(m^2{)}_i))\ge d.}$

Consequently, there are at leastd⋅D positions in the sequence ofn⋅N symbols taken from the alphabetA in which the two codewords differ, and hence

${\displaystyle \mathrm{\Delta }(C_{in}(C_{out}(m^1)),C_{in}(C_{out}(m^2)))\ge dD.}$

2. IfC_out andC_in arelinear block codes, thenC_out${\displaystyle \circ }$C_in is also a linear block code.

This property can be easily shown based on the idea of defining agenerator matrix for the concatenated code in terms of the generator matrices ofC_out andC_in.

A natural concept for a decoding algorithm for concatenated codes is to first decode the inner code and then the outer code. For the algorithm to be practical it must bepolynomial-time in the final block length. Consider that there is a polynomial-time unique decoding algorithm for the outer code. Now we have to find a polynomial-time 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 inexponential time of the inner block length, and we can thus use an exponential-time but optimalmaximum likelihood decoder (MLD) for the inner code.

In detail, let the input to the decoder be the vectory = (y₁, ...,y_N) ∈ (Aⁿ)^N. Then the decoding algorithm is a two-step process:

1. Use the MLD of the inner codeC_in to reconstruct a set of inner code wordsy' = (y'₁, ...,y'_N), withy'_i = MLD_Cin(y_i), 1 ≤i ≤N.
2. Run the unique decoding algorithm forC_out ony'.

Now, the time complexity of the first step isO(N⋅exp(n)), wheren =O(log(N)) is the inner block length. In other words, it isN^O(1) (i.e., polynomial-time) in terms of the outer block lengthN. As the outer decoding algorithm in step two is assumed to run in polynomial time the complexity of the overall decoding algorithm is polynomial-time as well.

The decoding algorithm described above can be used to correct all errors up to less thandD/4 in number. Usingminimum distance decoding, the outer decoder can correct all inputsy' with less thanD/2 symbolsy'_i in error. Similarly, the inner code can reliably correct an inputy_i if less thand/2 inner symbols are erroneous. Thus, for an outer symboly'_i to be incorrect after inner decoding at leastd/2 inner symbols must have been in error, and for the outer code to fail this must have happened for at leastD/2 outer symbols. Consequently, the total number of inner symbols that must be received incorrectly for the concatenated code to fail must be at leastd/2⋅D/2 =dD/4.

The algorithm also works if the inner codes are different, e.g., forJustesen codes. Thegeneralized minimum distance algorithm, developed by Forney, can be used to correct up todD/2 errors.^[2]It useserasure information from the inner code to improve performance of the outer code, and was the first example of an algorithm usingsoft-decision decoding.^[3][4]

Although a simple concatenation scheme was implemented already for the 1971Mariner Mars orbiter mission,^[5] concatenated codes were starting to be regularly used fordeep space communication with theVoyager program, which launched twospace probes in 1977.^[6] Since then, concatenated codes became the workhorse for efficient error correction coding, and stayed so at least until the invention ofturbo codes andLDPC codes.^[5][6]

Typically, the inner code is not a block code but asoft-decisionconvolutionalViterbi-decoded code with a short constraint length.^[7]For the outer code, a longer hard-decision block code, frequently aReed-Solomon code with eight-bit symbols, is used.^[1][5]The larger symbol size makes the outer code more robust toerror bursts that can occur due to channel impairments, and also because erroneous output of the convolutional code itself is bursty.^[1][5] Aninterleaving layer is usually added between the two codes to spread error bursts across a wider range.^[5]

The combination of an inner Viterbi convolutional code with an outerReed–Solomon code (known as an RSV code) was first used inVoyager 2,^[5][8] and it became a popular construction both within and outside of the space sector. It is still notably used today forsatellite communications, such as theDVB-Sdigital television broadcast standard.^[9]

In a looser sense, any (serial) combination of two or more codes may be referred to as a concatenated code. For example, within theDVB-S2 standard, a highly efficientLDPC 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 inherenterror floor.^[10]

A simple concatenation scheme is also used on the compact disc (CD), where an interleaving layer between two Reed–Solomon codes of different sizes spreads errors across various blocks.

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 passes information forth and back between the codes.^[6] This design has a better performance than any 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 implemented with two to five iterations in the "Galileo code" of theGalileo space probe.^[5]

• Gilbert–Varshamov bound
• Justesen code
• Singleton bound
• Zyablov bound

• Shu Lin; Daniel J. Costello Jr. (1983).Error Control Coding: Fundamentals and Applications.Prentice Hall. pp. 278–280.ISBN 978-0-13-283796-5.
• F.J. MacWilliams; N.J.A. Sloane (1977).The Theory of Error-Correcting Codes. North-Holland. pp. 307–316.ISBN 978-0-444-85193-2.

• Dave Forney (ed.)."Concatenated codes".Scholarpedia.
• University at Buffalo Lecture Notes on Coding Theory – Dr. Atri Rudra

• Error detection and correction
• Coding theory
• Finite fields
• Information theory

• CS1 errors: missing periodical
• Use dmy dates from July 2014