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

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

Определение

Пусть , , будут целыми числами . Код над алфавитом Q размера | Q | = q называется q -ичным R -покрывающим кодом длины n , если для каждого слова существует кодовое слово такое, что расстояние Хэмминга . Другими словами, сферы (или шары , или ладейные области) радиуса R относительно метрики Хэмминга вокруг кодовых слов C должны исчерпать конечное метрическое пространство . Радиус покрытия кода C - это наименьшее R такое, что C является R -покрывающим. Каждый совершенный код является покрывающим кодом минимального размера. д ≥ 2 {\displaystyle q\geq 2} н ≥ 1 {\displaystyle n\geq 1} Р ≥ 0 {\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)} К д ( н , 1 ) ≥ д н − 1 / ( н − 1 ) {\displaystyle K_{q}(n,1)\geq q^{n-1}/(n-1)} К д ( н , н − 2 ) ≥ д 2 / ( н − 1 ) {\displaystyle K_{q}(n,n-2)\geq q^{2}/(n-1)} В н {\displaystyle Q^{n}}

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

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

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

н1234567891011121314
К 3 ( н ,1)13592771-73156-186402-4861060-12692854-36457832-947721531-2770259049166610-177147
К 3 ( н ,2)133815-1726-3454-81130-219323-5557291919-21875062-656112204-19683
К 3 ( н ,3)133611-1214-2727-5457-105117-243282-657612-12151553-2187

Приложения

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

Ссылки

  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)}
Взято с "https://en.wikipedia.org/w/index.php?title=Covering_code&oldid=1229754675"