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

息子が私の仕事のことを聞いてきてから4日目。

息子：「今日も昨日の続きの話しして。」

私：「おっ！熱心だね。飽きっぽいのに今回は飽きてない。」

息子：「うるせー！」

私：「何ですか？その話し方は、我が家の話し方ではないですよ！それに、それが人にものを尋ねる態度ですか？（気取った口調で）」

息子：「おっ…おぅ…ごめんなさい。」

私：「よろしい。それでは始めましょうか？（気取った口調で）」

息子：「おっ…おぅ…。」

私：「昨日はようやく『誤り訂正符号』の入口の繰り返し符号について話しをしたね。今日は、その考え方をもう少し考えてみよう。昨日は0を送り（記録し）たい時に00、1を送り（記録し）たい時は、11を送る（記録する）ことで、01か10を受けた場合には間違った、つまり誤ったデータだと分かる、と話したね。」

息子：「うん、したねー。」

私：「昨日は言わなかったけど、2ビットの両方とも誤って00を送ったのに11を受け取る場合、あるいは11を送ったのに00を受け取る場合も考えられないかな？」

息子：「あっ！そうか！…確かにそういう時もあるかも知らないけど…でも、受け取った方では間違って無い、と思うよね？」

私：「うん。良く気がついたね。そういう場合は受け取った方では、間違って無い、つまり誤り無し、としか判断しようがないんだ。これはこの繰り返し符号の持つ性能、つまり誤り検出性能の限界なんだ。このことを、この誤り訂正符号の『誤り検出可能数』と言う。ここまで考えた、1ビットのデータを2ビット繰り返す、繰り返し符号の『誤り検出可能数』は1ビットになる。」

息子：「この繰り返し符号では、1ビットの誤りだったら、誤ったか、誤ってないかが分かるけど、2ビットの誤りだと誤ったか、誤ってないか分からない、ということだね。」

私：「そう！」

息子：「それじゃあ、あんまり役に立たないんじゃない？」

私：「まーそうだね。でも、『誤り訂正符号』の最も簡単で、最も基本の考え方なんだ。それに、そんなやたらに誤ってしまうようなデータの送り方や記録はしないから、こんな簡単な繰り返し符号でも、それなりに役には立つんだ。例えば、1000ビット送って、1ビットだけ誤る場合を考えてみると分かる。」

息子：「うーん…そうか！1000回送って1回しか誤らないなら、2回同時に誤るのは1000回を1000回繰り返すことになるから1000000回のうち1回だけ、つまり同時に2ビット誤るのは1000000ビット送って1回だけになるんだね。」

私：「おーっ！凄いねー！1000ビット送って1ビット誤るなら、2000ビット送って2ビット誤ると考えるかな？と思ったけど引っ掛からなかったね。『2ビット同時に』というのがポイントだね。そうなんだ。2ビットが組になってるからね。その組になってる2ビットが同時に間違う頻度は1000ビットを1000回送って1回ということになるんだ。組になってる2ビットのどちらも誤る確率はかなり低くなる、ということ。」

息子：「まぁね〜！それは分かったけどさー、やっぱりこの繰り返し符号じゃやっぱりダメな場合とかどうすんの？」

私：「そうなんだ、やはり昔の人もそう考えていろいろと工夫してるんだ。ここまで考えた繰り返し符号を元にもっと多くの誤りを見つけるにはどうしたら良いか考えてみよう。タクムなら、この繰り返し符号をどうすれば良いと思う？」

息子：「…繰り返しの数を増やす…かな？」

私：「そう！繰り返しの数を増やすことがまずは頭に浮かぶよね。他にも考えられないかな？」

息子：「うーん…（しばし先程まで話していた繰り返し符号の例を書いた紙を見つめて）、1の数のビット数が偶数になるようにする！！」

私：「ウワ〜ォ〜！！タクムちゃんスゴイねぇ〜！！サイコ〜！！正解！そうだね。1つは、繰り返し符号で繰り返しの数を増やす、もう1つは1のビット数が偶数になるようにする、だね。」

