Code de Reed-Muller

type de codes correcteurs linéaires

Les codes de Reed-Muller sont des codes correcteurs linéaires. Cette famille de codes, initialement binaire, doit son nom aux travaux de David E. Muller qui proposa le principe du code et à Irving S. Reed qui proposa une technique de décodage, publiés en 1954. Depuis, cette famille a été largement étudiée et généralisée aux corps finis de plus de 2 éléments. Historiquement, un code Reed-Muller d'ordre 1 en 5 variables, qui a 64 mots de longueur 32 et corrige 7 erreurs, a été utilisé par les sondes Mariner lancées par la NASA entre 1969 et 1973 pour assurer une transmission (numérique) correcte des photos de Mars.

Matrice du code de Hadamard augmenté [32, 6, 16] pour le code de Reed-Muller (1, 5) de la sonde spatiale Mariner 9 de la NASA

Un code de cette famille est identifié à l'aide de deux paramètres, en général notés et , appelés respectivement ordre et nombre de variables. Ces paramètres interviennent dans la description utilisant les fonctions booléennes : le code binaire de Reed-Muller d'ordre en , que l'on note , est l'ensemble des tables de vérité des fonctions booléennes en variables dont la forme algébrique normale (ANF) est de degré au plus . Lorsque l'alphabet est le corps fini à éléments, il suffit de considérer les fonctions -aires.

Code binaire

modifier

Une construction simple

modifier

On choisit un ordre quelconque sur les éléments de  . Une fonction booléenne   en   variables est alors identifiée au mot binaire défini par

 

En d'autres termes,   est la liste des valeurs prises par   dans un ordre quelconque mais fixe. On peut alors définir

 

  est le degré de l'ANF de  .

Exemple de  

modifier

Dans l'exemple donné en introduction, le code Reed-Muller d'ordre 1 en 5 variables,   vaut donc  

 .

Les fonctions booléennes en 5 variables sont identifiées chacune à un mot binaire de longueur 32

 

L'ensemble des mots du code est

 

Ainsi le code est l'ensemble des tables de vérité des fonctions booléennes affines en 5 variables, la table de vérité de   étant simplement le vecteur  .

Une autre construction

modifier

On décrit comment construire une matrice génératrice d'un code de longueur  . Posons :

 

Dans l'espace   on définit, pour toute partie  , les vecteurs   par

 

On définit également dans   l'opération binaire :

 

appelé produit extérieur.

  est un espace vectoriel à   dimensions sur le corps  , donc on écrit

 

Dans l'espace  , on définit les vecteurs de longueur   suivants :   et

 

  sont des hyperplans dans   (de dimension  ) :

 

Le code de Reed-Muller   d'ordre   et longueur   est le code généré par   et le produit extérieur d'au plus   des   (par convention, s'il y a moins d'un vecteur, le produit extérieur est appliqué comme l'identité).

En fait, derrière cette construction se cache est celle donnée par les fonctions booléennes. En effet, si   est une fonction booléenne en   variables, on a

  en posant  

  est le vecteur défini à la section Code binaire. Il est alors facile de vérifier que

 

Pour terminer, il suffit de remarquer que  , où   est la ième forme coordonnée, i.e :

 

Le vecteur   est donc égal à  . La famille des produits extérieurs d'au plus   vecteurs  , est donc constituée des vecteurs de la forme

  avec  .

Bien entendu, les   sont des fonctions booléennes en   variables dont le degré est exactement   et pour tous les  ,  , elles forment une famille génératrice des fonctions de degré au plus  .

On peut montrer que lorsque   est un hyperplan, la fonction   est affine. Il est donc suffisant de considérer des hyperplans engendrés par des fonctions linéairement indépendantes pour obtenir de la sorte les codes de Reed-Muller.

Paramètres

modifier

L'ensemble des fonctions booléennes de degré au plus   est un espace vectoriel, ce code est donc linéaire. Par définition, sa longueur est  . La famille des monômes de degré au plus   étant une base de cet espace, et ayant

 

éléments, sa dimension est  .

Le poids minimal du code   est obtenu, entre autres, par les monômes de degré   et vaut  .

L'ordre 1

modifier

Lorsque  , le code   est constitué des fonctions affines, c'est-à-dire des fonctions de la forme

 

où les   sont des éléments de  .

La distance minimale du code de Reed-Muller d'ordre 1 est  , ce qui en fait un code optimal selon la borne de Griesmer: un code ayant au moins autant de mots et une distance minimale au moins aussi grande ne peut pas être plus court que  .

On peut même facilement être plus précis. En effet, le polynôme énumérateur des poids se calcule simplement :

 

  désigne le poids de Hamming de  . Cela signifie qu'il existe 3 poids possibles pour les mots du code, soit   pour le mot nul, soit   pour le mot tout à  , soit   pour tous les autres mots. Pour prouver ce résultat il suffit de considérer la forme d'une fonction affine donnée ci-dessus. Si les   sont tous nuls pour  , la seule valeur prise par   est   et on obtient le mot tout à zéro ou tout à un selon la valeur de  , donc respectivement les termes   et  . Si l'un des   au moins est non nul pour  , alors les éléments   tels que   forment un espace affine de dimension  . Le cardinal de cet espace est donc  . On en déduit que l'ensemble des   tels que   a pour cardinal  . Le mot associé à   a donc un poids de  . Les   fonctions pour lesquelles l'un des   au moins est non nul donnent donc le terme  .

Liens externes

modifier

Article de E.F. Assmus sur les codes de Reed et Muller, détaillant de nombreuses propriétés de ces codes.