Code de Reed-Muller

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 $r$ et $m$, 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 $r$ en $m$, que l'on note $\mathrm {RM} (r,m)$, est l'ensemble des tables de vérité des fonctions booléennes en $m$ variables dont la forme algébrique normale (ANF) est de degré au plus $r$. Lorsque l'alphabet est le corps fini à $q$ éléments, il suffit de considérer les fonctions $q$-aires.

Code binaire

Une construction simple

On choisit un ordre quelconque sur les éléments de $\mathbb {F} _{2}^{m}=\{z_{0},...,z_{2^{m}-1}\}$. Une fonction booléenne $f$ en $m$ variables est alors identifiée au mot binaire défini par

$c_{f}=\left(f(z_{0}),...,f(z_{2^{m}-1})\right)$

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

$\mathrm {RM} (r,m)=\{c_{f}:d(f)\leq r\}$

où $d(f)$ est le degré de l'ANF de $f$.

Exemple de $\mathrm {RM} (1,5)$

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

$\mathbb {F} _{2}^{5}=\{z_{0}=(0,0,0,0,0),...,z_{31}=(1,1,1,1,1)\}$.

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

$c_{f}=\left(f(z_{0}),...,f(z_{31})\right)$

L'ensemble des mots du code est

$\mathrm {RM} (1,5)=\{c_{f}:\exists a\in \mathbb {F} ^{6}|f((X_{0},...,X_{4}))=a_{0}X_{0}+a_{1}X_{1}+a_{2}X_{2}+a_{3}X_{3}+a_{4}X_{4}+a_{5}\}$

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 $f$ étant simplement le vecteur $c_{f}$.

Une autre construction

On décrit comment construire une matrice génératrice d'un code de longueur $n=2^{m}$. Posons :

$\mathbb {F} _{2}^{m}=\{z_{0},\ldots ,z_{2^{m}-1}\}$

Dans l'espace $\mathbb {F} _{2}^{n}$ on définit, pour toute partie $A\subset \mathbb {F} _{2}^{m}$, les vecteurs $\mathbb {I} _{A}\in \mathbb {F} _{2}^{n}$ par

$\left(\mathbb {I} _{A}\right)_{i}={\begin{cases}1&{\mbox{ si }}z_{i}\in A\\0&{\mbox{ sinon}}\\\end{cases}}$

On définit également dans $\mathbb {F} _{2}^{n}$ l'opération binaire :

$w\wedge y=(w_{1}\cdot y_{1},\ldots ,w_{n}\cdot y_{n})$

appelé produit extérieur.

$\mathbb {F} _{2}^{m}$ est un espace vectoriel à $m$ dimensions sur le corps $\mathbb {F} _{2}$, donc on écrit

$(\mathbb {F} _{2})^{m}=\{(x_{0},\ldots ,x_{m-1})|x_{i}\in \mathbb {F} _{2}\}$

Dans l'espace $\mathbb {F} _{2}^{n}$, on définit les vecteurs de longueur $n$ suivants : $v_{0}=(1,1,1,1,1,1,1,1)$ et

$v_{i}=\mathbb {I} _{H_{i}}$

où $H_{i}$ sont des hyperplans dans $(\mathbb {F} _{2})^{m}$ (de dimension $n=2^{m}-1$) :

$H_{i}=\{x\in (\mathbb {F} _{2})^{m}\mid x_{i}=0\}$

Le code de Reed-Muller $(r,m)$ d'ordre $r$ et longueur $n=2^{m}$ est le code généré par $v_{0}$ et le produit extérieur d'au plus $r$ des $v_{i}$ (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 $f$ est une fonction booléenne en $m$ variables, on a

$\mathbb {I} _{A_{f}}=c_{f}$ en posant $A_{f}=\{z\in \mathbb {F} _{2}^{m}:f(z)=1\}$

où $c_{f}$ est le vecteur défini à la section Code binaire. Il est alors facile de vérifier que

$\mathbb {I} _{A_{f}}\wedge \mathbb {I} _{A_{g}}=\mathbb {I} _{A_{f\cdot g}}=c_{f\cdot g}$

Pour terminer, il suffit de remarquer que $H_{i}=A_{e_{i}+1}$, où $e_{i}$ est la ième forme coordonnée, i.e :

$e_{i}(x_{0},...,x_{m-1})=x_{i}$

Le vecteur $v_{i}$ est donc égal à $c_{e_{i}+1}$. La famille des produits extérieurs d'au plus $r$ vecteurs $v_{i}$, est donc constituée des vecteurs de la forme

$v_{i_{0}}\wedge ...\wedge v_{i_{l}}=c_{(e_{i_{0}}+1)...(e_{i_{l}}+1)}$ avec $l\leq r$.

Bien entendu, les ${(e_{i_{0}}+1)...(e_{i_{l}}+1)}$ sont des fonctions booléennes en $m$ variables dont le degré est exactement $l$ et pour tous les $(i_{0},...,i_{l})$, $l\leq r$, elles forment une famille génératrice des fonctions de degré au plus $r$.

On peut montrer que lorsque $H=A_{f}$ est un hyperplan, la fonction $f$ 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

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

$k={m \choose 0}+{m \choose 1}+...+{m \choose r}$

éléments, sa dimension est $k$.

Le poids minimal du code $\mathrm {RM} (r,m)$ est obtenu, entre autres, par les monômes de degré $r$ et vaut $2^{m-r}$.

L'ordre 1

Lorsque $r=1$, le code $\mathrm {RM} (r,m)$ est constitué des fonctions affines, c'est-à-dire des fonctions de la forme

$f(x_{0},...,x_{m-1})=a_{0}x_{0}+...+a_{m-1}x_{m-1}+a_{m}$

où les $a_{i}$ sont des éléments de $\mathbb {F} _{2}$.

La distance minimale du code de Reed-Muller d'ordre 1 est $2^{m-1}$, 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 $\mathrm {RM} (1,m)$.

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

$W(X,Y)=\sum _{c\in \mathrm {RM} (1,m)}X^{w(c)}Y^{2^{m}-w(c)}=Y^{2^{m}}+(2^{m+1}-2){X^{2^{m-1}}Y^{2^{m-1}}}+X^{2^{m}}$

où $w(c)$ désigne le poids de Hamming de $c$. Cela signifie qu'il existe 3 poids possibles pour les mots du code, soit $0$ pour le mot nul, soit $2^{m}$ pour le mot tout à $1$, soit $2^{m-1}$ 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 $a_{i}$ sont tous nuls pour $i\in \{1,...,m-1\}$, la seule valeur prise par $f$ est $a_{m}$ et on obtient le mot tout à zéro ou tout à un selon la valeur de $a_{m}$, donc respectivement les termes $Y^{2^{m}}$ et $X^{2^{m}}$. Si l'un des $a_{i}$ au moins est non nul pour $i\in \{1,...,m-1\}$, alors les éléments $x$ tels que $f(x)=0$ forment un espace affine de dimension $m-1$. Le cardinal de cet espace est donc $2^{m-1}$. On en déduit que l'ensemble des $x$ tels que $f(x)=1$ a pour cardinal $2^{m}-2^{m-1}=2^{m-1}$. Le mot associé à $f$ a donc un poids de $2^{m-1}$. Les $(2^{m+1}-2)$ fonctions pour lesquelles l'un des $a_{i}$ au moins est non nul donnent donc le terme $(2^{m+1}-2){X^{2^{m-1}}Y^{2^{m-1}}}$.

Liens externes

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