MacWilliams identitás

A matematika , a személyazonosságát MacWilliams egy olyan alkalmazás, a harmonikus analízis véges Abel-csoport , ha a csoport egy vektortér a dimenzió , mint egy véges . Jessie MacWilliams matematikusról kapta a nevét .

Ez főleg a kódot elmélet , a lineáris kódok , összeköti a számlálóra polinomok (en) a súlyok egy kódot, és annak kettős , ily módon lehetővé téve, például, hogy meghatározzák a számlálóra polinomja a súlyok a duális a a kódé.

A probléma helyzete

Cél

Ebben a cikkben C egy paraméterkódot [ n , k , δ] jelöl az F d véges mező fölött, ahol d a p prímszám teljes egészének hatványa .

A cél MacWilliams " identitás az, hogy válaszoljon a következő kérdésre: legyen C egy egyenes kódot, mi az a minimális távolság a Hamming értelemben a kettős kód?

A válasz nem csak a C minimális távolságától függ , valójában ismerni kell a C kód súlyainak teljes eloszlását , ami a következő meghatározást eredményezi:

A számlálóra polinom a súlyok a polinom amelynek együtthatók értéke a pozitív egész szám úgy, hogy ha i egy pozitív egész szám a együtthatója egytagú X i egyenlő a szavak száma a Hamming súlya kód egyenlő, hogy i .

A súlyok felsoroló polinomja tehát megfelel a kód különböző súlyainak eloszlásának.

Vegyük például azt az esetet, amikor n egyenlő k-vel , vagyis azzal, ahol nincs redundancia, az i sugár és a nulla vektor középpontja pontosan egy i pontot tartalmaz:

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

vagyis az n sorrend i- edik binomiális együtthatója megszorozva az ábécé 0-tól eltérő betűinek számával az i hatványra . Ebben az esetben a P ( X ) számláló polinom egyenlő:

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

A cél a kettős kód súlyainak felsoroló polinomjának megtalálása, a példában a kettős kód csak egyetlen szót tartalmaz, a null szót, a felsoroló polinom tehát a null polinom.

Eszközök

Az itt használt véges vektortér , nevezetesen az F d n , véges abeli csoport az összeadáshoz, kettős csoportja ezért véges és izomorf az ( F d n +) iránt, a harmonikus elemzés elmélete viszonylag egyszerű. Ebben az összefüggésben lehetővé teszi egy olyan Fourier-transzformáció definiálását, amelynek olyan szokásos tulajdonságai vannak, mint a Parseval-egyenlőség vagy a Poisson-összegzési képlet .

Az elmélet tovább egyszerűsödik a csoport vektorterstruktúrája miatt, izomorfizmus van a csoport és kettős tere között. Ha μ nem triviális karakter az F d mező additív csoportján, akkor az összes karaktert a következő χ y formában írjuk :

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

Itt „ . "Az alábbi egyenlőség által meghatározott nem degenerált bilinear formát jelöli, ha x = ( x i ) és y = ( y i ) az F d n két vektorát jelöli :

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

MacWilliams identitás

Az előző bekezdés jelöléseivel, ha Q ( X ) a C kettős kód súlyainak felsoroló polinomját jelöli , akkor a következő egyenlőséget ellenőrizzük:

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

Demonstráció

Tekintsük az g az F d n a a kommutatív gyűrű polinomok komplex együtthatók által meghatározott: ${\ 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 {with}} \ quad w (y) = \ sum _ {i = 0} ^ {n} c (y_ {i}).}

Itt, kijelöli a funkciója F d az , amely a 0 társult 0 és bármely más elem társult 1. A kérelmet tehát megfelel az Hamming tömeg funkciót . Ismételten ( y i ) az y különböző koordinátáit jelöli F d n kanonikus alapjaiban . $vs.$ ${} ^ {\ mathbb {N}}$ $w$

A következő egyenlet által definiált Q ( X ) polinom a C kettős kód felsoroló polinom súlya .

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

A Q ( X ) polinom meghatározása azt mutatja, hogy:

{\ 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 \ C} \ mu (cy).}

Ezért szükség van b y kiszámítására . Ha y a kettős kód egyik eleme, akkor cy egyenlő 0-val a C bármely c eleménél , arra következtetünk, hogy μ ( c . Y ) egyenlő 1-vel, és b y egyenlő a C számosságával , vagyis - azaz q k . Ha nincs C eleme , akkor a c-hez való alkalmazás egyesíti a μ-t ( c . Ott ) a csoport nem triviális karaktere ( C +). Ezért ortogonális a triviális karakterre, ez az ortogonalitás-reláció azt a tényt fejezi ki, hogy b y nulla. Arra következtetünk, hogy:

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

Ez az utolsó egyenlőség azt mutatja, hogy Q ( X ) valóban a kettős kód törlő polinomja.

a Q ( X ) polinom kielégíti a következő egyenlőséget:

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

Ha ( c i ) a c és ( y i ) koordinátái y , akkor a következő egyenlőségek érvényesek:

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

Ezután számítsuk ki a következő értéket:

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

