# Identitat de Mac Williams

En matemàtiques la identitat de MacWilliams és una aplicació de l'anàlisi harmònica sobre un grup abelià finit, en el cas on el grup és un espai vectorial de dimensió finita sobre un cos finit.
Es fa servir essencialment en teoria dels codis, per als codis lineals, relaciona els polinomis enumeradors dels pesos d'un codi i del seu dual, permetent així, per exemple, determinar el polinomi enumerador dels pesos del dual a partir del del codi.

## Plantejament del problema
### Objectiu

En aquest article C designa un codi de paràmetre [n, k ] sobre el cos finit F$_d$ on d és un enter potència d'un nombre primer p.
L'objectiu de la identitat de MacWilliams és respondre a la qüestió següent: sigui C un codi lineal, quina és la distància mínima en el sentit de Hamming del seu codi dual ?
La resposta no depèn només de la distància mínima de C, de fet és necessari conèixer tota la distribució dels pesos del codi C, el que dona lloc a la definició següent:
   * El polinomi enumerador dels pesos és el polinomi amb coeficients de valors enters positius tal que si i és un enter positiu el coeficient del monomi X$_i$ és igual al nombre de paraules del codi de pes de Hamming igual a i.
El polinomi enumeradors dels pesos correspon per tant a la distribució dels diferents pesos del codi.
Per exemple, en el cas on n és igual a k, és a dir aquell on no existeix cap redundància, l'esfera de radi i i de centre el vector nul conté exactament a$_i$ punts amb:
$a_{i}={n \choose i}(d-1)^{i}\;$
És a dir l'i-èsim coeficient binomial d'ordre n que multiplica el nombre de lletres diferents de 0 de l'alfabet a la potència i. en Aquest Cas, el polinomi enumerador P[X] és igual a:
$P[X]=\sum _{i=0}^{n}a_{i}X^{i}=\sum _{i=0}^{n}{n \choose i}(d-1)^{i}X^{i}={\Big1+(d-1)X{\Big )}^{n}\;$
L'objectiu és de trobar el polinomi enumerador dels pesos del codi dual, en l'exemple el codi dual no conté més que una única paraula, la paraula nul·la, són polinomi enumerador és doncs el polinomi nul.

### Eines

L'espai vectorial utilitzat aquí, és a dir F$_d$$^n$, és un grup abelià finit per a l'addició, el seu grup dual és doncs finit i isomorf a (F$_d$$^n$ +), la teoria de l'anàlisi harmònica és relativament senzilla. En aquest context, permet definir una transformada de Fourier que té les propietats usuals com la igualtat de Parseval o la fórmula del sumatori de Poisson.
La teoria encara se simplifica més a conseqüència de l'estructura d'espai vectorial del grup, existeix un isomorfisme entre el grup i el seu espai dual. Si μ és un caràcter no trivial sobre el grup additiu del cos F$_d$, tots els caràcters s'escriuen sota la forma hi següent:
$\forall x\in \mathbb {F} _{d}^{n}\quad \chi _{y}(x)=\mu (y.x)\quad avec\quad y\in \mathbb {F} _{d}^{n}\;$
Aquí . designa la forma bilineal no degenerada definida per la igualtat següent, si x = (x$_i$) i y = (y$^i$) designen dos vectors de F$_d$$^n$:
$x.y=\sum _{i=1}^{n}x_{i}.y_{i}\;$

## Identitat de MacWilliams

Amb les notacions del paràgraf precedent, si Q[X] designa el polinomi enumerador dels pesos del codi dual de C, llavors es verifica la igualtat següent:
$Q[X]={\frac {1}{d^{k}}}{\Big1+(d-1)X{\Big )}^{n}P{\Big{\frac {1-X}{1+(d-1)X}}{\Big )}\;$
$\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})\;$
Aquí c designa la funció de F$_d$ en C que a 0 li associa 0 i que a qualsevol altre element li associa 1. L'aplicació w correspon doncs a la funció pes de Hamming. A més, (y$_i$) designa les diferents coordenades de y en la base canònica de F$_d$$^n$.
   * El polinomi Q[X], definit per la igualtat següent, és el polinomi enumerador dels pesos del codi dual de C.
