Generalized minimum-distance decoding: Difference between revisions

Revision as of 03:20, 10 May 2011

Revision as of 03:21, 10 May 2011

Line 21:

# Run errors and erasure algorithm for <math>C_\text{out}</math> on <math>\mathbf{y}^{\prime\prime} = (y_1^{\prime\prime}, \ldots, y_N^{\prime\prime})</math>.

'''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})</math> < <math>Dd \over 2</math>. ''Then the deterministic GMD algorithm outputs'' <math>\mathbf{c}</math>.

Note that a [[Concatenated_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']</math> < <math>D</math>.

If <math>2e' + s'</math> < <math>D</math>, then the algorithm in '''Step 2''' will output <math>\mathbf{c}</math>. The lemma above says that in expectation, this is indeed the case. Note that this is not enough to prove '''Theorem 1''', but can be crucial in developing future variations of the algorithm.

'''Proof of lemma 1.''' For every <math>1 \le i \le N</math>, define <math>e_i = \Delta(y_i, c_i)</math>. This implies that

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>. Futher, by the [http://en.wikipedia.org/wiki/Linear linearity] of expectation, we get <math>\mathbb{E}[2e' + s'] \le {2 \over d}\sum_ie_i</math> < <math>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>