Concatenated error correction code: Difference between revisions

Revision as of 05:12, 24 November 2017

Latest revision as of 22:27, 28 May 2025

(15 intermediate revisions by 11 users not shown)

Line 17:

[[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 [https://web.archive.org/web/20121012080412/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==

Line 27:

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''∘<math>\circ</math>''C''_''in'', is thus a code of length ''Nn'' over the alphabet ''A'':<ref name="Forney"/>

:<math>C_{out} \circ C_{in}: A^{kK} \rightarrow A^{nN}</math>

It maps each input message ''m'' = (''m''₁, ''m''₂, ..., ''m''_K) to a codeword (''C''_''in''(''m''<nowiki>'</nowiki>₁), ''C''_''in''(''m''<nowiki>'</nowiki>₂), ..., ''C''_''in''(''m''<nowiki>'</nowiki>_N)),

Line 37:

==Properties==

'''1.''' The distance of the concatenated code ''C''_''out''∘<math>\circ</math>''C''_''in'' is at least ''dD'', that is, it is a [''nN'', ''kK'', ''D''<nowiki>'</nowiki>] code with ''D''<nowiki>'</nowiki> ≥ ''dD''.

''Proof:''

Line 49:

:<math>\Delta(C_{in}(C_{out}(m^1)), C_{in}(C_{out}(m^2))) \ge dD.</math>

'''2.''' If ''C''_''out'' and ''C''_''in'' are [[linear block code]]s, then ''C''_''out''∘<math>\circ</math>''C''_''in'' is also a linear block code.

This property can be easily shown based on the idea of defining a [[generator matrix]] for the concatenated code in terms of the generator matrices of ''C''_''out'' and ''C''_''in''.

Line 72:

|last=Forney

|title=Generalized Minimum Distance Decoding

|journal=IEEE Transactions on Information Theory

|volume=12

|issue=2

|pages=125–131

|publisher=IEEE

|date=April 1966

|doi=10.1109/TIT.1966.1053873

}}</ref>

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]].<ref>{{cite journal

Line 85:

|last2=Costello

|title=Generalized Minimum Distance Decoding for ''Q''ary Output Channels

|journal=IEEE Transactions on Information Theory

|volume=26

|issue=2

|pages=238–243

|publisher=IEEE

|date=March 1980

|doi=10.1109/TIT.1980.1056148

}}</ref><ref>{{cite journal

|first1=Yingquan

Line 97:

|last2=Hadjicostis

|title=Soft-Decision Decoding of Linear Block Codes Using Preprocessing and Diversification

|journal=IEEE Transactions on Information Theory

|volume=53

|issue=1

|pages=387–393

|publisher=IEEE

|date=January 2007

|doi=10.1109/tit.2006.887478

|s2cid=8338433

}}</ref>

==Applications==

Although a simple concatenation scheme was implemented already for the 1971 [[Mariner 8|Mariner]] Mars orbiter mission,<ref name="McEliece"/> concatenated codes were starting to be regularly used for [[Deep Space Network|deep space]] communication with the [[Voyager program]], which launched two [[space probe]]s 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]].<ref name="McEliece"/><ref name="deep-space-codes"/>

Typically, the inner code is not a block code but a [[soft-decision decoder|soft-decision]] [[convolutional code|convolutional]] [[Viterbi decoder|Viterbi-decoded]] code with a short constraint length.<ref name="Odenwalder">

Line 112 ⟶ 113:

|author=J. P. Odenwalder

|title=Optimal decoding of convolutional codes

|publisher=[[U.C.L.A.]], Systems Science Dept. ''(dissertation)''

|year=1970

}}

Line 140 ⟶ 141:

==See also==

*[[Gilbert–Varshamov bound]]

*[[Justesen code]]

*[[Zyablov bound]]

*[[Singleton bound]]

*[[Gilbert–VarshamovZyablov bound]]

== References ==

Line 149 ⟶ 150:

== Further reading ==

* {{cite book |author1=Shu Lin |author2=Daniel J. Costello Jr. | title=Error Control Coding: Fundamentals and Applications |url=https://archive.org/details/errorcontrolcodi00lins_044 |url-access=limited | publisher=[[Prentice Hall]] | year=1983 | isbn=978-0-13-283796-X5 | pages=278–280[https://archive.org/details/errorcontrolcodi00lins_044/page/n296 278]–280}}

* {{cite book | author=F.J. MacWilliams | authorlink=Jessie MacWilliams |author2=N.J.A. Sloane | title=The Theory of Error-Correcting Codes | url=https://archive.org/details/theoryoferrorcor0000macw | url-access=registration | publisher=North-Holland | year=1977 | isbn=978-0-444-85193-32 | pages=[https://archive.org/details/theoryoferrorcor0000macw/page/307 307–316] }}

== External links ==

* {{scholarpedia|title=Concatenated codes|urlname=Concatenated_codes|curator=[[Dave Forney]]}}

* [https://web.archive.org/web/20110606191907/http://www.cse.buffalo.edu/~atri/courses/coding-theory/fall07.html University at Buffalo Lecture Notes on Coding Theory – Dr. Atri Rudra]

{{CCSDS|state=collapsed}}