ビット誤り訂正について

1ビット誤り検出

元データ	結果データ
1100	1100	誤りなし
	0100 1000 1110 1101	1ビット誤り

これは簡単、パリティビットを付け加えればいいですね。 送ったデータのうち1ビットだけ誤りならば、受信側でパリティエラーになります。

元データ	結果データ	検証
1100.0	1100.0	0	誤りなし
	0100.0 1000.0 1110.0 1101.0 1100.1	1 1 1 1 1	パリティエラー

上の表で注意しなければならないのは、パリティ自体も誤る可能性がある、 ということです。 通常、データもパリティも同じ媒体で記録されたり伝送されたりしますので。

ここでちょっと定義します。 元データを A₁、A₂、… のように表し、 付加ビットを B₁、B₂、… のように表します。 元データのビット数は a、付加ビットのビット数は b と表すことにします。 上の例では、次のように表せます。

a=4、b=1 において、
送信側: B₁=A₁+A₂+A₃+A₄ となるようにパリティを生成
受信側: A₁+A₂+A₃+A₄+B₁≠ 0 なら誤りあり

ここで + は、XOR演算です。 誤り検出、訂正などすべてこのXOR演算が基本になっています。

1ビット誤り訂正

元データ	結果データ
1100	1100	誤りなし
	0100 1000 1110 1101	1ビット誤り

誤りの状態として4つ、そして正常な状態の1つ、あわせて5状態が、 誤り訂正用の付加ビットで区別できればいいことがわかります。 5状態なので、3ビットあればよさそうだな、 ということはだいたい想像できると思います。

「え、3ビット付け加えたらそのビットも誤るかもしれないじゃないか」 はい、その通りです。ので、3ビット付け加えたら、 誤りの状態として7つ、正常な状態の1つ、あわせて8状態となり、 …ちょうど3ビットで区別できそうですね。

さて、ここで7ビットの列 X₁、X₂… X₇を 考えてみます。但し、これらの間には次の関係が成り立つものとします。

X₁+X₃+X₅+X₇ = 0
X₂+X₃+X₆+X₇ = 0
X₄+X₅+X₆+X₇ = 0

ちょっとわかりにくいですか？ では、下の表を見て下さい。 この表で、* となっているXのビットを全てXORしたものが、 0となっていることにします。

X1	*	-	-
X2	-	*	-
X3	*	*	-
X4	-	-	*
X5	*	-	*
X6	-	*	*
X7	*	*	*
xor→	0	0	0

これはつまり、受信側での検証を示しています。 X₁…X₇を受信したら、 上記の式つまりこの表を用いてXOR計算をおこない、 検証結果が 0、0、0、であることを確認します。

さて、ここで、X_1〜7のうち、1ビットに誤りが生じたとします。

X1	*	-	-
X2	-	*	-
X3	*	*	-
X4	-	-	*
X5	*	-	*
X6	-	*	*
X7	*	*	*
xor→	1	0	1

例えば、X₅が誤ったとすると、そのビットが反転します。 そして、この誤りの影響が出るのは、上の表で * となっている部分だけであり、 検証結果として、1、0、1、というものが得られます。 表を良く見るとわかりますが、 この検証結果は、誤った X のビット位置によって、値が変わるようになっています。 つまり、検証結果を見ると、どのビットが誤ったかわかるのです。

あとは簡単ですね。このX_1〜7を、A_1〜4と、 B_1〜3に割り当てればよさそうです。 ただ、どこに割り振ってもいいか、というとそうではありません。 例えば、A_1〜4を、X_4〜7に割り振ってしまうと、

A₁+A₂+A₃+A₄ = 0

次のように割り当てると都合良さそうです。

B1	*	-	-
B2	-	*	-
A1	*	*	-
B3	-	-	*
A2	*	-	*
A3	-	*	*
A4	*	*	*
xor→	0	0	0

式で書いてBを移項するとこんな感じになります。

B₁ = A₁+A₂+A₄
B₃ = A₁+A₃+A₄
B₃ = A₂+A₃+A₄

これで1ビットの誤り訂正ができることになります。 つまり、送信側では上記の式に従ってAからBを作り、 受信側では、表を利用して、どのビットが誤ったのかを検出できます。

2ビット誤り検出+1ビット誤り訂正

B1	*	-	-
B2	-	*	-
A1	*	*	-
B3	-	-	*
A2	*	-	*
A3	-	*	*
A4	*	*	*
xor→	0	1	1

というわけで、2ビット誤ると、さらに誤って訂正されてしまいます。 上の例では、A₁とA₂の2ビットが誤ると、 A₃が誤っていると認識され、さらに誤って訂正されてしまいます。

