Smile Engineering Blog

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

The Continuing Story of Error Correction Code 2

単一パリティ符号とハミング符号

お約束

これからエラー検出・訂正について考えていく訳ですがエラー検出・訂正をするからには何か入力があって、それをどこかに送るなり保存するなりして、受け取った、あるいは読みだしたら間違えているかもしれないからエラーがあるか検査して、その結果エラーがあれば訂正できるなら訂正するわけです。
このシステムは実際には、線でつながっているシリアル通信かもしれないし、衛星通信かもしれないし、CPUにつながっているメモリかもしれないし、はたまたハードディスクに対する読み書きかもしれません。
ただ、エラー検出・訂正についてのみ考えたいのでこれからは以下のような単純なモデルを考えてみます。

  • 送信語
    送信者が送信したいデータのビット列。

  • 符号器
    送信語に誤り検出・訂正のための加工を施す装置。

  • 符号語
    符号器により送信語に誤り検出・訂正のための加工を施したビット列。

  • 通信路
    送信側から受信側へ符号語を送る経路。符号語は通信路を通過する際に誤りが加わる可能性がある。

  • 受信語
    通信路を通って受信した符号語のビット列。
    通信路でエラーが発生していなければ符号語と同一となる。

  • 復号器
    受信語から送信語と思われるビット列を取り出し受信者に渡す。

シリアル通信をイメージしている感じですが通信路をメモリやハードディスクと考えればコンピューターシステムでしょうし、電波だと考えれば無線システムと考えることができます。

単一パリティ符号

送信語の各ビットの中で1であるビットの数が偶数になるように検査ビットを付加する方法を偶数パリティ、1であるビットの数が奇数になるように検査ビットを付加する方法を奇数パリティといいます。 RS232Cで使用されているのがこの単一パリティ符号ですね。
偶数パリティとか奇数パリティと呼ばれているやつです。

偶数パリティであれば、送信符号の1のビット数を数えた結果が奇数であれば検査ビットとして1、偶数であれば検査ビットとして0を付加するだけです。符号語の1であるビット数は必ず偶数となります。奇数パリティなら符号語の1であるビットが奇数になるように検査ビットが付加されます。

受信側では受信符号の1の数を数えてこれが偶数であれば受信符号は正しいと認識し、1の数が奇数であれば間違えていると認識します。 (厳密に言えば奇数個の誤りは検出できるが偶数個の誤りは検出できない、となるため偶数ビット誤った場合は正しいと認識してしまいます)
単一パリティ符号は送信語のビット数が何ビットでも構わない、という特徴があります。1のビット数を数えるだけなので送信語は何ビットでも構わないんですね。

ただ、間違ってることはわかってもどこのビットが間違えているのかは分かりません。どこのビットが間違えているのか分からないのだから訂正することもできません。(もし、どこのビットが間違えているのか分かるのならそのビットを反転(1だったら0に、0だったら1に)すれば訂正することができます)
まとめると単一パリティ符号は

  • 奇数個の誤りを検出できる。
  • 送信語のビット数に制約がない。
  • 誤りの場所は分からない。

となります。

検査符号の計算方法

単一パリティ符号の検査符号は偶数パリティであれば、
- 送信語の1のビット数が奇数個であれば1。
- 送信語の1のビット数が偶数個であれば0。

でしたが、これを計算で求められるようにしておきましょう。

各ビットの値は0と1しかとりませんから送信語の各ビットを足していき、その合計が偶数か奇数かを判断すればよい訳です。 合計を2進数で考えると最下位のビットが0なら偶数、1なら奇数ですから合計の最下位だけを取り出せば偶数パリティとなります。
最下位ビットしか必要でないのだから最下位ビット以外は捨てて足し算する、ということにすると計算のルールは以下のようになります。


0+0=0 \\
0+1=1 \\
1+0=1 \\
1+1=0

2進数では  1 + 1 = 10 となりますが最下位ビット以外は捨てる、としたので  1 + 1 = 0 となります。他は普通の足し算ですね。
この計算ルールでパリティ符号を計算してみましょう。 例として以下のような送信符号3ビット( D_{3} D_{2} D_{1})、検査符号1ビット( P_{1})の単一パリティ符号を考えます。


