導入
シンドローム復号は、線形符号を対象とした復号方法です。標準テーブルと呼ばれるテーブルを使用してデコードを行います。これは、コードの冗長性がそれほど大きくない場合に使用できます。つまり、テーブルのサイズが冗長性において指数関数的に大きくなります。
原理は次のとおりです。ワードxを受信すると、制御行列は変更がコミットされたかどうかを判断できるようになります。そうである場合、制御行列はシンドロームと呼ばれる量を提供します。標準テーブルは、このシンドロームと行われる修正との対応を提供します。修正されたメッセージはx -eと等しくなります。
コンテクスト
修正コード
修正コードの目的は、メッセージの送信後にエラーを検出または修正することです。この修正は、冗長な情報を追加することによって可能になります。メッセージはより大きなセットに埋め込まれ、サイズの違いには冗長性が含まれ、埋め込みを介してメッセージのイメージが送信されます。メッセージが破損した場合、エラーを検出または修正するために冗長性が設計されています。簡単な例は、繰り返しコードです。メッセージはたとえば 3 回送信され、デコードは投票によって行われます。ここで、より大きなセットは最初のメッセージのサイズの 3 倍になります。
リニアコード
形式化の基本要素を思い出してみましょう。有限体F d内に長さkの値を持つシーケンスで構成されるベクトル空間E が存在します。つまり、ランクkからは、シーケンスのすべての値がゼロになります。これらの要素は、伝えたいメッセージを入れるスペースです。メッセージに必要な冗長性を提供するために、 EからFの値までの単射線形マップφ、つまりFの値までの長さnのシーケンスの空間dが存在します。関数 φ はエンコーディングと呼ばれ、φ( E ) はCとも呼ばれ、コードの φ( E )ワードの要素、 k はコードの長さ、 n はコードの次元と呼ばれます。これらの表記は記事全体で使用されます。
詳しい操作方法
デコードと線形性
線形性によりデコードが大幅に簡素化されます。これを確認するには、例を調べるのが最も簡単な方法です。 minitelで使用される、長さ 120、最小距離 3 の次元 127 のバイナリで完全なコードを考えてみましょう。メッセージmがエンコードされて受信者に送信されると、エラーが発生しやすいFの要素xが受信されます。
確実に訂正可能な最大エラー数tは、厳密に 3/2 未満の最大の整数、つまりt = 1 です。コードは完全であるため、コード ワードを中心とする半径1の閉じたボールがFの分割を形成します。 。したがって、 x はc + eとして一意に記述されます。ここで、 cはコードワード、 e は1以下の重みを持つFの要素です。送信中にp 個のエラーが発生する確率がpの減少関数である場合、 c はおそらく φ( m ) に等しくなります。
eの可能な値のセットは比較的小さく、ここではコードがバイナリであるため、 eがゼロベクトルで補正が行われないか、またはe の重みが1 である、つまりeが127 座標のうち1 に相当する 1 つを除き、ゼロのみを含むメッセージ。 2,127個の要素を含む空間には、最終的に 128 個のエラー ケースしか存在しません。
線形性により、中心が0で半径tの単一の閉じたボール、つまりこの例では 128 点のボールの知識に限定することができます。一般的な場合、半径tの閉じたボールは基数V t を持ちます(ハミング境界を参照) 。
実装
修正コードの理論は、行列H が制御行列と呼ばれ、そのカーネルがコードである次元n – kの空間におけるFの全射線形写像の存在を主張します。その結果、次の等式が成り立ちます。
完全なコードの場合、中心がゼロ ベクトルで半径tの閉じた球へのHの制限は全単射です。ここで、行列H はその線形適用で識別されます。ミニテルの場合、単位ボールには 128 個の点が含まれており、 Hの到着集合は次元 7 の空間であり、したがって基数 128 の空間でもあります。
- 要素H. t x はFのx点症候群と呼ばれます。
中心ゼロベクトルと半径tを持つボール内のHによる各シンドロームとその固有の先行詞を関連付ける標準テーブルと呼ばれるテーブルからのデータにより、デコードが可能になります。誤り訂正は、受信したFの要素から前件e を減算することで構成されます。求められるコードワードはc = x – eです。この方法のコンピュータ実装ではハッシュ テーブルが使用され、高速にデコードする方法です。
一般的な場合、確実に訂正可能なエラーの最大数の値tに加えて、コードの中心点と半径s を持つ閉じたボールがFの重なりを形成するような最小値s を考慮する必要があります。コードは、 sがtに等しい場合にのみ完全です。 Hには次のプロパティがあります。
- 中心ゼロ ベクトル、半径 t のボールに対するHの制限は単射的であり、中心ゼロ ベクトル、半径 t のボールに対するHの制限は全射的です。
Hの場合、2 つのデコード方法があります。 t x は、半径tの閉球内に前件を認めません。新しい送信要求が行われるか、半径sの閉球内で前件がランダムに選択され、方法は同じままです。すべての場合において、標準テーブルにはd nk 個のエントリが含まれます。ここで、 dは有限体の基数です。
