Лексикографический код

редактировать

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

Содержание

1 Конструкция
2 Комбинаторная теория игр
3 Примечания
4 Внешние ссылки

Конструкция

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

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

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

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

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

Примечания

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

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