多項式コード

符号理論において、多項式符号は、有効な符号語の集合が、与えられた固定多項式（より短い長さで、生成多項式と呼ばれる）で割り切れる多項式（通常は固定長）で構成される線形符号の一種です。

有限体 を固定し、その要素を記号と呼ぶ。多項式コードを構築する目的で、記号の列を多項式と 同一視する。${\displaystyle GF(q)}$${\displaystyle n}$${\displaystyle a_{n-1}\ldots a_{0}}$

${\displaystyle a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}.\,}$

整数を固定し、を次数の固定された多項式（生成多項式と呼ばれる）とします。によって生成される多項式コードは、で割り切れる（剰余なし）より小さい次数の多項式とまったく同じコードワードを持つコードです。 ${\displaystyle m\leq n}$${\displaystyle g(x)}$${\displaystyle m}$${\displaystyle g(x)}$${\displaystyle n}$${\displaystyle g(x)}$

、、生成多項式である 上の多項式コードを考えます。このコードは次のコードワードで構成されます。 ${\displaystyle GF(2)=\{0,1\}}$${\displaystyle n=5}$${\displaystyle m=2}$${\displaystyle g(x)=x^{2}+x+1}$

${\displaystyle 0\cdot g(x),\quad 1\cdot g(x),\quad x\cdot g(x),\quad (x+1)\cdot g(x),}$

${\displaystyle x^{2}\cdot g(x),\quad (x^{2}+1)\cdot g(x),\quad (x^{2}+x)\cdot g(x),\quad (x^{2}+x+1)\cdot g(x).}$

または明示的に記述すると:

${\displaystyle 0,\quad x^{2}+x+1,\quad x^{3}+x^{2}+x,\quad x^{3}+2x^{2}+2x+1,}$

${\displaystyle x^{4}+x^{3}+x^{2},\quad x^{4}+x^{3}+2x^{2}+x+1,\quad x^{4}+2x^{3}+2x^{2}+x,\quad x^{4}+2x^{3}+3x^{2}+2x+1.}$

多項式コードはバイナリガロア体上で定義されているため、多項式要素は -2 を法とした合計として表され、最終的な多項式は次のようになります。 ${\displaystyle GF(2)=\{0,1\}}$

${\displaystyle 0,\quad x^{2}+x+1,\quad x^{3}+x^{2}+x,\quad x^{3}+1,}$

${\displaystyle x^{4}+x^{3}+x^{2},\quad x^{4}+x^{3}+x+1,\quad x^{4}+x,\quad x^{4}+x^{2}+1.}$

同様に、2 進数の文字列として表現すると、コードワードは次のようになります。

${\displaystyle 00000,\quad 00111,\quad 01110,\quad 01001,}$

${\displaystyle 11100,\quad 11011,\quad 10010,\quad 10101.}$

これは、すべての多項式コードと同様に、実際には線形コードです。つまり、コードワードの線形結合は、やはりコードワードです。体が GF(2) であるこのようなケースでは、線形結合は、バイナリ形式で表現されたコードワードの XOR を取ることによって求められます (例: 00111 XOR 10010 = 10101)。

符号長が で生成多項式が 次である 上の多項式符号では、ちょうど 個の符号語が存在する。実際、定義により、が符号語となるのは、 の形式である場合のみであり、ここで(商) は 次数未満である。このような商が存在するため、可能な符号語の数も同じである。したがって、プレーン (符号化されていない) データ語の長さは である。${\displaystyle GF(q)}$${\displaystyle n}$${\displaystyle g(x)}$${\displaystyle m}$${\displaystyle q^{nm}}$${\displaystyle p(x)}$${\displaystyle p(x)=g(x)\cdot q(x)}$${\displaystyle q(x)}$${\displaystyle nm}$${\displaystyle q^{nm}}$${\displaystyle nm}$

Lidl & Pilz (1999) などの一部の著者は、マッピングをデータ ワードからコード ワードへの割り当てとしてのみ説明しています。ただし、これには、データ ワードがコード ワードの一部として表示されないという欠点があります。 ${\displaystyle q(x)\mapsto g(x)\cdot q(x)}$

