|
|
Enumerator polynomial
In coding theory, the weight enumerator polynomial of a binary linear code specifies the number of words of each possible Hamming weight.
Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C \subset \mathbb{F}_2^n} be a binary linear code length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} . The weight distribution is the sequence of numbers
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W(C;x,y) = \sum_{w=0}^n A_w x^w y^{n-w}.}
Contents
Basic properties
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W(C;0,1) = A_{0}=1 }
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W(C;1,1) = \sum_{w=0}^{n}A_{w}=|C| }
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle W(C;1,0) = A_{n}= 1 \mbox{ if } (1,\ldots,1)\in C\ \mbox{ and } 0 \mbox{ otherwise} }
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C \subset \mathbb{F}_2^n} by
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C^\perp = \{x \in \mathbb{F}_2^n \,\mid\, \langle x,c\rangle = 0 \mbox{ }\forall c \in C \} }
(where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \langle\ ,\ \rangle} denotes the vector dot product and which is taken over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_2} ).
The MacWilliams identity states that
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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.
