m partial cleanup of mess
|
→See also: alpha
Tags: Mobile edit Mobile web edit Advanced mobile edit
|
||
(45 intermediate revisions by 24 users not shown) | |||
Line 1: | Line 1: | ||
{{Use dmy dates|date=July 2014}} |
|||
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 for 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]].<ref name="Forney"> |
|||
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]].<ref name="Forney"> |
|||
{{cite journal |
{{cite journal |
||
|author= |
|author=G. D. Forney |
||
|author-link=Dave Forney |
|||
|title=Concatenated codes |
|title=Concatenated codes |
||
|publisher=MIT Press |
|publisher=MIT Press |
||
Line 10: | Line 12: | ||
Concatenated codes became widely used in space communications in the 1970s. |
Concatenated codes became widely used in space communications in the 1970s. |
||
==Background== |
|||
The idea of concatenated codes is that we can create a new code by composing an existing code with another code, that is over the desired alphabet. Consider the output of the first code (outer code) applied to be the message is <math>(\sigma_{1}...\sigma_{n-1})</math>. Now each <math>\sigma_{i}</math> can be interpreted as a string in smaller alphabet. Then the second code (inner code) can be used to encode each <math>\sigma_{i}</math> over a smaller alphabet. The final codeword is the concatenation of all these inner codewords. |
|||
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. |
|||
==Origin== |
|||
The field of [[channel coding]] is concerned with sending a stream of data at as high a rate as possible 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 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. |
|||
[[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== |
==Description== |
||
[[File:Concatenated codes diagram.png|thumb|upright=2|Schematic depiction of a concatenated code built upon an inner code and an outer code.]] |
|||
[[File:Concatenated_codes_diagram.png]] |
|||
[[File:Concatenation of Reed–Solomon code with Hadamard code.svg|thumb|400px|This is a pictorial representation of a code concatenation, and, in particular, the [[Reed–Solomon code]] with n=q=4 and k=2 is used as the outer code and the [[Hadamard code]] with n=q and k=log q is used as the inner code. Overall, the concatenated code is a <math>[q^2,k \log q]</math>-code.]] |
|||
Let <math>C_{out}</math> be a code with length <math>N</math> and rate <math>R</math> over an alphabet <math>A</math> with <math>K=N \cdot R</math> symbols. Let <math>C_{in}</math> be another code with length <math>n</math> and rate <math>r</math> over an alphabet <math>B</math> with <math>k=n*r</math> symbols. |
|||
The inner code <math>C_{in}</math> takes one of <math>k </math>possible inputs, encodes onto an n-tuple from <math>B</math>, transmits, and decodes into one of <math>k</math> possible outputs. We regard this as a (super) channel which can transmit one symbol from the alphabet <math>A</math>, also of size <math>k</math>. We use this channel <math>N</math> times to transmit each of the <math>N</math> symbols in a codeword of <math>C_{out}</math>. The concatenation of <math>C_{out}</math> (as outer code) with <math>C_{in}</math> (as inner code) is thus a code of length <math>Nn</math> over the alphabet <math>B</math>. |
|||
The key insight in this approach is that if <math>C_{in}</math> is decoded using a maximum-likelihood approach (thus showing an exponentially decreasing error probability with increasing length), and <math>C_{out}</math> is a code with length <math>N=2nr</math> that can be decoded in polynomial time of <math>N</math>, then the concatenated code can be decoded in polynomial time of its combined length <math>n2^{nr}</math> and shows an exponentially decreasing error probability, even if <math>C_{in}</math> has exponential decoding complexity. |
|||
In a generalization of above concatenation, there are <math>N</math> possible inner codes <math>C_{in_{i}}</math> and the <math>i-</math>th symbol in a codeword of <math>C_{out}</math> is transmitted across the inner channel using the <math>i-</math>th inner code. The [[Justesen code]]s are examples of generalized concatenated codes, where the outer code is a [[Reed-Solomon error correction]] code. |
|||
Consider the outer code and inner code: |
|||
<math>C_{out}</math>: <math>[Q]^K \rightarrow [Q]^N</math> |
|||
<math>C_{in}</math>: <math>[q]^k \rightarrow [q]^n</math> |
|||
Note that the alphabet size of <math>C_{out}</math> exactly matches |<math>C_{in}</math>|. |
|||
The concatenated code <math>C_{out}</math> · <math>C_{in}</math>: <math>[q]^k \rightarrow [q]^n</math> is defined as follows |
|||
Let ''C''<sub>''in''</sub> 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'': |
|||
Given <math>m = (m_{1},..,m_{K}) \in [Q]^K</math> , we have |
|||
:<math>C_{in}: A^k \rightarrow A^n</math> |
|||
Let ''C''<sub>''out''</sub> be a [''N'', ''K'', ''D''] code over an alphabet ''B'' with |''B''| = |''A''|<sup>''k''</sup> symbols: |
|||
:<math>C_{out}: B^K \rightarrow B^N</math> |
|||
The inner code ''C''<sub>''in''</sub> takes one of |''A''|<sup>''k''</sup> = |''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''<sub>''out''</sub>. The ''concatenation'' of ''C''<sub>''out''</sub> (as outer code) with ''C''<sub>''in''</sub> (as inner code), denoted ''C''<sub>''out''</sub>∘''C''<sub>''in''</sub>, 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''<sub>1</sub>, ''m''<sub>2</sub>, ..., ''m''<sub>K</sub>) to a codeword (''C''<sub>''in''</sub>(''m''<nowiki>'</nowiki><sub>1</sub>), ''C''<sub>''in''</sub>(''m''<nowiki>'</nowiki><sub>2</sub>), ..., ''C''<sub>''in''</sub>(''m''<nowiki>'</nowiki><sub>N</sub>)), |
|||
where (''m''<nowiki>'</nowiki><sub>1</sub>, ''m''<nowiki>'</nowiki><sub>2</sub>, ..., ''m''<nowiki>'</nowiki><sub>N</sub>) = ''C''<sub>''out''</sub>(''m''<sub>1</sub>, ''m''<sub>2</sub>, ..., ''m''<sub>K</sub>). |
|||
The ''key insight'' in this approach is that if ''C''<sub>''in''</sub> is decoded using a [[maximum likelihood decoding|maximum-likelihood approach]] (thus showing an exponentially decreasing error probability with increasing length), and ''C''<sub>''out''</sub> is a code with length ''N'' = 2<sup>''nr''</sup> 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<sup>''nr''</sup> = [[O notation|''O'']](''N''⋅log(''N'')) and shows an exponentially decreasing error probability, even if ''C''<sub>''in''</sub> has exponential decoding complexity.<ref name="Forney"/> This is discussed in more detail in section [[#Decoding concatenated codes|Decoding concatenated codes]]. |
|||
<math> C_{out}\cdot C_{in} (m) = (C_{in} (C_{out} (m_1)), . . ,C_{in} (C_{out} (m_{N}) ))</math> |
|||
In a generalization of above concatenation, there are ''N'' possible inner codes ''C''<sub>''in'',''i''</sub> and the ''i''-th symbol in a codeword of ''C''<sub>''out''</sub> is transmitted across the inner channel using the ''i''-th inner code. The [[Justesen code]]s are examples of generalized concatenated codes, where the outer code is a [[Reed–Solomon code]]. |
|||
where <math>C_{out}(m) = (C_{out} ((m_1), . . ,(m_N)))</math> |
|||
==Properties== |
==Properties== |
||
'''1.''' The distance of the concatenated code ''C''<sub>''out''</sub>∘''C''<sub>''in''</sub> is at least ''dD'', that is, it is a [''nN'', ''kK'', ''D''<nowiki>'</nowiki>] code with ''D''<nowiki>'</nowiki> ≥ ''dD''. |
|||
1. '''''Given <math>C_{out}</math> as an <math>(N, K, D)_q ^k</math> code and <math>C_{in}</math> as an <math>(n, k, d)_q</math> code, <math>C_{out} \circ C_{in}</math> is an <math>(nN, kK, dD)_q</math> code.''''' |
|||
''Proof:'' |
|||
where |
|||
Consider two different messages ''m''<sup>1</sup> ≠ ''m''<sup>2</sup> ∈ ''B''<sup>''K''</sup>. Let Δ denote the distance between two codewords. Then |
|||
:<math>\Delta(C_{out}(m^1), C_{out}(m^2)) \ge D.</math> |
|||
Thus, there are at least ''D'' positions in which the sequence of ''N'' symbols of the codewords ''C''<sub>''out''</sub>(''m''<sup>1</sup>) and ''C''<sub>''out''</sub>(''m''<sup>2</sup>) differ. For these positions, denoted ''i'', we have |
|||
<math>(N, K, D)</math> is the block length, dimension and distance of the outer code. |
|||
:<math>\Delta(C_{in}(C_{out}(m^1)_i), C_{in}(C_{out}(m^2)_i)) \ge d.</math> |
|||
Consequently, there are at least ''d''⋅''D'' positions in the sequence of ''n''⋅''N'' symbols taken from the alphabet ''A'' in which the two codewords differ, and hence |
|||
<math>(n, k, d)</math> is the block length, dimension and distance of the inner code. |
|||
:<math>\Delta(C_{in}(C_{out}(m^1)), C_{in}(C_{out}(m^2))) \ge dD.</math> |
|||
'''2.''' If ''C''<sub>''out''</sub> and ''C''<sub>''in''</sub> are [[linear block code]]s, then ''C''<sub>''out''</sub>∘''C''<sub>''in''</sub> is also a linear block code. |
|||
'''''PROOF:''''' |
|||
Consider <math>C_{out} \circ C_{in}</math>. The parameters such as block length, dimension and alphabet have already been defined. |
|||
Using the same parameters defined above, we have to prove that the distance is at least <math>dD</math>. |
|||
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''<sub>''out''</sub> and ''C''<sub>''in''</sub>. |
|||
We start the proof by considering <math>m^1 \ne m^2 \in [Q]^K</math>. |
|||
==Decoding concatenated codes== |
|||
Then, <math>\Delta(C_{out}(m^1), C_{out}(m^2)) \ge D</math>.............................................................(i) |
|||
A natural concept for a decoding algorithm for concatenated codes is to first decode the inner code and then the outer code. For the algorithm to be practical it must be [[polynomial-time]] in the final block length. Consider that there is a polynomial-time unique decoding algorithm for the outer code. Now we have to find a polynomial-time decoding algorithm for the inner code. It is understood that polynomial running time here means that running time is polynomial in the final block length. The main idea is that if the inner block length is selected to be logarithmic in the size of the outer code then the decoding algorithm for the inner code may run in [[exponential time]] of the inner block length, and we can thus use an exponential-time but optimal [[Decoding methods#Maximum likelihood decoding|maximum likelihood decoder]] (MLD) for the inner code. |
|||
Now for each position <math>1 \le i \le N</math> which contributes to the distance defined above, we have |
|||
In detail, let the input to the decoder be the vector ''y'' = (''y''<sub>1</sub>, ..., ''y''<sub>''N''</sub>) ∈ (''A''<sup>''n''</sup>)<sup>''N''</sup>. Then the decoding algorithm is a two-step process: |
|||
<math>\Delta(C_{in}(C_{out}(m^1)_i)</math>, <math>C_{out}(m^2)_i) \ge d</math>.............................................................(ii) |
|||
# Use the MLD of the inner code ''C''<sub>in</sub> to reconstruct a set of inner code words ''y''<nowiki>'</nowiki> = (''y''<nowiki>'</nowiki><sub>1</sub>, ..., ''y''<nowiki>'</nowiki><sub>''N''</sub>), with ''y''<nowiki>'</nowiki><sub>''i''</sub> = MLD<sub>''C''<sub>in</sub></sub>(''y''<sub>i</sub>), 1 ≤ ''i'' ≤ ''N''. |
|||
# Run the unique decoding algorithm for ''C''<sub>out</sub> on ''y''<nowiki>'</nowiki>. |
|||
Now, the time complexity of the first step is [[O notation|''O'']](''N''⋅exp(''n'')), where ''n'' = ''O''(log(''N'')) is the inner block length. In other words, it is ''N''<sup>''O''(1)</sup> (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. |
|||
We know that <math>C_{in}</math> has distance <math>d</math>. From (i) and (ii) we can infer that there are atleast <math>D</math> positions which satisfies the above equation. |
|||
<math>\Delta(C_{in}(C_{out}(m^1)), C_{out}(m^2)) \ge dD</math> |
|||
Thus it's proved that <math>C_{out} \circ C_{in}</math> is an <math>(nN, kK, dD)_q</math> code. |
|||
2. '''''If <math>C_{in}</math> and <math>C_{out}</math> are [[linear code]]s, then <math>C_{out} \circ C_{in}</math> is also a linear code.''''' |
|||
The proof is very simple and can be done by the following idea. Define a [[generator matrix]] for <math>C_{out} \circ C_{in}</math> in terms of the generator matrices of <math>C_{in}</math> and <math>C_{out}</math> |
|||
==Decoding Concatenated Codes== |
|||
A natural decoding algorithm for concatenated codes is that the code first decodes the inner code and then decodes the outer code. Consider that there is a polynomial time unique decoding algorithm for the outer code. Now we have to find a polynomial time decoding algorithm for the inner codes. It is understood that polynomial running time here means that running time is polynomial in the final block length. The main idea is to pick a decoding algorithm that runs in time singly exponential in the inner block length as long as the inner block length is logarithmic in the outer code block length. However, we have assumed that the inner block length is logarithmic in the outer code and thus, we can use the [[Decoding_methods#Maximum_likelihood_decoding|Maximum Likelihood Decoder]] (or MLD) for the inner code. |
|||
Let the input to the decoder be the vector <math>y = (y_1 . . y_N) \in [q^n]^N</math>. The decoding algorithm is a two step process: |
|||
1. Compute <math>y'= (y'_{1} . . y'_{N} ) \in [q^n]^N</math> as follows: |
|||
<math>y'_i = MLD_{C_{in}} (y_i), 1</math> < <math> i </math> < <math>N</math> |
|||
2. Run the unique decoding algorithm for <math>C_{out}</math> on <math>y'</math>. |
|||
|
|||
We now verify that each step of the algorithm above can be implemented in polynomial time: |
|||
1. The time complexity of Step 1 is <math>O(nqk)</math>, which for our choice of <math>k = O(log N)</math> (and constant rate) for the inner code, is <math>(nN)^{O(1)}</math> time. |
|||
2. Step 2 needs polynomial time by our assumption that the unique decoding algorithm for <math>C_{out}</math> takes <math>N^{O(1)}</math> time. This implies that the running time of the decoding algorithm is polynomial time overall. |
|||
===Remarks=== |
===Remarks=== |
||
The decoding algorithm described above can be used to correct all errors up to less than ''dD''/4 in number. Using [[minimum distance decoding]], the outer decoder can correct all inputs ''y''<nowiki>'</nowiki> with less than ''D''/2 symbols ''y''<nowiki>'</nowiki><sub>''i''</sub> in error. Similarly, the inner code can reliably correct an input ''y''<sub>''i''</sub> if less than ''d''/2 inner symbols are erroneous. Thus, for an outer symbol ''y''<nowiki>'</nowiki><sub>''i''</sub> to be incorrect after inner decoding at least ''d''/2 inner symbols must have been in error, and for the outer code to fail this must have happened for at least ''D''/2 outer symbols. 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. |
|||
1. '''''The decoding algorithm above can correct < <math>Dd \over 4</math> many errors.''''' |
|||
The algorithm also works if the inner codes are different, e.g., for [[Justesen code]]s. The [[generalized minimum distance decoding|generalized minimum distance algorithm]], developed by Forney, can be used to correct up to ''dD''/2 errors.<ref name="gmd"> |
|||
'''''PROOF:''''' |
|||
{{cite journal |
|||
|first=G. David |
|||
We prove the above theorem using the concept of <math>\textit{Bad Event}</math> which is defined as follows: |
|||
|last=Forney |
|||
Consider a bad event has occurred (at position <math>1</math> < <math> i </math> < <math>N</math>) if <math>MLD_{C_i}(y_i) \ne C_{out} (m)_I</math> where <math>m</math> was the original message and |
|||
|title=Generalized Minimum Distance Decoding |
|||
|journal=IEEE Transactions on Information Theory |
|||
<math> \Delta (C_{out} \circ C_{in} (m), y)</math> < <math>Dd \over 4</math> |
|||
|volume=12 |
|||
|issue=2 |
|||
We also know that if the number of bad events is less than <math>D \over 2</math>, then the decoder in Step 2 will output <math>m</math>. |
|||
|pages=125–131 |
|||
|date=April 1966 |
|||
Thus our goal is to find out when a bad event happens to complete the proof. |
|||
|doi=10.1109/TIT.1966.1053873 |
|||
}}</ref> |
|||
Also a bad event cannot happen at position <math>i</math>if |
|||
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 |
|||
|first1=Christopher C.H. |
|||
<math>\Delta(y_i,C_{out} (m)_i)</math> < <math>d \over 2</math> |
|||
|last1=Yu |
|||
|first2=Daniel J. |
|||
Now if the number of bad events is at least <math>D \over 2</math>, then the total number of errors is at least <math>D \over 2 \cdot</math> <math>d \over 2</math> = <math>Dd \over 4</math>, which is a contradiction. Thus, the number of bad events is strictly less than <math>D \over 2</math>. |
|||
|last2=Costello |
|||
|title=Generalized Minimum Distance Decoding for ''Q''ary Output Channels |
|||
|journal=IEEE Transactions on Information Theory |
|||
2. '''''The algorithm also works if the inner codes are different, e.g. [[Justesen code]]s.''''' |
|||
|volume=26 |
|||
|issue=2 |
|||
Also the [[generalized minimum distance decoding|Generalized Minimum Distance algorithm]] can correct up to <math>Dd \over 2</math> errors. |
|||
|pages=238–243 |
|||
|date=March 1980 |
|||
|doi=10.1109/TIT.1980.1056148 |
|||
}}</ref><ref>{{cite journal |
|||
|first1=Yingquan |
|||
|last1=Wu |
|||
|first2=Christoforos |
|||
|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 |
|||
|date=January 2007 |
|||
|doi=10.1109/tit.2006.887478 |
|||
|s2cid=8338433 |
|||
}}</ref> |
|||
==Applications== |
==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 [[ |
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"> |
||
{{cite journal |
{{cite journal |
||
|author=J. P. Odenwalder |
|author=J. P. Odenwalder |
||
|title=Optimal decoding of convolutional codes |
|title=Optimal decoding of convolutional codes |
||
|publisher=[[U.C.L.A.]], Systems Science Dept. |
|publisher=[[U.C.L.A.]], Systems Science Dept. (dissertation) |
||
|year=1970 |
|year=1970 |
||
}} |
}} |
||
</ref> |
</ref> |
||
For the outer code, a longer hard-decision block code, frequently [[Reed |
For the outer code, a longer hard-decision block code, frequentlya [[Reed-Solomon code]] with eight-bit symbols, is used.<ref name="Forney"/><ref name="McEliece"> |
||
{{cite journal |
{{cite journal |
||
|author1= |
|author1=Robert J. McEliece |
||
|author-link=Robert McEliece |
|||
|author2=Laif Swanson |
|author2=Laif Swanson |
||
|title= |
|title=Reed–Solomon Codes and the Exploration of the Solar System |
||
|publisher=JPL |
|publisher=JPL |
||
|date=20 |
|date=20 August 1993 |
||
}} |
}} |
||
</ref> |
</ref> |
||
The larger symbol size makes the outer code more robust to [[error burst |
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.<ref name="Forney"/><ref name="McEliece"/> An [[forward error correction#Interleaving|interleaving layer]] is usually added between the two codes to spread error bursts across a wider range.<ref name="McEliece"/> |
||
The combination of an inner Viterbi convolutional code with an outer |
The combination of an inner Viterbi convolutional code with an outer [[Reed–Solomon code]] (known as an RSV code) was first used in ''[[Voyager 2]]'',<ref name="McEliece"/><ref>R. Ludwig, J. Taylor, [http://descanso.jpl.nasa.gov/DPSummary/Descanso4--Voyager_new.pdf Voyager Telecommunications Manual], [[JPL]] DESCANSO ''(Design and Performance Summary Series)'', March 2002.</ref> andit 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.<ref>[http://www.etsi.org/deliver/etsi_en/300400_300499/300421/01.01.02_60/en_300421v010102p.pdf Digital Video Broadcasting (DVB); Framing structure, channel coding and modulation for 11/12 GHz satellite services], [[ETSI]] EN 300 421, V1.1.2, August 1997.</ref> |
||
In a |
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]].<ref>[http://www.etsi.org/deliver/etsi_en/302300_302399/302307/01.02.01_60/en_302307v010201p.pdf Digital Video Broadcasting (DVB); Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other broadband satellite applications (DVB-S2)], [[ETSI]] EN 302 307, V1.2.1, April 2009.</ref> |
||
A simple concatenation scheme is also used on the |
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 == |
== 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 |
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.<ref name="deep-space-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 |
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 twotofive iterations in the "Galileo code" of the [[Galileo (spacecraft)|Galileo space probe]].<ref name="McEliece"/> |
||
==See |
==See also== |
||
*[[Gilbert–Varshamov bound]] |
|||
*[[Justesen code]] |
*[[Justesen code]] |
||
*[[Reed solomon codes]] |
|||
*[[BCH Code]] |
|||
*[[Singleton bound]] |
*[[Singleton bound]] |
||
*[[ |
*[[Zyablov bound]] |
||
== References == |
== References == |
||
{{reflist|33em}} |
|||
{{reflist}} |
|||
== Further reading == |
== 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=[https://archive.org/details/errorcontrolcodi00lins_044/page/n296 278]–280}} |
|||
* {{cite book | author= |
* {{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] }} |
||
* {{cite book | author=F.J. MacWilliams | authorlink=Jessie MacWilliams | coauthors=N.J.A. Sloane | title=The Theory of Error-Correcting Codes | publisher=North-Holland | year=1977 | isbn=0-444-85193-3 | pages=307–316 }} |
|||
== External links == |
== External links == |
||
* {{scholarpedia|title=Concatenated codes|urlname=Concatenated_codes|curator=[[Dave Forney]]}} |
* {{scholarpedia|title=Concatenated codes|urlname=Concatenated_codes|curator=[[Dave Forney]]}} |
||
* [http://www.cse.buffalo.edu/~atri/courses/coding-theory/fall07.html University at Buffalo Lecture Notes on Coding Theory – Dr. Atri Rudra] |
* [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}} |
{{CCSDS|state=collapsed}} |
Incoding theory, concatenated codes form a class of error-correcting codes 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 complexity.[1] Concatenated codes became widely used in space communications in the 1970s.
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.
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 less than a certain threshold , 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 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 , so such an optimum decoder rapidly becomes infeasible.
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.
Let Cin be a [n, k, d] code, that is, a block code of length n, dimension k, minimum Hamming distance d, and rate r = k/n, over an alphabet A:
Let Cout be a [N, K, D] code over an alphabet B with |B| = |A|k symbols:
The inner code Cin 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 Cout. The concatenationofCout (as outer code) with Cin (as inner code), denoted Cout∘Cin, is thus a code of length Nn over the alphabet A:[1]
It maps each input message m = (m1, m2, ..., mK) to a codeword (Cin(m'1), Cin(m'2), ..., Cin(m'N)), where (m'1, m'2, ..., m'N) = Cout(m1, m2, ..., mK).
The key insight in this approach is that if Cin is decoded using a maximum-likelihood approach (thus showing an exponentially decreasing error probability with increasing length), and Cout is a code with length N = 2nr that can be decoded in polynomial time of N, then the concatenated code can be decoded in polynomial time of its combined length n2nr = O(N⋅log(N)) and shows an exponentially decreasing error probability, even if Cin has exponential decoding complexity.[1] This is discussed in more detail in section Decoding concatenated codes.
In a generalization of above concatenation, there are N possible inner codes Cin,i and the i-th symbol in a codeword of Cout is transmitted across the inner channel using the i-th inner code. The Justesen codes are examples of generalized concatenated codes, where the outer code is a Reed–Solomon code.
1. The distance of the concatenated code Cout∘Cin is at least dD, that is, it is a [nN, kK, D'] code with D' ≥ dD.
Proof: Consider two different messages m1 ≠ m2 ∈ BK. Let Δ denote the distance between two codewords. Then
Thus, there are at least D positions in which the sequence of N symbols of the codewords Cout(m1) and Cout(m2) differ. For these positions, denoted i, we have
Consequently, there are at least d⋅D positions in the sequence of n⋅N symbols taken from the alphabet A in which the two codewords differ, and hence
2.IfCout and Cin are linear block codes, then Cout∘Cin 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 Cout and Cin.
A natural concept for a decoding algorithm for concatenated codes is to first decode the inner code and then the outer code. For the algorithm to be practical it must be polynomial-time in the final block length. Consider that there is a polynomial-time unique decoding algorithm for the outer code. Now we have to find a polynomial-time decoding algorithm for the inner code. It is understood that polynomial running time here means that running time is polynomial in the final block length. The main idea is that if the inner block length is selected to be logarithmic in the size of the outer code then the decoding algorithm for the inner code may run in exponential time of the inner block length, and we can thus use an exponential-time but optimal maximum likelihood decoder (MLD) for the inner code.
In detail, let the input to the decoder be the vector y = (y1, ..., yN) ∈ (An)N. Then the decoding algorithm is a two-step process:
Now, the time complexity of the first step is O(N⋅exp(n)), where n = O(log(N)) is the inner 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.
The decoding algorithm described above can be used to correct all errors up to less than dD/4 in number. Using minimum distance decoding, the outer decoder can correct all inputs y' with less than D/2 symbols y'i in error. Similarly, the inner code can reliably correct an input yi if less than d/2 inner symbols are erroneous. Thus, for an outer symbol y'i to be incorrect after inner decoding at least d/2 inner symbols must have been in error, and for the outer code to fail this must have happened for at least D/2 outer symbols. 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 algorithm also works if the inner codes are different, e.g., for Justesen codes. The generalized minimum distance algorithm, developed by Forney, can be used to correct up to dD/2 errors.[2] It uses 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.[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.[6] 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.[5][6]
Typically, the inner code is not a block code but a soft-decision convolutional Viterbi-decoded code with a short constraint length.[7] For the outer code, a longer hard-decision block code, frequently a Reed-Solomon code with eight-bit symbols, is used.[1][5] The larger symbol size makes the outer code more robust to error bursts that can occur due to channel impairments, and also because erroneous output of the convolutional code itself is bursty.[1][5]Aninterleaving layer is usually added between the two codes to spread error bursts across a wider range.[5]
The combination of an inner Viterbi convolutional code with an outer Reed–Solomon code (known as an RSV code) was first used in Voyager 2,[5][8] and it became a popular construction both within and outside of the space sector. It is still notably used today for satellite communications, such as the DVB-S digital television broadcast standard.[9]
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.[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.
The description above is given for what is now called a serially concatenated code. Turbo codes, 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.[6] 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 space probe.[5]
{{cite journal}}
: Cite journal requires |journal=
(help)
{{cite journal}}
: Cite journal requires |journal=
(help)
{{cite journal}}
: Cite journal requires |journal=
(help)
| |
---|---|
Data compression |
|
Error Correction |
|
Telemetry command uplink |
|
Telemetry downlink |
|
Telemetry general |
|
Telemetry modulation systems |
|
Frequencies |
|
Networking, interoperability and monitoring |
|