Identitat de Mac Williams

De Viquipèdia
Salta a la navegació Salta a la cerca

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[modifica]

Objectiu[modifica]

Article principal: Codi lineal

En aquest article C designa un codi de paràmetre [n, k ] sobre el cos finit Fd 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 Xi é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 ai punts amb:

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

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[modifica]

L'espai vectorial utilitzat aquí, és a dir Fdn, és un grup abelià finit per a l'addició, el seu grup dual és doncs finit i isomorf a (Fdn +), 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 Fd, tots els caràcters s'escriuen sota la forma hi següent:

Aquí . designa la forma bilineal no degenerada definida per la igualtat següent, si x = (xi) i y = (yi) designen dos vectors de Fdn:

Identitat de MacWilliams[modifica]

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:

Aplicacions[modifica]

Codi sense redundància[modifica]

Es considera el codi sense redundància de l'exemple del paràgraf dels objectius, el polinomi enumerador dels pesos del codi és:

La identitat de MacWilliams dona per valor de Q[X] polinomi enumerador del codi dual:

El que dona les igualtats següents:

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[modifica]

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 dm-1.

En efecte, el codi dual està constituït per les paraules de la forma tx.H on x descriu l'espai vectorial Fdm. Es designa per (hi) 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.hi) és doncs un isomorfisme entre Fdm i el codi dual.

Sigui A el conjunt dels vectors a de Fdm 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 Fd*. En conseqüència cada classe de la partició de A conté d - 1 elements. Finalment, els vectors hi descriuen un sistema de representants de les classes de l'espai projectiu de Fd* (vegeu el paràgraf Existència i unicitat en el cas general). Se'n dedueix que el pes de (x.hi) é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 Fdm per tant un conjunt de cardinal dm - 1. El cardinal de A és per tant igual a dm - 1. (d - 1). El pes de (x.hi) és llavors igual a dm - 1 si x no és nul.


  • El polinomi enumerador dels pesos del codi de Hamming P[X] es defineix per la igualtat següent:

En efecte, el polinomi enumerador dels pesos del codi dual és el següent:

La identitat de MacWilliams mostra llavors que:

Q.E.D.

Referències[modifica]

  • 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[modifica]