Code de Hadamard

Le code de Hadamard est un code correcteur, nommé d'après Jacques Hadamard, à taux de transfert extrêmement faible mais à grande distance, couramment utilisé pour la détection et la correction d'erreurs lors de la transmission de messages sur des canaux très bruyants ou peu fiables.

Dans la notation standard de la théorie du codage pour les codes en bloc, le code de Hadamard est un code ${\displaystyle [2^{k},k,2^{k-1}]_{2}}$, c'est-à-dire un code linéaire sur un alphabet binaire, a une longueur de bloc de ${\displaystyle 2^{k}}$, la longueur (ou la dimension) du message ${\displaystyle k}$, et une distance minimale ${\displaystyle 2^{k}/2}$. Bien que la longueur du bloc soit très grande par rapport à la longueur du message, les erreurs peuvent être corrigées même dans des conditions extrêmement bruyantes.

Ce code étant localement déchiffrable, c'est-à-dire qu'il est possible de récupérer des parties du message original avec une forte probabilité, tout en ne disposant que d'une petite fraction du message reçu, il possède de nombreuses applications dans la théorie de la complexité des calculs et en particulier dans la conception de preuves vérifiables par probabilité. De plus, comme la distance relative du code de Hadamard est de 1/2, il est en théorie possible de récupérer des messages avec au maximum 1/4 de bits erronés. Cependant, en utilisant le décodage par liste, il est possible de calculer une courte liste de messages candidats possibles tant que moins de ${\displaystyle {\tfrac {1}{2}}-\epsilon }$ des bits du message reçu ont été corrompus.

Grâce à ses propriétés mathématiques uniques, les codes Hadamard sont intensément étudiés dans des domaines tels que la théorie du codage, les mathématiques et l'informatique théorique, outre ses applications dans de nombreuses technologies et industries.

Histoire

Bien que Jacques Hadamard n'ait pas inventé le code lui-même, il a défini la matrice de Hadamard vers 1893, bien avant que le premier code correcteur, le code de Hamming, ne soit développé dans les années 1940.

Le code de Hadamard est basé sur des matrices de Hadamard, et bien qu'il y ait beaucoup de matrices de Hadamard différentes qui pourraient être utilisées, normalement seulement la construction de Sylvester des matrices de Hadamard est utilisée pour obtenir les mots de code du code de Hadamard.

James Joseph Sylvester a développé sa construction, similaire aux matrices d'Hadamard, en 1867, ce qui est de fait antérieur aux travaux d'Hadamard sur les matrices d'Hadamard. Le nom de code de Hadamard est donc contesté et parfois le code est appelé code Walsh, en l'honneur du mathématicien américain Joseph Leonard Walsh.

Constructions

Normalement, les codes Hadamard sont basés sur la construction de matrices Hadamard par Sylvester, mais le terme " code de Hadamard " est également utilisé pour désigner les codes construits à partir de matrices Hadamard arbitraires, qui ne sont pas nécessairement de type Sylvester. Le lien entre les matrices Hadamard et la théorie de la construction du code a été trouvé pour la première fois par R. C. Bose et S. S. Shrikhande en 1959^[1].

Si ${\displaystyle n}$ est la taille de la matrice Hadamard, le code a les paramètres ${\displaystyle (n,log(n),n/2)_{2}}$, ce qui signifie que c'est un code binaire pas nécessairement linéaire avec des mots de code ${\displaystyle log(n)}$ de longueur de bloc ${\displaystyle n}$ et de distance minimale ${\displaystyle n/2}$.

Les constructions et schémas de décodage décrits ci-dessous s'appliquent pour le ${\displaystyle n}$ général, mais la propriété de linéarité et l'identification avec les codes Reed-Muller exigent que ${\displaystyle n}$ soit une puissance de 2 et que la matrice Hadamard soit équivalente à la matrice construite par la méthode

Construction utilisant des produits scalaires

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}}}$

Construction utilisant une matrice de générateur

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.

Construction utilisant des matrices Hadamard générales

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}$.

Distance

La distance d'un code est le minimum distance de Hamming entre deux mots de code distincts, c'est-à-dire le nombre minimum de positions auxquelles deux mots de code distincts diffèrent. Comme le code de Hadamard est un code linéaire, la distance est égale au minimum poids de Hamming entre tous ses mots-codes non nuls.

