MacWilliams identities

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].

References

[a1]	F.J. MacWilliams, "A theorem on the distribution of weights in a systematic code" Bell System Techn. J. , 42 (1963) pp. 79–94
[a2]	F.J. MacWilliams, N.J.A. Sloane, J.M. Goethals, "The MacWilliams identities for nonlinear codes" Bell System Techn. J. , 51 (1972) pp. 803–819
[a3]	V. Pless, "Power moment identities on weight distributions in error-correcting codes" Inform. and Control , 6 (1963) pp. 147–152