巡回符号

巡回符号（Cyclic Code）

巡回符号は、誤りを修正するための符号の一種であり、符号理論において重要な役割を果たします。この符号の特性は、その符号語が循環的であることです。具体的には、符号語の各シンボルを一定の方法でシフトすると、再び同じ符号語が生成されます。この性質が、巡回符号の効率的なエラー訂正能力をわかりやすく示しています。

巡回符号の基本概念

巡回符号は、以下のように定義されています。ある線形符号があり、その符号語が (c0, c1, ..., cn-1) で表されるとします。この符号語を一つのシフト操作で (cn-1, c0, c1, ..., cn-2) に変換した場合も、依然としてその符号語として認識されるとき、それは巡回符号と呼ばれます。

符号語は通常、符号語多項式 C(x) として表現され、この多項式は次の形を持ちます。

$$C(x) = c_{n-1}x^{n-1} + c_{n-2}x^{n-2} + ... + c_1x + c_0$$

ここで、係数は GF(2) 上のものであり、演算は排他的論理和（XOR）として行われます。この多項式の表現は、巡回符号がシフト操作によってもその形を保つ特性を示しています。

巡回符号の生成方法

巡回符号は、特定の方法で作成されます。まず、nがmより大きく、生成多項式 G(x) が m次の多項式であるとします。この時制御された情報シンボルを I(x) とし、G(x) と I(x) の積によって新たな多項式 C(x) を生成します。

$$C(x) = I(x) imes G(x)$$

この処理において、C(x) が巡回符号の条件を満たすことが確認できます。具体的には、元の多項式部分 C(x) を再度巡回させた場合、それは他の新しい符号語を作成しつつ、最終的には元の C(x) に戻ります。これにより、全ての符号語は相異なる値をもつことが保証されます。このような性質を持つ生成多項式は、しばしば原始多項式と呼ばれます。

組織符号の概念

一般的には、温度の変化や伝送ミスなどの影響を受けないように、循環符号は特定の方法で符号化されます。この過程では、最初に情報多項式 I(x) を用意し、次に xn-m との積を求め、生成多項式 G(x) で割った商と余りを用いて新たな符号 C(x) を生成します。このやり方により、符号の特性を維持しつつエラー訂正が可能になります。

巡回符号の利点

巡回符号の最大の利点は、シンプルな回路で符号化が実行できることです。シフトレジスタ回路を用いることで、生成多項式と情報多項式の組み合わせを手軽に実現できるため、実際の回路設計においても効率的です。たとえば、ハミング符号と比較した場合、ハミング符号は情報ベクトルと生成行列の積に基づくため、回路が大規模化する傾向がありますが、巡回符号を用いる場合、必要な計算は比較的単純なものになります。

他の符号との関係

巡回符号は、他の誤り訂正符号との関連性も持ちます。特に、単一パリティビットやハミング符号などは、巡回符号のサブセットであると言えるでしょう。例えば、ハミング符号の中には、巡回符号の条件を満たすものも存在します。また、BCH符号やリード・ソロモン符号といったより高度なエラー訂正技術も巡回符号の一形態として理解できます。

参考文献

• - 江藤良純、金子敏信『誤り訂正符号とその応用』オーム社、1996年
• - J.ユステセン、T.ホーホルト『誤り訂正符号入門』森北出版、2005年
• - 笠原正雄、佐竹賢治『誤り訂正符号と暗号の基礎数理』コロナ社、2004年

このように、巡回符号は誤り訂正の方法において非常に有用な技術であり、通信やデータの整合性を維持するために広く使用されています。

もう一度検索