息子：「（勝ち誇った顔で）フッ…タクム流！！」

私：「…なんだそれ…まーいいや。1つ目の繰り返し符号で繰り返しの数を増やす、ではどうすれば良いかな？」

息子：「これまで考えてた繰り返し符号では0、または1を送りたい時にそれぞれ00、11と2ビット同じ数を送ってたから1ビットの誤りまでしか分からないけど、3ビットとかもっと多くのビットで同じ数を送れば2ビット以上で誤った場合でも誤りが有るって分かる。」

私：「そうだね。じぁあ、2つ目の1のビット数が偶数になるようにする、だとどうなるかな？まずは3ビットの組で送る場合から考えた方が良いかな。」

息子：「うーん、こっちは難しいな…0を送る時は000だけど、1を送る時は111…だと奇数になるから、1を送る時は110…かな？」

私：「この場合は、0とか1を送るじゃなくて、2ビットの00、01、10、および11を送る場合を考えると良い。この場合について考えてみて。」

息子：「00は000、01は…1の数が偶数だから01の場合は011、10は101、そして111は110…かな？」

私：「そう！」

息子：「でもさ、こうなると繰り返しの数を増やした繰り返し符号とは違うことにならない？」

私：「良いことに気が付いたね。そうなんだ、繰り返し符号の繰り返しの数を増やした場合は、元の数の個数は1個、つまり元のデータのビット数は1ビットだ。これに対して繰り返し符号の1のビット数を偶数個にして送るビット数を増やした場合は、元のデータのビット数が2個になっているんだ。」

息子：「でも、それだと繰り返し符号の繰り返しの数を増やした場合は、誤った数が多くなっても分かるようになるけど、1のビット数を偶数にした場合は誤った数が多くなったら分かんないよね？」

私:「実はそうなんだけど、2ビットの繰り返し符号について、2通りの工夫を考えさせたのには訳が有るんだ。それはね、繰り返しの数を増やした繰り返し符号は、誤ったビット数が多くなっても付け足したビット数に応じて誤りを検出できるビット数も多くなる。だけど、一方で、無駄も多くなる。つまり、元のデータ、つまり元のビット数は1ビットなんだけど、本来は必要の無い繰り返すビットが多くなるから、それだけ無駄が多いことになるんだ。それに対して、1のビット数を偶数にした場合は検出できる誤りのビット数は1個のままなんだけど、送れる元のデータ数、つまりビット数が増えるんだ。」

息子：「そっかー！繰り返しの数を増やした繰り返し符号は検出できる誤りビット数が多くなるのに対して、1のビット数を偶数にすると送れる元のビット数が多くなるんだね！！」

私：「そういうこと。送る元のデータ数、つまりビット数は1ビットのまま誤りを検出できるビット数を増やすか、逆に誤りを検出できるビット数は1ビットのままだけど送る元のデータ数、つまりビット数を増やすか、ということ。繰り返し符号に対して、1のビット数を偶数にする符号は『パリティ検査符号』と呼ばれる。この『パリティ検査符号』は『パリティ・チェック』と呼ばれたりもする。少し、難しいこと言うと『繰り返し符号』と『パリティ検査符号』とは、互いに密接な関係がある誤り訂正符号で『双対符号（そうついふごう）』と言われる関係なんだ。このことは、次回話しをしよう。」

息子：「ふーん。何か少し面白くなってきたけど、相変わらず『誤り訂正符号』まで辿り着かないね。いつもの勉強の教え方と一緒で準備が長過ぎ！兄ちゃんが『パパに算数とか、数学とか、理科とか聞きに行くと面倒臭いことになるからやめとけ。』って言ってる理由がよくわかった。」

私：「な〜に〜っ！！言ったまったなっ！！漢（おとこ）は黙って熟考！！基本原理から理解しないと、結局は理解できてないんだ。すぐに忘れて何回も同じ事の繰り返しになるからかえって時間の無駄になるぞ。まー、自分で苦労しないと分からないかな。今日はここまでにしよう。」