Теорема Мак-Вильямс

В теории кодирования теорема Мак-Ви́льямс устанавливает связь между весовой функцией линейного кода и весовой функцией двойственного ему кода. Одним из следствий теоремы является получение верхней границы мощности кода. Названа в честь английского математика Шаблон:Не переведено.

Пусть $C\subset {𝔽}_2^n$ двоичный линейный код длины $n$. Весовым распределением кода $C$ называется числовая последовательность $\{A_w{\}}_{w=0}^n,$ где $A_w$ обозначает количество кодовых слов $C$ весом $w$:

$A_w=\mathrm{\#}\{c\in C\mid 𝗐(c)=w\}$.

Весовой функцией (или весовым энумератором) называется многочлен двух переменных

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

Элементарные свойства весовой функции

• $W(C;0,1)=A_0=1.$
• $W(C;1,1)=\sum _{w=0}^n{A}_w=|C|.$
• $W(C;1,0)=A_n=1,$ когда $(1,\dots ,1)\in C,$ иначе $W(C;1,0)=A_n=0.$
• $W(C;1,-1)=\sum _{w=0}^n{A}_w(-1{)}^{n-w}=A_n+(-1{)}^1{A}_{n-1}+\dots +(-1{)}^{n-1}{A}_1+(-1{)}^n{A}_0.$

Формулировка теоремы

Обозначим код, двойственный $C$, через

$C^{\perp }=\{x\in {𝔽}_2^n\mid \mathrm{\forall }c\in C:⟨x,c⟩=0\},$

где $⟨,⟩$ обозначает скалярное произведение векторов в векторном пространстве ${𝔽}_2^n$.

Теорема Мак-Вильямс гласит, что

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

Литература

• Pless V. Introduction to the theory of error-correcting codes. — Wiley, New York, § 8.2, 1998.
• Lint van J.H. Introduction to coding theory. — Springer-Verlag, Berlin, § 3.5, 1999.
• Roth R.M. Introduction to coding theory. — Cambridge University Press, Cambridge, § 4.4, 2006.

См. также

• Многочлены Кравчука
• Теорема Дельсарта