Décodage

Soit $f \in {\ifcase\BoldMath\ensuremath{\mathbb{F}}\or \ensuremath{\pmb{\mathbb{F}}}\fi _2}^{2^m}$, $f={(f_\omega)}_{\omega\in{\ifcase\BoldMath\ensuremath{\mathbb{F}}\or \ensuremath{\pmb{\mathbb{F}}}\fi _2}^m}$. Il faut trouver $u=(u_0,u_1,...,u_m)\in{\ifcase\BoldMath\ensuremath{\mathbb{F}}\or \ensuremath{\pmb{\mathbb{F}}}\fi _2}^{m+1}$ tel que $d(\psi(u),f)$ soit minimale. Posons déjà $\tau=(u_1,...,u_m)$ et

$$g_0(\tau)=\psi( \sum_{i=1}^m u_i X_i),$$

$$g_1(\tau)=\psi(1+\sum_{i=1}^m u_i X_i) \ .$$

En posant $F(\omega)={(-1)}^{f_\omega}$,

$$h_{2^m}(F)(\tau) = \sum_{\omega \in {F_2}^m}{(-1)}^{<\omega,\tau>-f_\omega}$$

est alors la différence entre le nombre de fois où

$$<\omega,\ \tau>-f_\omega=\sum_{i=1}^m \tau_i \omega_i-f_\omega ={g_0(\tau)}_\omega - f_\omega$$

est nul (noté $N_Z$) et le nombre de fois où il est égal à 1 (qui est $d(g_0(\tau),f)$).

On a donc $h_{2^m}(F)(\tau)=N_Z-d(g_0(\tau),f)$, or $N_Z+d(g_0(\tau),f)=2^m$, d'où

$$d(g_0(\tau),f) = \frac{1}{2} (2^m-h_{2^m}(F)(\tau)) \ .$$

De même, on obtient

$$d(g_1(\tau),f) = \frac{1}{2} (2^m+h_{2^m}(F)(\tau)) \ .$$

Il suffit donc de trouver $\tau\in{\ifcase\BoldMath\ensuremath{\mathbb{F}}\or \ensuremath{\pmb{\mathbb{F}}}\fi _2}^m$ tel que $\big\vert h_{2^m}(F)(\tau)\big\vert$ soit maximal.

Ensuite, si $h_{2^m}(F)(\tau)< 0$, il faut choisir $g_1(\tau)$, c'est-à-dire prendre $u_0=1$. Sinon, $g_0(\tau)$ convient, c'est-à-dire $u_0=0$.