4.解読器（DECODER）のアルゴリズム

さて、いよいよDECODERの仕様を説明します。ここでは、アルゴリズムの詳細は説明せず、どのような演算をもちいればエラー訂正できるかという方針で、説明を行います。今回の課題であるBCH(15,7)符号では以下の生成多項式を用いました。

すなわち、符号を示す多項式SB(x)は、（２）式の形をしているので、生成多項式G(x)で割るとあまりが０となる性質を持っています。すなわち、割り算のあまりを計算して０であれば、エラーがないと判断することができます。

BCH(15,7)符号ではデータが7ビット、冗長（パリティ）ビットが8ビットで、15ビットの符号中2ビットの誤り訂正が可能な符号です。

以下（９）式に示すように、生成多項式G(x)は

となり、G1(x)とG2(x)の積です。したがって、SB(x)はG1(x)でも、G2(x)でも割り切れることになります。すなわち、エラーがなければ、２つの余りは０となります。

送信信号SB(x)を送信して、RB(ｘ）なる信号を受信したとします。送信中にエラーがなければ、RB(x)はSB(ｘ）と同一であり、RB(ｘ）をG1(x)もしくはG2(x)で割ると余りは０となります。もし送信中にエラーが発生すると、RB(ｘ）をG1(x)もしくはG2(x)で割った余りは０ではなく、エラーの発生を検知することができます。

このRB(ｘ）をG1(x)で割った余りをS1(x)シンドロームとし、G2(x)で割ったあまりをS2(x)シンドロームとすると、S1(x)およびS2(x)は以下のような3次の多項式となります。

２つのシンドロームビット(S10, S11, S12, S13)と（S20, S21, S22, S23）の計８ビットにより、エラーのあるなし、エラー訂正可能かどうか、エラー訂正可能な場合に、反転すべきビット位置はどの位置かを知ることができます。ここでは、複雑なアルゴリズムでの解法はあきらめ、テーブルでの実装をします。というのも、シンドロームはすべてで８ビットであり、２５６通りの場合しかなく、TableすなわちROM等で実装が可能だからです。

表５にシンドロームとエラー位置の関係を示します。黄色のセルはシンドロームがともに０の場合に対応しており、エラーのない場合で、Noneと表示されています。青色のセルは１ビットエラーに対応しており、符号語１５ビットのエラーの位置１５通りを示しています。エラー位置は表６に示すように、（２）式のＸの指数と合わせています。赤色のセルは２ビットエラーに対応しており、15*14/2=105通りのパターンを示しています。各セルには２つの数値がしめされており、これらが２ビットエラーの位置に対応します。他のセルは３ビット以上のエラーがあり、エラー訂正不可能の状態を示しています。エラー発生は検知したが、訂正できない状態で１３５通りあります。

opフィールドとfuncフィールドが操作を指定している。rsはソースレジスタ、rtも通常はソースレジスタ、rdはデスティネーションレジスタと呼ぶ。