Code de Reed-Müller

Code de Reed-Müller

Les codes de Reed-Müller sont des codes correcteurs linéaires. Cette famille de codes, initialement binaire, doit son nom aux travaux de D.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.

Un code de cette famille est identifié à l'aide de deux paramètres, usuellement 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 RM(r,m), est l'ensemble des tables de verité 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.

Sommaire

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, cf 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)\le r\}

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

Exemple de 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_0X_0+ a_1X_1 + a_2X_2 + a_3X_3 + a_4X_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 cf.

Une autre construction

On décrit comment construire une matrice génératrice d'un code de longueur n = 2m. 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 : v0 = (1,1,1,1,1,1,1,1) et

v_i = \mathbb{I}_{ H_i }

où Hi sont des hyperplans dans (\mathbb{F}_2)^m (de dimension n = 2m − 1) :

H_i = \{ x \in ( \mathbb{F}_2 ) ^m \mid x_i = 0 \}

Le code de Reed-Müller (r,m) d'ordre r et longueur n = 2m est le code généré par v0 et le produit extérieur d'au plus r des vi (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ù cf 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ù ei est la ième forme coordonnée, i.e :

ei(x0,...,xm − 1) = xi

Le vecteur vi est donc égal à c_{e_i+1}. La famille des produits extérieurs d'au plus r vecteurs vi, 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\le 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 (i0,...,il), l\le r, elles forment une famille génératrice des fonctions de degré au plus r.

On peut montrer que lorsque H = Af 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 2m. La famille des monômes de degré au plus r étant une base de cette espace, et ayant

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

éléments, sa dimension est k.

Le poids minimal du code RM(r,m) est obtenu, entre autres, par les monômes de degré r et vaut 2m − r.

L'ordre 1

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

f(x0,...,xm − 1) = a0x0 + ... + am − 1xm − 1 + am

où les ai sont des éléments de \mathbb{F}_2.

La distance minimale du code de Reed-Muller d'ordre 1 est 2m − 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 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 2m pour le mot tout à 1, soit 2m − 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 ai sont tous nuls pour i\in\{1,...,m-1\}, la seule valeur prise par f est am et on obtient le mot tout à zéro ou tout à un selon la valeur de am, donc respectivement les termes y^{2^m} et X^{2^m}. Si l'un des ai 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 2m − 1. On en déduit que l'ensemble des x tels que f(x) = 1 a pour cardinal 2m − 2m − 1 = 2m − 1. Le mot associé à f a donc un poids de 2m − 1. Les (2m + 1 − 2) fonctions pour lesquelles l'un des ai 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 Müller, détaillant de nombreuses propriétés de ces codes.


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Code de Reed-Müller de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Code De Reed-Müller — Les codes de Reed Müller sont des codes correcteurs linéaires. Cette famille de codes, initialement binaire, doit son nom aux travaux de D.E. Muller qui proposa le principe du code et à Irving S. Reed qui proposa une technique de décodage,… …   Wikipédia en Français

  • Code de Reed-Muller — Code de Reed Müller Les codes de Reed Müller sont des codes correcteurs linéaires. Cette famille de codes, initialement binaire, doit son nom aux travaux de D.E. Muller qui proposa le principe du code et à Irving S. Reed qui proposa une technique …   Wikipédia en Français

  • Code de reed-müller — Les codes de Reed Müller sont des codes correcteurs linéaires. Cette famille de codes, initialement binaire, doit son nom aux travaux de D.E. Muller qui proposa le principe du code et à Irving S. Reed qui proposa une technique de décodage,… …   Wikipédia en Français

  • Reed–Muller code — Reed Muller codes are a family of linear error correcting codes used in communications. They are named after their discoverers, Irving S. Reed and D. E. Muller. Muller discovered the codes, and Reed proposed the majority logic decoding for the… …   Wikipedia

  • Reed-Muller-Code — Die Reed Muller Codes sind eine Familie von linearen, fehlerkorrigierenden Codes, die im Bereich der Kanalcodierung zur gesicherten Datenübertragung und Datenspeicherung Verwendung finden. Diese Klasse von Codes wurden von Irving S. Reed und… …   Deutsch Wikipedia

  • Reed — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Reed, qui signifie roseau en anglais, peut désigner : Patronyme Alan Reed (1907 1977), acteur américain. Andre Reed (1964 ), joueur américain de… …   Wikipédia en Français

  • Code Correcteur — Un code correcteur est une technique de codage basée sur la redondance. Elle est destinée à corriger les erreurs de transmission d une information (plus souvent appelée message) sur une voie de communication peu fiable. La théorie des codes… …   Wikipédia en Français

  • Code — redirects here. CODE may also refer to Cultural Olympiad Digital Edition. Decoded redirects here. For the television show, see Brad Meltzer s Decoded. For code (computer programming), see source code. For other uses, see Code (disambiguation).… …   Wikipedia

  • Muller — may refer to: Contents 1 People 2 Characters 3 Other 4 …   Wikipedia

  • Code correcteur — Un code correcteur est une technique de codage basée sur la redondance. Elle est destinée à corriger les erreurs de transmission d une information (plus souvent appelée message) sur une voie de communication peu fiable. La théorie des codes… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”