Namespaces
Variants
Actions

Difference between revisions of "MacWilliams identities"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
A <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m1100101.png" />-dimensional subspace <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m1100102.png" /> of the [[Linear space|linear space]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m1100103.png" /> of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m1100104.png" />-tuples over the [[Finite field|finite field]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m1100105.png" /> is called an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m1100107.png" /> linear code over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m1100108.png" />. The vectors in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m1100109.png" /> are called code words. The weight of a vector is the number of its non-zero components. A generator matrix for a code <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001010.png" /> is any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001011.png" />-matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001012.png" /> whose rows form a basis of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001013.png" />. The ordinary inner product of vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001014.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001015.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001016.png" /> is
+
<!--
 +
m1100101.png
 +
$#A+1 = 68 n = 0
 +
$#C+1 = 68 : ~/encyclopedia/old_files/data/M110/M.1100010 MacWilliams identities
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001017.png" /></td> </tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
The dual of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001018.png" /> is the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001019.png" /> linear code <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001020.png" /> defined by
+
A  $  k $-
 +
dimensional subspace  $  C $
 +
of the [[Linear space|linear space]]  $  V $
 +
of all  $  n $-
 +
tuples over the [[Finite field|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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001021.png" /></td> </tr></table>
+
$$
 +
u \cdot v = \sum _ {i = 1 } ^ { n }  u _ {i} v _ {i} .
 +
$$
  
The weight distribution of a code <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001022.png" /> of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001023.png" /> gives the number of vectors of each weight <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001024.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001025.png" />, denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001026.png" />. For example, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001027.png" /> be the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001028.png" /> linear code over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001029.png" /> with generating matrix
+
The dual of $  C $
 +
is the $  [ n,n - k ] $
 +
linear code $  C  ^  \bot  $
 +
defined by
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001030.png" /></td> </tr></table>
+
$$
 +
C  ^  \bot  = \left \{ {v \in V } : {u \cdot v = 0 \textrm{ for  all  }  u \in C } \right \} .
 +
$$
  
The only non-zero weights in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001031.png" /> are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001032.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001033.png" />.
+
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
  
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001034.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001035.png" />. These equations imply that the weight distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001036.png" /> is uniquely determined by the weight distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001037.png" />. These relations have been the most significant tool available for investigating and calculating weight distributions.
+
$$
 +
G = \left (
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001038.png" /> denote the number of vectors of weight <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001039.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001040.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001041.png" /> is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001042.png" /> linear code over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001043.png" />, then there are two equivalent sets of MacWilliams equations [[#References|[a1]]]:
+
\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}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001044.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>
+
\right ) .
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001045.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a2)</td></tr></table>
+
The only non-zero weights in  $  C $
 +
are  $  A _ {0} = A _ {7} = 1 $,
 +
$  A _ {3} = A _ {4} = 7 $.
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001046.png" />.
+
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.
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001047.png" />, both sets of equations say that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001048.png" />, which states the obvious result that an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001049.png" /> code over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001050.png" /> contains <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001051.png" /> codewords. The other equations are not so obvious. One can solve either set of equations for the weight distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001052.png" />, obtaining <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001053.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001054.png" />.
+
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 [[#References|[a1]]]:
  
An elegant and much used way to express these relations is in terms of polynomials. The weight enumerator of a code <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001055.png" /> of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001056.png" /> is:
+
$$ \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} ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001057.png" /></td> </tr></table>
+
$$ \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} ,
 +
$$
  
The following equation is equivalent to either (a1) or (a2) for a code <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001058.png" /> over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001059.png" />:
+
where  $  0 \leq  \nu \leq  n $.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001060.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a3)</td></tr></table>
+
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 $.
  
Two other sets of equations equivalent to either (a1), (a2) or (a3) and more convenient for some calculations are called the power moment identities [[#References|[a3]]]. They involve the Stirling numbers of the second kind <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001061.png" /> (cf. also [[Combinatorial analysis|Combinatorial analysis]]). One such set is
+
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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001062.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a4)</td></tr></table>
+
$$
 +
W _ {C} ( x,y ) = \sum _ {i = 0 } ^ { n }  A _ {i} x ^ {n - i } y  ^ {i} .
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001063.png" /></td> </tr></table>
+
The following equation is equivalent to either (a1) or (a2) for a code  $  C $
 +
over  $  { \mathop{\rm GF} } ( q ) $:
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001064.png" />.
+
$$ \tag{a3 }
 +
W _ {C  ^  \bot  } ( x,y ) = {
 +
\frac{1}{\left | C \right | }
 +
} W _ {C} ( x + ( q - 1 ) y,x - y ) .
 +
$$
  
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001065.png" /> or fewer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001066.png" />'s are unknown and that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001067.png" /> are known [[#References|[a3]]]. In this situation, the weight distributions of both <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001068.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m110/m110010/m11001069.png" /> are uniquely determined.
+
Two other sets of equations equivalent to either (a1), (a2) or (a3) and more convenient for some calculations are called the power moment identities [[#References|[a3]]]. They involve the [[Stirling numbers]] of the second kind  $  S ( r, \nu ) $(
 +
cf. also [[Combinatorial analysis|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 [[#References|[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 [[#References|[a2]]].
 
There are also MacWilliams equations for non-linear codes [[#References|[a2]]].

Latest revision as of 04:11, 6 June 2020


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