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

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

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

${\displaystyle A_{w}=\#\{c\in C\mid {\mathsf {w}}(c)=w\}}$.

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

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

• ${\displaystyle \displaystyle W(C;0,1)=A_{0}=1.}$
• ${\displaystyle \displaystyle W(C;1,1)=\sum _{w=0}^{n}A_{w}=|C|.}$
• ${\displaystyle \displaystyle W(C;1,0)=A_{n}=1,}$ когда ${\displaystyle (1,\ldots ,1)\in C,}$ иначе ${\displaystyle \displaystyle W(C;1,0)=A_{n}=0.}$
• ${\displaystyle \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}$, через

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

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

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

${\displaystyle 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.

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