Concatenated error correction 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 polynomial-time decoding complexity.

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.

In fact, the probability of decoding error can be made to decrease exponentially as the block length

However, the complexity of a naive optimum decoding scheme that simply computes the likelihood of every possible transmitted codeword increases exponentially with

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.

In other words, it is NO(1) (i.e., polynomial-time) 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 polynomial-time as well.

Similarly, the inner code can reliably correct an input yi if less than d/2 inner symbols are erroneous.

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 generalized minimum distance algorithm, developed by Forney, can be used to correct up to dD/2 errors.

[3][4] 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 two space probes in 1977.

[1][5] An interleaving layer is usually added between the two codes to spread error bursts across a wider range.

It is still notably used today for satellite communications, such as the DVB-S digital television broadcast standard.

[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.