McWilliams teorem

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 15 maj 2019; kontroller kräver 2 redigeringar .

I kodningsteorin etablerar McWilliams sats ett samband mellan viktfunktionen för en linjär kod och viktfunktionen för dess dubbla kod. En av konsekvenserna av satsen är att få en övre gräns för en kods kardinalitet. Uppkallad efter den engelska Florence McWilliams

Låt en binär linjär kod av längd . Viktfördelningen av koden är en numerisk sekvens där antalet kodord med vikt anger : ${\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\}

Viktfunktion (eller viktuppräkning ) är ett polynom av två variabler

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

Elementära egenskaper för viktfunktionen

$\displaystyle W(C;0,1)=A_{0}=1.$
$\displaystyle W(C;1,1)=\summa _{w=0}^{n}A_{w}=|C|.$
$\displaystyle W(C;1,0)=A_{n}=1,$ när annars $(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}.$

Uttalande av satsen

Beteckna den dubbla koden med $C$

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

där betecknar skalärprodukten av vektorer i ett vektorrum . $\langle \,,\,\rangle$ $\mathbb{F}_2^n$

McWilliams sats säger det

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

Litteratur

Pless V. Introduktion till teorin om felkorrigerande koder . - Wiley, New York, § 8.2, 1998.
Lint van JH Introduktion till kodningsteori . — Springer-Verlag, Berlin, § 3.5, 1999.
Roth R.M. Introduktion till kodningsteori . - Cambridge University Press , Cambridge, § 4.4, 2006.

Se även

Kravchuk polynom
Delsartes sats