多項式コード

線形コードの種類

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

意味

有限体 を固定し、その元を記号と呼ぶ。多項式符号を構成するために、記号列を多項式と 同一視する。 ${\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)である場合、線形結合は2進数で表された符号語のXORをとることで求められます（例：00111 XOR 10010 = 10101）。

エンコーディング

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

Lidl & Pilz (1999) などの一部の著者は、データ語からコード語へのマッピングのみを論じています。しかし、この方法には、データ語がコード語の一部として現れないという欠点があります。 ${\displaystyle q(x)\mapsto g(x)\cdot q(x)}$

代わりに、体系的なコードを作成するために、次のような手法がよく用いられます。長さ のデータワードが与えられた場合、まずを で乗算します。これにより、 は 桁左にシフトします。一般に、はで割り切れないため、有効なコードワードにはなりません。ただし、の右端のシンボルを調整することで得られる一意のコードワードがあります。これを計算するには、を で割った余りを計算します。 ${\displaystyle d(x)}$ ${\displaystyle n-m}$ ${\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 n-m}$ ${\displaystyle p(x)}$ ${\displaystyle x^{m}d(x)}$ ${\displaystyle n-m}$ ${\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年。

「https://en.wikipedia.org/w/index.php?title=Polynomial_code&oldid=1322991065」より取得