代わりに、体系的なコードを作成するために、次の方法がよく使用されます。長さ のデータ ワードが与えられた場合、最初に を掛けます。これにより、桁左にシフトする効果があります。一般に、はで割り切れません。つまり、有効なコード ワードにはなりません。ただし、の右端のシンボルを調整することで取得できる一意のコード ワードがあります。これを計算するには、を で割った余りを計算します。 ${\displaystyle d(x)}$${\displaystyle nm}$${\displaystyle d(x)}$${\displaystyle x^{m}}$${\displaystyle d(x)}$${\displaystyle m}$${\displaystyle x^{m}d(x)}$${\displaystyle g(x)}$${\displaystyle m}$${\displaystyle x^{m}d(x)}$${\displaystyle x^{m}d(x)}$${\displaystyle g(x)}$

${\displaystyle x^{m}d(x)=g(x)\cdot q(x)+r(x),\,}$

ここで、は より小さい次数である。データワードに対応するコードワードは次のように定義される。 ${\displaystyle r(x)}$${\displaystyle m}$${\displaystyle d(x)}$

${\displaystyle p(x):=x^{m}d(x)-r(x),\,}$

次のプロパティに注意してください。

1. ${\displaystyle p(x)=g(x)\cdot q(x)}$は で割り切れます。特に、は有効なコードワードです。${\displaystyle g(x)}$${\displaystyle p(x)}$
2. の次数は より小さいので、の左端のシンボルはの対応するシンボルと一致します。言い換えると、コード ワードの最初のシンボルは元のデータ ワードと同じです。残りのシンボルはチェックサム ディジットまたはチェック ビットと呼ばれます。${\displaystyle r(x)}$${\displaystyle m}$${\displaystyle nm}$${\displaystyle p(x)}$${\displaystyle x^{m}d(x)}$${\displaystyle nm}$${\displaystyle m}$

、、および生成多項式 を使用した上記のコードでは、データワードからコードワードへの次の割り当てが得られます。 ${\displaystyle n=5}$${\displaystyle m=2}$${\displaystyle g(x)=x^{2}+x+1}$

• 000 ↦ 000 00
• 001 ↦ 001 11
• 010 ↦ 010 01
• 011 ↦ 011 10
• 100 ↦ 100 10
• 101 ↦ 101 01
• 110 ↦ 110 11
• 111 ↦ 111 00

誤ったメッセージは、生成多項式による多項式除算によって非ゼロの剰余が生成されるため、簡単に検出できます。

コードワードにエラーがないと仮定すると、チェックサムの数字を取り除くだけで体系的なコードをデコードできます。 ${\displaystyle m}$

エラーがある場合は、デコードする前にエラー訂正を実行する必要があります。BCHコードなどの特定の多項式コードには、効率的なデコード アルゴリズムが存在します。

すべてのデジタル コードと同様に、多項式コードのエラー検出および訂正能力は、コードの最小ハミング距離によって決まります。多項式コードは線形コードであるため、最小ハミング距離は、非ゼロ コードワードの最小重みに等しくなります。上記の例では、01001 がコードワードであり、1 ビットのみが設定されている非ゼロ コードワードがないため、最小ハミング距離は 2 です。

多項式コードのより具体的な特性は、多くの場合、その生成多項式の特定の代数特性に依存します。次に、そのような特性の例をいくつか示します。

• 多項式符号は、生成多項式が を割り切る場合のみ巡回符号となります。${\displaystyle x^{n}-1}$
• 生成多項式が原始 である場合、 を条件として、結果のコードのハミング距離は少なくとも 3 になります。${\displaystyle n\leq 2^{m}-1}$
• BCH コードでは、高いハミング距離を実現するように、拡大体で特定の根を持つように生成多項式が選択されます。

巧みに選択された生成多項式を使用した多項式コードの代数的性質は、効率的なエラー訂正アルゴリズムを見つけるために利用されることもよくあります。これはBCH コードの場合です。

• 巡回コード- すべての巡回コードは多項式コードでもあります。一般的な例としてはCRCコードがあります。
• BCH コード– 高いハミング距離と効率的な代数的誤り訂正アルゴリズムを備えた巡回コードのファミリー。
• リード・ソロモン符号– 特に効率的な構造を持つ BCH 符号の重要なサブセット。

• WJ Gilbert および WK Nicholson: Modern Algebra with Applications、第 2 版、Wiley、2004 年。
• R. Lidl および G. Pilz. 応用抽象代数、第 2 版。Wiley、1999 年。