Identitate MacWilliams

În matematică , identitatea lui MacWilliams este o aplicație a analizei armonice pe un grup abelian finit , dacă grupul este un spațiu vectorial de dimensiune peste un câmp finit . Acesta poartă numele matematicianului Jessie MacWilliams .

Este utilizat în principal în teoria codurilor , pentru codurile liniare , conectează polinomii enumeratorilor (en) ai greutăților unui cod și dualul acestuia , făcând astfel posibilă, de exemplu, determinarea polinomului enumerator al greutăților dualului din din cea a codului.

Poziția problemei

Poartă

În acest articol C denotă un cod de parametru [ n , k , δ] peste câmpul finit F d unde d este un număr întreg de putere cu un număr prim p .

Obiectivul identității lui MacWilliams este să răspundă la următoarea întrebare: fie C un cod liniar, care este distanța minimă în sensul Hamming al codului său dual?

Răspunsul nu depinde doar de distanța minimă a lui C , este de fapt necesar să se cunoască întreaga distribuție a greutăților codului C , care dă naștere următoarei definiții:

Enumeratorul Polinomul a greutăților este polinomul a căror coeficienți cu valoare în numere întregi pozitive astfel încât , dacă i este un întreg pozitiv coeficientul de monom X i este egal cu numărul de cuvinte de cod greutate Hamming egal cu i .

Prin urmare, polinomul enumerator al greutăților corespunde distribuției diferitelor greutăți ale codului.

Luați în considerare, de exemplu, cazul în care n este egal cu k , adică cel în care nu există redundanță, sfera de rază i și de centru vectorul zero conține exact a i puncte cu:

{\ displaystyle a_ {i} = {n \ alege i} (d-1) ^ {i},}

adică al i -lea coeficient binomial de ordine n înmulțit cu numărul de litere altele decât 0 din alfabet la puterea i . În acest caz, polinomul enumerator P ( X ) este egal cu:

{\ displaystyle P (X) = \ sum _ {i = 0} ^ {n} a_ {i} X ^ {i} = \ sum _ {i = 0} ^ {n} {n \ alege i} (d -1) ^ {i} X ^ {i} = {\ Big (} 1+ (d-1) X {\ Big)} ^ {n}.}

Obiectivul este de a găsi polinomul enumerator al greutăților codului dual, în exemplu codul dual conține doar un singur cuvânt, cuvântul nul, polinomul său enumerator este deci polinomul nul.

Instrumente

Spațiul vectorial finit utilizat aici, și anume F d n , este un grup abelian finit pentru adiție, grupul său dual este deci finit și izomorf la ( F d n +), teoria analizei armonice este relativ simplă. În acest context, face posibilă definirea unei transformate Fourier având proprietăți obișnuite precum egalitatea Parseval sau formula de însumare Poisson .

Teoria este simplificată în continuare din cauza structurii spațiului vectorial al grupului, există un izomorfism între grup și spațiul său dual. Dacă μ este un caracter non-trivial din grupul aditiv al câmpului F d , toate caracterele sunt scrise în următoarea formă χ y :

{\ displaystyle \ forall x \ in \ mathbb {F} _ {d} ^ {n} \ quad \ chi _ {y} (x) = \ mu (yx) \ quad {\ text {cu}} \ quad y \ in \ mathbb {F} _ {d} ^ {n}.}

Aici, „ . "Denotă forma bilineară nedegenerată definită de următoarea egalitate, dacă x = ( x i ) și y = ( y i ) denotă doi vectori ai lui F d n :

{\ displaystyle xy = \ sum _ {i = 1} ^ {n} x_ {i} .y_ {i}.}

Identitate MacWilliams

Cu notațiile paragrafului anterior, dacă Q ( X ) denotă polinomul enumerator al ponderilor codului dual al lui C , atunci se verifică următoarea egalitate:

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

Demonstrație

Luați în considerare funcția g de F d n în inelul comutativ al polinoame cu complexe coeficienți , definite prin: ${\ displaystyle {} ^ {\ mathbb {C} [X]}}$

{\ 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 {cu}} \ quad w (y) = \ sum _ {i = 0} ^ {n} c (y_ {i}).}

Aici, desemnează funcția F d în care cu 0 asociază 0 și cu orice alt element asociază 1. Aplicația corespunde deci funcției de greutate Hamming . Încă o dată, ( y i ) reprezintă diferitele coordonatele y în baza canonică F d n . $vs.$ ${} ^ {\ mathbb {N}}$ $w$

Polinomul Q ( X ) definită prin următoarea ecuație, este greutățile enumeratorul polinom de cod dual C .

{\ displaystyle Q (X) = {\ frac {1} {q ^ {k}}} \ sum _ {c \ în C} g (c).}

Definiția polinomului Q ( X ) arată că:

{\ 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 {cu}} \ quad b_ {y} = \ sum _ {c \ în C} \ mu (cy).}

Prin urmare, este necesar să se calculeze b y . Dacă y este un element al codului dual, atunci cy este egal cu 0 pentru orice element c al lui C , deducem că μ ( c . Y ) este egal cu 1 și b y este egal cu cardinalitatea lui C , adică - adică q k . Dacă nu există niciun element al lui C , atunci aplicația la c combină μ ( c . Acolo ) există un caracter netivial al grupului ( C +). Prin urmare, este ortogonală cu caracterul banal, această relație de ortogonalitate exprimă faptul că b y este zero. Deducem că:

