Generalized minimum-distance decoding: Difference between revisions

Revision as of 16:23, 9 November 2020

Revision as of 15:41, 13 May 2023

Line 89:

For the proof of '''[[Lemma (mathematics)|Lemma 1]]''', we only use the randomness to show that

: <math display="block">\Pr[y_i'' = ?] = {2\omega_i \over d}.</math>

In this version of the GMD algorithm, we note that

: <math display="block">\Pr[y_i'' = ?] = \Pr \left [\theta \in \left [0, \tfrac{2\omega_i}{d} \right ] \right ] = \tfrac{2\omega_i}{d}.</math>

The second [[Equality (mathematics)|equality]] above follows from the choice of <math>\theta</math>. The proof of '''Lemma 1''' can be also used to show <math>\mathbb{E}[2e' + s'] < D</math> for version2 of GMD. In the next section, we will see how to get a deterministic version of the GMD algorithm by choosing <math>\theta</math> from a polynomially sized set as opposed to the current infinite set <math>[0, 1]</math>.