Smile Engineering Blog

ジェイエスピーからTipsや技術特集、プロジェクト物語を発信します

The Continuing Story of Error Correction Code

はじめに

最近、思うところがありエラー検出・訂正を勉強しています。

ネットの情報や書籍を頼りにやっていますが本格的なところは、行列だ、ベクトルだ、線形代数だ、巡回符号がどうのこうので多項式がなんとかで、挙句の果てはガロアなんとかだ、ときて心が折れます。それぐらい知っていてあたいまえだよね、というスタンスです。Wikipediaを見てもそんな感じですよね。 意味不明な数学記号のあめあらしです。

一番嫌なのは「当然こうなる」、「明白である」、「証明はここではしない」のようなパターン。独学だと聞く相手もいないので、例え「こういうことかな」と思ってもそれが正しいのか、はたまた間違っているのかわからない。 ひたすら試行錯誤。

反対に、数式を使わずに説明する、みたいなのもありますが数式を使わないで説明できるのはせいぜいハミング符号ぐらいまでで、CRCやBCHぐらいになるともう数式使わないと、もう無理。理解には程遠いものになってしまいます。

じゃあ、どうすりゃいいんだよ、となりますね。という訳で本ブログでは

  • ちょっとだけ本題を進める。
  • それについてちょっとだけ数学的に考察してみる。
  • 以下、繰り返し。

という方針で進めていこうかと思います。 数学知識が必要になったら説明し、証明が必要なら都度書いていく。他のサイト、書籍参照はしない。 こんな感じで自分が躓いたところ、悩んだところを思い出しながら、ひたすら書き綴っていきたいと思います。
今回は数学的要素一切なしエラー検出事始めです。

では、エラー検出・訂正の終わらない話、はじまりはじまり。

何もしないと何が起こるか

4ビットのコードを送ってみる

まずは4ビットのコードを相手に送ることを考えてみます。
4ビットのコードなので全部で16種類あります。送信側から4ビットのコードを通信路に入力します。受信側は通信路から4ビットのコードを受け取ります。通信路と書きましたが、通信でなくても、例えばメモリに書いた、読んだでも良いし何かバイナリのデータを入れて、取り出すといったものを考えてください。

完璧な通信路で送ってみる

最初は通信路として絶対に間違うことのない完璧なものを使ってみます。

送信 受信 送信 受信
0000 0000 1000 1000
0001 0001 1001 1001
0010 0010 1010 1010
0011 0011 1011 1011
0100 0100 1100 1100
0101 0101 1101 1101
0110 0110 1110 1110
0111 0111 1111 1111

送信したコードと受信したコードは完全に一致しています。素晴らしい!!
あたりまえですね。通信路は入力したものを間違いなく出力してくれるのだから入力と出力は一致します。

怪しい通信路で送ってみる

次に怪しい通信路を通してコードを送信してみます。怪しい通信路なのでたまに1と0を取り違えることがあります。

  • 入力:0000
  • 出力:0010

0000を入力したのに受け取ったのは0010でした。別のコードになっていますね。今は入力が0000だったよ、と分かっているので「あぁ、間違ってるな」とわかりますが送信側が何を送ったか知らなければ間違っていることに気づかないわけです。

そもそも何がいけないのか?

ここでは1ビットだけデータが変化したのですがデータが1ビット変化した結果のコードも有効なコードなわけです。4ビットで表すことのできる16通りのコードすべてが有効なコードなのですから1ビット誤っただけでも別のコードになってしまう訳ですね。
これでは絶対に誤りに気づくことはできません。

何か知らんが魔法をかけて送ってみる

上の例では4ビットのコードをそのまま送っていましたが今回は4ビットのコードに魔法をかけて送ってみます。魔法をかけるのが符号器、魔法を解くのが復号器とします。 魔法をかける復号器は入力されたデータを以下のような5ビットのデータに変えてしまいます。

入力データ 魔法のかかったデータ
0000 00000
0001 00011
0010 00101
0011 00110
0100 01001
0101 01010
0110 01100
0111 01111
1000 10001
1001 10010
1010 10100
1011 10111
1100 11000
1101 11011
1110 11101
1111 11110