これを検出するにはどうすればよいのでしょうか？ 簡単には、さらに全体にパリティを設けます。 全体にパリティを適用すると、2ビット誤るとパリティは一致してしまいますので、 2ビット誤っていることがわかります。 つまり、B₄をパリティとすると、次のように送信側で構成します。

B₁ = A₁+A₂+A₄
B₂ = A₁+A₃+A₄
B₃ = A₂+A₃+A₄
B₄ = A₁+A₂+A₃+A₄+B₁+B₂+B₃ (= A₁+A₂+A₃)

受信側では、つぎのような計算を行ないます。

Y₁ = A₁+A₂+A₄+B₁
Y₂ = A₁+A₃+A₄+B₂
Y₃ = A₂+A₃+A₄+B₃
Y₄ = A₁+A₂+A₃+A₄+B₁+B₂+B₃+B₄
(※受信側では Y₄ = A₁+A₂+A₃ にはできません)

Y1〜3	Y4
0	0	誤りはなし
0以外	1	A1〜4、B1〜3の1ビット誤り訂正
0	1	B4の1ビット誤り訂正(無視)
0以外	0	2ビット誤り検出

誤り訂正に必要な付加ビット数

誤り訂正能力	最低必要なビット数 b
1ビット誤り検出	1
1ビット誤り訂正	log2(a+b+1)
2ビット誤り検出+1ビット誤り訂正	1+log2(a+b+1) ※上記の構成法の場合

コード間距離

コード間距離とは、ある正当なコードからある正当なコードに変化させるのに、 最低何ビット変えなければならないか、ということです。 受信側へ送られてくるコード列 X₁…X_nを、 何ビット変化させれば、別の正しいコード列となるか、ということです。

1ビット変化させただけで別のコードになってしまう場合は、誤り検出も訂正もできません。
コード間距離が2ある場合は、1ビット変化させたものは必ず誤りですので、 1ビット誤り検出ができます。
コード間距離が3になると、もし1ビット誤った場合に、 どちらの正しいコードにより近いか、がわかりますので、 1ビット誤り訂正ができます。
コード間距離が4の場合は、 2ビット誤ったコードは正当なコードからどちらも距離2以上ですので、 2ビット誤り検出＋1ビット誤り訂正が可能となります。

受信側で、誤りの検出だけ出来れば良くて、誤り訂正が不要な場合はどうでしょう？ この場合は、コード間距離-1が、誤り検出できるビット数になります。 上記で議論してきた、1ビット誤り訂正コードも、 訂正ではなく誤り検出としてだけ用いるならば、2ビット誤り検出が可能です。 同様に、1ビット誤り訂正＋2ビット誤り検出コードは、 訂正ではなく誤り検出としてだけ用いるならば、任意の3ビット誤り検出が可能です。

実際の例 - 430HX

64ビットですので、誤っていない状態を含めて65通り、 よって付加が7ビットあれば1ビット誤り訂正が可能であり、 さらにパリティを付けて、付加ビットが8ビットあれば、 1ビット誤り訂正、2ビット誤り検出ができます。 パリティ付きのSIMMは、36ビット構成であり、 2枚で72ビット=64ビット+8ビットとなり、丁度うまくいくことになります。

この誤り訂正回路を実際に設計してみましょう。 まず、2進数で1から71まで71ビット分の表を書きます。 次に、この中で単独ビットのものを付加ビットとして、上からP0、P1、P2、… P6 まで割り当てます。 最後に、空いた部分を、D0〜D63を割り当てます。 こうしてできた表はこちらになります。 この表から、メモリに書き込む時はP0〜P6及びP7を計算して書き込み、 読み出した時にもこの表から誤り位置を計算して訂正することができます。 430HXはこの表に相当する回路が入っているわけですね。

CRC16チェック

これらの性質から、任意のビット列65519ビットに対してCRCを生成して、 CRC内容16ビットを出力すると、受信側では、1ビットの誤り訂正を行なうことができます。

さて、CRC16が上記の性質を持つためには、 CRC生成多項式が因数分解できない必要があるのですが、 実際には、X+1で割り切れてしまいます。 X+1というのは実はパリティそのものです。

というわけで、一般に広く用いられているCRC16チェックというのは、 1ビット誤り訂正＋2ビット誤り検出のコードであり、 任意のビット列32751ビットに対してCRCを生成して、 CRC内容16ビットを出力すると、受信側では、1ビットの誤り訂正＋2ビットの誤り検出が できるようになっています。 現実には誤り訂正に用いられることは少なく誤り検出としてのみ用いられますので、 32751ビット中任意の3ビット誤りを検出することができる、というわけです。

(96-12-22 ここまで)
(98-8-14 修正)

戻る