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

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

Общие сведения о кодах, исправляющих ошибки

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

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

Заявление о границах

Предварительные определения

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

Определение границы

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

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

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

где

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

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

Это следует из определения $d$ что если максимум

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

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

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

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

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

$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}.$

Откуда:

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

Радиус покрытия и радиус упаковки

Основная статья: Набор Делоне

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

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

s ≤ т и т ≤ р .

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

Идеальные коды

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

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

См. также

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

Ссылки

• Пи Джей Кэмерон; Дж. А. Тас; С. Э. Пейн (1976). «Полярности обобщенных шестиугольников и совершенных кодов». Геометрии посвященные . 5 (4): 525–528. дои : 10.1007/BF00150782 . S2CID   121071671 .
• Хилл, Р. (1988). Первый курс теории кодирования . Издательство Оксфордского университета . ISBN  0-19-853803-0 .
• МакВильямс, ФДж ; НЯА Слоан (1977). Теория кодов, исправляющих ошибки . Северная Голландия. ISBN  0-444-85193-3 .
• Плесс, В. (1982). Введение в теорию кодов, исправляющих ошибки . Джон Уайли и сыновья. ISBN  0-471-08684-3 .
• Роман, С. (1992), Теория кодирования и информации , GTM , vol. 134, Нью-Йорк: Springer-Verlag, ISBN.  0-387-97812-7
• Тиетявяйнен, А. (1973). «О несуществовании совершенных кодов над конечными полями» . СИАМ J. Appl. Математика . 24 : 88–96. дои : 10.1137/0124010 .
• ван Линт, Дж. Х. (1992). Введение в теорию кодирования . ГТМ . Том. 86 (2-е изд.). Спрингер-Верлаг. ISBN  3-540-54894-7 .
• ван Линт, Дж. Х. (1975). «Обзор совершенных кодов» . Математический журнал Роки Маунтин . 5 (2): 199–224. дои : 10.1216/RMJ-1975-5-2-199 .