# MacWilliams identities

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

A $k$- dimensional subspace $C$ of the linear space $V$ of all $n$- tuples over the finite field ${ \mathop{\rm GF} } ( q )$ is called an $[ n,k ]$ linear code over ${ \mathop{\rm GF} } ( q )$. The vectors in $C$ are called code words. The weight of a vector is the number of its non-zero components. A generator matrix for a code $C$ is any $( k \times n )$- matrix $G$ whose rows form a basis of $C$. The ordinary inner product of vectors $u = ( u _ {1} \dots u _ {n} )$, $v = ( v _ {1} \dots v _ {n} )$ in $V$ is

$$u \cdot v = \sum _ {i = 1 } ^ { n } u _ {i} v _ {i} .$$

The dual of $C$ is the $[ n,n - k ]$ linear code $C ^ \bot$ defined by

$$C ^ \bot = \left \{ {v \in V } : {u \cdot v = 0 \textrm{ for all } u \in C } \right \} .$$

The weight distribution of a code $C$ of length $n$ gives the number of vectors of each weight $i$, $0 \leq i \leq n$, denoted by $A _ {i}$. For example, let $C$ be the $[ 7,4 ]$ linear code over ${ \mathop{\rm GF} } ( 2 )$ with generating matrix

$$G = \left ( \begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \end{array} \right ) .$$

The only non-zero weights in $C$ are $A _ {0} = A _ {7} = 1$, $A _ {3} = A _ {4} = 7$.

While the weight distribution does not, in general, uniquely determine a code, it gives important information that has both practical and theoretical significance. The most fundamental result about weight distributions are the MacWilliams equations, a set of linear relations between the weight distributions of $C$ and $C ^ \bot$. These equations imply that the weight distribution of $C ^ \bot$ is uniquely determined by the weight distribution of $C$. These relations have been the most significant tool available for investigating and calculating weight distributions.

Let $B _ {i}$ denote the number of vectors of weight $i$ in $C ^ \bot$. If $C$ is an $[ n,k ]$ linear code over ${ \mathop{\rm GF} } ( q )$, then there are two equivalent sets of MacWilliams equations [a1]:

$$\tag{a1 } \sum _ {j = 0 } ^ { {n } - \nu } \left ( \begin{array}{c} {n - j } \\ \nu \end{array} \right ) A _ {j} = q ^ {k - \nu } \sum _ {j = 0 } ^ \nu \left ( \begin{array}{c} {n - j } \\ {n - \nu } \end{array} \right ) B _ {j} ,$$

$$\tag{a2 } \sum _ {j = \nu } ^ { n } \left ( \begin{array}{c} j \\ \nu \end{array} \right ) A _ {j} = q ^ {k - \nu } \sum _ {j = 0 } ^ \nu ( - 1 ) ^ {j} \left ( \begin{array}{c} {n - j } \\ {n - \nu } \end{array} \right ) ( q - 1 ) ^ {\nu - j } B _ {j} ,$$

where $0 \leq \nu \leq n$.

If $\nu = 0$, both sets of equations say that $\sum _ {j = 0 } ^ {n} A _ {j} = q ^ {k} B _ {0} = q ^ {k}$, which states the obvious result that an $[ n,k ]$ code over ${ \mathop{\rm GF} } ( q )$ contains $q ^ {k}$ codewords. The other equations are not so obvious. One can solve either set of equations for the weight distribution of $C ^ \bot$, obtaining $B _ {0} = 1$ and $B _ {4} = 7$.

An elegant and much used way to express these relations is in terms of polynomials. The weight enumerator of a code $C$ of length $n$ is:

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

The following equation is equivalent to either (a1) or (a2) for a code $C$ over ${ \mathop{\rm GF} } ( q )$:

$$\tag{a3 } W _ {C ^ \bot } ( x,y ) = { \frac{1}{\left | C \right | } } W _ {C} ( x + ( q - 1 ) y,x - y ) .$$

Two other sets of equations equivalent to either (a1), (a2) or (a3) and more convenient for some calculations are called the power moment identities [a3]. They involve the Stirling numbers of the second kind $S ( r, \nu )$( cf. also Combinatorial analysis). One such set is

$$\tag{a4 } \sum _ {j = 0 } ^ { n } j ^ {r} A _ {j} = \sum _ {j = 0 } ^ { { \min } ( n,r ) } ( - 1 ) ^ {j} B _ {j} \cdot$$

$$\cdot \left ( \sum _ {\nu = j } ^ { r } \nu! S ( r, \nu ) q ^ {k - \nu } ( q - 1 ) ^ {\nu - j } \left ( \begin{array}{c} {n - j } \\ {n - \nu } \end{array} \right ) \right ) ,$$

where $0 \leq r$.

The power moments are particularly useful for giving conditions under which the weight distributions of a code and its dual are uniquely determined. This is illustrated in the following theorem: A unique solution to the power moments exists under the conditions that $s$ or fewer $A _ {i}$' s are unknown and that $B _ {1} \dots B _ {s - 1 }$ are known [a3]. In this situation, the weight distributions of both $C$ and $C ^ \bot$ are uniquely determined.

There are also MacWilliams equations for non-linear codes [a2].

How to Cite This Entry:
MacWilliams identities. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=MacWilliams_identities&oldid=47743
This article was adapted from an original article by V. Pless (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article