Хэмминг связан

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

Исходное сообщение и закодированная версия оба составлены в алфавите из q букв. Каждое кодовое слово содержит n букв. Исходное сообщение (длиной m ) короче n букв. Сообщение преобразуется в n -буквенное кодовое слово с помощью алгоритма кодирования, передается по зашумленному каналу и, наконец, декодируется получателем. Процесс декодирования интерпретирует искаженное кодовое слово, называемое просто словом , как действительное кодовое слово, «ближайшее» к полученной строке из n букв.

Математически существует ровно q ^m возможных сообщений длины m , и каждое сообщение можно рассматривать как вектор длины m . Схема кодирования преобразует m -мерный вектор в n -мерный вектор. Возможны ровно q ^m допустимых кодовых слов, но любое из q ⁿ слов может быть получено, поскольку зашумленный канал может исказить одну или несколько из n букв при передаче кодового слова.

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

Пусть обозначает максимально возможный размер -арного блочного кода длины и минимальное расстояние Хэмминга между элементами блочного кода (обязательно положительное для ).${\displaystyle \ A_{q}(n,d)}$${\displaystyle д}$${\displaystyle \ С}$${\displaystyle n}$ ${\displaystyle д}$${\displaystyle q^{n}>1}$

Тогда граница Хэмминга равна:

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

где

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

Из определения следует, что если не более ${\displaystyle д}$

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

ошибки допускаются во время передачи кодового слова , то декодирование с минимальным расстоянием декодирует его правильно (т.е. декодирует полученное слово как отправленное кодовое слово). Таким образом, говорят, что код способен исправлять ошибки.${\displaystyle т}$

Для каждого кодового слова рассмотрим шар фиксированного радиуса вокруг . Каждая пара этих шаров (сфер Хэмминга) не пересекается по свойству коррекции ошибок. Пусть будет числом слов в каждом шаре (другими словами, объемом шара). Слово, находящееся в таком шаре, может отклоняться не более чем на компоненты от центра шара , который является кодовым словом. Число таких слов затем получается путем выбора до компонентов кодового слова для отклонения к одному из возможных других значений (напомним, код является -арным: он принимает значения в ). Таким образом,${\displaystyle c\in C}$${\displaystyle т}$${\displaystyle с}$${\displaystyle т}$${\displaystyle м}$${\displaystyle т}$${\displaystyle т}$${\displaystyle n}$${\displaystyle (q-1)}$${\displaystyle д}$${\displaystyle {\mathcal {A}}_{q}^{n}}$

${\displaystyle m={\begin{matrix}\sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}\end{matrix}}.}$

${\displaystyle A_{q}(n,d)}$это (максимальное) общее количество кодовых слов в , и, таким образом, по определению , наибольшее количество шаров, у которых нет двух шаров, имеющих общее слово. Взяв объединение слов в этих шарах с центром в кодовых словах, получим набор слов, каждое из которых подсчитано ровно один раз, то есть подмножество (где слова) и, таким образом:${\displaystyle С}$${\displaystyle т}$${\displaystyle {\mathcal {A}}_{q}^{n}}$${\displaystyle |{\mathcal {A}}_{q}^{n}|=q^{n}}$

${\displaystyle A_{q}(n,d)\times m=A_{q}(n,d)\times {\begin{matrix}\sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}\end{matrix}}\leq q^{n}.}$

Откуда:

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

Для кода C (подмножества ) радиус покрытия C — это наименьшее значение r , при котором каждый элемент из содержится по крайней мере в одном шаре радиуса r с центром в каждом кодовом слове C. Радиус упаковки C — это наибольшее значение s , при котором множество шаров радиуса s с центром в каждом кодовом слове C взаимно не пересекаются .${\displaystyle A_{q}(n,d)}$${\displaystyle {\mathcal {A}}_{q}^{n}}$${\displaystyle {\mathcal {A}}_{q}^{n}}$

Из доказательства границы Хэмминга видно , что для имеем:${\displaystyle t\,=\,\left\lfloor {\frac {1}{2}}(d-1)\right\rfloor }$

s ≤ t и t ≤ r .

Следовательно, s ≤ r и если равенство имеет место, то s = r = t . Случай равенства означает, что граница Хэмминга достигнута.

Коды, достигающие границы Хэмминга, называются совершенными кодами . Примерами служат коды, имеющие только одно кодовое слово, и коды, представляющие собой целое . Другой пример — повторные коды , в которых каждый символ сообщения повторяется нечетное фиксированное число раз для получения кодового слова, где q = 2. Все эти примеры часто называют тривиальными совершенными кодами. В 1973 году Тиетявяйнен доказал ^[1] , что любой нетривиальный совершенный код над алфавитом с простой степенью имеет параметры кода Хэмминга или кода Голея .${\displaystyle \scriptstyle {\mathcal {A}}_{q}^{n}}$

Совершенный код можно интерпретировать как код, в котором шары радиуса Хэмминга t с центром на кодовых словах точно заполняют пространство ( t — радиус покрытия = радиус упаковки). Квазисовершенный код — это код, в котором шары радиуса Хэмминга t с центром на кодовых словах не пересекаются, а шары радиуса t +1 покрывают пространство, возможно, с некоторыми перекрытиями. ^[2] Другой способ сказать это — код является квазисовершенным , если его радиус покрытия на единицу больше его радиуса упаковки. ^[3]

• Связано Жильбер-Варшамов
• Гризмер связан
• Джонсон связан
• Плоткин связан
• Теория скорости-искажения
• Синглтон-граница

• PJ Cameron; JA Thas; SE Payne (1976). «Полярности обобщенных шестиугольников и совершенные коды». Geometriae Dedicata . 5 (4): 525– 528. doi :10.1007/BF00150782. S2CID  121071671.
• Хилл, Р. (1988). Первый курс по теории кодирования . Oxford University Press . ISBN 0-19-853803-0.
• MacWilliams, FJ ; NJA Sloane (1977). Теория кодов, исправляющих ошибки . Северная Голландия. ISBN 0-444-85193-3.
• Плесс, В. (1982). Введение в теорию кодов, исправляющих ошибки . John Wiley & Sons. ISBN 0-471-08684-3.
• Роман, С. (1992), Теория кодирования и информации , GTM , т. 134, Нью-Йорк: Springer-Verlag, ISBN 0-387-97812-7
• Тиетявяйнен, А. (1973). «О несуществовании совершенных кодов над конечными полями». SIAM J. Appl. Math . 24 : 88–96 . doi :10.1137/0124010.
• van Lint, JH (1992). Введение в теорию кодирования . GTM . Том 86 (2-е изд.). Springer-Verlag. ISBN 3-540-54894-7.
• ван Линт, Дж. Х. (1975). «Обзор совершенных кодов». Rocky Mountain Journal of Mathematics . 5 (2): 199– 224. doi : 10.1216/RMJ-1975-5-2-199 .