<page>
    <title>Identité de MacWilliams</title>
    <id>1571386</id>
    <revision>
      <id>28790520</id>
      <timestamp>2008-04-19T14:29:19Z</timestamp>
      <contributor>
        <username>Dtcube</username>
        <id>95</id>
      </contributor>
      <text xml:space="preserve">En [[mathématiques]] l''''identité de MacWilliams''' est une application de l'[[analyse harmonique sur un groupe abélien fini]], dans le cas où le [[groupe (mathématiques)| groupe]] est un [[espace vectoriel]] de [[dimension]] finie sur un [[corps fini]].

Elle est utilisée essentiellement en [[théorie des codes]], pour les [[code linéaire|codes linéaires]], elle relie les '''polynômes énumérateurs des poids''' d'un code et de son [[code dual|dual]], permettant ainsi, par exemple, de déterminer le polynôme énumérateur des poids du dual à partir de celui du code.

== Position du problème ==
=== Objectif ===
{{Article détaillé|Code linéaire}}
Dans cet article ''C'' désigne un code de paramètre [''n'', ''k'', δ] sur le corps fini ''F''&lt;sub&gt;d&lt;/sub&gt; où ''d'' est un entier puissance d'un [[nombre premier]] ''p''.

L'objectif de l''''identité de MacWilliams''' est de répondre à la question suivante : soit ''C'' un code linéaire quel est la distance minimale au sens de [[distance de Hamming|Hamming]] de son code dual ?

La réponse de dépend pas uniquement de la distance minimale de ''C'', il est en fait nécessaire de connaître toute la distribution des [[poids de Hamming|poids]] du code ''C'', ce qui donne lieu à la définition suivante :

:* Le '''[[polynôme]] énumérateur des poids''' est le polynôme dont à coefficients à valeur dans les [[entier naturel|entiers positifs]] tel que si ''i'' est un entier positif le coefficient du monôme ''X''&lt;sup&gt;i&lt;/sup&gt; est égal au nombre de mots du code de poids de Hamming égal à ''i''.

Le polynôme énumérateur des poids correspond donc à la distribution des différents poids du code.

Considérons par exemple le cas où ''n'' est égal à ''k'', c'est à dire celui où il n'existe aucune redondance, la sphère de rayon ''i'' et de centre le vecteur nulle contient exactement ''a''&lt;sub&gt;i&lt;/sub&gt; points avec :
&lt;center&gt;&lt;math&gt;a_i= {n \choose i}  (d-1)^i \;&lt;/math&gt;&lt;/center&gt;
C'est à dire le ''i''-ème coefficient binomial d'ordre ''n'' que multiplie le nombre de lettres différente de 0 de l'alphabet à la puissance ''i''. Dans ce cas, le polynôme énumérateur ''P''[''X]] est égal à :
&lt;center&gt;&lt;math&gt;P[X]= \sum_{i=0}^n a_i X^i = \sum_{i=0}^n {n \choose i}  (d-1)^i X^i= \Big(1 + (d-1)X \Big)^n \;&lt;/math&gt;&lt;/center&gt;
L'objectif est de trouver le polynôme énumérateur des poids du code dual, dans l'exemple le code dual ne contient qu'un unique mot, le mot nul, sont polynôme énumérateur est donc le polynôme nul.

