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

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

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

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

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

Тогда

A_q(n,\;d)\leqslant\frac{q^n}{\displaystyle\sum_{k=0}^t\binom{n}{k}(q-1)^k},

где

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

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

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

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

\sum_{k=0}^t \binom{n}{k}(q-1)^k

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

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

M\times\sum_{k=0}^t\binom{n}{k}(q-1)^k\leqslant|\mathcal{A}_q^n|=q^n,

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

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

а, значит,

A_q(n,\;d)\leqslant\frac{q^n}{\displaystyle\sum_{k=0}^t\binom{n}{k}(q-1)^k}.

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

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

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