McWilliams tétel

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. május 15-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A kódoláselméletben a McWilliams-tétel kapcsolatot hoz létre egy lineáris kód súlyfüggvénye és a kettős kód súlyfüggvénye között. A tétel egyik következménye, hogy egy kód számosságának felső korlátját kapjuk. Nevét Florence McWilliams

Legyen egy hosszúságú bináris lineáris kód . A kód súlyeloszlása egy numerikus sorozat, ahol a súllyal rendelkező kódszavak számát jelöli : ${\displaystyle C\subset \mathbb {F} _{2}^{n))$ $n$ $C$ $\{A_{w}\}_{w=0}^{n},$ $\displaystyle A_{w}$ $C$ $w$

A_{w}=\#\{c\in C\mid {\mathsf {w}}(c)=w\}

A súlyfüggvény (vagy súlyszámláló ) két változó polinomja

W(C;x,y)=\sum _{w=0}^{n}A_{w}x^{w}y^{nw}.

A súlyfüggvény elemi tulajdonságai

$\displaystyle W(C;0,1)=A_{0}=1.$
$\displaystyle W(C;1,1)=\sum _{w=0}^{n}A_{w}=|C|.$
$\displaystyle W(C;1,0)=A_{n}=1,$ amikor másképp $(1,\ldots ,1)\in C,$ $\displaystyle W(C;1,0)=A_{n}=0.$
$\displaystyle W(C;1,-1)=\sum _{w=0}^{n}A_{w}(-1)^{nw}=A_{n}+(-1)^ {1}A_{n-1}+\ldots +(-1)^{n-1}A_{1}+(-1)^{n}A_{0}.$

tétel állítása

Jelölje a kettős kódot $C$

C^{\perp }=\{x\in \mathbb {F} _{2}^{n}\,\mid \,\forall c\in C:\langle x,c\rangle =0 {\mbox{ }}\},

ahol a vektortérben lévő vektorok skaláris szorzatát jelöli . $\langle \,,\,\rangle$ $\mathbb{F}_2^n$

A McWilliams-tétel ezt mondja

W(C^{\perp };x,y)={\frac {1}{\mid C\mid }}W(C;yx,y+x).

Irodalom

Pless V. Bevezetés a hibajavító kódok elméletébe . - Wiley, New York, 8.2. §, 1998.
Lint van JH Bevezetés a kódoláselméletbe . – Springer-Verlag, Berlin, 1999., 3.5.
Roth R.M. Bevezetés a kódoláselméletbe . - Cambridge University Press , Cambridge, 4.4. §, 2006.

Lásd még

Kravcsuk polinomok
Delsarte tétele