応用代数学入門

応用代数学入門―暗号・符号・バーコードの仕組みが分かる

3月の試験の為に本を探してたら、図書館で面白い本を見つけた。いろいろな符号や暗号についてが理論的説明付きで載ってた。
バーコードとか身近で使われてる符号って誤り検出・訂正なんかの様子が目に見えてわかるから面白い。

2 of 5 コード

1〜10の整数を次のように符号化するコード

1: 11000   2: 10100   3: 01100   4: 10010   5: 01010
6: 00110   7: 10001   8: 01001   9: 00101   0: 00011

読み方は簡単でそれぞれのビットを 0, 1, 2, 4, 7として、法11で加算すればいい。
何でこのようなコードにするかというと、必ず2ビットだけが1になるので誤りを検出できるから。
バーコードとかいろんなコードがこの2of5コードを基本にして3of9コードとか拡張した誤り検出符号を使っているらしい。
この系列は覚えやすいから目でバーコードを読めるようになるかも(笑)

QRコード

QRコードはリード・ソロモン符号が使われているらしい。
リード・ソロモン符号っていうのはBCH符号の一種。
最大で30%までの誤り訂正が可能らしい。

モールス符号

モールス符号は長いバー、短いバー、短い空白、長い空白を使って符号化する方法。
モールス符号は可変長符号で、全体の長さを短くする為に出現頻度の高いアルファベットに短いコードが割り当てられている。*1
逆に言えば覚えにくい符号。

他にも点字とかパンチカードとかいろいろ書いてある。面白い。

おまけ：ISBNのチェックディジット

ISBNにはチェックディジットが付いていて

ISBN4-89471-493-0

なら最後の0がチェックディジット。計算方法は

(4, 8, 9, 4, 7, 1, 4, 9, 3)・(10, 9, 8, 7, 6, 5, 4, 3, 2) mod 11 = 0

・は内積の意味。
本の裏を見るとISBNの上に2of7のバーコードが書いてあってこれは
978 - ISBN番号 - チェックディジット
って数字になっている。当然チェックディジットは違う数字。

*1:ハフマン符号というわけではないみたい