D\ _ {3}、D\ _ {2}、D\ _ {1}、P\ _ {1}

送信符号3ビット( D_{3} D_{2} D_{1})を全部足した値が検査符号となるのですから偶数パリティの検査符号 P_{1}


P\ _ {1} = D\ _ {3} + D\ _ {2} + D\ _ {1}

と表すことができます。
また、奇数パリティであれば


P\ _ {1} = D\ _ {3} + D\ _ {2} + D\ _ {1} + 1

となります。
奇数パリティの検査符号は
- 送信語の1のビット数が奇数個であれば0。
- 送信語の1のビット数が偶数個であれば1。
ですから偶数パリティとは逆になります。だから偶数パリティを反転させればよい→1を足せばよい、ということです。

送信符号が何ビットあっても各ビットをひたすら上記足し算ルールで足していった値が検査符号になる、ということですね。

単一パリティ符号からハミング符号

単一パリティ符号はどこかに1ビットの誤りがあればそれを検出できるが、その誤りがどのビットなのかはわからない、という符号です。 誤りがどのビットなのかわからないのですから訂正することもできませんね。

そこで、複数のパリティ符号を付加して誤ったビットの位置を特定できるようにしたものがハミング符号となります。誤ったビットがわかるのですからそのビットを反転(0なら1、1なら0)してやれば訂正できたことになります。問題はどうやって誤ったビットの位置を特定するか、です。

以下の7ビットでハミング符号を構成してみます。

 b_{7}  b_{6}  b_{5}  b_{4}  b_{3}  b_{2}  b_{1}

でも何故7ビット?8ビットのほうがきりが良いんじゃないの・・・

ハミング符号を8ビットで構成することはできますが、7ビットのハミング符号は符号理論の中ではきりの良いビット数になります。 理由については後々、数学的考察を行った上で考えてみることにします。 とりあえず、ここではそういうもんなんだ、ということにして先に進みます。

で、どうやって誤ったビット位置を特定するの?

1ビットのパリティでは誤ったビット位置を特定することはできませんが、複数のパリティを付加して誤ったビット位置を特定できるようにします。複数のパリティはそれぞれ異なる送信語の複数のビットを担当してもらいます。それぞれのパリティだけでは担当しているビットの何れかに誤りがある、ということしかわかりませんが複数のパリティの結果から誤りのビット位置を特定します。

では、ハミング符号の作り方、はじまりはじまり・・・

 P_{3} を配置する

 P_{3} D_{4} D_{3} D_{2}を担当してもらいます。  D_{4} D_{3} D_{2} P_{3}の何れかが1ビット誤りを起こすと P_{3}が1になります。

 b_{7}  b_{6}  b_{5}  b_{4}  b_{3}  b_{2}  b_{1}
 D_{4}  D_{3}  D_{2}  P_{3}

 P_{2} を配置する

 P_{2} D_{4} D_{3} D_{1}を担当してもらいます。  P_{3}の隣に D_{1}、更にその隣に P_{2}を配置します。  D_{4} D_{3} D_{1} P_{2}の何れかが1ビット誤りを起こすと P_{2}が1になります。

 b_{7}  b_{6}  b_{5}  b_{4}  b_{3}  b_{2}  b_{1}
 D_{4}  D_{3}  D_{1}  P_{2}

 P_{1} を配置する

 P_{1} D_{4} D_{2} D_{1}を担当してもらいます。  P_{2}の隣に P_{1}を配置します。  D_{4} D_{2} D_{1} P_{1}の何れかが1ビット誤りを起こすと P_{1}が1になります。

 b_{7}  b_{6}  b_{5}  b_{4}  b_{3}  b_{2}  b_{1}
 D_{4}  D_{2}  D_{1}  P_{1}

完成

まとめるとこうなります。

 b_{7}  b_{6}  b_{5}  b_{4}  b_{3}  b_{2}  b_{1}
 D_{4}  D_{3}  D_{2}  P_{3}  D_{1}  P_{2}  P_{1}

4ビットの送信語と3ビットのパリティで合計7ビットの符号語ができました。3ビットのパリティは以下の式により計算できます。


P\ _ {3} = D\ _ {4} + D\ _ {3} + D\ _ {2} \\
P\ _ {2} = D\ _ {4} + D\ _ {3} + D\ _ {1} \\
P\ _ {1} = D\ _ {4} + D\ _ {2} + D\ _ {1} \\

