Concatenated error correction code

In coding theory, concatenated codes form a class of error-correcting codes that are derived by combining an inner code and an outer code. They were conceived in 1966 by Dave Forney as a solution for the problem of finding a code that has both exponentially decreasing error probability with increasing block length and polynomial-time decoding complexity. Concatenated codes became widely used in space communications in the 1970s.

Origin

The field of channel coding is concerned with sending a stream of data at as high a rate as possible 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

Schematic depiction of a concatenated code built upon an inner code and an outer code.

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:

$C_{in}:A^{k}\rightarrow A^{n}$

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

$C_{out}:B^{K}\rightarrow B^{N}$

The inner code C_in takes one of |A|^k = |B| possible inputs, encodes into an n-tuple 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:

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

It maps each input message m = (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).

The key insight in this approach is that if C_in is decoded using a maximum-likelihood 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 and shows an exponentially decreasing error probability, even if C_in has exponential decoding complexity.

In a generalization of above concatenation, there are N possible inner codes C_in,i and the i-th symbol in a codeword of C_out is transmitted across the inner channel using the i-th inner code. The Justesen codes are examples of generalized concatenated codes, where the outer code is a Reed-Solomon code.

Properties

1. Given $C_{out}$ as an $(N,K,D)_{q}^{k}$ code and $C_{in}$ as an $(n,k,d)_{q}$ code, $C_{out}\circ C_{in}$ is an $(nN,kK,dD)_{q}$ code.

where

$(N,K,D)$ is the block length, dimension and distance of the outer code.

$(n,k,d)$ is the block length, dimension and distance of the inner code.

PROOF: Consider $C_{out}\circ C_{in}$. The parameters such as block length, dimension and alphabet have already been defined. Using the same parameters defined above, we have to prove that the distance is at least $dD$.

We start the proof by considering $m^{1}\neq m^{2}\in [Q]^{K}$.

Then, $\Delta (C_{out}(m^{1}),C_{out}(m^{2}))\geq D$.............................................................(i)

Now for each position $1\leq i\leq N$ which contributes to the distance defined above, we have

$\Delta (C_{in}(C_{out}(m^{1})_{i})$, $C_{out}(m^{2})_{i})\geq d$.............................................................(ii)

We know that $C_{in}$ has distance $d$. From (i) and (ii) we can infer that there are atleast $D$ positions which satisfies the above equation.

$\Delta (C_{in}(C_{out}(m^{1})),C_{out}(m^{2}))\geq dD$

Thus it's proved that $C_{out}\circ C_{in}$ is an $(nN,kK,dD)_{q}$ code.

2. If $C_{in}$ and $C_{out}$ are linear codes, then $C_{out}\circ C_{in}$ is also a linear code.

The proof is very simple and can be done by the following idea. Define a generator matrix for $C_{out}\circ C_{in}$ in terms of the generator matrices of $C_{in}$ and $C_{out}$

Decoding Concatenated Codes

A natural decoding algorithm for concatenated codes is that the code first decodes the inner code and then decodes the outer code. 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 codes. It is understood that polynomial running time here means that running time is polynomial in the final block length. The main idea is to pick a decoding algorithm that runs in time singly exponential in the inner block length as long as the inner block length is logarithmic in the outer code block length. However, we have assumed that the inner block length is logarithmic in the outer code and thus, we can use the Maximum Likelihood Decoder (or MLD) for the inner code.

Let the input to the decoder be the vector $y=(y_{1}..y_{N})\in [q^{n}]^{N}$. The decoding algorithm is a two step process:

1. Compute $y'=(y'_{1}..y'_{N})\in [q^{n}]^{N}$ as follows:

$y'_{i}=MLD_{C_{in}}(y_{i}),1$ < $i$ < $N$

2. Run the unique decoding algorithm for $C_{out}$ on $y'$.

We now verify that each step of the algorithm above can be implemented in polynomial time:

1. The time complexity of Step 1 is $O(nqk)$, which for our choice of $k=O(logN)$ (and constant rate) for the inner code, is $(nN)^{O(1)}$ time.

2. Step 2 needs polynomial time by our assumption that the unique decoding algorithm for $C_{out}$ takes $N^{O(1)}$ time. This implies that the running time of the decoding algorithm is polynomial time overall.

Remarks

1. The decoding algorithm above can correct < $Dd \over 4$ many errors.

PROOF:

We prove the above theorem using the concept of ${\textit {BadEvent}}$ which is defined as follows: Consider a bad event has occurred (at position $1$ < $i$ < $N$) if $MLD_{C_{i}}(y_{i})\neq C_{out}(m)_{I}$ where $m$ was the original message and

$\Delta (C_{out}\circ C_{in}(m),y)$ < $Dd \over 4$

We also know that if the number of bad events is less than $D \over 2$, then the decoder in Step 2 will output $m$.

Thus our goal is to find out when a bad event happens to complete the proof.

Also a bad event cannot happen at position $i$ if

$\Delta (y_{i},C_{out}(m)_{i})$ < $d \over 2$

Now if the number of bad events is at least $D \over 2$, then the total number of errors is at least $D \over 2\cdot$ $d \over 2$ = $Dd \over 4$, which is a contradiction. Thus, the number of bad events is strictly less than $D \over 2$.

2. The algorithm also works if the inner codes are different, e.g. Justesen codes.

Also the Generalized Minimum Distance algorithm can correct up to $Dd \over 2$ errors.

Applications

Concatenated codes were starting to be regularly used for deep space communication with the Voyager program, which launched their first probe in 1977. (A simple concatenation scheme however was already implemented for the 1971 Mariner Mars orbiter mission.) 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.

Typically, the inner code is not a block code but a soft-decision convolutional Viterbi-decoded code with a short constraint length. For the outer code, a longer hard-decision block code, frequently Reed Solomon with 8-bit symbols, is selected. 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. An interleaving layer is usually added between the two codes to spread burst errors across a wider range.

The combination of an inner Viterbi convolutional code with an outer Reed-Solomon code (known as an RSV code) was first used on Voyager 2, 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 DVB-S digital television broadcast standard.

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 DVB-S2 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.

A simple concatenation scheme is also used on the Compact Disc, where an interleaving layer between two Reed-Solomon 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. 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.

See Also

• Justesen code
• Reed solomon codes
• BCH Code
• Singleton bound
• Gilbert-Varshamov bound

Further reading

• Shu Lin, Daniel J. Costello, Jr. (1983). Error Control Coding: Fundamentals and Applications. Prentice Hall. pp. 278–280. ISBN 0-13-283796-X.{{cite book}}: CS1 maint: multiple names: authors list (link)
• F.J. MacWilliams (1977). The Theory of Error-Correcting Codes. North-Holland. pp. 307–316. ISBN 0-444-85193-3. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

External links

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