Code de Hadamard

Lorsqu'il reçoit un message binaire ${\displaystyle x\in \{0,1\}^{k}}$ de longueur ${\displaystyle k}$, le code de Hadamard encode le message en un mot de code ${\displaystyle C_{\text{Had}}(x)}$ à l'aide d'une fonction d'encodage ${\displaystyle {\text{Had}}:\{0,1\}^{k}\to \{0,1\}^{2^{k}}.}$ Cette fonction utilise le produit scalaire ${\displaystyle \langle x,y\rangle }$ de deux vecteurs ${\displaystyle x,y\in \{0,1\}^{k}}$, qui est défini comme suit:

${\displaystyle \langle x,y\rangle =\sum _{i=1}^{k}x_{i}y_{i}\ {\bmod {\ }}2\,.}$

Ensuite, l'encodage Hadamard de ${\displaystyle x}$ est défini comme la séquence de produits scalaires tous avec ${\displaystyle x}$ :

${\displaystyle C_{\text{Had}}(x)={\Big (}\langle x,y\rangle {\Big )}_{y\in \{0,1\}^{k}}}$

Le code de Hadamard est un code linéaire, et tous les codes linéaires peuvent être générés par une matrice de générateur ${\displaystyle G}$. Cette matrice est telle que ${\displaystyle C_{\text{Had}}(x)=x\cdot G}$ est valable pour tous les ${\displaystyle x\in \{0,1\}^{k}}$, où le message ${\displaystyle x}$ est vu comme un vecteur ligne et le produit vecteur-matrice est compris dans le espace vectoriel sur le champ fini. ${\displaystyle \mathbb {F} _{2}}$. En particulier, une manière équivalente d'écrire la définition interne du produit pour le code de Hadamard consiste à utiliser la matrice du générateur dont les colonnes sont constituées de chaînes de caractères " toutes " ${\displaystyle y}$ de longueur ${\displaystyle k}$, c'est-à-dire,

${\displaystyle G={\begin{pmatrix}\uparrow &\uparrow &&\uparrow \\y_{1}&y_{2}&\dots &y_{2^{k}}\\\downarrow &\downarrow &&\downarrow \end{pmatrix}}\,}$

où ${\displaystyle y_{i}\in \{0,1\}^{k}}$ est le ${\displaystyle i}$-ième vecteur binaire dans ordre lexicographique. Par exemple, la matrice génératrice pour le code de Hadamard de dimension ${\displaystyle k=3}$ est:

${\displaystyle G={\begin{bmatrix}0&0&0&0&1&1&1&1\\0&0&1&1&0&0&1&1\\0&1&0&1&0&1&0&1\end{bmatrix}}}$

La matrice ${\displaystyle G}$ est une matrice ${\displaystyle (k\times 2^{k})}$ et donne lieu à l'opérateur linéaire ${\displaystyle {\text{Had}}:\{0,1\}^{k}\to \{0,1\}^{2^{k}}}$.

Une autre façon de définir le code de Hadamard est en termes de matrice de contrôle de parité : la matrice de contrôle de parité du code de Hadamard est égale à la matrice de génération du code de Hamming.

Les codes Hadamard généralisés sont obtenus à partir d'un ${\displaystyle {\text{n}}\times {\text{n}}}$ matrice de Hadamard ${\displaystyle {\text{H}}}$. En particulier, les mots de code ${\displaystyle 2n}$ du code sont les lignes de ${\displaystyle {\text{H}}}$ et les lignes de ${\displaystyle {\text{-H}}}$. Pour obtenir un code sur l'alphabet ${\displaystyle \{0,1\}}$, le mapping ${\displaystyle {\text{-1}}\rightarrow 1}$, ${\displaystyle 1\rightarrow 0}$, ou, de manière équivalente, ${\displaystyle x\rightarrow (1-x)/2}$, est appliqué aux éléments de la matrice. Le fait que la distance minimale du code soit ${\displaystyle n/2}$ découle de la propriété de définition des matrices de Hadamard, à savoir que leurs lignes sont mutuellement orthogonales. Cela implique que deux lignes distinctes d'une matrice Hadamard diffèrent exactement par leurs positions ${\displaystyle n/2}$, et, comme la négation d'une ligne n'affecte pas l'orthogonalité, que toute ligne de ${\displaystyle {\text{H}}}$ diffère de toute ligne de ${\displaystyle {\text{-H}}}$ par ses positions ${\displaystyle n/2}$ également, sauf lorsque les lignes correspondent, auquel cas elles diffèrent par leurs positions ${\displaystyle n}$.

1. Choisissez ${\displaystyle u\in \mathbb {F} _{2}^{k}}$ uniformément au hasard
2. Requête ${\displaystyle y}$ à la position marquée par ${\displaystyle u}$ et ${\displaystyle u+e_{i}}$
3. Sortie ${\displaystyle \langle y,u\rangle +\langle y,u+e_{i}\rangle }$

Une fois reçue la sortie de l'algorithme ci-dessus, nous pouvons obtenir :

S'il n'y a pas d'erreur aux positions ${\displaystyle u}$ et ${\displaystyle u+e_{i}}$, alors il est possible de récupérer le ${\displaystyle ieme}$ bit de ${\displaystyle x}$. Puisque ${\displaystyle \Delta (C_{Had}(x),y)\leq {\tfrac {2^{r}}{10}}}$, la probabilité d'erreur à une seule position est ${\displaystyle \leq {\tfrac {1}{10}}}$. Par l'Inégalité de Boole, la probabilité d'obtenir une erreur à ${\displaystyle u}$ et ${\displaystyle u+e_{i}}$ n'est pas supérieure à la somme des probabilités des deux événements, dans ce cas particulier étant ${\displaystyle {\tfrac {1}{5}}}$. Au total, la probabilité de déterminer le ${\displaystyle ieme}$ bit par ${\displaystyle x_{i}}$ du message ${\displaystyle x}$ est supérieure au complément d'obtention d'une erreur, c'est-à-dire ${\displaystyle \geq 1-{\tfrac {1}{5}}={\tfrac {4}{5}}}$.