Покрывающий код

В теории кодирования покрывающий код представляет собой набор элементов (называемых кодовыми словами ) в пространстве, обладающий тем свойством, что каждый элемент пространства находится в пределах фиксированного расстояния от некоторого кодового слова.

Определение

Пусть , , будут целыми числами . Код над алфавитом Q размера | Q | = q называется q -ичным R -покрывающим кодом длины n , если для каждого слова существует кодовое слово такое, что расстояние Хэмминга . Другими словами, сферы (или шары , или ладейные области) радиуса R относительно метрики Хэмминга вокруг кодовых слов C должны исчерпать конечное метрическое пространство . Радиус покрытия кода C - это наименьшее R такое, что C является R -покрывающим. Каждый совершенный код является покрывающим кодом минимального размера. ${\displaystyle q\geq 2}$ ${\displaystyle n\geq 1}$ ${\displaystyle R\geq 0}$ ${\displaystyle C\subseteq Q^{n}}$ ${\displaystyle y\in Q^{n}}$ ${\displaystyle x\in C}$ ${\displaystyle d_{H}(x,y)\leq R}$ ${\displaystyle Q^{n}}$

Пример

C = {0134,0223,1402,1431,1444,2123,2234,3002,3310,4010,4341} — 5-арный 2-покрывающий код длины 4. ^[1]

Проблема покрытия

Определение минимального размера q -ичного R -покрывающего кода длины n является очень сложной задачей. Во многих случаях известны только верхняя и нижняя границы с большим зазором между ними. Каждая конструкция покрывающего кода дает верхнюю границу для K _q ( n ,  R ). Нижние границы включают границу покрытия сферы и границы Родемиха и . ^[2] Задача покрытия тесно связана с задачей упаковки в , то есть определением максимального размера q -ичного e - кода с исправлением ошибок длины n . ${\displaystyle K_{q}(n,R)}$ ${\displaystyle K_{q}(n,1)\geq q^{n-1}/(n-1)}$ ${\displaystyle K_{q}(n,n-2)\geq q^{2}/(n-1)}$ ${\displaystyle Q^{n}}$

Проблема футбольных пулов

Частным случаем является задача о футбольных ставках , основанная на ставках на футбольные ставки , где цель состоит в том, чтобы придумать систему ставок на n футбольных матчей, которая, независимо от результата, имеет не более R «промахов». Таким образом, для n матчей с не более чем одним «промахом» ищется тернарное покрытие K ₃ ( n ,1).

Если тогда необходимо 3 ^{n - k} , то для n = 4, k = 2 необходимо 9; для n = 13, k = 3 необходимо 59049. ^[3] Наилучшие границы, известные по состоянию на 2011 год ^[4] , следующие : ${\displaystyle n={\tfrac {1}{2}}(3^{k}-1)}$

Приложения

В стандартной работе ^[5] по покрывающим кодам перечислены следующие приложения.

• Сжатие с искажением
• Сжатие данных
• Ошибки декодирования и стирания
• Вещание в сетях взаимоподключения
• Футбольные пулы ^[6]
• Воспоминания, которые можно записать один раз
• Игра Берлекэмпа-Гейла
• Кодирование речи
• Сотовая связь
• Суммы подмножеств и графы Кэли

Ссылки

1. PRJ Östergård (1991). «Верхние границы для q -ичных покрывающих кодов». Труды IEEE по теории информации . 37 : 660–664.
2. ER Rodemich (1970). «Покрытие ладейными областями». Журнал комбинаторной теории . 9 : 117–128.
3. Кампс, HJL; ван Линт, JH (декабрь 1967 г.). «Проблема футбольного пула для 5 матчей» (PDF) . Журнал комбинаторной теории . 3 (4): 315–325. doi :10.1016/S0021-9800(67)80102-9 . Получено 9 ноября 2022 г. .
4. «Оценки K3(n, R) (нижняя и верхняя границы размера троичных оптимальных покрывающих кодов)» (PDF) . АВТОМАТИЧЕСКАЯ ТЕХНИКА . Архивировано (PDF) из оригинала 27 октября 2022 года . Проверено 9 ноября 2022 г.
5. Г. Коэн, И. Хонкала, С. Лицын, А. Лобштейн (1997). Коды покрытия . Эльзевир . ISBN 0-444-82511-8.{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
6. Х. Хямяляйнен, И. Хонкала, С. Лицын, PRJ Östergård (1995). «Футбольный бильярд — игра для математиков». Американский математический ежемесячник . 102 : 579–588.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )

Внешние ссылки

• Литература по кодам покрытия
• Границы K q ( n , R ) {\displaystyle K_{q}(n,R)}