Граница Хэмминга
В теории кодирования грани́ца Хэ́мминга определяет пределы возможных значений параметров произвольного блокового кода. Также известна как граница сферической упаковки. Коды, достигающие границы Хэмминга, называют совершенными или плотноупакованными.
Формулировка
Пусть обозначает максимально возможную мощность -ичного блокового кода длины и минимального расстояния (-ичный блоковый код длины — это подмножество слов с алфавитом , состоящим из элементов).
Тогда
где
Доказательство
По определению , если при передаче кодового слова случилось до ошибок, то с помощью декодирования, ограниченного минимальным расстоянием, мы будем способны безошибочно распознать посланное кодовое слово.
Для данного кодового слова , рассмотрим сферу радиуса вокруг . Благодаря тому, что данный код способен исправлять до ошибок, ни одна сфера не пересекается ни с какой другой и содержит
- слов, так как мы можем позволить (и менее) символам (из всех символов слова) принять одно из возможных значений, отличных от значения соответствующего символа данного слова (вспомним, что сам код является -ичным).
Пусть обозначает количество слов в . Объединяя сферы вокруг всех кодовых слов, мы замечаем, что результирующее множество содержится в . Так как сферы непересекающиеся, можно суммировать элементы каждой из них и получить
откуда для любого кода
а, значит,
Совершенные коды
Коды, достигающие границы Хэмминга, называют совершенными. Были открыты следующие типы совершенных кодов: коды Хэмминга и коды Голея. Имеются ещё тривиальные совершенные коды: двоичные коды с повторением нечётной длины, коды с одним кодовым словом и коды, включающие всё множество .
Титвайненом и Ван Линтом было доказано, что любой нетривиальный совершенный код имеет параметры кода Хэмминга или кода Голея[1][2].
Примечания
- ↑ Tietavainen A., Perko A. There are no unknown perfect binary codes. — Annales Universitatis Turkuensis. — Ser. A, I 148, 3-10[6], 1971.
- ↑ 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 с.
См. также
- Граница Синглтона
- Неравенство Гильберта — Варшамова
- Граница Плоткина
- Граница Джонсона