Enumerator polynomial

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

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

$A\_t\; =\; \#\{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\; mbox\{\; iff\; \}\; (1,ldots,1)in\; C\; mbox\{\; and\; \}\; 0\; mbox\{\; otherwise.\}$
4. $W(C;1,-1)\; =\; sum\_\{w=0\}^\{n\}A\_\{w\}(-1)^\{n-w\}\; =\; A\_\{n\}+(-1)^\{1\}A\_\{n-1\}+ldots+(-1)^\{n-1\}A\_\{1\}+(-1)^\{n\}A\_\{0\}$

MacWilliams identity

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

$C^perp\; =\; \{x\; in\; mathbb\{F\}\_2^n\; ,mid,\; langle\; x,crangle\; =\; 0\; mbox\{\; \}forall\; c\; in\; C\; \}$

(where denotes the vector dot product and which is taken over $mathbb\{F\}\_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\}\; \#\; leftlbrace\; (c\_1,c\_2)\; in\; C\; times\; C\; mid\; d(c\_1,c\_2)\; =\; i\; rightrbrace$

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\}\; =\; \#\; leftlbrace\; c\; in\; C\; mid\; d(c,x)\; =\; i\; rightrbrace\; .$

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 A first course in coding theory. Oxford University Press.
• Pless, Vera Introduction to the theory of error-correcting codes. John Wiley & Sons.
• J.H. van Lint Introduction to Coding Theory. 2nd ed, Springer-Verlag. Chapters 3.5 and 4.3.