Enumeratorpolynom

I kodningsteorin anger viktuppräkningspolynomet för en binär linjär kod antalet ord för varje möjlig Hamming - vikt .

Låt $C\subset \mathbb {F} _{2}^{n}$ vara en binär linjär kodlängd $n$ . Viktfördelningen är talföljden

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

ange antalet kodord c i C med vikten t som t sträcker sig från 0 till n . Viktuppräknaren det bivariata polynomet

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

Grundläggande egenskaper

$W(C;0,1)=A_{0}=1$
$W(C;1,1)=\summa _{w=0}^{n}A_{w}=|C|$
$W(C;1,0)=A_{n}=1{\mbox{ if }}( 1,\ldots ,1)\i C\ {\mbox{ och }}0{\mbox{ annars}}$
$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}$

MacWilliams identitet

Beteckna den dubbla koden för $C\subset \mathbb {F} _{2}^{n}$ med

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

(där $\langle \ ,\ \rangle$ betecknar vektorpunktprodukten och som tas över $\mathbb {F} _{2}$ ).

MacWilliams identitet säger det

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

Identiteten är uppkallad efter Jessie MacWilliams .

Avståndsräknare

Avståndsfördelningen eller inre fördelningen av en kod C med storleken M och längden n är talföljden

A_{i}={\frac {1}{M}}\# \left\lbrace (c_{1},c_{2})\in C\times C\mid d(c_{1},c_{2})=i\right\rbrace

där i sträcker sig från 0 till n . Avståndsuppräkningspolynomet är _

A(C;x,y)=\summa _{i=0}^{n}A_{i}x ^{i}y^{ni}

och när C är linjär är detta lika med vikträknaren.

Den yttre fördelningen av C är 2 ⁿ -x- n +1-matrisen B med rader indexerade med element av GF(2) ⁿ och kolumner indexerade med heltal 0... n , och poster

B_{x,i}=\#\left\lbrace c\in C\mid d(c,x)=i\right\rbrace .

₀ Summan av raderna i B är M gånger den inre fördelningsvektorn ( A ,..., A _n ).

En kod C är regelbunden om raderna i B som motsvarar kodorden i C alla är lika.

Hill, Raymond (1986). En första kurs i kodningsteori . Oxford Applied Mathematics and Computing Science Series. Oxford University Press . s. 165–173 . ISBN 0-19-853803-0 .
Pless, Vera (1982). Introduktion till teorin om felkorrigerande koder . Wiley-Interscience-serien i diskret matematik. John Wiley & Sons . s. 103–119. ISBN 0-471-08684-3 .
JH van Lint (1992). Introduktion till kodningsteori . GTM . Vol. 86 (andra upplagan). Springer-Verlag . ISBN 3-540-54894-7 . Kapitel 3.5 och 4.3.