Ha c i nulla, akkor μ ( c i . Y ) egyenlő 1-vel bármely y érték esetén , c ( y ) = 0, ha y nulla, és 1 egyébként, ebből az következik, hogy S i = 1 + ( q - 1 ) X. Ha c i nem nulla, akkor az alkalmazást kell kapcsolódó μ ( C i . Y ) egy nem triviális jellegű az adalékanyag-csoport a mező F d . Ezért merőleges a triviális karakterre és:

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

A következő egyenlőségekre következtetünk:

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

A következő egyenlőségre következtetünk:

{\ displaystyle g (c) = {\ frac {1} {q ^ {k}}} {\ Nagy (} 1+ (q-1) X {\ Nagy)} ^ {nw (c)} {\ Nagy (} 1-X {\ Big)} ^ {w (c)} = {\ frac {1} {q ^ {k}}} {\ Big (} 1+ (q-1) X {\ Big)} ^ {n} {\ Nagy (} {\ frac {1-X} {1+ (q-1) X}} {\ Nagy)} ^ {w (c)}.}

Így Q ( X ) kifejezésére a következő egyenlőséget kapjuk :

{\ displaystyle Q (X) = {\ frac {1} {q ^ {k}}} {\ Nagy (} 1+ (q-1) X {\ Nagy)} ^ {n} \ összeg _ {c \ itt: 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} } {\ Nagy)},}

amely befejezi a tüntetést.

Alkalmazások

Kód redundancia nélkül

Tekintsük a kódot az objektív bekezdés példájának redundanciája nélkül, a kód súlyainak felsoroló polinomja:

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

A MacWilliams identitása megadja a kettős kód Q ( X ) felsoroló polinomjának értékét :

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

amely a következő kapcsolatokat adja:

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

A kettős kódnak valóban egyetlen, nulla súlyú eleme van, a MacWilliams azonosítója valóban megadja a kettős kód felsoroló polinomját.

Hamming-kód

Határozzuk meg a Hamming-kód súlyainak felsoroló polinomját. Az itt használt módszer abból áll, hogy közvetlenül meghatározzuk a kettős kód felsoroló polinomját, és MacWilliams identitását használjuk a Hamming kód levezetésére.

Az itt használt jelölések a részletes cikkre vonatkoznak, különösen m jelöli az n - k értéket , vagyis a kettős kód dimenzióját, H pedig a kód vezérlő mátrixát.

A Hamming-kód összes nem nulla kettős kód szavának súlya megegyezik d m-1-vel .

Valójában a kettős kód t x alakú szavakból áll . H ahol x az F d m vektorteret írja le . Jelöljük (h i ) az i változó 1-től n az N mátrix oszlopait H amelyek szintén vektorok dimenzió m . Az alkalmazás x társítja a vektor ( x . H i ) tehát egy izomorfizmus közötti F d m , és a duális kód.

Legyen A az a készlet vektorok egy az F d m úgy, hogy a . X jelentése más, mint 0. A metszéspontja az osztályok a projektív tér Egy alkotnak partíció a A . Ezenkívül a . x akkor és csak akkor különbözik a 0-tól, ha λ a . x különbözik 0-tól F d * bármely λ eleménél . Következésképpen minden osztály a partíció A tartalmaz d - 1 elemek. Végül a h i vektorok leírják az F d m projektív tér osztályainak képviselőinek rendszerét (vö. A Létezés és egyediség általános bekezdésben ) . Azt következtetni, hogy a súlya ( x . H i ) egyenlő a frakció számláló a bíboros A és nevező d - 1.

A komplement a A , ha x nem nulla, egy hipersík az F d m , ezért egy sor kardinális d m - 1 . A számossága A ezért egyenlő azzal, d m - 1 . ( d - 1). A súlya ( x . H i ) ezután egyenlő d m - 1 , ha x értéke nem nulla.

A P ( X ) Hamming-kód súlyainak felsoroló polinomját a következő egyenlőség határozza meg:

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

Valójában a kettős kód súlyainak felsoroló polinomja a következő:

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

MacWilliams személyazonossága azt mutatja, hogy:

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

amely befejezi a tüntetést.

Lásd is

Bibliográfia

Michel Demazure , Az algebra tanfolyama: elsődlegesség, oszthatóság, kódok [ a kiadások részlete ]
(in) Jessie MacWilliams és Neil Sloane , A hibajavító kódok elmélete, Észak-Hollandia , 1977 ( ISBN 978-0-444-85009-6 )
André Warusfel , Véges algebrai struktúrák, Éditions Hachette , 1971
Gabriel Peyré, A Fourier-transzformáció diszkrét algebra, Éditions Ellipses , 2004 ( ISBN 978-2-72981867-8 )

Külső linkek

Christine Bachoc, „ Code course ” , a Bordeaux I. Egyetemen , 2004-2005
Christine Bachoc, „ A Fourier-transzformáció diszkrét matematikája ” , a Bordeaux-i Egyetemen , 2004-2005
Alexei Pantchichkine, "Az kriptológia, az információk biztonsága és kódolása " , a Grenoble Egyetemen