MacWilliams identities

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 of length $n$. The weight distribution is the sequence of numbers

:$A_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_^n A_w x^w y^.$

Basic properties

#$W(C;0,1) = A_=1$
#$W(C;1,1) = \sum_^A_=, C,$
#$W(C;1,0) = A_= 1 \mbox (1,\ldots,1)\in C\ \mbox 0 \mbox$
#$W(C;1,-1) = \sum_^A_(-1)^ = A_+(-1)^A_+\ldots+(-1)^A_+(-1)^A_$

MacWilliams identity

Denote the dual code of $C \subset \mathbb_2^n$ by

:$C^\perp = \$

(where $\langle\ ,\ \rangle$ denotes the vector dot product and which is taken over $\mathbb_2$).

The MacWilliams identity states that

:$W(C^\perp;x,y) = \frac 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 \# \left\lbrace (c_1,c_2) \in C \times C \mid d(c_1,c_2) = i \right\rbrace$

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

:$A(C;x,y) = \sum_^n A_i x^i y^$

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

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

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

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

*
*
* {{cite book , author=J.H. van Lint , title=Introduction to Coding Theory , edition=2nd , publisher=Springer-Verlag , series= GTM , volume=86 , date=1992 , isbn=3-540-54894-7 , url-access=registration , url=https://archive.org/details/introductiontoco0000lint Chapters 3.5 and 4.3.

Coding theory
Error detection and correction
Mathematical identities
Polynomials