情報ラボ ＞ パリティマジック
カードを1枚だけ裏返してください。どこを裏返したか、必ず言い当てます。
まず「カードを並べる」を押してください。赤と黒がでたらめに並びます。
ビットをクリックしても切り替えられます。金色の枠がパリティビットです。
いちばん右の点線の枠がチェックディジットです。他の12桁から計算で求まります。
よくある入力ミスを再現します。検査で見つかるでしょうか。
パリティ検査で「誤りあり」と分かるかどうかを試してみてください。
| 誤りの数 | 検出 | 位置の特定 |
|---|---|---|
| 1か所 | できる | できる（訂正も可能） |
| 2か所 | できる | できない |
| 4か所（長方形の角） | できない | できない |
手品の種は、事前に足しておいた1列にあります。
カードを並べたあと、それぞれの行と列について「赤いカードの数が偶数になるように」1枚ずつ追加します。これで、盤面のすべての行とすべての列で、赤の数が偶数に揃います。
この状態で誰かが1枚裏返すと、そのカードがある行と列だけ、赤の数が奇数に変わります。他の行や列は影響を受けません。ですから、奇数になっている行と列を探し、その交わったところが答えになります。
種を知ってしまえば単純ですが、これはコンピュータが実際に使っている誤り検出の考え方そのものです。
パリティ（parity）とは、日本語で「偶奇性」のことです。ある数が偶数か奇数かという性質を指します。
データ通信では、送るデータの中に含まれる「1」の個数が偶数か奇数かを調べ、その情報を1ビット付け加えて送ります。この付け加えるビットをパリティビットといいます。
2つのやり方があります。
| 方式 | ルール | 例：1011010（1が4個） |
|---|---|---|
| 偶数パリティ | 全体の1の個数が偶数になるようにする | 1011010 + 0 |
| 奇数パリティ | 全体の1の個数が奇数になるようにする | 1011010 + 1 |
どちらを使うかは、送る側と受け取る側であらかじめ決めておきます。仕組みとしては同じで、どちらが優れているということはありません。
受信側は、届いたデータの1の個数を数えるだけです。偶数パリティなのに1の個数が奇数だったら、途中で何かが変わったと分かります。
この仕組みの良いところは、追加するのがたった1ビットで済むことです。7ビットのデータを守るのに1ビット、つまり約14%の増加だけで誤りに気づけます。回路も単純で、排他的論理和（XOR）を並べるだけで作れます。
便利な仕組みですが、万能ではありません。
1の個数が2つ変わると、偶奇は元に戻ってしまいます。たとえば1が2個増えれば、偶数のままです。パリティ検査は「正常」と判断してしまいます。
一般に、パリティビットで検出できるのは奇数個の誤りだけです。偶数個の誤りは見逃します。
1次元のパリティでは、「どこかが違う」ことは分かっても、「どこが違うか」は特定できません。そのため、誤りを見つけたらデータを捨てて送り直してもらうことになります。これを検出はできるが訂正はできない、といいます。
ただし、パリティマジックのように縦横の両方向にパリティを付けると、話が変わります。行と列の交点から位置を特定できるので、1か所の誤りなら訂正までできるのです。これを水平垂直パリティといいます。
パリティチェックは、いまも幅広く使われています。
より強力な方式としては、CRC（巡回冗長検査）やハミング符号があります。QRコードが多少汚れても読み取れるのも、リード・ソロモン符号という誤り訂正の仕組みが入っているからです。考え方の出発点は、どれもこのパリティと同じです。
そもそも、データはなぜ壊れるのでしょうか。
通信では、電波や電気信号にノイズが混じります。近くの機器から出る電磁波、雷、機器そのものの熱による揺らぎ。こうした影響で、0が1に、1が0に変わってしまうことがあります。記録媒体でも、経年変化や宇宙線の影響でビットが反転することが知られています。
1ビットの反転でも、影響は深刻になりえます。金額のデータなら桁が変わり、プログラムなら誤動作します。だから、データを扱うあらゆる場面で誤り検出の仕組みが組み込まれているのです。
誤りを見つけたら送り直してもらう、という方法には限界があります。宇宙探査機からのデータのように、送り直すのに何時間もかかる場合。あるいは、CDやQRコードのように、そもそも送り直せない場合です。
そこで、誤りを見つけるだけでなく、その場で直してしまう仕組みが考え出されました。誤り訂正符号といいます。
考え方の基本は、パリティマジックと同じです。複数のパリティを組み合わせ、その結果から誤りの位置を特定します。ハミング符号では、パリティビットの当たり方を工夫することで、どのビットが誤っているかを数値として直接求められるようにしています。
QRコードが多少汚れたり欠けたりしても読み取れるのは、リード・ソロモン符号という強力な誤り訂正が組み込まれているためです。最大で全体の30%が失われても復元できる設定もあります。QRコードの真ん中に会社のロゴを載せられるのは、この余力を利用しているのです。
同じ考え方は、日常のあちこちに埋め込まれています。
| 対象 | しくみ |
|---|---|
| 本のISBN | 最後の1桁が検査用の数字（チェックディジット） |
| 商品のバーコード | 最後の1桁が検査用の数字 |
| クレジットカード番号 | Luhnアルゴリズムという計算で確認 |
| マイナンバー | 最後の1桁が検査用の数字 |
これらは、番号を手で入力したときの打ち間違いを見つけるための仕組みです。1桁打ち間違えたり、隣どうしの数字を入れ替えたりすると、計算が合わなくなります。パリティビットと同じく、少しの情報を足しておくことで、間違いに気づけるようにするという発想です。
パリティと同じ考え方は、身近な番号にも使われています。本や商品の番号の最後についている1桁が、それです。チェックディジットといいます。
商品バーコード（JANコード）と本のISBNは、どちらも13桁で、同じ計算方法を使っています。
なぜ位置によって1倍と3倍を使い分けるのでしょうか。すべて1倍で足すだけだと、隣り合った数字を入れかえても合計が変わりません。「12」を「21」と打ち間違えても気づけないのです。重みを変えることで、こうした入れかえミスも検出できるようになります。
この方式で見つけられるのは、1桁の打ち間違いのすべてと、隣り合う2桁の入れかえのほとんどです。ただし完全ではなく、差が5になる組み合わせの入れかえだけは見逃します。上のツールで実際に試せます。
レジで商品をスキャンしたとき、読み取りに失敗すると「ピッ」と鳴らずにやり直しになります。あれは、この計算が合わなかったということです。
授業では、実際にカードや磁石を並べて演示してから、このツールで種明かしをすると効果的です。