=== Outils ===
{{Article détaillé|Analyse harmonique sur un espace vectoriel fini}}
L'espace vectoriel utilisé ici, à savoir ''F''&lt;sub&gt;d&lt;/sub&gt;&lt;sup&gt;n&lt;/sup&gt;, est un [[groupe abélien]] [[groupe fini|fini]] pour l'addition, son [[caractère d'un groupe fini|groupe dual]] est donc fini et [[isomorphe]] à (''F''&lt;sub&gt;d&lt;/sub&gt;&lt;sup&gt;n&lt;/sup&gt; +), la théorie de l'analyse harmonique est relativement simple. Dans ce contexte, elle permet de définir une [[transformée de Fourier]] disposant des propriétés usuelles comme l'[[égalité de Parseval]] ou la [[formule sommatoire de Poisson]].

La théorie est encore simplifiée du fait de la structure d'espace vectoriel du groupe, il existe un isomorphisme entre le groupe et son espace dual. Si μ est un caractère non trivial sur le groupe additif du corps ''F''&lt;sub&gt;d&lt;/sub&gt;, tous les caractères s'écrivent sous la forme χ&lt;sub&gt;y&lt;/sub&gt; suivante :
&lt;center&gt;&lt;math&gt;\forall x \in \mathbb F_d^n \quad \chi_y(x) = \mu (y.x) \quad avec \quad y \in \mathbb F_d^n\;&lt;/math&gt;&lt;/center&gt;
Ici '''.''' désigne la forme bilinéaire non dégénérée définie par l'égalité suivante, si ''x'' = (''x''&lt;sub&gt;i&lt;/sub&gt;) et ''y'' = (''y''&lt;sub&gt;i&lt;/sub&gt;) désigne deux vecteurs de ''F''&lt;sub&gt;d&lt;/sub&gt;&lt;sup&gt;n&lt;/sup&gt; :
&lt;center&gt;&lt;math&gt;x.y = \sum_{i=1}^n x_i.y_i\;&lt;/math&gt;&lt;/center&gt;

== Identité de MacWilliams ==
Avec les notations du paragraphe précédent, si ''Q''[''X''] désigne le polynôme énumérateur des poids du code dual de ''C'', alors l'égalité suivante est vérifiée :
&lt;center&gt;&lt;math&gt;Q[X]=\frac 1{d^k}\Big( 1 + (d-1)X\Big)^n P\Big(\frac{1-X}{1 + (d-1)X} \Big)\;&lt;/math&gt;&lt;/center&gt;

{{boîte déroulante|align=left|titre=Démonstration|contenu=

Considérons la fonction ''g'' de ''F''&lt;sub&gt;d&lt;/sub&gt;&lt;sup&gt;n&lt;/sup&gt; dans ''C''[''X''] l'[[anneau (mathématiques)|anneau]] des polynômes à coefficients [[nombre complexe|complexes]], définie par :
&lt;center&gt;&lt;math&gt;\forall x \in \mathbb F_d^n \quad g(x) = \sum_{y \in \mathbb F_d^n}\mu(x.y) X^{w(y)} \quad avec \quad w(y) = \sum_{i = 0}^n c(y_i) \;&lt;/math&gt;&lt;/center&gt;
Ici ''c'' désigne la fonction de ''F''&lt;sub&gt;d&lt;/sub&gt; dans ''C'' qui à 0 associe 0 et à tout autre élément associe 1. L'application ''w'' correspond donc à la fonction ''poids de Hamming''. Une fois encore, (''y''&lt;sub&gt;i&lt;/sub&gt;) désigne les différentes coordonnées de ''y'' dans la base canonique de ''F''&lt;sub&gt;d&lt;/sub&gt;&lt;sup&gt;n&lt;/sup&gt;.

:* '''Le polynôme ''Q''[''X''], défini par l'égalité suivante, est le polynôme énumérateur des poids du code dual de ''C''.'''
&lt;center&gt;&lt;math&gt;Q[X] = \frac 1{q^k} \sum_{c \in C} g(c) \; &lt;/math&gt;&lt;/center&gt;
La définition du polynôme ''Q''[''X''] montre que :
&lt;center&gt;&lt;math&gt;Q[X] = \frac 1{q^k} \sum_{c \in C} g(c) = \frac 1{q^k} \sum_{y \in \mathbb F_d^n} \sum_{c \in C} \mu(c.y) X^{w(y)} = \frac 1{q^k} \sum_{y \in \mathbb F_d^n} b_y X^{w(y)} \quad avec \quad b_y = \sum_{c \in C} \mu(c.y) \; &lt;/math&gt;&lt;/center&gt;
Il est donc nécessaire de calculer ''b''&lt;sub&gt;y&lt;/sub&gt;. Si ''y'' est un élément du code dual, alors ''c.y'' est égal à 0 pour tout ''c'' élément de ''C'', on en déduit que μ(''c''.''y'') est égal à 1 et ''b''&lt;sub&gt;y&lt;/sub&gt; est égal au cardinal de ''C'', c'est à dire ''q''&lt;sup&gt;k&lt;/sup&gt;. Si ''y'' n'est pas élément de ''C'', alors l'application qui à ''c'' associe μ(''c''.''y'') est un caractère non trivial du groupe (''C'', + ). Il est donc orthogonal au caractère trivial, cette relation d'orthogonalité exprime le fait que ''b''&lt;sub&gt;y&lt;/sub&gt; est nul. On en déduit que :
&lt;center&gt;&lt;math&gt;Q[X]=\sum_{c \in C^{\perp}} X^{w(c)} \; &lt;/math&gt;&lt;/center&gt;
Cette dernière égalité démontre que ''Q''[''X''] est bien le polynôme annulateur du code dual.

:* '''le polynôme ''Q''[''X''] vérifie l'égalité suivante :'''
&lt;center&gt;&lt;math&gt;Q[X]=\frac 1{d^k}\Big( 1 + (d-1)X\Big)^n P\Big(\frac{1-X}{1 + (d-1)X} \Big)\;&lt;/math&gt;&lt;/center&gt;
Si (''c''&lt;sub&gt;i&lt;/sub&gt;) sont les coordonnées de ''c'' et (''y''&lt;sub&gt;i&lt;/sub&gt;) celle de ''y'', alors les égalités suivantes sont vérifiées :

&lt;center&gt;&lt;math&gt;g(c) = \frac 1{q^k} \sum_{y \in \mathbb F_d^n}\mu(c.y) X^{w(y)} = \frac 1{q^k} \sum_{y \in \mathbb F_d^n} \prod_{i=1}^n \mu(c_i.y_i) X^{c(y_i)} \;&lt;/math&gt;&lt;/center&gt;
Calculons alors la valeur suivante :
&lt;center&gt;&lt;math&gt;S_i = \sum_{y \in \mathbb F_d} \mu(c_i.y) X^{c(y)} \;&lt;/math&gt;&lt;/center&gt;
Si ''c''&lt;sub&gt;i&lt;/sub&gt; est nul alors μ(''c''&lt;sub&gt;i&lt;/sub&gt;.''y'') est égal à 1 pour toute valeur de ''y'', ''c''(''y'') vaut 0 si ''y'' est nul et 1 sinon, on en déduit que ''S''&lt;sub&gt;i&lt;/sub&gt; = 1 + (''q'' - 1)X.
Si ''c''&lt;sub&gt;i&lt;/sub&gt; est non nul alors l'application qui à ''y'' associe μ(''c''&lt;sub&gt;i&lt;/sub&gt;.''y'') est un caractère non trivial du groupe additif du corps ''F''&lt;sub&gt;d&lt;/sub&gt;. Il est donc orthogonal au caractère trivial et :
&lt;center&gt;&lt;math&gt;\sum_{y \in \mathbb F_d} \mu(c_i.y) = 0 \quad donc \quad \sum_{y \in \mathbb F_d y \ne 0} \mu(c_i.y) = -1 \;&lt;/math&gt;&lt;/center&gt;
On en déduit les égalités suivantes :
&lt;center&gt;&lt;math&gt;S_i = \sum_{y \in \mathbb F_d} \mu(c_i.y) X^{c(y)} =\mu(c_i.0)X^0 + \Big(\sum_{y \in \mathbb F_d y \ne 0} \mu(c_i.y) \Big)X = 1 -X \;&lt;/math&gt;&lt;/center&gt;
On en déduit l'égalité suivante :
&lt;center&gt;&lt;math&gt;g(c) = \frac 1{q^k}\Big(1 + (q-1)X \Big)^{n-w(c)}\Big( 1 -X \Big)^{w(c)}=\frac 1{q^k}\Big(1 + (q-1)X \Big)^n \Big(\frac {1-X}{1 + (q-1)X} \Big)^{w(c)}\;&lt;/math&gt;&lt;/center&gt;
On obtient donc pour expression de ''Q''[''X''], l'égalité suivante :
&lt;center&gt;&lt;math&gt;Q[X] = \frac 1{q^k}\Big(1 + (q-1)X \Big)^n \sum_{c \in C} \Big(\frac {1-X}{1 + (q-1)X} \Big)^{w(c)}= \frac 1{d^k}\Big( 1 + (d-1)X\Big)^n P\Big(\frac{1-X}{1 + (d-1)X} \Big)\;&lt;/math&gt;&lt;/center&gt;
Ce qui termine la démonstration.
}}

== Applications ==
=== Code sans redondance ===
Considérons le code sans redondance de l'exemple du paragraphe des objectifs, le polynôme énumérateur des poids du code est :
&lt;center&gt;&lt;math&gt;P[X]= \Big(1 + (d-1)X \Big)^n \;&lt;/math&gt;&lt;/center&gt;
L'identité de MacWilliams donne pour valeur de ''Q''[''X''] polynôme énumérateur du code dual :
&lt;center&gt;&lt;math&gt;Q[X]=\frac 1{d^n}\Big( 1 + (d-1)X\Big)^n \Big( 1 + (d-1)\frac{1-X}{1 + (d-1)X} \Big)^n \;&lt;/math&gt;&lt;/center&gt;
Ce qui donne les égalités suivantes :
&lt;center&gt;&lt;math&gt;Q[X]=\frac 1{d^n}\Big( 1 + (d-1)X\Big)^n \Big(\frac{d}{1 + (d-1)X} \Big)^n = 1 \;&lt;/math&gt;&lt;/center&gt;
Le code dual possède en effet un unique élément de poids nul, l'identité de MacWilliams fournit bien le polynôme énumérateur du code dual.
=== Code de Hamming ===
{{Article détaillé|Code de Hamming}}
Déterminons le polynôme énumérateur des poids du code de Hamming. La méthode utilisée ici consiste à déterminer le polynôme énumérateur du code dual directement et d'utiliser l'identité de MacWilliams pour déterminer le polynôme énumérateur du code dual du code dual, égal au code de Hamming.

Les notations utilisées ici sont celles de l'article détaillé, en particulier ''m'' désigne la valeur ''n'' - ''k'', c'est à dire la dimension du code dual et ''H'' désigne la matrice de contrôle du code.

:* ''Tous les mots du code dual non nuls du code de Hamming ont un poids égal à ''d''&lt;sup&gt;m-1&lt;/sup&gt;.''
En effet, le code dual est constitué des mots de la forme &lt;sup&gt;t&lt;/sup&gt;''x''.''H'' où ''x'' décrit l'espace vectoriel ''F''&lt;sub&gt;d&lt;/sub&gt;&lt;sup&gt;m&lt;/sup&gt;. Désignons par (h&lt;sub&gt;i&lt;/sub&gt;) pour ''i'' variant de 1 à ''n'' les ''n'' colonnes de la matrice ''H'' qui sont aussi des vecteurs de dimension ''m''. L'application qui à ''x'' associe le vecteur (''x''.''h''&lt;sub&gt;i&lt;/sub&gt;) est donc un [[isomorphisme]] entre ''F''&lt;sub&gt;d&lt;/sub&gt;&lt;sup&gt;m&lt;/sup&gt; et le code dual.

Soit ''A'' l'ensemble des vecteurs ''a'' de ''F''&lt;sub&gt;d&lt;/sub&gt;&lt;sup&gt;m&lt;/sup&gt; tel que ''a''.''x'' soit différent de 0. L'intersection des classes de l'espace projectifs avec ''A'' forment une [[Partition (mathématiques)|partition]] de ''A''. De plus, ''a''.''x'' est différent de 0 si et seulement si λ''a''.''x'' est différent de 0 pour tout λ élément de ''F''&lt;sub&gt;d&lt;/sub&gt;&lt;sup&gt;*&lt;/sup&gt;. En conséquence chaque classe de la partition de ''A'' contient ''d'' - 1 éléments. Enfin, les vecteurs ''h''&lt;sub&gt;i&lt;/sub&gt; décrivent un système de représentants des classes de l'[[espace projectif]] de ''F''&lt;sub&gt;d&lt;/sub&gt;&lt;sup&gt;m&lt;/sup&gt; ''(cf le paragraphe [[Code de Hamming#Existence et unicité dans le cas général|Existence et unicité dans le cas général]])''. On en déduit que le poids de (''x''.''h''&lt;sub&gt;i&lt;/sub&gt;) est égal à la fraction de numérateur le cardinal de ''A'' et de dénominateur ''d'' - 1.

Le complémentaire de ''A'', si ''x'' n'est pas nul, est un hyperplan de ''F''&lt;sub&gt;d&lt;/sub&gt;&lt;sup&gt;m&lt;/sup&gt; donc un ensemble de cardinal ''d''&lt;sup&gt;m - 1&lt;/sup&gt;. Le cardinal de ''A'' est donc égal à ''d''&lt;sup&gt;m - 1&lt;/sup&gt;. (''d'' - 1). Le poids de (''x''.''h''&lt;sub&gt;i&lt;/sub&gt;) est alors égal à ''d''&lt;sup&gt;m - 1&lt;/sup&gt; si ''x'' n'est pas nul.

:* ''Le polynôme énumérateur des poids du code de Hamming ''P''[''X''] est défini par l'égalité suivante :''
&lt;center&gt;&lt;math&gt;P[X]=\frac 1{d^m}\Bigg( \Big( 1 + (d-1)X\Big)^n + (d^m -1)\Big( 1 + (d-1)X\Big)^{n-d^{m-1}}(1 - X)^{d^{m-1}} \Bigg)\;&lt;/math&gt;&lt;/center&gt;
En effet, le polynôme énumérateur des poids du code dual est le suivant :
&lt;center&gt;&lt;math&gt;Q[X]=1 + (d^m -1)X^{d^{m-1}}\;&lt;/math&gt;&lt;/center&gt;
L'identité de MacWilliams montre alors que :
&lt;center&gt;&lt;math&gt;P[X]=\frac 1{d^m}\Big( 1 + (d-1)X\Big)^n \Big( 1 + (d^m -1)\Big( \frac{1-X}{1 + (d-1)X} \Big)^{d^{m-1}}\Big) = 
\frac 1{d^m}\Bigg( \Big( 1 + (d-1)X\Big)^n + (d^m -1)\Big( 1 + (d-1)X\Big)^{n-d^{m-1}}(1 - X)^{d^{m-1}} \Bigg)\;&lt;/math&gt;&lt;/center&gt;
Ce qui termine la démonstration.

==Notes et références==
===Liens externes===
* {{fr}} [http://www.ufr-mi.u-bordeaux.fr/CSI/Cours/code.pdf Cours de code] par Christine Bachoc Université de Bordeaux
* {{fr}} [http://www.ufr-mi.u-bordeaux.fr/CSI/Cours/mathdis.pdf Mathématiques discrètes de la transformée de Fourier] C. Bachoc Université de Bordeaux I
* {{fr}} [http://www-fourier.ujf-grenoble.fr/~panchish/5cc4.pdf Cryptologie, sécurité et codage d'information] par A. A. Pantchichkine

===Références===
* M. Demazure ''Cours d'algèbre. Primalité, divisibilité, codes'' Cassini 1997
* F. J. MacWilliams &amp; JJA ''Sloane The Theory of Error-Correcting Codes'' North-Holland, 1977
* A. Warusfel ''Structures algébriques finies'' Hachette 1971
* G. Peyré ''L'algèbre discrète de la transformée de Fourier'' Ellipses Marketing 2004

{{portail mathématiques}}

[[Catégorie:Analyse harmonique discrète]]
[[Catégorie:Théorie des codes]]</text>
    </revision>
  </page>