Concatenated error correction code: Difference between revisions

Revision as of 08:40, 8 July 2019

Latest revision as of 22:27, 28 May 2025

(8 intermediate revisions by 6 users not shown)

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 102:

|pages=387–393

|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 111 ⟶ 113:

|author=J. P. Odenwalder

|title=Optimal decoding of convolutional codes

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

|year=1970

}}

Line 139 ⟶ 141:

==See also==

*[[Gilbert–Varshamov bound]]

*[[Justesen code]]

*[[Zyablov bound]]

*[[Singleton bound]]

*[[Gilbert–VarshamovZyablov bound]]

== References ==

Line 148 ⟶ 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-5 | 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-2 | pages=[https://archive.org/details/theoryoferrorcor0000macw/page/307 307–316] }}

== External links ==