辞書式コード
辞書式符号（レキシコード）は、貪欲法で生成される誤り訂正符号であり、非常に優れた特性を持つ。これらは、ウラジミール・レーベンシュタイン[1]とジョン・ホートン・コンウェイ、ニール・スローン[2]によって独立に構築された。2進辞書式符号は線形符号であり、ハミング符号や2進ゴレイ符号などが含まれる。[2]
工事
有限体上の長さn、最小距離dのレキシコードは、すべてゼロのベクトルから始めて、それまでに追加したベクトルからハミング距離dが最小となる次のベクトル（辞書式順序）を反復的に追加することで生成されます。例えば、長さ 3 、最小距離 2 のレキシコードは、次の例で「X」でマークされたベクトルで構成されます。
ベクター コードで？ 000 X 001 010 011 X 100 101 X 110 X 111
以下に、最大2mのコードワード辞書から得られる、dビット最小ハミング距離によるnビット辞書全体の表を示します。例えば、F4コード（n=4、d=2、m=3）、拡張ハミングコード（n=8、d=4、m=4）、そして特にゴレイコード（n=24、d=8、m=12）は、近隣のコードと比較して非常にコンパクトです。
n \ d 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 は辞書式コードを生成し、パラメータは 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 ++ ) { // 以前のすべての辞書コードをスキャンしますfor ( k = j -1 ; k >= 0 ; k -- ) // 辞書コード。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の2進辞書式符号の符号語は、石の山の集合上で行われるグランディのゲームにおける勝利の位置を符号化する。このゲームでは、各移動は任意の1つの山を最大d − 1個の小さな山に置き換えることで構成され、最後の石を取ることが目標となる。[2]
注記
- ^ Levenšteĭn, VI (1960)、「Об одном классе систематических кодов」 [体系的コードのクラス]、Doklady Akademii Nauk SSSR (ロシア語)、131 (5): 1011–1014、MR 0122629;ソビエト数学誌『ドクラディ1』（1960年）、368-371頁の英訳
- ^ abc Conway, John H. ; Sloane, NJA (1986)、「辞書式コード：ゲーム理論からの誤り訂正コード」、IEEE Transactions on Information Theory、32 (3): 337– 348、CiteSeerX 10.1.1.392.795、doi :10.1109/TIT.1986.1057187、MR 0838197
- ^ Trachtenberg, Ari (2002)、「与えられたトレリス複雑度を持つ辞書式コードの設計」、IEEE Transactions on Information Theory、48 (1): 89– 100、doi :10.1109/18.971740、MR 1866958
外部リンク
- ボブ・ジェンキンスのバイナリ辞書表
- 辞書とその変種のオンラインジェネレータ
- OEISシーケンス A075928 (ハミング距離 4 のバイナリ レキシコード内のコードワードのリストを 10 進数で記述したもの。)
- グラフ上の誤り訂正符号：レキシコード、トレリス、因子グラフ
