Generalized minimum-distance decoding: Difference between revisions

Revision as of 21:09, 29 March 2013

Revision as of 03:22, 26 October 2013

Line 23:

'''Theorem 1.''' ''Let y be a received word such that there exists a [[codeword]]'' <math>\mathbf{c} = (c_1,\ldots, c_N) \in C_\text{out}\circ{C_\text{in}} \subseteq [q^n]^N</math> ''such that'' <math>\Delta(\mathbf{c}, \mathbf{y}) < \frac{Dd}{2}</math>. ''Then the deterministic GMD algorithm outputs'' <math>\mathbf{c}</math>.

Note that a [[Concatenated_codesConcatenated codes|naive decoding algorithm for concatenated codes]] can correct up to <math>Dd \over 4</math> errors.

'''Lemma 1.''' ''Let the assumption in Theorem 1 hold. And if'' <math>\mathbf{y^{\prime\prime}}</math> ''has'' <math>e'</math> ''errors and'' <math>s'</math> ''erasures(when compared with'' <math>\mathbf{c}</math>'') after'' '''Step 1''', ''then'' <math>\mathbb{E}[2e' + s'] < D</math>.

Line 33:

<math>\sum_{i=1}^N e_i < \frac{Dd}{2} \qquad\qquad (1)</math>

Next for every <math>1 \le i \le N</math>, we define two [[Indicatorindicator variable|indicator variables]]s:

: <math>X{_i^?} = 1</math> iff <math>y_i^{\prime\prime} = ?,</math>

Line 49:

: <math>\mathbb{E}[2X{_i^e + X{_i^?}}] \le {{2e_i} \over d}\qquad\qquad (2)</math>

Clearly, by definition <math>e' = \sum_{i}X{_i^e}</math> and <math>s' = \sum_{i}X{_i^?}</math>. Further, by the [[Linear|linearitylinear]]ity of expectation, we get <math>\mathbb{E}[2e' + s'] \le {2 \over d}\sum_ie_i < D</math>. We consider two cases to prove (2) : <math>i'th</math> block is correctly decoded('''Case 1'''), <math>i'th</math> block is incorrectly decoded('''Case 2''')

'''Case 1:''' <math>(c_i = C_\text{in}(y_i'))</math>

Line 114:

==See also==

#[[Concatenated code|Concatenated codes]]s

#[[Reed Solomon|Reed Solomon error correction]]

#[[Berlekamp–Welch algorithm|Welch Berlekamp algorithm]]