В математике и информатике , в области теории кодирования , граница Хэмминга — это ограничение на параметры произвольного блочного кода : она также известна как граница сферической упаковки или граница объема из интерпретации в терминах упаковки шаров в метрике Хэмминга в пространство всех возможных слов. Она дает важное ограничение на эффективность , с которой любой код с исправлением ошибок может использовать пространство, в которое встроены его кодовые слова . Код, достигающий границы Хэмминга, называется идеальным кодом .
Исходное сообщение и закодированная версия оба составлены в алфавите из q букв. Каждое кодовое слово содержит n букв. Исходное сообщение (длиной m ) короче n букв. Сообщение преобразуется в n -буквенное кодовое слово с помощью алгоритма кодирования, передается по зашумленному каналу и, наконец, декодируется получателем. Процесс декодирования интерпретирует искаженное кодовое слово, называемое просто словом , как действительное кодовое слово, «ближайшее» к полученной строке из n букв.
Математически существует ровно q m возможных сообщений длины m , и каждое сообщение можно рассматривать как вектор длины m . Схема кодирования преобразует m -мерный вектор в n -мерный вектор. Возможны ровно q m допустимых кодовых слов, но любое из q n слов может быть получено, поскольку зашумленный канал может исказить одну или несколько из n букв при передаче кодового слова.
Набор алфавита — это набор символов с элементами. Набор строк длины в наборе алфавита обозначается . ( В этом наборе строк есть отдельные строки.) -арный блочный код длины — это подмножество строк , где набор алфавита — это любой набор алфавита, имеющий элементы. (Выбор набора алфавита не влияет на результат, при условии, что алфавит имеет размер .)
Пусть обозначает максимально возможный размер -арного блочного кода длины и минимальное расстояние Хэмминга между элементами блочного кода (обязательно положительное для ).
Тогда граница Хэмминга равна:
где
Из определения следует, что если не более
ошибки допускаются во время передачи кодового слова , то декодирование с минимальным расстоянием декодирует его правильно (т.е. декодирует полученное слово как отправленное кодовое слово). Таким образом, говорят, что код способен исправлять ошибки.
Для каждого кодового слова рассмотрим шар фиксированного радиуса вокруг . Каждая пара этих шаров (сфер Хэмминга) не пересекается по свойству коррекции ошибок. Пусть будет числом слов в каждом шаре (другими словами, объемом шара). Слово, находящееся в таком шаре, может отклоняться не более чем на компоненты от центра шара , который является кодовым словом. Число таких слов затем получается путем выбора до компонентов кодового слова для отклонения к одному из возможных других значений (напомним, код является -арным: он принимает значения в ). Таким образом,
это (максимальное) общее количество кодовых слов в , и, таким образом, по определению , наибольшее количество шаров, у которых нет двух шаров, имеющих общее слово. Взяв объединение слов в этих шарах с центром в кодовых словах, получим набор слов, каждое из которых подсчитано ровно один раз, то есть подмножество (где слова) и, таким образом:
Откуда:
Для кода C (подмножества ) радиус покрытия C — это наименьшее значение r , при котором каждый элемент из содержится по крайней мере в одном шаре радиуса r с центром в каждом кодовом слове C. Радиус упаковки C — это наибольшее значение s , при котором множество шаров радиуса s с центром в каждом кодовом слове C взаимно не пересекаются .
Из доказательства границы Хэмминга видно , что для имеем:
Следовательно, s ≤ r и если равенство имеет место, то s = r = t . Случай равенства означает, что граница Хэмминга достигнута.
Коды, достигающие границы Хэмминга, называются совершенными кодами . Примерами служат коды, имеющие только одно кодовое слово, и коды, представляющие собой целое . Другой пример — повторные коды , в которых каждый символ сообщения повторяется нечетное фиксированное число раз для получения кодового слова, где q = 2. Все эти примеры часто называют тривиальными совершенными кодами. В 1973 году Тиетявяйнен доказал [1] , что любой нетривиальный совершенный код над алфавитом с простой степенью имеет параметры кода Хэмминга или кода Голея .
Совершенный код можно интерпретировать как код, в котором шары радиуса Хэмминга t с центром на кодовых словах точно заполняют пространство ( t — радиус покрытия = радиус упаковки). Квазисовершенный код — это код, в котором шары радиуса Хэмминга t с центром на кодовых словах не пересекаются, а шары радиуса t +1 покрывают пространство, возможно, с некоторыми перекрытиями. [2] Другой способ сказать это — код является квазисовершенным , если его радиус покрытия на единицу больше его радиуса упаковки. [3]
