MacWilliams identitet

I matematikk er identiteten til MacWilliams en anvendelse av harmonisk analyse på en endelig abelsk gruppe , hvis gruppen er et vektorrom med dimensjon over et endelig felt . Den er oppkalt etter matematikeren Jessie MacWilliams .

Den brukes hovedsakelig i kodeteori , for lineære koder , den forbinder tellerpolynomene  (en) av vektene til en kode og dens doble , og gjør det for eksempel mulig å bestemme tellerpolynomet av vektene til det doble fra av koden.

Plassering av problemet

Mål

I denne artikkelen C betegner en parameterkode [ n , k , δ] over det endelige feltet F d hvor d er et helt tall kraft av et primtall p .

Målet med MacWilliams ' identitet er å svare på følgende spørsmål: la C være en lineær kode, hva er minimumsavstanden i Hamming- forstanden til dens dobbelkode?

Svaret avhenger ikke bare av minimumsavstanden til C , det er faktisk nødvendig å vite hele fordelingen av vektene til koden C , noe som gir opphav til følgende definisjon:

• Den enumeratoren polynom av vektene er polynomet hvis koeffisienter med verdier i de positive heltall slik at hvis jeg er et positivt helt tall koeffisienten for monomial X i er lik antallet ord av Hamming-vekten koden lik i .

Opptellerpolynomet til vektene tilsvarer derfor fordelingen av de forskjellige vektene i koden.

Betrakt for eksempel det tilfellet hvor n er lik k , dvs. en hvor det ikke er noen redundans, den kule med radius i og for midten nullvektoren inneholder nøyaktig en I- punktene med:

påJeg=(ikkeJeg)(d-1)Jeg,{\ displaystyle a_ {i} = {n \ velg i} (d-1) ^ {i},}

det vil si den i -de binomiale koeffisienten for orden n multiplisert med antall andre bokstaver enn 0 i alfabetet til kraften i . I dette tilfellet er tellerpolynomet P ( X ) lik:

P(X)=∑Jeg=0ikkepåJegXJeg=∑Jeg=0ikke(ikkeJeg)(d-1)JegXJeg=(1+(d-1)X)ikke.{\ displaystyle P (X) = \ sum _ {i = 0} ^ {n} a_ {i} X ^ {i} = \ sum _ {i = 0} ^ {n} {n \ velg i} (d -1) ^ {i} X ^ {i} = {\ Big (} 1+ (d-1) X {\ Big)} ^ {n}.}

Målet er å finne tellerpolynomet til vektene av den doble koden, i eksemplet inneholder den dobbelte koden bare ett enkelt ord, nullordet, dets tellerpolynom er derfor nullpolynomet.

Verktøy

Det endelige vektorrommet som brukes her, nemlig F d n , er en endelig abelisk gruppe for tillegg, dens dobbelte gruppe er derfor endelig og isomorf til ( F d n +), teorien om harmonisk analyse er relativt enkel. I denne sammenheng gjør det det mulig å definere en Fourier-transform som har de vanlige egenskapene som Parseval-likhet eller Poisson-summeringsformelen .

Teorien er ytterligere forenklet på grunn av vektorromsstrukturen til gruppen, det er en isomorfisme mellom gruppen og dens dobbelte rom. Hvis μ er en ikke-triviell tegn på additivgruppen av feltet F d , blir alle tegnene skrives i den følgende form χ y :

∀x∈Fdikkeχy(x)=μ(y.x)medy∈Fdikke.{\ displaystyle \ forall x \ in \ mathbb {F} _ {d} ^ {n} \ quad \ chi _ {y} (x) = \ mu (yx) \ quad {\ text {with}} \ quad y \ in \ mathbb {F} _ {d} ^ {n}.}

Her, “  .  "Betegner den ikke-degenererte bilineære formen definert av følgende likhet, hvis x = ( x i ) og y = ( y i ) betegner to vektorer av F d n  :

x.y=∑Jeg=1ikkexJeg.yJeg.{\ displaystyle xy = \ sum _ {i = 1} ^ {n} x_ {i} .y_ {i}.}

MacWilliams identitet