4ビットの送信語の組み合わせに対して生成されるパリティをすべて計算してみましょう。

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

試してみる

送信語が


D\ _ {4} = 0、D\ _ {3} = 0、D\ _ {2} = 0、D\ _ {1} = 0

のときに D_{4}が誤って1になった以下のような受信語の場合を考えてみます。


D\ _ {4} = 1、D\ _ {3} = 0、D\ _ {2} = 0、P\ _ {3} = 0、D\ _ {1} = 1、P\ _ {2} = 0、P\ _ {1} = 0

復号器で計算するパリティ P'_{3} P'_{2} P'_{1}とすると


P'\ _ {3} = D\ _ {4} + D\ _ {3} + D\ _ {2} = 1 + 0 + 0 = 1\\
P'\ _ {2} = D\ _ {4} + D\ _ {3} + D\ _ {1} = 1 + 0 + 0 = 1 \\
P'\ _ {1} = D\ _ {4} + D\ _ {2} + D\ _ {1} = 1 + 0 + 0 = 1 \\

となり、受信語のパリティ


P\ _ {3} = 0\\
P\ _ {2} = 0\\
P\ _ {1} = 0\\

とは異なっていますからどこかに誤りが発生した、ということがわかります。

 P_{3} を確認する

受信語の P_{3}は0ですが復号器で計算した P'_{3}は1です。ということは P_{3}の担当しているビットに誤りがあった、ということですね。
 D_{4} D_{3} D_{2}の何れかに誤りがあるようで、少なくとも D_{1}は誤っていない、とわかります。

 P_{2} を確認する

受信語の P_{2}は0ですが復号器で計算した P'_{2}は1です。ということは P_{2}の担当しているビットも誤りがあった、ということですね。
 P_{2}の担当は  D_{4} D_{3} D_{1}ですからこのうちの何れかに誤りがあったということになりますが、 P_{3}を確認したときに D_{1}は誤っていない、とわかっていますから誤りは D_{4} D_{3}の何れかとなります。更に D_{2}は誤っていない、ということもわかります。

 P_{1} を確認する

受信語の P_{1}は0ですが復号器で計算した P'_{1}は1です。ということは P_{1}の担当しているビットも誤りがあった、ということになります。
 P_{2}の担当は  D_{4} D_{2} D_{1}ですからこのうちの何れかに誤りがあったということになりますが、 P_{3}を確認したときに D_{1}は誤っていない、更に P_{2}を確認したときに D_{2}も誤っていないとわかっていますから誤りは D_{4}である、ということがわかりました。

誤ったビット位置を簡単に特定する方法

パリティビットを順番に確認しながら誤ったビット位置を特定してきましたが、実は誤ったビット位置を特定する方法があります。 受信語のパリティ


P\ _ {3} = 0、P\ _ {2} = 0、P\ _ {1} = 0

ですが復号器で計算したパリティ


P'\ _ {3} = 1、P'\ _ {2} = 1、P'\ _ {1} = 1

です。二つのパリティの異なっているビットを1としたビット列を作るとこのケースではすべてのパリティが異なっていますから 111というビット列が得られます。これを2進数として考えると10進数では7ですね。よって誤りがあったのはビット7である b_{7}です。 b_{7} D_{4}に対応していますから誤りがあったのは D_{4}である、となります。

ただ、この方法はこうなるようにパリティ符号を構成したからであってパリティ符号すべてがこういう特徴を持っている訳ではありません。この辺も後々考えていきます。

でも、なんか信じられん・・・

ではもう少し試してみましょう。 送信語が


D\ _ {4} = 1、D\ _ {3} = 0、D\ _ {2} = 1、D\ _ {1} = 0

のときに D_{2}が誤って受信語が以下のようになった場合、


D\ _ {4} = 1、D\ _ {3} = 0、D\ _ {2} = 0、P\ _ {3} = 0、D\ _ {1} = 0、P\ _ {2} = 1、P\ _ {1} = 0

復号器で計算したパリティ


