Русская Википедия:Граница Хэмминга
В теории кодирования грани́ца Хэ́мминга определяет пределы возможных значений параметров произвольного блокового кода. Также известна как граница сферической упаковки. Коды, достигающие границы Хэмминга, называют совершенными или плотноупакованными.
Формулировка
Пусть <math>A_q(n,\;d)</math> обозначает максимально возможную мощность <math>q</math>-ичного блокового кода <math>C</math> длины <math>n</math> и минимального расстояния <math>d</math> (<math>q</math>-ичный блоковый код длины <math>n</math> — это подмножество слов <math>\mathcal{A}_q^n</math> с алфавитом <math>\mathcal{A}_q</math>, состоящим из <math>q</math> элементов).
Тогда
- <math>A_q(n,\;d)\leqslant\frac{q^n}{\displaystyle\sum_{k=0}^t\binom{n}{k}(q-1)^k},</math>
где
- <math>t=\left\lfloor\frac{d-1}{2}\right\rfloor.</math>
Доказательство
По определению <math>d</math>, если при передаче кодового слова случилось до <math>t=\left\lfloor\frac{d-1}{2}\right\rfloor</math> ошибок, то с помощью декодирования, ограниченного минимальным расстоянием, мы будем способны безошибочно распознать посланное кодовое слово.
Для данного кодового слова <math>c\in C</math>, рассмотрим сферу радиуса <math>t</math> вокруг <math>c</math>. Благодаря тому, что данный код способен исправлять до <math>t=\left\lfloor\frac{d-1}{2}\right\rfloor</math> ошибок, ни одна сфера не пересекается ни с какой другой и содержит
- <math>\sum_{k=0}^t \binom{n}{k}(q-1)^k</math>
- слов, так как мы можем позволить <math>t</math> (и менее) символам (из всех <math>n</math> символов слова) принять одно из <math>(q-1)</math> возможных значений, отличных от значения соответствующего символа данного слова (вспомним, что сам код является <math>q</math>-ичным).
Пусть <math>M</math> обозначает количество слов в <math>C</math>. Объединяя сферы вокруг всех кодовых слов, мы замечаем, что результирующее множество содержится в <math>\mathcal{A}_q^n</math>. Так как сферы непересекающиеся, можно суммировать элементы каждой из них и получить
- <math>M\times\sum_{k=0}^t\binom{n}{k}(q-1)^k\leqslant|\mathcal{A}_q^n|=q^n,</math>
откуда для любого кода <math>C</math>
- <math>M\leqslant\frac{q^n}{\displaystyle\sum_{k=0}^t\binom{n}{k}(q-1)^k},</math>
а, значит,
- <math>A_q(n,\;d)\leqslant\frac{q^n}{\displaystyle\sum_{k=0}^t\binom{n}{k}(q-1)^k}.</math>
Совершенные коды
Коды, достигающие границы Хэмминга, называют совершенными. Были открыты следующие типы совершенных кодов: коды Хэмминга и коды Голея. Имеются ещё тривиальные совершенные коды: двоичные коды с повторением нечётной длины, коды с одним кодовым словом и коды, включающие всё множество <math>F_q^n</math>.
Титвайненом и Ван Линтом было доказано, что любой нетривиальный совершенный код имеет параметры кода Хэмминга или кода Голея[1][2].
Примечания
Литература
- MacWilliams F. J. and Sloane N. J. A. The Theory of Error-Correcting Codes. — Amsterdam, Netherlands, North-Holland, § 1.5, § 6.8, 1977.
- Книга:Блейхут Р.: Теория и практика кодов
См. также