Dans les lignes qui suivent, nous allons demonstrer que ${\displaystyle C_{\text{Had, r}}}$ a un poids égal à ${\displaystyle 2^{r-1}}$. Considérons un message ${\displaystyle x\neq 0}$. Soit sa ième entrée ${\displaystyle x_{i}=1.x}$ est codé comme ${\displaystyle c=(x_{1},x_{2},...,x_{r})(H_{r}^{0},H_{r}^{1},....H_{r}^{2^{r}-1})}$, où ${\displaystyle H_{r}^{j}}$ est la représentation binaire de ${\displaystyle 0\leq j\leq 2^{r}-1}$, c'est-à-dire qu'il contient tous les vecteurs de ${\displaystyle \{0,1\}^{2}}$. Notez également que le ${\displaystyle j}$-ième bit des mots de code c est ${\displaystyle \langle x,H_{r}^{j}\rangle }$. Regrouper toutes les colonnes de la matrice du générateur en paires ${\displaystyle (u,v)}$ de sorte que ${\displaystyle v=u+e_{i}}$ (c'est-à-dire que v et u sont les mêmes sauf en position ième). Notez que cela partitionne toutes les colonnes en paires disjointes ${\displaystyle 2^{r-1}}$. Ensuite,

${\displaystyle \langle x,v\rangle =\langle x,u+e_{i}\rangle =\langle x,u\rangle +\langle x,e_{i}\rangle =\langle x,u\rangle +x_{i}=\langle x,u\rangle +1}$

Ainsi, nous avons exactement celui de ${\displaystyle \langle x,v\rangle }$ et ${\displaystyle \langle x,u\rangle }$ est 1. Comme le choix de la paire ${\displaystyle (u,v)}$ était arbitraire, nous avons prouvé que pour tout mot de code c non nul tel que ${\displaystyle c\in C_{\text{Had}},wt(c)=2^{r-1}}$.

Localement déchiffrable

Un code localement déchiffrable est un code qui permet de récupérer un seul bit du message original avec une forte probabilité en ne regardant qu'une petite partie du mot reçu. Plus formellement, le problème de déchiffrement local peut être décrit comme :

Déchiffrement local : Soit ${\displaystyle C\subseteq \{0,1\}^{n}}$ un code et la carte de codage soit ${\displaystyle E:{0,1}^{k}\rightarrow C}$. Étant donné ${\displaystyle r\in {0,1}^{n}}$ et ${\displaystyle i\in [k]}$ tel que ${\displaystyle \triangle (r,E(m))<\rho }$ pour quelques ${\displaystyle m\in {0,1}^{k}}$. Trouve ${\displaystyle m_{i}}$.

Une question naturelle à se poser serait si on doit le faire tourner pendant le temps ${\displaystyle \Omega (k)}$ ? Et la réponse à cette question est non. Pour pouvoir répondre à cette question, nous allons mesurer la complexité d'un algorithme de déchiffrement basé sur le nombre d'emplacements interrogés par l'algorithme à partir du mot entré/reçu.

Selon le modèle d'accès aléatoire, c'est-à-dire que l'accès à un emplacement donné dans un mot reçu est compté comme une opération. Nous définirons une classe de codes décodables basée sur le nombre d'emplacements auxquels un algorithme doit accéder afin de récupérer un emplacement donné d'un message et une fraction des erreurs qu'il peut tolérer.

Définition ((${\displaystyle t,\epsilon }$)-code déchiffrement localement). ${\displaystyle C\subset \textstyle \sum ^{n}}$, avec une carte de codage ${\displaystyle E:\textstyle \sum ^{k}\rightarrow \textstyle \sum ^{n}}$, est (t,${\displaystyle \epsilon }$)-code localement déchiffrable s'il existe un algorithme ${\displaystyle A}$ tel que pour tous les messages ${\displaystyle x\in \textstyle \sum ^{k}}$, ${\displaystyle r\in \textstyle \sum ^{n}}$ et ${\displaystyle i\in [k]}$ tel que ${\displaystyle \triangle (r,E(x))\leq -\epsilon }$,

${\displaystyle Pr[A(i,r)\neq x_{i}]\leq 0.1}$

et ${\displaystyle A}$ accède au maximum aux coordonnées de ${\displaystyle t}$ à partir de ${\displaystyle r}$.

Algorithme

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 }$

Analyse

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

${\displaystyle =\langle y,u\rangle +\langle y,u+e_{i}\rangle }$ mod ${\displaystyle 2}$

${\displaystyle =\langle y,u\rangle +\langle y,u\rangle +\langle y,e_{i}\rangle }$ mod ${\displaystyle 2}$

${\displaystyle =\langle y,e_{i}\rangle }$ mod ${\displaystyle 2}$

${\displaystyle =y_{i}}$

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}}}$.

Optimalité

Pour ${\displaystyle k\leq 7}$ les codes Hadamard linéaires se sont avérés optimaux dans le sens de la distance minimale^[2].

Applications réelles

Le 14 novembre 1971, le vaisseau spatial Mariner 9 est entré en orbite autour de Mars et a commencé à prendre des photos. Un code de Hadamard amélioré a été utilisé pendant la mission pour corriger les erreurs de transmission des images. Les mots de données utilisés au cours de cette mission étaient de 6 bits, ce qui représentait 64 valeurs de niveaux de gris. En raison des limites de la qualité de l'alignement de l'émetteur à ce moment-là (à cause des problèmes de la boucle de poursuite du Doppler), la longueur maximale des données utiles était d'environ 30 bits. Au lieu d'utiliser un code de répétition, une code de Hadamard ${\displaystyle [32,6,16]}$ a été utilisé.

Notes et références

Liens externes

• Essential Coding Theory par Guruswami V., Rudra A. et Sudan M., 2019
• Algorithmic Introduction to Coding Theory (Lecture 14) par Sudan M., 2002
• List decoding of binary codes par Guruswami V., 2009
• Folded RS Codes, Local Decoding par Kopparty S., 2016

Bibliographie

• (en) Amadei M., Manzoli U. et Merani, M.L. On the assignment of Walsh and quasi-orthogonal codes in a multicarrier DS-CDMA system with multiple classes of users, IEEE, 2002, (ISBN 0-7803-7632-3)
• (en) Arora S. et Barak B., Computational Complexity: A Modern Approach, Cambridge University Press, 2009, (ISBN 9780521424264)

• Portail des télécommunications
• Portail de l'informatique théorique