Код покрытия - Википедия - Covering code

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

Определение

Позволять , , быть целые числа.A код над алфавит Q размера |Q| = q называетсяq-ари р-покрытие кода длины песли за каждое слово Существует кодовое слово так что Расстояние Хэмминга Другими словами, сферы (или же мячи или ладьи) радиус ротносительно Хэмминга метрика вокруг кодовых слов C должен исчерпать конечный метрическое пространство . радиус покрытия кода C самый маленький р такой, что C является р-покрытие. идеальный код покрывающий код минимального размера.

Пример

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

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

В решимость минимального размера из q-ари р-покрытие кода длины п это очень сложная проблема. Во многих случаях только верхняя и нижняя границы известны с большим разрывом между ними. каждая конструкция покрывающего кода дает оценку сверху на Kq(прК нижним оценкам относятся граница покрытия сферы и оценки Родемича и .[2]Проблема покрытия тесно связана с проблемой упаковки в , т.е. определение максимального размера q-ари е-исправление ошибок код длины п.

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

Частным случаем является проблема футбольных бассейнов, на основе футбольный бассейн ставки, цель которых - предсказать результаты п футбольные матчи как домашнюю победу, ничью или победу на выезде, или, по крайней мере, для прогнозирования п - 1 из них с множественными ставками. Таким образом, тернарное покрытие, K3(п, 1), ищется.

Если затем 3п-k необходимы, поэтому для п = 4, k = 2, 9 необходимо; за п = 13, k = 3, 59049.[3] Лучшие границы, известные по состоянию на 2011 год[4] находятся

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

Приложения

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

Рекомендации

  1. ^ П.Р.Дж. Östergård, Верхние границы для q-арные коды покрытия, IEEE Transactions по теории информации, 37 (1991), 660-664
  2. ^ Родемич Е.Р. Покрытие ладейными доменами. Журнал комбинаторной теории, 9 (1970), 117-128
  3. ^ http://alexandria.tue.nl/repository/freearticles/593454.pdf
  4. ^ http://www.sztaki.hu/~keri/codes/3_tables.pdf
  5. ^ Г. Коэн, И. Хонкала, С. Лицын, А. Лобштейн, Коды покрытия, Эльзевир (1997) ISBN  0-444-82511-8
  6. ^ Х. Хямяляйнен, И. Хонкала, С. Лицын, P.R.J. Östergård, Футбольные бассейны - игра для математиков, Американский математический ежемесячный журнал, 102 (1995), 579-588

внешняя ссылка