Admin: Created page with "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..."

2019-05-04T02:36:16Z

Created page with "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..."

New page

In [[coding theory]], '''concatenated codes''' form a class of [[error-correcting code]]s 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 [[polynomial-time]] decoding [[Computational complexity theory|complexity]].
Concatenated codes became widely used in space communications in the 1970s.

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

[[Noisy-channel coding theorem|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 <math>R</math> less than a certain threshold <math>C</math>, 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 <math>N</math> 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 <math>N</math>, so such an optimum decoder rapidly becomes infeasible.

In his [http://mitpress.mit.edu/catalog/item/default.asp?tid=5813&ttype=2 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 (vector space)|dimension]] ''k'', minimum [[Hamming distance]] ''d'', and [[code rate|rate]] ''r'' = ''k''/''n'', over an alphabet ''A'':
:<math>C_{in}: A^k \rightarrow A^n</math>
Let ''C''''out'' be a [''N'', ''K'', ''D''] code over an alphabet ''B'' with |''B''| = |''A''|''k'' symbols:
:<math>C_{out}: B^K \rightarrow B^N</math>
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'':
It uses [[erasure code|erasure]] information from the inner code to improve performance of the outer code, and was the first example of an algorithm using [[soft-decision decoding]].

==Applications==
Although a simple concatenation scheme was implemented already 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]].
For the outer code, a longer hard-decision block code, frequently a [[Reed-Solomon code]] with eight-bit symbols, is used.
The larger symbol size makes the outer code more robust to [[error burst]]s that can occur due to channel impairments, and also because erroneous output of the convolutional code itself is bursty. and it became a popular construction both within and outside of the space sector. It is still notably used today for [[satellite communication]]s, such as the [[DVB-S]] [[digital television]] broadcast standard.

In a looser 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 (CD), where an interleaving layer between two Reed–Solomon codes of different sizes spreads errors across various blocks.

== Turbo codes: A parallel concatenation approach ==
The description above is given for what is now called a serially concatenated code. [[Turbo code]]s, 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. 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 the [[Galileo (spacecraft)|Galileo space probe]].

==See also==
*[[Justesen code]]
*[[Zyablov bound]]

==Source==
[http://wikipedia.org/ http://wikipedia.org/]

[[Category:Error-correcting codes]]

Concatenated error correction code - Revision history

Admin: Created page with "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..."