Лексикографический код
Лексикографические коды или лексикоды — это жадно генерируемые коды с исправлением ошибок с удивительно хорошими свойствами. Они были произведены независимо Владимир Левенштейн [1] и Джон Хортон Конвей и Нил Слоан . [2] Двоичные лексикографические коды являются линейными кодами и включают коды Хэмминга и двоичные коды Голея . [2]
Строительство [ править ]
Лексикод длины n и минимального расстояния d в конечном поле генерируется путем итеративного добавления следующего вектора (в лексикографическом порядке ) с минимальным расстоянием Хэмминга d из векторов, добавленных на данный момент. Например, лексикод длины 3 с минимальным расстоянием 2 будет состоять из векторов, отмеченных знаком «X» в следующем примере:
Вектор В коде? 000 Х 001 010 011 Х 100 101 Х 110 Х 111
Вот таблица всех n-битных лексикодов по d-битному минимальному расстоянию Хэмминга, в результате максимум 2 м словарь кодовых слов.Например, код F 4 (n=4,d=2,m=3), расширенный код Хэмминга (n=8,d=4,m=4) и особенно код Голея (n=24,d=8,m =12) демонстрирует исключительную компактность по сравнению с соседями.
н\д 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 1 2 2 1 3 3 2 1 4 4 3 1 1 5 5 4 2 1 1 6 6 5 3 2 1 1 7 7 6 4 3 1 1 1 8 8 7 4 4 2 1 1 1 9 9 8 5 4 2 2 1 1 1 10 10 9 6 5 3 2 1 1 1 1 11 11 10 7 6 4 3 2 1 1 1 1 12 12 11 8 7 4 4 2 2 1 1 1 1 13 13 12 9 8 5 4 3 2 1 1 1 1 1 14 14 13 10 9 6 5 4 3 2 1 1 1 1 1 15 15 14 11 10 7 6 5 4 2 2 1 1 1 1 1 16 16 15 11 11 8 7 5 5 2 2 1 1 1 1 1 1 17 17 16 12 11 9 8 6 5 3 2 2 1 1 1 1 1 1 18 18 17 13 12 9 9 7 6 3 3 2 2 1 1 1 1 1 1 19 19 18 14 13 10 9 8 7 4 3 2 2 1 1 1 1 1 1 20 20 19 15 14 11 10 9 8 5 4 3 2 2 1 1 1 1 1 21 21 20 16 15 12 11 10 9 5 5 3 3 2 2 1 1 1 1 22 22 21 17 16 12 12 11 10 6 5 4 3 2 2 1 1 1 1 23 23 22 18 17 13 12 12 11 6 6 5 4 2 2 2 1 1 1 24 24 23 19 18 14 13 12 12 7 6 5 5 3 2 2 2 1 1 25 25 24 20 19 15 14 12 12 8 7 6 5 3 3 2 2 1 1 26 26 25 21 20 16 15 12 12 9 8 7 6 4 3 2 2 2 1 27 27 26 22 21 17 16 13 12 9 9 7 7 5 4 3 2 2 2 28 28 27 23 22 18 17 13 13 10 9 8 7 5 5 3 3 2 2 29 29 28 24 23 19 18 14 13 11 10 8 8 6 5 4 3 2 2 30 30 29 25 24 19 19 15 14 12 11 9 8 6 6 5 4 2 2 31 31 30 26 25 20 19 16 15 12 12 10 9 6 6 6 5 3 2 32 32 31 26 26 21 20 16 16 13 12 11 10 7 6 6 6 3 3 33 ... 32 ... 26 ... 21 ... 16 ... 13 ... 11 ... 7 ... 6 ... 3
Все нечетные 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]
Примечания [ править ]
- ^ Levenšteĭn, V. I. (1960), "Об одном классе систематических кодов" [A class of systematic codes], Doklady Akademii Nauk SSSR (in Russian), 131 (5): 1011–1014, MR 0122629 ; English translation in Soviet Math. Doklady 1 (1960), 368–371
- ^ Jump up to: Перейти обратно: а б с Конвей, Джон Х .; Слоан, NJA (1986), «Лексикографические коды: коды с исправлением ошибок из теории игр», IEEE Transactions on Information Theory , 32 (3): 337–348, CiteSeerX 10.1.1.392.795 , doi : 10.1109/TIT.1986.1057187 , МР 0838197
- ^ Трахтенберг, Ари (2002), «Проектирование лексикографических кодов с заданной решетчатой сложностью», IEEE Transactions on Information Theory , 48 (1): 89–100, doi : 10.1109/18.971740 , MR 1866958