|
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>.
==Decoding Concatenatedconcatenated Codescodes==
A natural concept for a decoding algorithm for concatenated codes is that the codeto first decodesdecode the inner code and then decodes 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 codescode. It is understood that polynomial running time here means that running time is polynomial in the final block length. The main idea is tothat pickif athe decodinginner algorithmblock thatlength runsis inselected timeto singlybe exponentiallogarithmic in the innersize blockof lengththe asouter longcode asthen the innerdecoding blockalgorithm length is logarithmic infor the outerinner code blockmay length.run However,in we[[exponential havetime]] assumed thatof the inner block length is logarithmic in the outer code, and thus, we can thus use thean exponential-time but optimal [[Decoding_methods#Maximum_likelihood_decoding|Maximummaximum Likelihoodlikelihood Decoderdecoder]] (or MLD) for the inner code.
LetIn detail, let the input to the decoder be the vector <math>''y'' = (y_1''y''<sub>1</sub>, . .., y_N''y''<sub>''N''</sub>) \in∈ [q^(''A''<sup>''n]^''</sup>)<sup>''N''</mathsup>. TheThen the decoding algorithm is a two -step process:
# 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''.
2. # Run the unique decoding algorithm for ''C''< mathsub> C_{out }</ mathsub> on ''y''< mathnowiki> y'</ mathnowiki>. ▼
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.
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===
1. '''''The decoding algorithm described above can correct <up <math>Ddto \overless 4</math>than many errors.'''dD''/4 errors.
''Proof:'' We prove the above theorem using the concept of <math>\textit{Bad Event}</math> which is defined as follows: ▼
'''''PROOF:'''''
▲We prove the above theorem using the concept of <math>\textit{Bad Event}</math> which is defined as follows:
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
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>.
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]] can be used to correct up to ''dD''/2 errors.
2. '''''The algorithm also works if the inner codes are different, e.g. [[Justesen code]]s.'''''
Also the [[generalized minimum distance decoding|Generalized Minimum Distance algorithm]] can correct up to <math>Dd \over 2</math> errors.
==Applications==
| 