Concatenated error correction code: Difference between revisions

Revision as of 09:32, 26 June 2011

Revision as of 10:22, 26 June 2011

Line 62:

===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 messages with less than ''D''/2 outer symbols in error. Similarly, the inner code can reliably correct an input if less than ''d''/2 inner symbols are erroneous. Thus, for an outer symbol 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 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 decoding algorithm described above can be used to correct all errors less than ''dD''/4.

''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

<math> \Delta (C_{out} \circ C_{in} (m), y)</math> < <math>Dd \over 4</math>

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

Thus our goal is to find out when a bad event happens to complete the proof.

Also a bad event cannot happen at position <math>i</math> if

<math>\Delta(y_i,C_{out} (m)_i)</math> < <math>d \over 2</math>

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.