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

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

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

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

Тогда

A q ( n , d ) ⩽ q n ∑ k = 0 t ( n k ) ( q − 1 ) k , {displaystyle A_{q}(n,;d)leqslant {frac {q^{n}}{displaystyle sum _{k=0}^{t}{inom {n}{k}}(q-1)^{k}}},}

где

t = ⌊ d − 1 2 ⌋ . {displaystyle t=leftlfloor {frac {d-1}{2}} ight floor .}

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

По определению d {displaystyle d} , если при передаче кодового слова случилось до t = ⌊ d − 1 2 ⌋ {displaystyle t=leftlfloor {frac {d-1}{2}} ight floor } ошибок, то с помощью декодирования, ограниченного минимальным расстоянием, мы будем способны безошибочно распознать посланное кодовое слово.

Для данного кодового слова c ∈ C {displaystyle cin C} , рассмотрим сферу радиуса t {displaystyle t} вокруг c {displaystyle c} . Благодаря тому, что данный код способен исправлять до t = ⌊ d − 1 2 ⌋ {displaystyle t=leftlfloor {frac {d-1}{2}} ight floor } ошибок, ни одна сфера не пересекается ни с какой другой и содержит

∑ k = 0 t ( n k ) ( q − 1 ) k {displaystyle sum _{k=0}^{t}{inom {n}{k}}(q-1)^{k}} слов, так как мы можем позволить t {displaystyle t} (и менее) символам (из всех n {displaystyle n} символов слова) принять одно из ( q − 1 ) {displaystyle (q-1)} возможных значений, отличных от значения соответствующего символа данного слова (вспомним, что сам код является q {displaystyle q} -ичным).

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

M × ∑ k = 0 t ( n k ) ( q − 1 ) k ⩽ | A q n | = q n , {displaystyle M imes sum _{k=0}^{t}{inom {n}{k}}(q-1)^{k}leqslant |{mathcal {A}}_{q}^{n}|=q^{n},}

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

M ⩽ q n ∑ k = 0 t ( n k ) ( q − 1 ) k , {displaystyle Mleqslant {frac {q^{n}}{displaystyle sum _{k=0}^{t}{inom {n}{k}}(q-1)^{k}}},}

а, значит,

A q ( n , d ) ⩽ q n ∑ k = 0 t ( n k ) ( q − 1 ) k . {displaystyle A_{q}(n,;d)leqslant {frac {q^{n}}{displaystyle sum _{k=0}^{t}{inom {n}{k}}(q-1)^{k}}}.}

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

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

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