$Q[X]={\frac {1}{q^{k}}}\sum _{c\in C}g(c)\;$
La definició del polinomi Q[X] mostra que:
$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 amb\quad b_{y}=\sum _{c\in C}\mu (c.y)\;$
Per tant, cal calcular b$_y$. Si y és un element del codi dual, llavors c.y és igual a 0 per a tot c element de C, se'n dedueix que μ(c.y) és igual a 1 i b$_y$ és igual al cardinal de C, és a dir q$^k$. Si y no és element de C, llavors l'aplicació que a c li associa μ(c.y) és un caràcter no trivial del grup (C, +). És per tant ortogonal al caràcter trivial, aquesta relació d'ortogonalitat expressa el fet que b$_y$ no és nul. Se'n dedueix que:
$Q[X]=\sum _{c\in C^{\perp }}X^{w(c)}\;$
Aquesta última igualtat demostra que Q[X] és el polinomi anul·lador del codi dual.
    el polinomi Q[X] verifica la següent igualtat:
$Q[X]={\frac {1}{d^{k}}}{\Big1+(d-1)X{\Big )}^{n}P{\Big{\frac {1-X}{1+(d-1)X}}{\Big )}\;$
Si (c$_i$) són les coordenades de c i (y$_i$) la de y, llavors es verifiquen les igualtats següents:
$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})}\;$
Es calcula llavors el següent valor:
$S_{i}=\sum _{y\in \mathbb {F} _{d}}\mu (c_{i}.y)X^{c(y)}\;$
Si c$^i$ és nul llavors μ(c$_i$ és igual a 1 per a tot valor de y, c(y) val 0 si y és nul i 1 si no, se'n dedueix que S$_i$ = 1 + (q - 1)X. Si c no és nul llavors l'aplicació que a y li associa μ(c$_i$.y) és un caràcter no trivial del grup additiu del cos F$_d$. És per tant ortogonal al caràcter trivial i:
$\sum _{y\in \mathbb {F} _{d}}\mu (c_{i}.y)=0\quad donc\quad \sum _{y\in \mathbb {F} _{d}y\neq 0}\mu (c_{i}.y)=-1\;$
Se'n dedueixen les igualtats següents:
$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\neq 0}\mu (c_{i}.y){\Big )}X=1-X\;$
Se'n dedueix la igualtat següent:
$g(c)={\frac {1}{q^{k}}}{\Big1+(q-1)X{\Big )}^{n-w(c)}{\Big1-X{\Big )}^{w(c)}={\frac {1}{q^{k}}}{\Big1+(q-1)X{\Big )}^{n}{\Big{\frac {1-X}{1+(q-1)X}}{\Big )}^{w(c)}\;$
S'obté per tant per a expressió de Q[X], la igualtat següent:
$Q[X]={\frac {1}{q^{k}}}{\Big1+(q-1)X{\Big )}^{n}\sum _{c\in C}{\Big{\frac {1-X}{1+(q-1)X}}{\Big )}^{w(c)}={\frac {1}{d^{k}}}{\Big1+(d-1)X{\Big )}^{n}P{\Big{\frac {1-X}{1+(d-1)X}}{\Big )}\;$

## Aplicacions
### Codi sense redundància

Es considera el codi sense redundància de l'exemple del paràgraf dels objectius, el polinomi enumerador dels pesos del codi és:
$P[X]={\Big1+(d-1)X{\Big )}^{n}\;$
La identitat de MacWilliams dona per valor de Q[X] polinomi enumerador del codi dual:
$Q[X]={\frac {1}{d^{n}}}{\Big1+(d-1)X{\Big )}^{n}{\Big1+(d-1){\frac {1-X}{1+(d-1)X}}{\Big )}^{n}\;$
El que dona les igualtats següents:
$Q[X]={\frac {1}{d^{n}}}{\Big1+(d-1)X{\Big )}^{n}{\Big{\frac {d}{1+(d-1)X}}{\Big )}^{n}=1\;$
El codi dual posseeix en efecte un únic element de pes nul, la identitat de MacWilliams subministra el polinomi énumérateur del codi dual.

