Concatenated error correction code: Difference between revisions

Revision as of 11:11, 23 August 2009

Revision as of 11:38, 23 August 2009

Line 8:

The ''key insight'' in this approach is that if ''I'' is decoded using a [[maximum likelihood decoding|maximum-likelihood approach]] (thus showing an exponentially decreasing error probability with increasing length), and ''C'' is a code with length ''N''=2^''(n*r)'' that can be decoded in polynomial time of ''N'', then the concatenated code can be decoded in polynomial time of its combined length ''n*2^(n*r)'' and shows an exponentially decreasing error probability, even if ''I'' has exponential decoding complexity.

In a generalisation of above concatenation, there are ''N'' possible inner codes ''I''_''i'' and the ''i''-th symbol in a codeword of ''C'' is transmitted across the inner channel using the ''i''-th inner code. The [[Justesen code]]s are examples of generalised concatenated codes, where the outer codescode is a [[Reed-Solomon code]].

==Applications==

Concatenated codes were first implemented for [[deep space]] communication in the [[Voyager program]], which launched their first probe in 1977.<ref name="deep-space-codes">K. Andrews et al., ''The Development of Turbo and LDPC Codes for Deep-Space Applications'', Proceedings of the IEEE, Vol. 95, No. 11, Nov. 2007.</ref> 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 code|convolutional]] [[Viterbi decoder|Viterbi-decoded]] code with a short constraint length. For the outer code, a hard-decision block code, most frequently [[Reed Solomon]] with 8-bit symbols, is selected. The larger symbol size makes the outer code more robust to [[error burst|burst error]]s that may occur due to channel impairments, and because erroneous output of the convolutional code itself is bursty. Additionally, an [[interleaving]] layer may be used that spreads 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, became the most popular construction, and was already used on the Voyager probes. It is still in use today for deep-space and [[satellite communication]], notably the [[DVB-S]] [[digital television]] broadcast standard.