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

Article principal: Codi lineal

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}={\Big (}1+(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

Article principal: Anàlisi harmònica sobre un espai vectorial finit

L'espai vectorial utilitzat aquí, és a dir F_dⁿ, és un grup abelià finit per a l'addició, el seu grup dual és doncs finit i isomorf a (F_dⁿ +), 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ⁱ) designen dos vectors de F_dⁿ:

$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}}}{\Big (}1+(d-1)X{\Big )}^{n}P{\Big (}{\frac {1-X}{1+(d-1)X}}{\Big )}\;$

Demostració

Es considera la funció g de F_dⁿ en C[X] l'anell dels polinomis amb coeficients complexos, definit per: $\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ⁿ.

• 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}}}{\Big (}1+(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ⁱ é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}}}{\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)}\;$

S'obté per tant per a expressió de Q[X], la igualtat següent:

$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 )}\;$ AMb lo que queda demostrat.

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]={\Big (}1+(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}}}{\Big (}1+(d-1)X{\Big )}^{n}{\Big (}1+(d-1){\frac {1-X}{1+(d-1)X}}{\Big )}^{n}\;$

El que dona les igualtats següents:

$Q[X]={\frac {1}{d^{n}}}{\Big (}1+(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

Article principal: 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 ^tx.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 (}{\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 )}\;$

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}}}{\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 )}\;$

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