P'\ _ {3} = D\ _ {4} + D\ _ {3} + D\ _ {2} = 1 + 0 + 0 = 1\\
P'\ _ {2} = D\ _ {4} + D\ _ {3} + D\ _ {1} = 1 + 0 + 0 = 1 \\
P'\ _ {1} = D\ _ {4} + D\ _ {2} + D\ _ {1} = 1 + 0 + 0 = 1 \\

受信語のパリティ


P\ _ {3} = 0\\
P\ _ {2} = 1\\
P\ _ {1} = 0\\

二つのパリティの異なるビットを1としたビット列は 101であり10進数で表すと5。誤りはビット5であるから b_{5} D_{2}が誤っているよ、ということで検出成功です。

いや、じゃぁパリティが誤ったら?

送信語が


D\ _ {4} = 0、D\ _ {3} = 1、D\ _ {2} = 1、D\ _ {1} = 0

のときに P_{3}が誤って受信語が以下のようになった場合、


D\ _ {4} = 0、D\ _ {3} = 1、D\ _ {2} = 1、P\ _ {3} = 1、D\ _ {1} = 0、P\ _ {2} = 1、P\ _ {1} = 1

復号器で計算したパリティ


P'\ _ {3} = D\ _ {4} + D\ _ {3} + D\ _ {2} = 0 + 1 + 1 = 0\\
P'\ _ {2} = D\ _ {4} + D\ _ {3} + D\ _ {1} = 0 + 1 + 0 = 1 \\
P'\ _ {1} = D\ _ {4} + D\ _ {2} + D\ _ {1} = 0 + 1 + 0 = 1 \\

受信語のパリティ


P\ _ {3} = 1\\
P\ _ {2} = 1\\
P\ _ {1} = 1\\

二つのパリティの異なるビットを1としたビット列は 100であり10進数で表すと4。誤りはビット4であるから b_{4} P_{3}が誤っているよ、となります。

2ビット間違えたらだめじゃね?

はい、ここまでの話はあくまで1ビット誤ったらその位置が特定できるよ、ということで2ビット間違えた時は考えていません。2ビット、あるいはそれ以上誤ったらどうなるのでしょうか?誤りが検出できる?訂正は可能?

つっこみどころは色々ありますが、今回の話はここまで。
次回は、誤りを検出、訂正できるビット数を考えてみましょう。

適応フィルタを作ってみる

信号処理の分野では、適応フィルタが色々な目的で使用されています。ちょっとした理由で適応フィルタのプログラムを作ってみました。

  • ADF【Adaptive Filter】
  • 適応フィルタの構成
  • 適応アルゴリズム
  • サンプルコード:NLMSで作ってみる
    • FIRフィルタ
      • サンプルコード
    • ADF
      • サンプルコード

ADF【Adaptive Filter】

適応フィルタ【Adaptive Filter】とは、出力が目的とする信号に近づく(収束する)ように係数を自動で更新していく適応信号処理で、応用例として代表的なものはエコーキャンセラやノイズキャンセラだと思います。

適応フィルタの構成

f:id:jspnet:20200306002903p:plain:right:w400 適応フィルタの構成は、適応アルゴリズムとフィルタ部です。 フィルタ部でd(n)に似たy(n)を合成、

{
 y(n) = \sum_{k=0}^{N}h_k x(n-k)
}

入力x(n)と誤差e(n)に基づいて、フィルタ係数h(n)を最適係数に近づけます。

{
 e(n)=d(n)-y(n)
}

誤差e(n)のパワーを最小にする。

続きを読む

思考のサルベージ(その7)

各工程で心がけたい思想を掘り起こしてみる

システムテスト工程末期、客先リリース直前での不具合修正と性能変化ついて考えます。

ちょっとした判定ミス

SWの動作としてはよくあるやつで、メインループで、実行命令を受信し、命令内容に従いHWを設定して後は命令実行完了の応答送信までHW任せ、次の実行命令が来ていれば同じことを繰り返し、来ていなければいったんsleep状態に入ります。 今回は、「特別なケース」の考慮が漏れていて、不具合につながっていました。

影響範囲

客先リリース直前です、不具合が直ればそれで良いとはなりません。修正による影響範囲を明確にしなければなりません。処理性能の側面でも考慮が必要です。今回は、メインループの中に判定分を1つ追加し、「特別なケース」の場合に関数コールをするという数ステップの修正で、他の不具合を引き起こすような修正ではありません。また、「特別なケース」は性能測定対象外なので、追加した判定分1つのオーバーヘッドは乗りますが、大きな性能劣化には繋がらないと判断されました。