Med notasjonene i forrige avsnitt, hvis Q ( X ) betegner tellerpolynomet til vektene av den doble koden til C , blir følgende likhet bekreftet:

Spørsmål(X)=1dk(1+(d-1)X)ikkeP(1-X1+(d-1)X).{\ displaystyle Q (X) = {\ frac {1} {d ^ {k}}} {\ Big (} 1+ (d-1) X {\ Big)} ^ {n} P {\ Big (} {\ frac {1-X} {1+ (d-1) X}} {\ Big)}.} Demonstrasjon

Betrakt funksjon g av F d n i det kommutative ringen av polynomer med komplekse koeffisienter , definert av: VS[X]{\ displaystyle {} ^ {\ mathbb {C} [X]}}

∀x∈Fdikkeg(x)=∑y∈Fdikkeμ(x.y)Xw(y)medw(y)=∑Jeg=0ikkevs.(yJeg).{\ displaystyle \ forall x \ in \ mathbb {F} _ {d} ^ {n} \ quad g (x) = \ sum _ {y \ in \ mathbb {F} _ {d} ^ {n}} \ mu (xy) X ^ {w (y)} \ quad {\ text {with}} \ quad w (y) = \ sum _ {i = 0} ^ {n} c (y_ {i}).}

Her betegner funksjon av F d i hvilken med 0 tilknyttede 0 og med eventuelle andre element tilknyttede 1. Søknaden tilsvarer derfor den vekt Hamming funksjon . Nok en gang betegner ( y i ) de forskjellige koordinatene til y på det kanoniske grunnlaget for F d n . vs.{\ displaystyle c}IKKE{\ displaystyle {} ^ {\ mathbb {N}}}w{\ displaystyle w}

• Polynomet Q ( X ) som er definert ved den følgende ligning, er enumeratoren polynomiske vektene av dual-kode C .

Spørsmål(X)=1qk∑vs.∈VSg(vs.).{\ displaystyle Q (X) = {\ frac {1} {q ^ {k}}} \ sum _ {c \ in C} g (c).}

Definisjonen av polynomet Q ( X ) viser at:

Spørsmål(X)=1qk∑vs.∈VSg(vs.)=1qk∑y∈Fdikke∑vs.∈VSμ(vs..y)Xw(y)=1qk∑y∈FdikkebyXw(y)medby=∑vs.∈VSμ(vs..y).{\ displaystyle 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 (cy) X ^ {w (y)} = {\ frac {1} {q ^ {k}}} \ sum _ {y \ in \ mathbb {F} _ {d} ^ {n}} b_ {y} X ^ {w (y)} \ quad {\ text {with}} \ quad b_ {y} = \ sum _ {c \ in C} \ mu (cy).}

Det er derfor nødvendig å beregne b y . Hvis y er et element av den doble koden, er cy lik 0 for ethvert c- element av C , vi trekker ut at μ ( c . Y ) er lik 1 og b y er lik kardinaliteten til C , det vil si - dvs. q k . Hvis det ikke er noe element av C , er applikasjonen til c kombinerer μ ( c . Der ) er en ikke-privat karakter av gruppen ( C +). Det er derfor ortogonalt i forhold til trivial karakter, denne ortogonalitetsforholdet uttrykker det faktum at b y er null. Vi utleder at:

Spørsmål(X)=∑vs.∈VS⊥Xw(vs.).{\ displaystyle Q (X) = \ sum _ {c \ in C ^ {\ perp}} X ^ {w (c)}.}

Denne siste likestillingen viser at Q ( X ) faktisk er det annullerende polynomet til den dobbelte koden.

• polynomet Q ( X ) tilfredsstiller følgende likhet:

Spørsmål(X)=1dk(1+(d-1)X)ikkeP(1-X1+(d-1)X).{\ displaystyle Q (X) = {\ frac {1} {d ^ {k}}} {\ Big (} 1+ (d-1) X {\ Big)} ^ {n} P {\ Big (} {\ frac {1-X} {1+ (d-1) X}} {\ Big)}.}

Hvis ( c i ) er koordinatene til c og ( y i ) den til y , så har følgende likheter:

