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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Пусть двоичный линейный код длины . Весовым распределением кода называется числовая последовательность где обозначает количество кодовых слов весом :

.

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

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

[править | править код]
  • когда иначе

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

[править | править код]

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

где обозначает скалярное произведение векторов в векторном пространстве .

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

Литература

[править | править код]
  • 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.