Identité de MacWilliams

(Redirigé depuis Identité de Mac Williams)

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 est un espace vectoriel de dimension finie sur un corps fini. Elle porte le nom de la mathématicienne Jessie MacWilliams.

Elle est utilisée essentiellement en théorie des codes, pour les codes linéaires, elle relie les polynômes énumérateurs (en) des poids d'un code et de son 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

modifier

Objectif

modifier

Dans cet article C désigne un code de paramètre [n, k, δ] sur le corps fini Fdd 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, quelle est la distance minimale au sens de Hamming de son code dual ?

La réponse ne dépend pas uniquement de la distance minimale de C, il est en fait nécessaire de connaître toute la distribution des 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 entiers positifs tel que si i est un entier positif le coefficient du monôme Xi 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 ai points avec :

 

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 à :

 

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, son polynôme énumérateur est donc le polynôme constant égal à 1.

L'espace vectoriel fini utilisé ici, à savoir Fdn, est un groupe abélien fini pour l'addition, son groupe dual est donc fini et isomorphe à (Fdn +), 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 Fd, tous les caractères s'écrivent sous la forme χy suivante :

 

Ici, « . » désigne la forme bilinéaire non dégénérée définie par l'égalité suivante, si x = (xi) et y = (yi) désigne deux vecteurs de Fdn :

 

Identité de MacWilliams

modifier

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 :

 

Applications

modifier

Code sans redondance

modifier

Considérons le code sans redondance de l'exemple du paragraphe des objectifs, le polynôme énumérateur des poids du code est :

 

L'identité de MacWilliams donne pour valeur de Q(X) polynôme énumérateur du code dual :

 

ce qui donne les égalités suivantes :

 

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

modifier

Déterminons le polynôme énumérateur des poids du code de Hamming. La méthode utilisée ici consiste à déterminer directement le polynôme énumérateur du code dual et d'utiliser l'identité de MacWilliams pour en déduire celui du 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 à dm-1.

En effet, le code dual est constitué des mots de la forme tx.Hx décrit l'espace vectoriel Fdm. Désignons par (hi) 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.hi) est donc un isomorphisme entre Fdm et le code dual.

Soit A l'ensemble des vecteurs a de Fdm tel que a.x soit différent de 0. L'intersection des classes de l'espace projectifs avec A forment une 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 Fd*. En conséquence chaque classe de la partition de A contient d - 1 éléments. Enfin, les vecteurs hi décrivent un système de représentants des classes de l'espace projectif de Fdm (cf le paragraphe Existence et unicité dans le cas général). On en déduit que le poids de (x.hi) 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 Fdm donc un ensemble de cardinal dm - 1. Le cardinal de A est donc égal à dm - 1. (d - 1). Le poids de (x.hi) est alors égal à dm - 1 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 :
 

En effet, le polynôme énumérateur des poids du code dual est le suivant :

 

L'identité de MacWilliams montre alors que :

 

ce qui termine la démonstration.

Voir aussi

modifier

Bibliographie

modifier

Liens externes

modifier