### Codi de Hamming

Es Determina el polinomi enumerador dels pesos del codi de Hamming. El mètode utilitzat aquí consisteix a determinar el polinomi enumerador del codi dual directament i utilitzar la identitat de MacWilliams per a determinar el polinomi enumerador del codi dual del codi dual, igual al codi de Hamming.
Les notacions utilitzades aquí són les de l'article principal, en particular m designa el valor n - k, és a dir la dimensió del codi dual i H designa la matriu de control del codi.
   * Totes les paraules del codi dual no nul·les del codi d'Hamming tenen un pes igual a d$^{m-1}$.
En efecte, el codi dual està constituït per les paraules de la forma $^t$x.H on x descriu l'espai vectorial F$_d$$^m$. Es designa per (h$_i$) per a i variant d'1 a n les n columnes de la matriu H que són també vectors de dimensió m L'aplicació que a x li associa el vector (x.h$_i$) és doncs un isomorfisme entre F$_d$$^m$ i el codi dual.
Sigui A el conjunt dels vectors a de F$_d$$^m$ tal que a.x sigui diferent de 0. La intersecció de les classes de l'espai projectiu amb A formen una partició de A. A més, a.x és diferent de 0 si i només si λa.x és diferent de 0 per a tot λ element de F$_d$$^*$. En conseqüència cada classe de la partició de A conté d - 1 elements. Finalment, els vectors h$_i$ descriuen un sistema de representants de les classes de l'espai projectiu de F$_d$$^*$ (vegeu el paràgraf Existència i unicitat en el cas general). Se'n dedueix que el pes de (x.h$_i$) és igual a la fracció de numerador el cardinal de A i de denominador d - 1.
El complementari de A, si x no és nul, és un hiperpla de F$_d$$^m$ per tant un conjunt de cardinal d$_{m-1}$. El cardinal de A és per tant igual a d$_{m-1}$. (d - 1). El pes de (x.h$_i$) és llavors igual a d$^{m-1}$ si x no és nul.
   * El polinomi enumerador dels pesos del codi de Hamming P[X] es defineix per la igualtat següent:
$P[X]={\frac {1}{d^{m}}}{\Bigg{\Big1+(d-1)X{\Big )}^{n}+(d^{m}-1){\Big1+(d-1)X{\Big )}^{n-d^{m-1}}(1-X)^{d^{m-1}}{\Bigg )}\;$
En efecte, el polinomi enumerador dels pesos del codi dual és el següent:
$Q[X]=1+(d^{m}-1)X^{d^{m-1}}\;$
La identitat de MacWilliams mostra llavors que:
$P[X]={\frac {1}{d^{m}}}{\Big1+(d-1)X{\Big )}^{n}{\Big1+(d^{m}-1){\Big{\frac {1-X}{1+(d-1)X}}{\Big )}^{d^{m-1}}{\Big )}={\frac {1}{d^{m}}}{\Bigg{\Big1+(d-1)X{\Big )}^{n}+(d^{m}-1){\Big1+(d-1)X{\Big )}^{n-d^{m-1}}(1-X)^{d^{m-1}}{\Bigg )}\;$
Q.E.D.

## Referències

* M. Demazure Cours d'algèbre. Primalité, divisibilité, codes Cassini 1997
* F. J. MacWilliams & 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

## Enllaços externs

* (francès) Cours de code per Christine Bachoc Université de Bordeaux
* (francès) Mathématiques discrètes de la transformée de Fourier C. Bachoc Université de Bordeaux I
* (francès) Cryptologie, sécurité et codage d'information Arxivat 2006-11-27 a Wayback Machine. par A. A. Pantchichkine