Misplaced Pages

Enumerator polynomial

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Regular code) 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}.}

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 2-by-n+1 matrix B with rows indexed by elements of GF(2) 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.

References

Categories: