Code Hadamard

Le code Hadamard est un code correcteur d'erreurs nommé d'après le mathématicien français Jacques Hadamard qui est 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. En 1971, le code a été utilisé pour transmettre des photos de Mars vers la Terre depuis la sonde spatiale Mariner 9 de la NASA . En raison de ses propriétés mathématiques uniques, le code Hadamard est non seulement utilisé par les ingénieurs, mais également intensément étudié en théorie du codage , en mathématiques et en informatique théorique . Le code Hadamard est également connu sous les noms de code Walsh , famille Walsh , et code Walsh-Hadamard en hommage au mathématicien américain Joseph Leonard Walsh .

Le code Hadamard est un exemple de code linéaire de longueur sur un alphabet binaire . Malheureusement, ce terme est quelque peu ambigu car certaines références supposent une longueur de message tandis que d'autres supposent une longueur de message de . Dans cet article, le premier cas est appelé code Hadamard tandis que le second est appelé code Hadamard augmenté .

Le code Hadamard est unique en ce sens que chaque mot de code non nul a un poids de Hamming exactement égal à , ce qui implique que la distance du code est également égale à . Dans la notation théorique standard du codage pour les codes de blocs , le code Hadamard est un Δcode, c'est-à-dire qu'il s'agit d'un code linéaire sur un alphabet binaire , qui a une longueur de bloc , une longueur de message (ou dimension) , et une distance minimale . La longueur du bloc est très grande par rapport à la longueur du message, mais d'un autre côté, les erreurs peuvent être corrigées même dans des conditions extrêmement bruyantes.

Le code Hadamard augmenté est une version légèrement améliorée du code Hadamard ; il s'agit d'un code Δ et a donc un débit légèrement meilleur tout en maintenant la distance relative de , et est donc préféré dans les applications pratiques. Dans la théorie des communications, on l'appelle simplement le code Hadamard et il est identique au code Reed-Muller du premier ordre sur l'alphabet binaire.

Normalement, les codes Hadamard sont basés sur la construction de matrices Hadamard par Sylvester , mais le terme « code Hadamard » est également utilisé pour désigner des codes construits à partir de matrices Hadamard arbitraires , qui ne sont pas nécessairement de type Sylvester. En général, un tel code n'est pas linéaire. De tels codes ont été construits pour la première fois par Raj Chandra Bose et Sharadchandra Shankar Shrikhande en 1959. Si n est la taille de la matrice Hadamard, le code a des paramètres , ce qui signifie qu'il s'agit d'un code binaire pas nécessairement linéaire avec 2 n mots de code de longueur de bloc n et de distance minimale n /2. Le schéma de construction et de décodage décrit ci-dessous s'applique à n général , mais la propriété de linéarité et l'identification avec les codes de Reed-Muller nécessitent que n soit une puissance de 2 et que la matrice Hadamard soit équivalente à la matrice construite par la méthode de Sylvester.

Le code Hadamard est un code localement décodable , qui permet de récupérer des parties du message d'origine avec une forte probabilité, tout en ne considérant qu'une petite fraction du mot reçu. Cela donne lieu à des applications en théorie de la complexité computationnelle et en particulier dans la conception de preuves vérifiables de manière probabiliste . Étant donné que la distance relative du code Hadamard est de 1/2, on ne peut normalement espérer récupérer qu'à partir d'une fraction d'erreur d'au plus 1/4. En utilisant le décodage de liste , cependant, il est possible de calculer une courte liste de messages candidats possibles tant que moins de des bits du mot reçu ont été corrompus.

Dans les communications à accès multiple par répartition de code (CDMA), le code Hadamard est appelé code Walsh et est utilisé pour définir des canaux de communication individuels . Dans la littérature CDMA, il est courant de désigner les mots de code par le terme « codes ». Chaque utilisateur utilisera un mot de code différent, ou « code », pour moduler son signal. Étant donné que les mots de code Walsh sont mathématiquement orthogonaux , un signal codé en Walsh apparaît comme un bruit aléatoire pour un terminal mobile compatible CDMA , à moins que ce terminal n'utilise le même mot de code que celui utilisé pour coder le signal entrant .

Le code Hadamard est le nom le plus couramment utilisé pour ce code dans la littérature. Cependant, dans l'usage moderne, ces codes correcteurs d'erreurs sont appelés codes Walsh-Hadamard.

Il y a une raison à cela :

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

Le code Hadamard est basé sur les matrices Hadamard, et bien qu'il existe de nombreuses matrices Hadamard différentes qui pourraient être utilisées ici, normalement seule la construction de matrices Hadamard de Sylvester est utilisée pour obtenir les mots de code du code Hadamard.

