Лексикографический код - Википедия - Lexicographic code

Лексикографические коды или лексикоды жадно генерируются коды с исправлением ошибок с замечательно хорошими свойствами. Их производили самостоятельноВладимир Левенштейн[1] и по Джон Хортон Конвей и Нил Слоан.[2] Двоичные лексикографические коды: линейные коды, и включить Коды Хэмминга и двоичные коды Голея.[2]

Строительство

Лексикод минимального расстояния d и длина п через конечное поле генерируется, начиная с вектора со всеми нулями и итеративно добавляя следующий вектор (в лексикографический порядок ) минимального Расстояние Хэмминга d из добавленных векторов. В качестве примера, лексикод длины 3 с минимальным расстоянием 2 будет состоять из векторов, отмеченных знаком "X" в следующем примере:

ВекторВ коде?
000Икс
001
010
011Икс
100
101Икс
110Икс
111

Поскольку лексикоды линейны, их также можно построить с помощью основа.[3]

Комбинаторная теория игр

Теория лексикографических кодов тесно связана с комбинаторная теория игр. В частности, кодовые слова в двоичном лексикографическом коде расстояния d закодировать выигрышные позиции в варианте Игра Гранди, играемый на кучке камней, в которой каждый ход состоит из замены любой кучи не более чем на d - 1 куча поменьше, и цель - взять последний камень.[2]

Примечания

  1. ^ Левенштейн, В.И. (1960), "Об одном классе систематических кодов" [Класс систематических кодов], Доклады Академии Наук СССР (на русском), 131 (5): 1011–1014, МИСТЕР  0122629; Английский перевод в Советская математика. Доклады 1 (1960), 368–371
  2. ^ а б c Конвей, Джон Х.; Слоан, Н. Дж. А. (1986), «Лексикографические коды: коды с исправлением ошибок из теории игр», IEEE Transactions по теории информации, 32 (3): 337–348, Дои:10.1109 / TIT.1986.1057187, МИСТЕР  0838197
  3. ^ Трахтенберг, Ари (2002), "Разработка лексикографических кодов с заданной сложностью решетки", IEEE Transactions по теории информации, 48 (1): 89–100, Дои:10.1109/18.971740, МИСТЕР  1866958

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