Граница Хэмминга

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

В теории кодирования грани́ца Хэ́мминга определяет пределы возможных значений параметров произвольного блокового кода. Также известна как граница сферической упаковки. Коды, достигающие границы Хэмминга, называют совершенными или плотноупакованными.

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

Пусть обозначает максимально возможную мощность -ичного блокового кода длины и минимального расстояния (-ичный блоковый код длины  — это подмножество слов с алфавитом , состоящим из элементов).

Тогда

где

Доказательство[править | править вики-текст]

По определению , если при передаче кодового слова случилось до ошибок, то с помощью декодирования, ограниченного минимальным расстоянием, мы будем способны безошибочно распознать посланное кодовое слово.

Для данного кодового слова , рассмотрим сферу радиуса вокруг . Благодаря тому, что данный код способен исправлять до ошибок, ни одна сфера не пересекается ни с какой другой и содержит

слов, так как мы можем позволить (и менее) символам (из всех символов слова) принять одно из возможных значений, отличных от значения соответствующего символа данного слова (вспомним, что сам код является -ичным).

Пусть обозначает количество слов в . Объединяя сферы вокруг всех кодовых слов, мы замечаем, что результирующее множество содержится в . Так как сферы непересекающиеся, можно суммировать элементы каждой из них и получить

откуда для любого кода

а, значит,

Совершенные коды[править | править вики-текст]

Коды, достигающие границы Хэмминга, называют совершенными. Были открыты следующие типы совершенных кодов: коды Хэмминга и коды Голея. Имеются ещё тривиальные совершенные коды: двоичные коды с повторением нечётной длины, коды с одним кодовым словом и коды, включающие всё множество .

Титвайненом и Ван Линтом было доказано, что любой нетривиальный совершенный код имеет параметры кода Хэмминга или кода Голея[1][2].

Примечания[править | править вики-текст]

  1. Tietavainen A., Perko A. There are no unknown perfect binary codes. — Annales Universitatis Turkuensis. — Ser. A, I 148, 3-10[6], 1971.
  2. Lint van J. H. Nonexistence theorems for perfect error-correcting codes. — Computers in Algebra and Number Theory. — Vol. IV [6], 1971.

Литература[править | править вики-текст]

  • MacWilliams F. J. and Sloane N. J. A. The Theory of Error-Correcting Codes. — Amsterdam, Netherlands, North-Holland, § 1.5, § 6.8, 1977.
  • Блейхут Р. Теория и практика кодов, контролирующих ошибки = Theory and Practice of Error Control Codes. — М.: Мир, 1986. — 576 с.

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