魔法を解く復号器は受け取った5ビットのデータを以下のように変換します。

魔法のかかったデータ 受信データ
00000 0000
00001
00010
00011 0001
00100
00101 0010
00110 0011
00111
01000
01001 0100
01010 0101
01011
01100 0110
01101
01010
01111 0111
10000
10001 1000
10010 1001
10011
10100 1010
10101
10110
10111 1011
11000 1100
11001
11010
11011 1101
11100
11101 1110
11110 1111
11111

完璧な通信路で送ってみる

ではデータを送ってみましょう。 まずは完璧な通信路を通してみます。 入力するデータは0010です。符号器に0010を入れると魔法がかかって00101になります。 完璧な通信路なので通過した後も00101のままです。 では受け取ったデータ00101を復号器をつかって魔法を解きます。 表の00101を探すと0010ですね。正しく受け取れました。

怪しい通信路で送ってみる

次は怪しい通信路を通してみます。 入力するデータは0010です。符号器に0000を入れると魔法がかかって00101になります。 怪しい通信路を魔法のかかったデータが通過していきますが00101が10101になったとします。 1ビット変化していますね。 では受け取ったデータ00101を復号器をつかって魔法を解きます。 表の10101を探すと・・・、?になっています。間違いにきづいたようですね。

何故間違いに気づくようになったのか?

「おまえが言うところの魔法とやらをかけたからだろ、しかも魔法ったってただの偶数パリティじゃねーかよ!!」
はいそうです。
でも、ここに重要なポイントがあります。 魔法が何かはとりあえず脇に置いといて、符号器が何をしたかを見てみましょう。

入力コードは4ビットでしたが、符号器の出力は5ビットになっています。
4ビットのデータを5ビットにして送った 、ここが重要です。

上の例では魔法がかかったデータ00101が10101になった、としましたが魔法がかかったデータは5ビットあるので通信路で誤るビットの位置も5通りあるはずです。

  • 00101 → 0101
  • 00101 → 0101
  • 00101 → 0001
  • 00101 → 001
  • 00101 → 0010

この5通りのデータを復号器で魔法を解くとすべて?になります。表を確認してみてください。
この魔法はデータが正しければ正しいデータ、1ビット誤った場合はすべて?にマッピングしているのです。 通信路に送り出すデータを4ビットから5ビットに増やすことにより表現できるビットのパターンは2倍になります。 この2倍に増えたビットパターンの空間で誤りのない正しいデータは正しいデータに、1ビット誤ったデータは?のデータに割り当てる、これにより1ビット誤ったよ、ということが認識できるようになるのです。

ビット数を増やして正しいデータの割り当てられる領域以外の領域を増やす、そしてその正しいデータが割り当てられたパターン以外の場所に誤ったパターンを割り当てる。この割り当て方で色々なエラー検出が生み出されるのではないでしょうか。

自分が思っていたイメージとは違った・・・

エラー検出・訂正というのは正しいデータ列の後ろに何か数学の魔法で計算した謎のビットを付ける、この謎のビットからエラーが検出・訂正できるんだ、って思っていたんですよ。今回の例で言えば

 D_{4}  D_{3}  D_{2}  D_{1}  P_{1}

Dは入力データでPが謎のビット。 この謎のビット  P_{1} がすべてを解決してくれる、と。
でも、今回の話からすると符号器は入力データが占める領域よりも広い領域に正しいデータをマッピングして復号器がそれを元に戻す。元に戻す際に正しいデータではない値に復号されたら、それは通信路で何か間違えている、と判断する。
とすれば元のデータをどのようにマッピングするか、という問題なので符号器の出力(通信路を通るデータ)が入力データの後ろに謎のビットが付く、という形でなくても良い、ということなのでは。

という訳で、今回はここまで。
次回はここまでの話をちょっとだけ数学的要素を取り入れながら考えて、ハミング距離について考えてみます。