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

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

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

$A_w=\mathrm{\#<!--\; \#\; -->}\{c\in <!--\; \in \; -->C\mid <!--\; \mid \; -->\mathsf{w}(c)=w\}$$A_{w}=\#\{c\in C\mid {\mathsf {w}}(c)=w\}$.

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

$W(C;x,y)=\underset{w=0}{\overset{n}{\sum <!--\; \sum \; -->}}{A}_w{x}^w{y}^{n-<!--\; -\; -->w}.$$W(C;x,y)=\sum _{w=0}^{n}A_{w}x^{w}y^{n-w}.$

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

• $W(C;0,1)=A_0=1.$$\displaystyle W(C;0,1)=A_{0}=1.$ 
• $W(C;1,1)=\underset{w=0}{\overset{n}{\sum <!--\; \sum \; -->}}{A}_w=|C|.$$\displaystyle W(C;1,1)=\sum _{w=0}^{n}A_{w}=|C|.$ 
• $W(C;1,0)=A_n=1,$$\displaystyle W(C;1,0)=A_{n}=1,$  когда $(1,\dots <!--\; \dots \; -->,1)\in <!--\; \in \; -->C,$$(1,\ldots ,1)\in C,$  иначе $W(C;1,0)=A_n=0.$$\displaystyle W(C;1,0)=A_{n}=0.$ 
• $W(C;1,-<!--\; -\; -->1)=\underset{w=0}{\overset{n}{\sum <!--\; \sum \; -->}}{A}_w(-<!--\; -\; -->1{)}^{n-<!--\; -\; -->w}=A_n+(-<!--\; -\; -->1{)}^1{A}_{n-<!--\; -\; -->1}+\dots <!--\; \dots \; -->+(-<!--\; -\; -->1{)}^{n-<!--\; -\; -->1}{A}_1+(-<!--\; -\; -->1{)}^n{A}_0.$$\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}.$ 

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

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

$C^{\perp <!--\; \perp \; -->}=\{x\in <!--\; \in \; -->{\mathbb{F}}_2^n\mid <!--\; \mid \; -->\mathrm{\forall <!--\; \forall \; -->}c\in <!--\; \in \; -->C:⟨<!--\; ⟨\; -->x,c⟩<!--\; ⟩\; -->=0\},$$C^{\perp }=\{x\in \mathbb {F} _{2}^{n}\,\mid \,\forall c\in C:\langle x,c\rangle =0{\mbox{ }}\},$ 

где $⟨<!--\; ⟨\; -->,⟩<!--\; ⟩\; -->$$\langle \,,\,\rangle$  обозначает скалярное произведение векторов в векторном пространстве ${\mathbb{F}}_2^n$$\mathbb{F}_2^n$ .

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

$W(C^{\perp <!--\; \perp \; -->};x,y)=\frac{1}{\mid <!--\; \mid \; -->C\mid <!--\; \mid \; -->}W(C;y-<!--\; -\; -->x,y+x).$$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.

См. такжеПравить

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