McWilliamsin lause

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 15.5.2019 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Koodausteoriassa McWilliamsin teoreema muodostaa yhteyden lineaarisen koodin painofunktion ja sen kaksoiskoodin painofunktion välille . Yksi lauseen seurauksista on saada koodin kardinaalisuuden yläraja. Nimetty englantilaisen Florence McWilliamsin mukaan

Olkoon binääri lineaarinen koodi pituus . Koodin painojakauma on numeerinen sekvenssi, jossa ilmaisee painosanojen lukumäärää : ${\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\}

Painofunktio (tai painonlaskija ) on kahden muuttujan polynomi

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

Painofunktion perusominaisuudet

$\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,$ kun toisin $(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}.$

Lauseen lause

Merkitse kaksoiskoodi merkillä $C$

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

jossa tarkoittaa vektoreiden skalaarituloa vektoriavaruudessa . $\langle \,,\,\rangle$ $\mathbb{F}_2^n$

McWilliamsin lause sanoo sen

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

Kirjallisuus

Pless V. Johdatus virheenkorjauskoodien teoriaan . - Wiley, New York, § 8.2, 1998.
Lint van JH Johdatus koodausteoriaan . — Springer-Verlag, Berliini, § 3.5, 1999.
Roth R.M. Johdatus koodausteoriaan . - Cambridge University Press , Cambridge, § 4.4, 2006.

Katso myös

Kravchukin polynomit
Delsarten lause