Teorema McWilliams

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 15 mai 2019; verificările necesită 2 modificări .

În teoria codificării, teorema McWilliams stabilește o legătură între funcția de greutate a unui cod liniar și funcția de greutate a codului său dual . Una dintre consecințele teoremei este obținerea unei limite superioare a cardinalității unui cod. Numit după englez Florence McWilliams

Fie un cod liniar binar de lungime . Distribuția de pondere a codului este o secvență numerică în care denotă numărul de cuvinte de cod cu greutate : $C\subset \mathbb {F} _{2}^{n)$ $n$ $C$ $\{A_{w}\}_{w=0}^{n},$ $\displaystyle A_{w}$ $C$ $w$

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

Funcția de pondere (sau enumeratorul de ponderi ) este un polinom de două variabile

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

Proprietăți elementare ale funcției de greutate

$\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,$ când altfel $(1,\ldots,1)\în 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}.$

Enunțul teoremei

Indicați codul dual prin $C$

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

unde denotă produsul scalar al vectorilor dintr-un spațiu vectorial . $\langle \,,\,\rangle$ $\mathbb{F}_2^n$

Teorema McWilliams spune asta

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

Literatură

Pless V. Introducere în teoria codurilor de corectare a erorilor . - Wiley, New York, § 8.2, 1998.
Lint van JH Introducere în teoria codificării . — Springer-Verlag, Berlin, § 3.5, 1999.
Roth R.M. Introducere în teoria codificării . - Cambridge University Press , Cambridge, § 4.4, 2006.

Vezi și

polinoame Kravchuk
teorema lui Delsarte