思わぬ結果

不具合は解消されましたが、処理速度としては不利となるオーバーヘッドが増える修正なのに、何故か処理性能が数パーセント向上してしまいました。修正の結果必要な処理がスキップされている可能性も考えられます。逆に性能が劣化していれば、よけな処理が活性化している場合もあります。 調べてみると、オーバーヘッドが効いて、ループ処理の中の実行命令の受信タイミングが変わり、毎周期行われるようになり、sleepに入ることがなくなっていました。結果的に全体としての処理性能が向上していたのです。

HW依存

HW依存が大きい処理系では、ちょっとしたタイミングのずれで、処理性能に影響が出てしまいます。テスト工程初期であれば、さほど問題視されませんが、客先リリース前ともなると、例え性能が向上したとしても、もちろん劣化したとしてもですが、原因の究明は必須です。大切なことは、事前にあらゆる可能性を考慮し、起こりうることを見極めることです。

何か掘り起こせた?

  • HW依存の大きい処理系では処理タイミングを考慮することが重要。
  • 性能の変化点では、要因の究明は必須。

必要な修正は実装しなければいけないのだから、性能目標さえクリアしていて、論理的な説明さえできればなんの問題もありません。

おしまい

誤ってループ処理千回余計にやってました、なんて言ったら大目玉ですけどね。

PyTorchで京大BERT日本語Pretrainedモデルを使ってみよう

自然言語処理で注目を集めるBERT

Googleによって提案されたBERTは、自然言語処理のあらゆる分野へ流用が可能で、ますます注目を集めています。自然言語処理を学んでる方でしたら、一度は触ってみたいですよね!
今日は京大から公開されている、 PyTorch & BERT日本語Pretrainedモデル を使って、単語特徴ベクトルを取り出す方法を紹介します。

nlp.ist.i.kyoto-u.ac.jp

続きを読む

Cannot set LC_XXX to default locale: No such file or directory

はじめに

ことあるたびに目にする、

Cannot set LC_ALL to default locale: No such file or directory

のメッセージ。検索率の高いエラーメッセージなので、回避策?をここに記す。

続きを読む

MIPSとMCPS(?)、100MIPSは100MHzで動くか?

信号処理とMISP(前編・後編)では、ソフトウェアのベンチマークとしてMIPS【Million Instructions Per Second 】が使われることについて書いてきました。
前編(信号処理とMIPS - Smile Engineering Blog
後編(信号処理とMIPS・後編 - Smile Engineering Blog

もう少し突っ込んだ話をしますと、実は開発の現場ではMIPSでちょっと困る話があります。

f:id:jspnet:20191015234008p:plain:left 命令数を指標としても1命令にどれくらいの時間*1がかかるのかによって実際の処理量(演算量)が変わるからです。そこで、あまり馴染みのない言葉かも知れませんが、MCPS【Million Cycles Per Second 】という表現をご存知でしょうか・・・
ここで「MCPS」という略語がスタンダードなものとして定着しているか?には賛否あると思いますが、本記事に関しては【Million Cycles Per Second 】の略として使用したいと思います。

MCPS【Million Cycles Per Second 】とは?

まずMIPSですが、

MIPS計算

そのソフトウェアが何命令か、Million Instructions Per Second なので1秒間に何百万命令か?ということですが、デジタル信号処理のソフトウェアを考えたとき、MIPS計算は次の式になります。この時のフレームサイズとはサンプル数です。

MIPS = 命令数 × サンプリング周波数 / フレームサイズ × 10^{-6}

MCPS計算

命令数をサイクル数に置き換えただけです。

MCPS = サイクル数 × サンプリング周波数 / フレームサイズ × 10^{-6}

ソフトウェアの演算量を表す時にMIPSという言葉を使う場合が多いですが、実際のところは命令数ではなくサイクル数による計測が多いです。命令数を測定した場合(または算出した場合)MIPSになりますが、実際のところは1命令に何サイクルかかるかによってMIPSの意味が変わります。

ソフトウェアに求められるMIPSとは、100MIPSは100MHzで動くか?

*1:サイクル数

続きを読む

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

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