符号化

本

数学の楽しさを中学生に伝えたければ、この本はオススメ。

数学的ひらめき
数学的ひらめき
posted with amazlet on 06.12.13
芳沢 光雄
光文社
売り上げランキング: 2943
Amazon.co.jp で詳細を見る

以下のような興味が引かれる内容がてんこ盛りである。

  • ISBN(International Standard Book Number)番号
    • 書籍に振られている管理番号。雑誌を除いてほとんどの本に振られているので見てもらえれば、と思うが、ISBNという文字に続いて10桁のコードが書かれている。この番号、けっこう考えられて作られている。
    • 例：ISBN4-334-03377-6（これ、この本のISBN)
      • 4は国名を表す
      • 334は出版社
      • 03377は書名
      • 最後の6、これは読み取り時に誤りを検出するために使用される。ISBN番号でハイフンを除いて書くと…
ISBN a_{1} a_{2} a_{3} a_{4} a_{5} a_{6} a_{7} a_{8} a_{9} a_{10}
→ a_{1}〜a_{9}には 0, 1, 2, ... ,9のどれかが入り、
a_{10}には 0, 1, 2, ... , 9, xのいずれかが入る(xは10とみなされる)
→上記例の場合、出版社コード部分は3文字だが、2桁の場合もある

…となる。
ここで、ISBN番号は、a_{1} \times 1 + a_{2} \times 2 + \times a_{3} \times 3 + ... + a_{10} \times 10が11の倍数になるようにISBN番号は決められている。
上記例の場合では…

 4 \times 1 + 3 \times 2 + 3 \times 3 + 4 \times 4 + 0 \times 5 + 3 \times 6 + 3 \times 7 + 7 \times 8 + 7 \times 9 + 6 \times 10 = 253 = 23 \times 11

…となり、たしかに11の倍数になっている。
ここで示すa_{1}〜a_{10}のいずれかの数値a_{i} (1 \leq i \leq 10)の読み取りを誤った場合、誤って読み取った数値をbと置くと、上記計算の結果は絶対に11の倍数にならないという性質を持っている。

bと誤って読み取った場合の計算式は以下のとおり。
 a_{1} \times 1 + ... + a_{i - 1} + b \times i + a_{i+1} \times (i + 1) + ... + a_{10} \times 10となり、
前式からこの式を引くと a_{i} \times i - b \times i = (a_{i} -b) \times iとなる。
つまり、 a_{i} - bは -10 〜 10の範囲にある整数ということになり、
ぜったいに11にはならない、ということになる。

つまり、最後の1桁で読み取りの誤りを検知する機能を持っているわけだ。非常に面白い。こういう仕組みを誤り検出符号というらしい。バーコードも同じ仕組みを持っている。
決まったルールと決まった桁数だから、計算式をチップ化して瞬時に判断させることも簡単だろう。たかがコード、されどコードという感じがする。
本書では誤り検出符号をさらに発展させた誤り訂正符号についても説明されているのだが、それは本書を読んでのお楽しみ、ということで。