В математике и информатике , в области теории кодирования , граница Хэмминга является пределом параметров произвольного блочного кода : она также известна как граница упаковки сфер или граница объема из интерпретации в терминах упаковки шаров. в метрике Хэмминга в пространство всех возможных слов. Это дает важное ограничение на эффективность, с которой любой код с исправлением ошибок может использовать пространство, в котором его кодовые словавстроены. Код, который достигает границы Хэмминга, называется совершенным кодом .
Справочная информация о кодах с исправлением ошибок
Исходное сообщение и закодированная версия состоят из q букв алфавита. Каждое кодовое слово состоит из n букв. Исходное сообщение (длиной m ) короче n букв. Сообщение преобразуется в n- буквенное кодовое слово алгоритмом кодирования, передается по зашумленному каналу и, наконец, декодируется приемником. Процесс декодирования интерпретирует искаженное кодовое слово, называемое просто словом , как действительное кодовое слово, "ближайшее" к принятой строке из n букв.
Математически существует ровно q m возможных сообщений длины m , и каждое сообщение можно рассматривать как вектор длины m . Схема кодирования преобразует m -мерный вектор в n- мерный вектор. Возможны ровно q m допустимых кодовых слов, но может быть принято любое из q n слов, потому что зашумленный канал может исказить одну или несколько из n букв при передаче кодового слова.
Заявление о привязке
Предварительные определения
Набор алфавита представляет собой набор символов с элементы. Набор струн длины по набору алфавита обозначаются . (Есть отдельные строки в этом наборе строк.) A -арный блочный код длины является подмножеством строк , где алфавит установлен любой алфавитный набор, имеющий элементы. (Выбор алфавита установлен не влияет на результат, если алфавит имеет размер ; например, любой блочный код, определенный с помощью алфавита можно преобразовать в единицу с помощью алфавита простым шифром подстановки и наоборот. EG для блочного кода длины 2 кодовые слова а также можно преобразовать в кодовые слова а также и наоборот. Возможно более одного такого шифра подстановки, но различия не имеют отношения к оценке и ее доказательству.)
Определение границы
Позволять обозначают максимально возможный размер -арный блочный код длины и минимальное расстояние Хэмминга между элементами блочного кода (обязательно положительный для ).
Тогда оценка Хэмминга:
где
Доказательство
Из определения что если самое большее
ошибки совершаются во время передачи кодового слова, тогда декодирование с минимальным расстоянием декодирует его правильно (т. е. оно декодирует полученное слово как кодовое слово, которое было отправлено). Таким образом, считается, что код может исправлять ошибки.
Для каждого кодового слова , рассмотрим шар фиксированного радиуса вокруг . Каждая пара этих шаров (сфер Хэмминга) не пересекаетсясвойство исправления ошибок. Позволять- количество слов в каждом шаре (другими словами, объем шара). Слово, содержащееся в таком шаре, может отклоняться не более чем накомпоненты из тех шара центра , который является кодовым словом. Затем количество таких слов получается путем выбора до принадлежащий компоненты кодового слова для отклонения от одного из возможные другие значения (напомним, код -ary: принимает значения в ). Таким образом,
это (максимальное) общее количество кодовых слов в , а значит, по определению , наибольшее количество шаров, у которых нет двух шаров, имеющих общее слово. В результате объединения слов в этих шарах с центрами кодовых слов получается набор слов, каждое из которых считается точно один раз, то есть подмножество слов (где слова) и так:
Откуда:
Радиус покрытия и радиус упаковки
Для код C (подмножество), То радиус покрытия из C является наименьшим значением г таким образом, что каждый элементсодержится в по меньшей мере одного шара радиуса г с центром в точке каждого кодового слова C . Радиус упаковки из C представляет наибольшее значение х таких , что множество шаров радиуса с центром в начале каждого кодового слова C попарно не пересекаются.
Из доказательства оценки Хэмминга видно, что для , у нас есть:
- s ≤ t и t ≤ r .
Следовательно, s ≤ r и если выполняется равенство, то s = r = t . Случай равенства означает, что оценка Хэмминга достигается.
Совершенные коды
Коды, которые достигают границы Хэмминга, называются совершенными кодами . Примеры включают коды, содержащие только одно кодовое слово, и коды, содержащие все. Другой пример - повторяющиеся коды , где каждый символ сообщения повторяется нечетное фиксированное количество раз, чтобы получить кодовое слово, где q = 2. Все эти примеры часто называют тривиальными совершенными кодами. В 1973 году было доказано, что любой нетривиальный совершенный код над алфавитом со степенью простого числа имеет параметры кода Хэмминга или кода Голея . [1]
Совершенный код можно интерпретировать как код, в котором шары радиуса Хэмминга t с центрами на кодовых словах точно заполняют пространство ( t - радиус покрытия = радиус упаковки). Квази-совершенный код является тот , в котором шары радиуса Хемминга т сосредоточены на кодовых слов не пересекаются и шары радиуса т + 1 крышка пространство, возможно , с некоторыми наложений. [2] Другой способ сказать это: код является квази-совершенным, если его радиус покрытия на единицу больше, чем радиус его упаковки. [3]
Смотрите также
Заметки
- ^ Хилл (1988) стр. 102
- Перейти ↑ McWilliams and Sloane, p. 19
- ↑ Роман 1992 , стр. 140
Рекомендации
- Раймонд Хилл (1988). Первый курс теории кодирования . Издательство Оксфордского университета . ISBN 0-19-853803-0.
- FJ MacWilliams ; NJA Sloane (1977). Теория кодов, исправляющих ошибки . Северная Голландия. ISBN 0-444-85193-3. CS1 maint: обескураженный параметр ( ссылка )
- Вера Плесс (1982). Введение в теорию кодов, исправляющих ошибки . Джон Вили и сыновья. ISBN 0-471-08684-3. CS1 maint: обескураженный параметр ( ссылка )
- Роман, Стивен (1992), Теория кодирования и информации , GTM , 134 , Нью-Йорк: Springer-Verlag, ISBN 0-387-97812-7
- Дж. Х. ван Линт (1992). Введение в теорию кодирования . GTM . 86 (2-е изд.). Springer-Verlag. ISBN 3-540-54894-7. CS1 maint: обескураженный параметр ( ссылка )
- Дж. Х. ван Линт (1975). «Обзор совершенных кодов» . Математический журнал Роки-Маунтин . 5 (2): 199–224. DOI : 10,1216 / RMJ-1975-5-2-199 . CS1 maint: обескураженный параметр ( ссылка )
- П. Дж. Кэмерон; JA Thas; С. Е. Пейн (1976). «Полярности обобщенных шестиугольников и совершенные коды». 5 : 525–528. DOI : 10.1007 / BF00150782 . Цитировать журнал требует
|journal=
( помощь )