coding theory Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are studied ...

, the weight enumerator polynomial of a binary

linear code In coding theory, a linear code is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although turbo codes can be seen as ...

specifies the number of words of each possible

Hamming weight The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the most typical case, a string ...

. Let

C \subset \mathbb_2^n

be a binary linear code length

n

. The weight distribution is the sequence of numbers :

A_t = \#\

giving the number of

codeword In communication, a code word is an element of a standardized code or protocol. Each code word is assembled in accordance with the specific rules of the code and assigned a unique meaning. Code words are typically used for reasons of reliability, ...

s ''c'' in ''C'' having weight ''t'' as ''t'' ranges from 0 to ''n''. The weight enumerator is the bivariate

polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example ...

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 In coding theory, the dual code of a linear code :C\subset\mathbb_q^n is the linear code defined by :C^\perp = \ where :\langle x, c \rangle = \sum_^n x_i c_i is a scalar product. In linear algebra terms, the dual code is the annihilator ...

C \subset \mathbb_2^n

by :

C^\perp = \

(where

\langle\ ,\ \rangle

denotes the vector

dot product In mathematics, the dot product or scalar productThe term ''scalar product'' means literally "product with a scalar as a result". It is also used sometimes for other symmetric bilinear forms, for example in a pseudo-Euclidean space. is an alge ...

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 Florence Jessie Collinson MacWilliams (4 January 1917 – 27 May 1990) was an English mathematician who contributed to the field of coding theory, and was one of the first women to publish in the field. MacWilliams' thesis "Combinatorial Problems ...

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 Springer Science+Business Media, commonly known as Springer, is a German multinational publishing company of books, e-books and peer-reviewed journals in science, humanities, technical and medical (STM) publishing. Originally founded in 1842 ...

, 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