g(vs.)=1qk∑y∈Fdikkeμ(vs..y)Xw(y)=1qk∑y∈Fdikke∏Jeg=1ikkeμ(vs.Jeg.yJeg)Xvs.(yJeg).{\ displaystyle g (c) = {\ frac {1} {q ^ {k}}} \ sum _ {y \ in \ mathbb {F} _ {d} ^ {n}} \ mu (cy) 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})}.}

La oss deretter beregne følgende verdi:

SJeg=∑y∈Fdμ(vs.Jeg.y)Xvs.(y).{\ displaystyle S_ {i} = \ sum _ {y \ in \ mathbb {F} _ {d}} \ mu (c_ {i} .y) X ^ {c (y)}.}

Dersom c i er null så μ ( c i . Y ) er lik 1 for enhver verdi av y , c ( y ) = 0 hvis y er null, og en annen måte, følger det at S i = 1 + ( q - 1 ) X. Hvis c i ikke er null, er applikasjonen som skal assosieres μ ( c i . Y ) en ikke-karakteristisk karakter av additivgruppen i feltet F d . Det er derfor vinkelrett på den trivielle karakteren og:

∑y∈Fdμ(vs.Jeg.y)=0derfor∑y∈Fdy≠0μ(vs.Jeg.y)=-1{\ displaystyle \ sum _ {y \ in \ mathbb {F} _ {d}} \ mu (c_ {i} .y) = 0 \ quad {\ text {derfor}} \ quad \ sum _ {y \ in \ mathbb {F} _ {d} y \ neq 0} \ mu (c_ {i} .y) = - 1 \;}

Vi utleder følgende likheter:

SJeg=∑y∈Fdμ(vs.Jeg.y)Xvs.(y)=μ(vs.Jeg.0)X0+(∑y∈Fdy≠0μ(vs.Jeg.y))X=1-X.{\ displaystyle 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.}

Vi utleder følgende likhet:

g(vs.)=1qk(1+(q-1)X)ikke-w(vs.)(1-X)w(vs.)=1qk(1+(q-1)X)ikke(1-X1+(q-1)X)w(vs.).{\ displaystyle g (c) = {\ frac {1} {q ^ {k}}} {\ Big (} 1+ (q-1) X {\ Big)} ^ {nw (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)}.}

Vi oppnår således for uttrykk for Q ( X ) følgende likhet:

Spørsmål(X)=1qk(1+(q-1)X)ikke∑vs.∈VS(1-X1+(q-1)X)w(vs.)=1dk(1+(d-1)X)ikkeP(1-X1+(d-1)X),{\ displaystyle Q (X) = {\ frac {1} {q ^ {k}}} {\ Big (} 1+ (q-1) X {\ Big)} ^ {n} \ sum _ {c \ i 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} } {\ Stor)},}

som avslutter demonstrasjonen.

applikasjoner

Kode uten redundans

Tenk på koden uten redundans i eksemplet i det objektive avsnittet, tellerpolynomet til kodes vekt er:

P(X)=(1+(d-1)X)ikke.{\ displaystyle P (X) = {\ Big (} 1+ (d-1) X {\ Big)} ^ {n}.}

Identiteten til MacWilliams gir verdien av Q ( X ) tellerpolynom av dobbeltkoden:

Spørsmål(X)=1dikke(1+(d-1)X)ikke(1+(d-1)1-X1+(d-1)X)ikke,{\ displaystyle 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},}

som gir følgende bånd:

Spørsmål(X)=1dikke(1+(d-1)X)ikke(d1+(d-1)X)ikke=1.{\ displaystyle Q (X) = {\ frac {1} {d ^ {n}}} {\ Big (} 1+ (d-1) X {\ Big)} ^ {n} {\ Big (} { \ frac {d} {1+ (d-1) X}} {\ Big)} ^ {n} = 1.}

Dobbeltkoden har faktisk et enkelt element med null vekt, identiteten til MacWilliams gir faktisk tellerpolynomet til dobbeltkoden.

Hamming-kode