{\ displaystyle Q (X) = \ sum _ {c \ in C ^ {\ perp}} X ^ {w (c)}.}

Această ultimă egalitate arată că Q ( X ) este într-adevăr polinomul de anulare a codului dual.

polinomul Q ( X ) îndeplinește următoarea egalitate:

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

Dacă ( c i ) sunt coordonatele lui c și ( y i ) cele ale lui y , atunci se mențin următoarele egalități:

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

Să calculăm apoi următoarea valoare:

{\ displaystyle S_ {i} = \ sum _ {y \ in \ mathbb {F} _ {d}} \ mu (c_ {i} .y) X ^ {c (y)}.}

Dacă c i este zero, atunci μ ( c i . Y ) este egal cu 1 pentru orice valoare a lui y , c ( y ) = 0 dacă y este zero și 1 în caz contrar, rezultă că S i = 1 + ( q - 1 ) X. Dacă c i nu este zero, atunci aplicația care trebuie asociată μ ( c i . Y ) este un caracter netrivial al grupului aditiv al câmpului F d . Prin urmare, este ortogonală cu caracterul banal și:

{\ displaystyle \ sum _ {y \ in \ mathbb {F} _ {d}} \ mu (c_ {i} .y) = 0 \ quad {\ text {prin urmare}} \ quad \ sum _ {y \ in \ mathbb {F} _ {d} y \ neq 0} \ mu (c_ {i} .y) = - 1 \;}

Deducem următoarele egalități:

{\ 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.}

Deducem următoarea egalitate:

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

Astfel, obținem pentru expresia lui Q ( X ), următoarea egalitate:

{\ displaystyle Q (X) = {\ frac {1} {q ^ {k}}} {\ Big (} 1+ (q-1) X {\ Big)} ^ {n} \ sum _ {c \ în 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)},}

care pune capăt demonstrației.

Aplicații

Cod fără redundanță

Să luăm în considerare codul fără redundanță al exemplului de paragraf al obiectivelor, polinomul enumerator al ponderilor codului este:

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

Identitatea lui MacWilliams dă valoarea polinomului enumeratorului Q ( X ) al codului dual:

{\ 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},}

care dă următoarele legături:

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

Codul dual are într-adevăr un singur element cu greutate zero, identitatea MacWilliams furnizează într-adevăr polinomul enumerator al codului dual.

Cod Hamming

Să determinăm polinomul enumerator al greutăților codului Hamming. Metoda utilizată aici constă în determinarea directă a polinomului enumerator al codului dual și utilizarea identității lui MacWilliams pentru a deduce cea a codului Hamming.

Notările utilizate aici sunt cele din articolul detaliat, în special m denotă valoarea n - k , adică dimensiunea codului dual și H denotă matricea de control a codului.

Toate cuvintele cu cod dual non-zero ale codului Hamming au o greutate egală cu d m-1 .

Într-adevăr, codul dual constă din cuvinte de forma t x . H unde x descrie spațiul vectorial F d m . Să notăm cu (h i ) pentru i variind de la 1 la n cele n coloane ale matricei H care sunt și vectori de dimensiune m . Aplicația la x asociază vectorul ( x . H i ) este deci un izomorfism între F d m și codul dual.

Fie A mulțimea vectorilor a lui F d m astfel încât a . x este alta decât 0. Intersecția claselor spatiului proiectiv cu A formează o partiție de A . În plus, a . x este diferit de 0 dacă și numai dacă λ a . x este diferit de 0 pentru orice element λ al lui F d * . În consecință, fiecare clasă a partiției A conține elemente d - 1. În cele din urmă, vectorii h i descriu un sistem de reprezentanți ai claselor spațiului proiectiv al lui F d m (vezi paragraful Existență și unicitate în cazul general ) . Deducem că greutatea lui ( x . H i ) este egală cu fracția de numărător cardinalul lui A și a numitorului d - 1.

Complementul lui A , dacă x nu este zero, este un hiperplan de F d m, deci un set de cardinale d m - 1 . Cardinalitatea lui A este, prin urmare, egală cu d m - 1 . ( d - 1). Greutatea lui ( x . H i ) este apoi egală cu d m - 1 dacă x nu este zero.

Polinomul enumerator al greutăților codului Hamming P ( X ) este definit de următoarea egalitate:

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

Într-adevăr, polinomul enumerator al ponderilor codului dual este după cum urmează:

{\ displaystyle Q (X) = 1 + (d ^ {m} -1) X ^ {d ^ {m-1}}.}

Identitatea MacWilliams arată că:

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

care pune capăt demonstrației.

Vezi și tu

Bibliografie

Michel Demazure , Cursul algebrei: primalitate, divizibilitate, coduri [ detaliu ediții ]
(în) Jessie MacWilliams și Neil Sloane , Theory of Error-Correcting Codes, North-Holland , 1977 ( ISBN 978-0-444-85009-6 )
André Warusfel , Structuri algebrice finite, Éditions Hachette , 1971
Gabriel Peyré, Algebra discretă a transformatei Fourier, Éditions Ellipses , 2004 ( ISBN 978-2-72981867-8 )

linkuri externe

Christine Bachoc, „ Curs de cod ” , la universitatea Bordeaux I , 2004-2005
Christine Bachoc, „ Matematică discretă a transformatei Fourier ” , la Universitatea din Bordeaux I , 2004-2005
Alexei Pantchichkine, „ Criptologie, securitate și codificare a informațiilor ” , la Universitatea din Grenoble I