Normal-form game: Difference between revisions
Jump to navigation
Jump to search
en>SchreiberBike Repairing links to disambiguation pages - You can help! - Graph |
en>Toni 001 m changed link from "Nash equilibria" to "Nash equilibrium" |
||
| Line 1: | Line 1: | ||
In [[coding theory]], the '''weight enumerator polynomial''' of a binary [[linear code]] specifies the number of words of each possible [[Hamming weight]]. | |||
Let <math>C \subset \mathbb{F}_2^n</math> be a binary linear code length <math>n</math>. The '''weight distribution''' is the sequence of numbers | |||
:<math> A_t = \#\{c \in C \mid w(c) = t \} </math> | |||
giving the number of [[codeword]]s ''c'' in ''C'' having weight ''t'' as ''t'' ranges from 0 to ''n''. The '''weight enumerator''' is the bivariate [[polynomial]] | |||
:<math> W(C;x,y) = \sum_{w=0}^n A_w x^w y^{n-w}.</math> | |||
==Basic properties== | |||
#<math> W(C;0,1) = A_{0}=1 </math> | |||
#<math> W(C;1,1) = \sum_{w=0}^{n}A_{w}=|C| </math> | |||
#<math> W(C;1,0) = A_{n}= 1 \mbox{ iff } (1,\ldots,1)\in C\ \mbox{ and } 0 \mbox{ otherwise.} </math> | |||
#<math> 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} </math> | |||
==MacWilliams identity== | |||
Denote the [[dual code]] of <math>C \subset \mathbb{F}_2^n</math> by | |||
:<math>C^\perp = \{x \in \mathbb{F}_2^n \,\mid\, \langle x,c\rangle = 0 \mbox{ }\forall c \in C \} </math> | |||
(where <math><,></math> denotes the vector [[dot product]] and which is taken over <math>\mathbb{F}_2</math>). | |||
The '''MacWilliams identity''' states that | |||
:<math>W(C^\perp;x,y) = \frac{1}{\mid C \mid} W(C;y-x,y+x). </math> | |||
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 | |||
:<math> A_i = \frac{1}{M} \# \left\lbrace (c_1,c_2) \in C \times C \mid d(c_1,c_2) = i \right\rbrace </math> | |||
where ''i'' ranges from 0 to ''n''. The '''distance enumerator polynomial''' is | |||
:<math> A(C;x,y) = \sum_{i=0}^n A_i x^i y^{n-i} </math> | |||
and when ''C'' is linear this is equal to the weight enumerator. | |||
The '''outer distribution''' of ''C'' is the 2<sup>''n''</sup>-by-''n''+1 matrix ''B'' with rows indexed by elements of GF(2)<sup>''n''</sup> and columns indexed by integers 0...''n'', and entries | |||
:<math> B_{x,i} = \# \left\lbrace c \in C \mid d(c,x) = i \right\rbrace . </math> | |||
The sum of the rows of ''B'' is ''M'' times the inner distribution vector (''A''<sub>0</sub>,...,''A''<sub>''n''</sub>). | |||
A code ''C'' is '''regular''' if the rows of ''B'' corresponding to the codewords of ''C'' are all equal. | |||
==References== | |||
* {{cite book | last=Hill | first=Raymond | title=A first course in coding theory | publisher=[[Oxford University Press]] | series=Oxford Applied Mathematics and Computing Science Series | date=1986 | isbn=0-19-853803-0 | pages=165–173 }} | |||
* {{cite book | last = Pless | first = Vera | authorlink=Vera Pless | title = Introduction to the theory of error-correcting codes | publisher = [[John Wiley & Sons]]|series = Wiley-Interscience Series in Discrete Mathematics | date = 1982| isbn = 0-471-08684-3 | pages=103–119 }} | |||
* {{cite book | author=J.H. van Lint | title=Introduction to Coding Theory | edition=2nd ed | publisher=[[Springer-Verlag]] | series=[[Graduate Texts in Mathematics|GTM]] | volume=86 | date=1992 | isbn=3-540-54894-7 }} Chapters 3.5 and 4.3. | |||
[[Category:Coding theory]] | |||
[[Category:Error detection and correction]] | |||
[[Category:Mathematical identities]] | |||
Revision as of 23:01, 12 December 2013
In coding theory, the weight enumerator polynomial of a binary linear code specifies the number of words of each possible Hamming weight.
Let be a binary linear code length . The weight distribution is the sequence of numbers
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
Basic properties
MacWilliams identity
Denote the dual code of by
(where denotes the vector dot product and which is taken over ).
The MacWilliams identity states that
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
where i ranges from 0 to n. The distance enumerator polynomial is
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
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
- 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
My blog: http://www.primaboinca.com/view_profile.php?userid=5889534 - 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
My blog: http://www.primaboinca.com/view_profile.php?userid=5889534 - 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
My blog: http://www.primaboinca.com/view_profile.php?userid=5889534 Chapters 3.5 and 4.3.