Многочлен перечислителя

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

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

Пусть — двоичный линейный код длины . Распределение веса — это последовательность чисел ${\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 . Перечислитель веса — это двумерный полином

${\displaystyle W(C;x,y)=\sum _{w=0}^{n}A_{w}x^{w}y^{n-w}.}$

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

1. ${\displaystyle W(C;0,1)=A_{0}=1}$
2. ${\displaystyle W(C;1,1)=\sum _{w=0}^{n}A_{w}=|C|}$
3. ${\displaystyle W(C;1,0)=A_{n}=1{\mbox{ if }}(1,\ldots ,1)\in C\ {\mbox{ and }}0{\mbox{ otherwise}}}$
4. ${\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}}$

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

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

${\displaystyle C^{\perp }=\{x\in \mathbb {F} _{2}^{n}\,\mid \,\langle x,c\rangle =0{\mbox{ }}\forall c\in C\}}$

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

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

${\displaystyle W(C^{\perp };x,y)={\frac {1}{\mid C\mid }}W(C;y-x,y+x).}$

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

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

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

${\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 . Полином перечислителя расстояний равен

${\displaystyle A(C;x,y)=\sum _{i=0}^{n}A_{i}x^{i}y^{n-i}}$

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

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

${\displaystyle B_{x,i}=\#\left\lbrace c\in C\mid d(c,x)=i\right\rbrace .}$

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

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

Ссылки

• Хилл, Рэймонд (1986). Первый курс по теории кодирования . Oxford Applied Mathematics and Computing Science Series. Oxford University Press . С. 165–173. ISBN 0-19-853803-0.
• Плесс, Вера (1982). Введение в теорию кодов, исправляющих ошибки . Серия Wiley-Interscience по дискретной математике. John Wiley & Sons . стр. 103–119. ISBN 0-471-08684-3.
• JH van Lint (1992). Введение в теорию кодирования . GTM . Том 86 (2-е изд.). Springer-Verlag . ISBN 3-540-54894-7.Главы 3.5 и 4.3.