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

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

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

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

.

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

Элементарные свойства весовой функции[править | править код]

  • когда иначе

Формулировка теоремы[править | править код]

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

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

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

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

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

См. также[править | править код]