James Joseph Sylvester a développé sa construction des matrices de Hadamard en 1867, ce qui est en réalité antérieur aux travaux de Hadamard sur les matrices de Hadamard. Le nom de code de Hadamard est donc controversé et le code est parfois appelé code de Walsh , en hommage au mathématicien américain Joseph Leonard Walsh .

Un code Hadamard augmenté a été utilisé lors de la mission Mariner 9 de 1971 pour corriger les erreurs de transmission d'images. Les valeurs binaires utilisées lors de cette mission étaient longues de 6 bits, ce qui représentait 64 valeurs de niveaux de gris .

En raison des limitations de la qualité de l'alignement de l'émetteur à l'époque (en raison de problèmes de boucle de suivi Doppler), la longueur maximale des données utiles était d'environ 30 bits. Au lieu d'utiliser un code de répétition , un code Hadamard [32, 6, 16] a été utilisé.

Des erreurs allant jusqu'à 7 bits par mot de 32 bits pourraient être corrigées à l'aide de ce schéma. Comparé à un code à 5 répétitions , les propriétés de correction d'erreur de ce code Hadamard sont bien meilleures, mais son taux est comparable. L'algorithme de décodage efficace a été un facteur important dans la décision d'utiliser ce code.

Le circuit utilisé a été appelé « Green Machine ». Il utilise la transformée de Fourier rapide qui peut augmenter la vitesse de décodage d'un facteur trois. Depuis les années 1990, l'utilisation de ce code par les programmes spatiaux a plus ou moins cessé, et le réseau spatial profond de la NASA ne prend pas en charge ce système de correction d'erreur pour ses antennes paraboliques de plus de 26 m.

Bien que tous les codes Hadamard soient basés sur des matrices Hadamard, les constructions diffèrent de manière subtile selon les domaines scientifiques, les auteurs et les utilisations. Les ingénieurs, qui utilisent les codes pour la transmission de données, et les théoriciens du codage , qui analysent les propriétés extrêmes des codes, souhaitent généralement que le débit du code soit le plus élevé possible, même si cela signifie que la construction devient mathématiquement légèrement moins élégante.

D'autre part, pour de nombreuses applications des codes Hadamard en informatique théorique, il n'est pas si important d'atteindre le taux optimal, et par conséquent des constructions plus simples de codes Hadamard sont préférées car elles peuvent être analysées de manière plus élégante.

Lorsqu'on lui donne un message binaire de longueur , le code Hadamard encode le message en un mot de code à l'aide d'une fonction d'encodage. Cette fonction utilise le produit scalaire de deux vecteurs , qui est défini comme suit :

Ensuite, le codage Hadamard de est défini comme la séquence de tous les produits scalaires avec :

Comme mentionné ci-dessus, le code Hadamard augmenté est utilisé dans la pratique car le code Hadamard lui-même est quelque peu gaspilleur. En effet, si le premier bit de est nul, , alors le produit interne ne contient aucune information sur , et par conséquent, il est impossible de décoder complètement à partir de ces seules positions du mot de code. D'un autre côté, lorsque le mot de code est restreint aux positions où , il est toujours possible de décoder complètement . Il est donc logique de restreindre le code Hadamard à ces positions, ce qui donne lieu au codage Hadamard augmenté de ; c'est-à-dire .

Le code Hadamard est un code linéaire, et tous les codes linéaires peuvent être générés par une matrice génératrice . Il s'agit d'une matrice telle que valable pour tout , où le message est considéré comme un vecteur de lignes et le produit vecteur-matrice est compris dans l' espace vectoriel sur le corps fini . En particulier, une manière équivalente d'écrire la définition du produit scalaire pour le code Hadamard est obtenue en utilisant la matrice génératrice dont les colonnes sont constituées de toutes les chaînes de longueur , c'est-à-dire,

où est le -ième vecteur binaire dans l'ordre lexicographique . Par exemple, la matrice génératrice pour le code Hadamard de dimension est :

La matrice est une α-matrice et donne lieu à l' opérateur linéaire .

La matrice génératrice du code Hadamard augmenté est obtenue en limitant la matrice aux colonnes dont la première entrée est un. Par exemple, la matrice génératrice du code Hadamard augmenté de dimension est :

Alors est une application linéaire avec .

En général , la matrice génératrice du code Hadamard augmenté est une matrice de contrôle de parité pour le code de Hamming étendu de longueur et de dimension , ce qui fait du code Hadamard augmenté le code dual du code de Hamming étendu. Une autre façon de définir le code Hadamard est donc de l'utiliser en termes de matrice de contrôle de parité : la matrice de contrôle de parité du code Hadamard est égale à la matrice génératrice du code de Hamming.

