Enumerator polynomial

Short description: Specifies the number of words of a binary linear code of each possible Hamming weight

In coding theory, the weight enumerator polynomial of a binary linear code specifies the number of words of each possible Hamming weight.

Let $C\subset {\mathbb{𝔽}}_2^n$ be a binary linear code length $n$. The weight distribution is the sequence of numbers

$A_t=\mathrm{\#}\{c\in C\mid w(c)=t\}$

giving the number of codewords c in C having weight t as t ranges from 0 to n. The weight enumerator is the bivariate polynomial

$W(C;x,y)=\sum _{w=0}^n{A}_w{x}^w{y}^{n-w}.$

Basic properties

1. $W(C;0,1)=A_0=1$
2. $W(C;1,1)=\sum _{w=0}^n{A}_w=|C|$
3. $W(C;1,0)=A_n=1\text{ if }(1,\dots ,1)\in C\text{ and }0\text{ otherwise}$
4. $W(C;1,-1)=\sum _{w=0}^n{A}_w(-1{)}^{n-w}=A_n+(-1{)}^1{A}_{n-1}+\dots +(-1{)}^{n-1}{A}_1+(-1{)}^n{A}_0$

MacWilliams identity

Denote the dual code of $C\subset {\mathbb{𝔽}}_2^n$ by

$C^{\perp }=\{x\in {\mathbb{𝔽}}_2^n\mid ⟨x,c⟩=0\mathrm{\forall }c\in C\}$

(where $⟨,⟩$ denotes the vector dot product and which is taken over ${\mathbb{𝔽}}_2$).

The MacWilliams identity states that

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

The identity is named after Jessie MacWilliams.

Distance enumerator

The distance distribution or inner distribution of a code C of size M and length n is the sequence of numbers

$A_i=\frac{1}{M}\mathrm{\#}\{(c_1,c_2)\in C\times C\mid d(c_1,c_2)=i\}$

where i ranges from 0 to n. The distance enumerator polynomial is

$A(C;x,y)=\sum _{i=0}^n{A}_i{x}^i{y}^{n-i}$

and when C is linear this is equal to the weight enumerator.

The outer distribution of C is the 2ⁿ-by-n+1 matrix B with rows indexed by elements of GF(2)ⁿ and columns indexed by integers 0...n, and entries

$B_{x,i}=\mathrm{\#}\{c\in C\mid d(c,x)=i\}.$

The sum of the rows of B is M times the inner distribution vector (A₀,...,A_n).

A code C is regular if the rows of B corresponding to the codewords of C are all equal.

References

• Hill, Raymond (1986). A first course in coding theory. Oxford Applied Mathematics and Computing Science Series. Oxford University Press. pp. 165–173. ISBN 0-19-853803-0. https://archive.org/details/firstcourseincod0000hill. 
• Pless, Vera (1982). Introduction to the theory of error-correcting codes. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons. pp. 103–119. ISBN 0-471-08684-3. 
• J.H. van Lint (1992). Introduction to Coding Theory. GTM. 86 (2nd ed.). Springer-Verlag. ISBN 3-540-54894-7. https://archive.org/details/introductiontoco0000lint.  Chapters 3.5 and 4.3.