(Redirected from MacWilliams identities )
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}}
n
{\displaystyle n}
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
W
(
C
;
0
,
1
)
=
A
0
=
1
{\displaystyle W(C;0,1)=A_{0}=1}
W
(
C
;
1
,
1
)
=
∑
w
=
0
n
A
w
=
|
C
|
{\displaystyle W(C;1,1)=\sum _{w=0}^{n}A_{w}=|C|}
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}}}
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}}
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 }
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 (A 0 ,...,A n
A code C is regular if the rows of B corresponding to the codewords of C are all equal.
References
Categories :
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
**DISCLAIMER** We are not affiliated with Wikipedia, and Cloudflare.
The information presented on this site is for general informational purposes only and does not constitute medical advice.
You should always have a personal consultation with a healthcare professional before making changes to your diet, medication, or exercise routine.
AI helps with the correspondence in our chat.
We participate in an affiliate program. If you buy something through a link, we may earn a commission 💕
↑
be a binary linear code of length 
. The weight distribution is the sequence of numbers
denotes the vector 
).