Les codes de Hadamard sont obtenus à partir d'une matrice de Hadamard n x n H . En particulier, les 2 n mots de code du code sont les lignes de H et les lignes de − H . Pour obtenir un code sur l'alphabet {0,1}, l'application −1 ↦ 1, 1 ↦ 0, ou, de manière équivalente, x ↦ (1 − x )/2, est appliquée aux éléments de la matrice. Le fait que la distance minimale du code soit n /2 résulte de la propriété définissant les matrices de Hadamard, à savoir que leurs lignes sont mutuellement orthogonales. Cela implique que deux lignes distinctes d'une matrice de Hadamard diffèrent exactement en n /2 positions, et, puisque la négation d'une ligne n'affecte pas l'orthogonalité, que toute ligne de H diffère également de toute ligne de − H en n /2 positions, sauf lorsque les lignes correspondent, auquel cas elles diffèrent en n positions.

Pour obtenir le code Hadamard augmenté ci-dessus avec , la matrice Hadamard H choisie doit être de type Sylvester, ce qui donne lieu à une longueur de message de .

La distance d'un code est la distance de Hamming minimale entre deux mots de code distincts, c'est-à-dire le nombre minimal de positions auxquelles deux mots de code distincts diffèrent. Étant donné que le code de Walsh-Hadamard est un code linéaire , la distance est égale au poids de Hamming minimal parmi tous ses mots de code non nuls. Tous les mots de code non nuls du code de Walsh-Hadamard ont un poids de Hamming de exactement par l'argument suivant.

Soit un message non nul. La valeur suivante est alors exactement égale à la fraction de positions dans le mot de code qui sont égales à un :

Le fait que cette dernière valeur soit exactement est appelé le principe de sous-somme aléatoire . Pour voir qu'il est vrai, supposons sans perte de généralité que . Alors, lorsqu'il est conditionné par les valeurs de , l'événement est équivalent à pour un certain dépendant de et . La probabilité que cela se produise est exactement . Ainsi, en fait, tous les mots de code non nuls du code Hadamard ont un poids de Hamming relatif , et donc, sa distance relative est .

La distance relative du code Hadamard augmenté est la même, mais elle n'a plus la propriété que chaque mot de code non nul a un poids exact puisque le vecteur tout s est un mot de code du code Hadamard augmenté. C'est parce que le vecteur code en . De plus, chaque fois que est non nul et n'est pas le vecteur , le principe de sous-somme aléatoire s'applique à nouveau, et le poids relatif de est exactement .

Un code localement décodable est un code qui permet de récupérer un seul bit du message d'origine avec une forte probabilité en ne regardant qu'une petite partie du mot reçu.

Un code est localement décodable par requête si un bit de message, , peut être récupéré en vérifiant les bits du mot reçu. Plus formellement, un code, , est localement décodable, s'il existe un décodeur probabiliste, , tel que (Remarque : représente la distance de Hamming entre les vecteurs et ) :

Théorème 1 : Le code de Walsh–Hadamard est -localement décodable pour tout .

Lemme 1 : Pour tous les mots de code, dans un code Walsh–Hadamard, , , où représentent les bits en positions et respectivement, et représente le bit en position .

Soit le mot de code correspondant au message .

Soit la matrice génératrice de .

Par définition, . De là, . Par construction de , . Par conséquent, par substitution, .

Pour prouver le théorème 1, nous allons construire un algorithme de décodage et prouver son exactitude.

Entrée : mot reçu

Pour chaque :

1. Choisissez uniformément au hasard.
2. Choisissez tel que , où est le -ième vecteur de base standard et est le xor au niveau du bit de et .

Sortie : Message

Pour tout message, , et un mot reçu tel que différent de sur au plus une fraction de bits, peut être décodé avec une probabilité d'au moins .

Par le lemme 1, . Puisque et sont choisis uniformément, la probabilité que soit au plus . De même, la probabilité que soit au plus . Par la borne d'union , la probabilité que soit ou ne corresponde pas aux bits correspondants dans soit au plus . Si et correspondent tous les deux à , alors le lemme 1 s'appliquera, et donc, la valeur appropriée de sera calculée. Par conséquent, la probabilité est décodée correctement et est au moins . Par conséquent, pour que et soit positif, .

Par conséquent, le code Walsh-Hadamard est décodable localement pour .

Pour k ≤ 7, les codes linéaires Hadamard se sont avérés optimaux dans le sens de la distance minimale.