Русская Википедия:Теорема Мак-Вильямс

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

В теории кодирования теорема Мак-Ви́льямс устанавливает связь между весовой функцией линейного кода и весовой функцией двойственного ему кода. Одним из следствий теоремы является получение верхней границы мощности кода. Названа в честь английского математика en (Florence Jessie MacWilliams).

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

<math> A_w = \#\{c \in C \mid \mathsf{w}(c) = w \} </math>.

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

<math> W(C;x,y) = \sum_{w = 0}^n A_w x^w y^{n-w}.</math>

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

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

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

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

<math>C^\perp = \{x \in \mathbb{F}_2^n \,\mid\, \forall c \in C: \langle x,c\rangle = 0 \mbox{ } \}, </math>

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

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

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

Литература

• 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.

См. также

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