MacWilliams identities
   HOME

TheInfoList



OR:

In coding theory, 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. 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 codewords ''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 exa ...
: 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 ...
of 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 algebra ...
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''0,...,''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 in ...
, 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