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

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

Формулировка

Пусть ${\displaystyle A_{q}(n,\;d)}$ обозначает максимально возможную мощность ${\displaystyle q}$-ичного блокового кода ${\displaystyle C}$ длины ${\displaystyle n}$ и минимального расстояния ${\displaystyle d}$ (${\displaystyle q}$-ичный блоковый код длины ${\displaystyle n}$ — это подмножество слов ${\displaystyle {\mathcal {A}}_{q}^{n}}$ с алфавитом ${\displaystyle {\mathcal {A}}_{q}}$, состоящим из ${\displaystyle q}$ элементов).

Тогда

${\displaystyle A_{q}(n,\;d)\leqslant {\frac {q^{n}}{\displaystyle \sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}}},}$

где

${\displaystyle t=\left\lfloor {\frac {d-1}{2}}\right\rfloor .}$

Доказательство

По определению ${\displaystyle d}$, если при передаче кодового слова случилось до ${\displaystyle t=\left\lfloor {\frac {d-1}{2}}\right\rfloor }$ ошибок, то с помощью декодирования, ограниченного минимальным расстоянием, мы будем способны безошибочно распознать посланное кодовое слово.

Для данного кодового слова ${\displaystyle c\in C}$, рассмотрим сферу радиуса ${\displaystyle t}$ вокруг ${\displaystyle c}$. Благодаря тому, что данный код способен исправлять до ${\displaystyle t=\left\lfloor {\frac {d-1}{2}}\right\rfloor }$ ошибок, ни одна сфера не пересекается ни с какой другой и содержит

${\displaystyle \sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}}$

слов, так как мы можем позволить ${\displaystyle t}$ (и менее) символам (из всех ${\displaystyle n}$ символов слова) принять одно из ${\displaystyle (q-1)}$ возможных значений, отличных от значения соответствующего символа данного слова (вспомним, что сам код является ${\displaystyle q}$-ичным).

Пусть ${\displaystyle M}$ обозначает количество слов в ${\displaystyle C}$. Объединяя сферы вокруг всех кодовых слов, мы замечаем, что результирующее множество содержится в ${\displaystyle {\mathcal {A}}_{q}^{n}}$. Так как сферы непересекающиеся, можно суммировать элементы каждой из них и получить

${\displaystyle M\times \sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}\leqslant |{\mathcal {A}}_{q}^{n}|=q^{n},}$

откуда для любого кода ${\displaystyle C}$

${\displaystyle M\leqslant {\frac {q^{n}}{\displaystyle \sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}}},}$

а, значит,

${\displaystyle A_{q}(n,\;d)\leqslant {\frac {q^{n}}{\displaystyle \sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}}}.}$

Совершенные коды

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

Титвайненом и Ван Линтом было доказано, что любой нетривиальный совершенный код имеет параметры кода Хэмминга или кода Голея^[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 с.

См. также

• Граница Синглтона
• Неравенство Гильберта — Варшамова
• Граница Плоткина
• Граница Джонсона