McWilliams teorem

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 15. maj 2019; checks kræver 2 redigeringer .

I kodningsteorien etablerer McWilliams-sætningen en forbindelse mellem vægtfunktionen af en lineær kode og vægtfunktionen af dens dobbeltkode . En af konsekvenserne af sætningen er at opnå en øvre grænse for en kodes kardinalitet. Opkaldt efter den engelske Florence McWilliams

Lad en binær lineær kode af længde . Kodens vægtfordeling er en numerisk sekvens , der angiver antallet af kodeord med vægt : ${\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\}

Vægtfunktion (eller vægttæller ) er et polynomium af to variable

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

Elementære egenskaber for vægtfunktionen

$\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,$ når ellers $(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}.$

Udtalelse af sætningen

Betegn den dobbelte kode med $C$

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

hvor angiver skalarproduktet af vektorer i et vektorrum . $\langle \,,\,\rangle$ $\mathbb{F}_2^n$

McWilliams sætning siger det

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

Litteratur

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

Se også

Kravchuk polynomier
Delsartes sætning