La oss bestemme tellerpolynomet til vekten av Hamming-koden. Metoden som brukes her består i å direkte bestemme tellerpolynomet til den dobbelte koden og bruke identiteten til MacWilliams for å utlede den for Hamming-koden.

Notasjonene som brukes her er de i den detaljerte artikkelen, spesielt m betegner verdien n - k , det vil si dimensjonen til den dobbelte koden og H betegner kontrollmatrisen til koden.

• Alle de dobbelte kodeordene fra Hamming-koden som ikke er null, har en vekt lik d m-1 .

Faktisk består den dobbelte koden av ord med formen t x . H der x beskriver vektorrommet F d m . La oss betegne ved (h i ) for i varierende fra 1 til n i n rekkene i matrisen H som også er vektorer av dimensjon m . Søknaden til x assosierer vektoren ( x . H i ) er derfor en isomorfi mellom F d m og dual-kode.

La A være settet med vektorer a av F d m slik at a . x er forskjellig fra 0. Skjæringen av klassene av projeksjonsrommet med A danner en skillevegg av A . I tillegg vil en . x er forskjellig fra 0 hvis og bare hvis λ a . x er forskjellig fra 0 for enhver λ element av F d * . Følgelig hver klasse av delingen av A inneholder d - 1 elementer. Til slutt beskriver vektorene h i et system med representanter for klassene i det projiserende rommet til F d m (se avsnitt Eksistens og unikhet i det generelle tilfellet ) . Vi utleder at vekten til ( x . H i ) er lik brøkdelen av telleren kardinalen til A og nevneren d - 1.

Komplementet til A , hvis x ikke er null, er et hyperplan av F d m, derfor et sett med kardinal d m - 1 . Kardinaliteten til A er derfor lik d m - 1 . ( d - 1). Vekten av ( x . H i ) er da lik d m - 1 hvis x ikke er null.

• Tellerpolynomet til vektene av Hamming-koden P ( X ) er definert av følgende likhet:

P(X)=1dm((1+(d-1)X)ikke+(dm-1)(1+(d-1)X)ikke-dm-1(1-X)dm-1).{\ displaystyle P (X) = {\ frac {1} {d ^ {m}}} {\ Bigg (} {\ Big (} 1+ (d-1) X {\ Big)} ^ {n} + (d ^ {m} -1) {\ Big (} 1+ (d-1) X {\ Big)} ^ {nd ^ {m-1}} (1-X) ^ {d ^ {m-1 }} {\ Bigg)}.}

Faktisk er tellerpolynomet for vektene av den dobbelte koden som følger:

Spørsmål(X)=1+(dm-1)Xdm-1.{\ displaystyle Q (X) = 1 + (d ^ {m} -1) X ^ {d ^ {m-1}}.}

Identiteten til MacWilliams viser at:

P(X)=1dm(1+(d-1)X)ikke(1+(dm-1)(1-X1+(d-1)X)dm-1)=1dm((1+(d-1)X)ikke+(dm-1)(1+(d-1)X)ikke-dm-1(1-X)dm-1),{\ displaystyle 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)} ^ {nd ^ {m-1}} (1-X) ^ {d ^ {m-1}} { \ Bigg)},}

som avslutter demonstrasjonen.

Se også

Bibliografi

• Michel Demazure , Course of algebra: primality, divisibility, codes [ detalj of editions ]
• (i) Jessie MacWilliams og Neil Sloane , Theory of Error-Correcting Codes, Nord-Holland , 1977 ( ISBN  978-0-444-85009-6 )
• André Warusfel , Endelige algebraiske strukturer, Éditions Hachette , 1971
• Gabriel Peyré, den diskrete algebraen til Fourier-transformasjonen, Éditions Ellipses , 2004 ( ISBN  978-2-72981867-8 )

Eksterne linker

• Christine Bachoc, “  Kode kurs  ” , ved Bordeaux I universitet , 2004-2005
• Christine Bachoc, “  Discrete Mathematics of the Fourier Transform  ” , ved Universitetet i Bordeaux I , 2004-2005
• Alexei Pantchichkine, "  Kryptologi, sikkerhet og koding av informasjon  " , på Universitetet i Grenoble I

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">