Многочлен перечислителя
Определяет количество слов двоичного линейного кода каждого возможного веса Хэмминга.

В теории кодирования полином перечислителя весов двоичного линейного кода определяет количество слов каждого возможного веса Хэмминга .

Пусть — двоичный линейный код длины . Распределение веса — это последовательность чисел С ⊂ Ф 2 н {\displaystyle C\subset \mathbb {F} _{2}^{n}} н {\displaystyle n}

А т = # { с ∈ С ∣ ж ( с ) = т } {\displaystyle A_{t}=\#\{c\in C\mid w(c)=t\}}

давая число кодовых слов c в C, имеющих вес t, когда t изменяется от 0 до n . Перечислитель веса — это двумерный полином

Вт ( С ; х , у ) = ∑ ж = 0 н А ж х ж у н − ж . {\displaystyle W(C;x,y)=\sum _{w=0}^{n}A_{w}x^{w}y^{nw}.}

Основные свойства

  1. Вт ( С ; 0 , 1 ) = А 0 = 1 {\displaystyle W(C;0,1)=A_{0}=1}
  2. Вт ( С ; 1 , 1 ) = ∑ ж = 0 н А ж = | С | {\displaystyle W(C;1,1)=\sum _{w=0}^{n}A_{w}=|C|}
  3. Вт ( С ; 1 , 0 ) = А н = 1  если  ( 1 , … , 1 ) ∈ С    и  0  в противном случае {\displaystyle W(C;1,0)=A_{n}=1{\mbox{ если }}(1,\ldots ,1)\in C\ {\mbox{ и }}0{\mbox{ в противном случае}}}
  4. Вт ( С ; 1 , − 1 ) = ∑ ж = 0 н А ж ( − 1 ) н − ж = А н + ( − 1 ) 1 А н − 1 + … + ( − 1 ) н − 1 А 1 + ( − 1 ) н А 0 {\displaystyle W(C;1,-1)=\sum _{w=0}^{n}A_{w}(-1)^{nw}=A_{n}+(-1)^{1}A_{n-1}+\ldots +(-1)^{n-1}A_{1}+(-1)^{n}A_{0}}

Идентификация Мак-Вильямса

Обозначим дуальный код через С ⊂ Ф 2 н {\displaystyle C\subset \mathbb {F} _{2}^{n}}

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

(где обозначает векторное скалярное произведение , а которое берется ). ⟨   ,   ⟩ {\displaystyle \langle \,\ \rangle} Ф 2 {\displaystyle \mathbb {F} _{2}}

Идентификация Мак-Вильямса гласит, что

Вт ( С ⊥ ; х , у ) = 1 ∣ С ∣ Вт ( С ; у − х , у + х ) . {\displaystyle W(C^{\perp };x,y)={\frac {1}{\mid C\mid }}W(C;yx,y+x).}

Личность названа в честь Джесси МакВильямс .

Перечислитель расстояний

Распределение расстояний или внутреннее распределение кода C размера M и длины n — это последовательность чисел

А я = 1 М # { ( с 1 , с 2 ) ∈ С × С ∣ г ( с 1 , с 2 ) = я } {\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 }

где i варьируется от 0 до n . Полином перечислителя расстояний равен

А ( С ; х , у ) = ∑ я = 0 н А я х я у н − я {\displaystyle A(C;x,y)=\sum _{i=0}^{n}A_{i}x^{i}y^{ni}}

а когда C линейна, то она равна перечислителю веса.

Внешнее распределение C представляет собой матрицу B размером 2 n на n +1 со строками, индексированными элементами GF(2) n , и столбцами , индексированными целыми числами 0... n , и записями

Б х , я = # { с ∈ С ∣ г ( с , х ) = я } . {\displaystyle B_{x,i}=\#\left\lbrace c\in C\mid d(c,x)=i\right\rbrace .}

Сумма строк матрицы B равна M , умноженному на вектор внутреннего распределения ( A 0 ,..., A n ).

Код C является регулярным , если все строки B, соответствующие кодовым словам C, равны.

Ссылки

Retrieved from "https://en.wikipedia.org/w/index.php?title=Enumerator_polynomial&oldid=1256495426#MacWilliams_identity"