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

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

Справочная информация о кодах, исправляющих ошибки [ править ]

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

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

Заявление о привязке [ править ]

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

Тогда оценка Хэмминга:

${\ 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 d}$

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

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

Для каждого кодового слова рассмотрим шар фиксированного радиуса вокруг . Каждая пара этих шаров (сфер Хэмминга) не пересекаются по свойству исправления ошибок. Позвольте быть количество слов в каждом шаре (другими словами, объем шара). Слово , которое находится в таком шаре может отклоняться не более чем в компонентах от тех шара центра , который является кодовым словом. Число таких слов , затем получают путем выбора до из компонентов кодового слова отклоняться к одному из возможных других значений (напомним, что код -ичный: он принимает значения в ). Таким образом,${\ displaystyle c \ in C}$${\ displaystyle t}$${\ displaystyle c}$${\ displaystyle t}$${\ displaystyle m}$${\ displaystyle t}$${\ displaystyle t}$${\ displaystyle n}$${\ Displaystyle (д-1)}$${\ displaystyle q}$${\ 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 C}$${\displaystyle t}$${\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 является наименьшим значением г таким образом, что каждый элемент содержится по меньшей мере , одного шара радиуса г с центром в точке каждого кодового слова C . Радиус упаковки из C представляет наибольшее значение х таких , что множество шаров радиуса с центром в начале каждого кодового слова 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 - радиус покрытия = радиус упаковки). Квази-совершенный код является тот , в котором шары радиуса Хемминга т сосредоточены на кодовых слов не пересекаются и шары радиуса т + 1 крышка пространство, возможно , с некоторыми наложений. ^[2] Другой способ сказать это: код является квази-совершенным, если его радиус покрытия на единицу больше, чем радиус его упаковки. ^[3]

См. Также [ править ]

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

Примечания [ править ]

Ссылки [ править ]

• Раймонд Хилл (1988). Первый курс теории кодирования . Издательство Оксфордского университета . ISBN 0-19-853803-0.
• FJ MacWilliams ; NJA Sloane (1977). Теория кодов, исправляющих ошибки . Северная Голландия. ISBN 0-444-85193-3.
• Вера Плесс (1982). Введение в теорию кодов, исправляющих ошибки . Джон Вили и сыновья. ISBN 0-471-08684-3.
• Роман, Стивен (1992), Теория кодирования и информации , GTM , 134 , Нью-Йорк: Springer-Verlag, ISBN 0-387-97812-7
• Дж. Х. ван Линт (1992). Введение в теорию кодирования . GTM . 86 (2-е изд.). Springer-Verlag. ISBN 3-540-54894-7.
• Дж. Х. ван Линт (1975). «Обзор совершенных кодов» . Математический журнал Скалистых гор . 5 (2): 199–224. DOI : 10,1216 / RMJ-1975-5-2-199 .
• П. Дж. Кэмерон; JA Thas; С. Е. Пейн (1976). «Полярности обобщенных шестиугольников и совершенные коды». 5 : 525–528. DOI : 10.1007 / BF00150782 . Cite journal requires |journal= (help)