Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Enumerator polynomial
Specifies the number of words of a binary linear code of each possible Hamming weight

In coding theory, the weight enumerator polynomial of a binary linear code specifies the number of words of each possible Hamming weight.

Let C ⊂ F 2 n {\displaystyle C\subset \mathbb {F} _{2}^{n}} be a binary linear code of length n {\displaystyle n} . The weight distribution is the sequence of numbers

A t = # { c ∈ C ∣ w ( c ) = t } {\displaystyle A_{t}=\#\{c\in C\mid w(c)=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

W ( C ; x , y ) = ∑ w = 0 n A w x w y n − w . {\displaystyle W(C;x,y)=\sum _{w=0}^{n}A_{w}x^{w}y^{n-w}.}
We don't have any images related to Enumerator polynomial yet.
We don't have any YouTube videos related to Enumerator polynomial yet.
We don't have any PDF documents related to Enumerator polynomial yet.
We don't have any Books related to Enumerator polynomial yet.
We don't have any archived web articles related to Enumerator polynomial yet.

Basic properties

  1. W ( C ; 0 , 1 ) = A 0 = 1 {\displaystyle W(C;0,1)=A_{0}=1}
  2. W ( C ; 1 , 1 ) = ∑ w = 0 n A w = | C | {\displaystyle W(C;1,1)=\sum _{w=0}^{n}A_{w}=|C|}
  3. W ( C ; 1 , 0 ) = A n = 1  if  ( 1 , … , 1 ) ∈ C    and  0  otherwise {\displaystyle W(C;1,0)=A_{n}=1{\mbox{ if }}(1,\ldots ,1)\in C\ {\mbox{ and }}0{\mbox{ otherwise}}}
  4. W ( C ; 1 , − 1 ) = ∑ w = 0 n A w ( − 1 ) n − w = A n + ( − 1 ) 1 A n − 1 + … + ( − 1 ) n − 1 A 1 + ( − 1 ) n A 0 {\displaystyle W(C;1,-1)=\sum _{w=0}^{n}A_{w}(-1)^{n-w}=A_{n}+(-1)^{1}A_{n-1}+\ldots +(-1)^{n-1}A_{1}+(-1)^{n}A_{0}}

MacWilliams identity

Denote the dual code of C ⊂ F 2 n {\displaystyle C\subset \mathbb {F} _{2}^{n}} by

C ⊥ = { x ∈ F 2 n ∣ ⟨ x , c ⟩ = 0   ∀ c ∈ C } {\displaystyle C^{\perp }=\{x\in \mathbb {F} _{2}^{n}\,\mid \,\langle x,c\rangle =0{\mbox{ }}\forall c\in C\}}

(where ⟨   ,   ⟩ {\displaystyle \langle \ ,\ \rangle } denotes the vector dot product and which is taken over F 2 {\displaystyle \mathbb {F} _{2}} ).

The MacWilliams identity states that

W ( C ⊥ ; x , y ) = 1 ∣ C ∣ W ( C ; y − x , y + x ) . {\displaystyle W(C^{\perp };x,y)={\frac {1}{\mid C\mid }}W(C;y-x,y+x).}

The identity is named after Jessie MacWilliams.

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 = 1 M # { ( c 1 , c 2 ) ∈ C × C ∣ d ( c 1 , c 2 ) = i } {\displaystyle A_{i}={\frac {1}{M}}\#\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 ) = ∑ i = 0 n A i x i y n − i {\displaystyle A(C;x,y)=\sum _{i=0}^{n}A_{i}x^{i}y^{n-i}}

and when C is linear this is equal to the weight enumerator.

The outer distribution of C is the 2n-by-n+1 matrix B with rows indexed by elements of GF(2)n and columns indexed by integers 0...n, and entries

B x , i = # { c ∈ C ∣ d ( c , x ) = i } . {\displaystyle B_{x,i}=\#\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 (A0,...,An).

A code C is regular if the rows of B corresponding to the codewords of C are all equal.