彼らは数学しか勉強できない

誤り検出・訂正符号と間違い探しゲーム

「和人、ちょっといい？」

　休日、部屋で自習していると遊びに来ていた愛華に呼ばれた。スマホを片手に手招きしている。

「なんだ」

「連絡先交換用のQRコード作ったんだけどね、和人のスマホで読み取れるか確認してほしいの」

「自分ので確認しろよ」

「もうしたよ。ほかの端末でも確かめておかないともしものとき困るじゃん」

「はいはい。わかったよ」

　てか、QRコードってそんな簡単に作れるのか。マジで便利な時代に生まれたな。

　内心でそんなことを思いながら俺はスマホを取り出し、愛華の作ったQRコードを読み取る。コードの中心には猫のイラストが描かれていた。

「いけたぞ。つーか、イラストつきかよ。どうりでコードがデカいわけだ」

「イラストがついてるのと大きさって関係あるの？」

「コードが小さいと汚れやそれみたいにイラストがついてる場合、上手く読み取れないんだ。だからその分コードを大きくしないといけない」

「へぇ。でもコードが大きくても読み取れないことたまにあるよ」

「それはコードの汚れが相当ひどいか誤り訂正レベルが低いかのどっちかだな」

「誤り訂正レベルって何？」　

　日常で使わないからな。知らなくても当然だろう。

「誤り訂正レベルは文字通りコードに誤りがあったときにそれを訂正する機能のレベル。QRコードだとリード・ソロモン符号ってのが多く使われてる」

「和人って無駄に知識豊富だよね」

「ひとこと余計だ」

「そのリードなんとか符号って難しいの？」

「リード・ソロモン符号な。理解するにはある程度高度の数学知識は要る。誤り訂正じゃないけどパリティ符号なら少ない知識でも理解できると思う」

　俺はそう言って引き出しからノートを取り出した。自習よりはいい時間つぶしになるだろう。

　パリティ符号は簡単に言うとデータの誤りを検出する方法。パリティは英語表記だと「parity」で数学では主に「偶奇性」と訳される。

「パリティ符号の仕組みは単純。例えば0001というビット列があったとき、1の個数が偶数個なら0、奇数個なら1をビット列に追加する。この場合は1を追加」

　0001 1

「愛華、次の5つのビット列のうちひとつだけ誤りがある。どのビット列かわかるか？」

　0101000　0000011　0101011　0010000　1100000 0

「一番右にある0ってさっき言ってたパリティ符号？」

　愛華の問いに俺は首肯する。

「えーと、1が偶数個のときは0を追加するんだよね」

「ああ。その逆で1を追加することもあるけどな。まあどっちでも別に問題ない」

「ふぅん。それなら0010000かな。この列だけ1が奇数個になってるから」

「正解。これはパリティチェックと呼ばれる」

「どれが間違いかはわからないの？」

「パリティチェックではどのビットが誤りかは判断できない。ただ、ビット列を上手く並べれば訂正することができる。下に図を描く」

　○●○●○● 1

　●●●○●● 1

　○●○○●● 1

　○○●○●○ 0

　１１０１１１

「見分けやすくするために各ビットを○と●に置き換えてパリティ符号は数字のままにした」

「これ、○と●のどっちが1なの？」

「どっちを1にしても矛盾はしないんだけど今回は●を1にする。それじゃあ愛華、ここで問題だ」

　○●○●○●　

　●○○○○●　

　○●○○●●　

　○●○●●○

「この6×4の24個の丸のうちひとつだけ反転している。反転させる前の垂直方向のパリティ符号が上から順に1、1、1、1。水平方向のパリティ符号が左から順に1、1、1、0、0、1だったとする。このとき、どの丸が反転したか当ててくれ」

「いきなり問題出してこないでよ。えっと……さっきみたいにパリティ符号を追加すればいいんだよね」

　愛華は不満を言いながらも律儀に作業を進める。

　○●○●○●　1

　●○○○○●　0

　○●○○●●　1

　○●○●●○　1

　１１０００１

「反転させる前の縦のパリティ符号が1、1、1、1で横のパリティ符号が1、1、1、0、0、1だから……これ？」

　○●○●○●

　●○〇（↓）○○●

　○●○○●●

　○●○●●○

「正解。この方法ならどのビットが誤りか特定できるから訂正可能。垂直水平パリティと呼ばれる方法だ」

「横一列しかない場合はどうするの？　垂直水平パリティだっけ、それだと無理じゃない？」

「俺が最初に出した例だと垂直水平パリティは使えない。訂正するときはハミング符号と呼ばれる誤り訂正符号を使うんだが仕組みは少し複雑だ」

　パリティ符号では追加するのは1ビットだけだったがハミング符号では3ビット追加する。ただし、追加するビット数は送信するデータ量によって異なる。

　一般にハミング符号では送信するビット数は整数をkとして2（　k）－1ビット。送信前のデータのビット数が2（　k）－1－k、追加するビット数がkだ。

「追加するビットの生成方法は複数あるんだが今回はなるべく簡潔にする」

　まず1つ目は送信前データの1桁目、3桁目、4桁目のパリティ。2つ目が1桁目、2桁目、4桁目のパリティ。3つ目が2桁目、3桁目、4桁目のパリティ。

　例えばビット列が0001の場合

　1つ目　0001→1

　2つ目　0001→1

　3つ目　0001→1

よって、送信するビット列（データ）は0001111となる。

そこまで説明すると愛華は「うーん」と唸った。

「パリティ符号と比べるとやること多いね。それで、どうやって間違いを訂正するの？」

「それを今から説明する」

　受信したデータを仮に1001111とする。最初の4ビット1001と追加した3ビット111を使ってパリティを計算する。

　1000 111→1001　 パリティ符号は0

　1011 111→1011　パリティ符号は1

　1011 111→0111　パリティ符号は1

「受信した3ビットは011で最初の1桁目が違っている。よって、誤っているのは1桁目のビットってことだ。これを0に変えれば訂正完了」

「理屈はなんとなくわかったけど手順が多くて頭がこんがらがりそう。それにしても、和人は数学の話になるとめちゃくちゃ喋るよね」

　学校でもそれくらいの調子でいけば友達増えるのに、と愛華は肩を竦めた。「余計なお世話だ」と反論しようとしたが、それを言うと友達が少ないことを認めてしまうことになる。俺はただ黙っていることしかできなかった。