Loading article…
辞書式符号またはレキシコードとは、貪欲法によって生成された、非常に優れた特性を持つ 誤り訂正符号のことです。これらは、ウラジミール・レベンシュタイン[ 1 ]とジョン・ホートン・コンウェイおよびニール・スローン[ 2 ]によって独立に作成されました。バイナリ辞書式符号は線形符号であり、ハミング符号とバイナリ・ゴレイ符号が含まれます[ 2 ]。
有限体上の長さnで最小距離dのレキシコードは、すべてゼロのベクトルから始めて、これまでに追加されたベクトルの中から最小ハミング距離dの次のベクトル (辞書順) を繰り返し追加することによって生成されます。例として、最小距離 2 の長さ 3 のレキシコードは、次の例で「X」でマークされたベクトルで構成されます。
ここに、dビット最小ハミング距離によるすべてのnビット辞書の表を示します。これは、最大2m個のコードワード辞書から得られます。たとえば、F4コード（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言語で辞書式コードを生成し、Golayコード（N=24、D=8）のパラメータを設定します。
#include <stdio.h> #include <stdlib.h> int main () { /* GOLAY CODE 生成 */ 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 ++ ) { //以前のすべてのレキシコードをスキャンします。if ( pc ( z [ k ] ^ i ) < D ) //逆チェックbreak ; //はるかに高速です... if ( k == -1 ) { //新しいレキシコードを追加します。for ( k = 0 ; k < N ; k ++ ) //それを出力します。printf ( "% d " , ( i >> k ) & 1 ); printf ( " : %d \ n " , j ); z [ j ++ ] = i; } } }辞書式符号の理論は、組み合わせゲーム理論と密接に関連している。特に、距離dのバイナリ辞書式符号の符号語は、石の山の集合上で行われるグランディのゲームの変種における勝利位置を符号化する。このゲームでは、各操作は任意の 1 つの山を最大d − 1 個のより小さな山に置き換えることであり、目標は最後の石を取ることである。[ 2 ]