小学5年生が理解する「誤り訂正符号」（デジタル社会を支えるテクノロジー：誤り訂正符号って何？その40）

私：「では、ここまでのことを整理しよう『畳込み符号』の『符号語』は

00,11,01,01,00,10,11、

途中で加える誤りは

00,10,01,00,00,01,00、

『符号語』に『誤り』が加わって、受け手が受け取る『受信語』は

00,01,00,01,00,11,11

となる。」

息子：「うん。で、誤り訂正はどうやるの？」

私：「慌てるでない。考えられる全てのビットの並び、つまり考えられる全ての『符号語』と、受け取ったビット、つまり『受信語』とを比較して、最も『ハミング距離』が小さい『符号語』とする。」

息子：「慌てるでない、って何だよ！時代劇じゃないんだからさ。それはどうでも良いや。全ての考えられる『符号語』なんて全部作って比べることなんてできるの？」

私：「実は『ブロック符号』でも、今言った方法が1番良いやり方なんだけど、『符号語』の数が多い『ブロック符号』を使うことが多いのでそういうやり方をあまりしないんだけど、『畳込み符号』は一緒に考えてきたような高々3ビットの合計を2つ程度の場合が多いからできるんだ。」

息子：「ふーん。でも『ブロック符号』でもできる例があるんだ。それも知りたいな。」

私：「そうだね。この後ぐらいに見ていこうか。」

息子：「うん。でも、先ずはこれだね。」

私：「そうだね。では、はじめてみよう。『受信語』は

00,01,00,01,00,11,11だったね。そして元のデータの最初の2ビットは0、つまり00だったことを思い出そう。これを状態00と言う。この状態00がスタートとして、ビットが増やしていきながら『符号語』を作っていく。ビットを増やす時に状態は2つの状態にしか移れない、という点に気をつけよう。例えば、元のデータが0の時は状態00、元のデータが1の時は状態10に移る。そして、連続した3ビットの合計と3ビットの間のビットを除いた合計を並べた2ビットの『符号語』の要素と、その都度2ビット5『受信語』の要素との『ハミング距離』を求めて、そこまでの履歴の合計の『ハミング距離』を求める。その時点で1つの状態において考えられる『符号語』の候補のうち『ハミング距離』の小さい方だけ残していって最終的に残った『符号語』を送り手が送った『符号語』とする。それでは1つずつ見ていこうか。」

息子：「まずは状態00からスタートして…元のデータ0の時は状態00で連続した3ビットの合計は0で、連続した3ビットの間を除いた合計も0なので、『符号語』の要素は00で『受信語』との『ハミング距離』は0。元のデータ1の時は状態10で連続した3ビットの合計は1で、連続した3ビットの間を除いた合計も1なので、『符号語』の要素は11だから『受信語』との『ハミング距離』は2だね。ここで『ハミング距離』の小さい方を残すの？」

私：「異なる2つの状態から同じ1つの状態になる場合だけ、『ハミング距離』の小さい方だけを残せば良いから、この時点では必要ないよ。」

息子：「そういうことね。でも、これをこの先続けていくのは大変だね。」

私：「そうだね。『トレリス線図』という図を使う方法を使おうか。」

息子：「『トレリス線図』？テトリスみたいだね。」