Лексикографические коды или лексикоды — это жадно генерируемые коды с исправлением ошибок с удивительно хорошими свойствами. Они были произведены независимо Владимиром Левенштейном [1] и Джоном Хортоном Конвеем и Нилом Слоаном . [2] Двоичные лексикографические коды являются линейными кодами и включают коды Хэмминга и двоичные коды Голея . [2]
Лексикод длины n и минимального расстояния d в конечном поле генерируется путем итеративного добавления следующего вектора (в лексикографическом порядке ) с минимальным расстоянием Хэмминга d из добавленных к этому моменту векторов. Например, лексикод длины 3 с минимальным расстоянием 2 будет состоять из векторов, отмеченных знаком «X» в следующем примере:
Вот таблица всех n-битных лексикодов с минимальным расстоянием Хэмминга d-бит, полученная в результате словаря кодовых слов длиной не более 2 м . Например, код F 4 (n=4,d=2,m=3), расширенный код Хэмминга (n=8,d=4,m=4) и особенно код Голея (n=24,d=8,m =12) демонстрирует исключительную компактность по сравнению с соседями.
Все нечетные d-битные расстояния лексикода являются точными копиями четных битовых расстояний d+1 минус последнее измерение, поэтому нечетномерное пространство никогда не сможет создать что-то новое или более интересное, чем четномерное пространство d+1, указанное выше.
Поскольку лексикоды линейны, их можно построить и с помощью их базиса . [3]
После C генерируется лексикографический код и устанавливаются параметры для кода Голея (N=24, D=8).
#include <stdio.h> #include <stdlib.h> int main () { /* Генерация КОДА ГОЛЕЯ */ int i , j , k ; int _pc [ 1 << 16 ] = {0} ; _ // Макрос PopCount for ( i = 0 ; i < ( 1 << 16 ); i ++ ) for ( j = 0 ; j < 16 ; j ++ ) _pc [ i ] += ( i >> j ) & 1 ; #define pc(X) (_pc[(X)&0xffff] + _pc[((X)>>16)&0xffff]) #define N 24 // N бит #define D 8 // Расстояние между D битами unsigned int * z = malloc ( 1 << 29 ); for ( i = j = 0 ; i < ( 1 << N ); i ++ ) { // Сканируем все предыдущие for ( k = j -1 ; k >= 0 ; k -- ) // лексикоды. if ( pc ( z [ k ] ^ i ) < D ) // Обратная проверка Break ; // намного быстрее... if ( k == -1 ) { // Добавляем новый лексикод для ( k = 0 ; k < N ; k ++ ) // и печатаем его printf ( "%d" , ( i >> к ) & 1 ); printf ( ": %d \n " , j ); z [ j ++ ] = я ; } } }
Теория лексикографических кодов тесно связана с комбинаторной теорией игр . В частности, кодовые слова в двоичном лексикографическом коде расстояния d кодируют выигрышные позиции в варианте игры Гранди , играемой на наборе куч камней, в которой каждый ход состоит из замены любой одной кучки не более чем на d − 1 меньшую. кучи, и цель – взять последний камень. [2]