QRコードを作るプログラムを作る（5）

誤り訂正コードの作成です。

ここはもっとも難航したところなので、ブログも書きづらい。
規格書およびネットで検索して参考にさせていただいた情報に
もとにプログラムを書くことはできましたが、なぜそうなのという
ところが完全には理解できていないせいである。

最初に、ネットで検索して、大変参考になったページを

を書き留めておきます。

そもそもQRコード作成の手順としては

http://www.swetake.com/qr/qr1.html

この方の説明は全体的にとてもわかりやすいもので、
おそらくページの説明なしに、私は完成できなかったと思います。
大変感謝です。

それから、ガロア体というのは下記のページを見て参考にしました。

http://chichiue.hahaue.com/gf.html
http://en.wikipedia.org/wiki/Finite_field_arithmetic

結局、数学として理解できないことはいったんさしおいて、プログラム作成にあたって、
理解したことは次のとおりである。

• 誤り訂正コードの生成多項式に登場する係数 αⁿ のところで指数 n に対する整数が一意に存在する。
• 指数 n に対する整数の求め方は ８桁の２進数で指数0のとき "00000001"から初めて、指数が上がるたびに左にシフトしていき、桁があふれたとき "00011101"と排他的論理和をする。
• αの指数n=0 　　"00000001"　（１）10進
• αの指数n=1 　　左シフト ⇒ "00000010"  (2)
• αの指数n=2 　　左シフト ⇒ "00000100" (3)
• αの指数n=7 　　左シフト ⇒ "10000000" (128)
• αの指数n=8 　　左シフト ⇒ "00000000"  XOR "00011101" ⇒　"00011101" (29)
• αの指数n=9 　　左シフト ⇒ "00111010" (58)
• αの指数n=10　　左シフト ⇒ "01110100" (116)
• αの指数n=11　　左シフト ⇒ "11101000" (232)
• αの指数n=12　　左シフト ⇒ "11010000" XOR "00011101" ⇒　"11001101" (205)
• αの指数n=255 のとき "00000001" に戻る
• 生成多項式の係数の演算において掛け算　α^m * αⁿx⁸  ＝　α^(m+n)x⁸  になる。 
• αの指数は255以上にならない。前述の計算で２５５以上になるときは255を減ずる。
• α^{255 =} α⁰  だからだ。 
• 符号化によって生成したデータコード語列をコード語総数-1乗から始まる多項式に当てはめる。これをf(x)としておく。
• たとえば1-H型のデータコード語列  32, 68, 35, 115, 10, 82, 127, 0, 236 があったとすると 1-H型のコード語数総数は 26 なので
• f(x)=32x²⁵ +68x²⁴ + 35x²³ +115x²² +10x²¹ +82x²⁰ +127x¹⁹ +0x¹⁸ +236x¹⁷  
• 誤り訂正コード数に応じて３１の生成多項式が用意されている。これをg(x)とする。
•  1-H型の場合誤り訂正語数は１７である。（総コード数(26)-データコード数(9)=17)
  17語の場合てに生成多項式は
• g(x)=x¹⁷＋α⁴³x¹⁶＋α¹³⁹x¹⁵＋α²⁰⁶x¹⁴＋α⁷⁸x¹³＋α⁴³x¹²＋α²³⁹x¹¹＋α¹²³x¹⁰＋α²⁰⁶x⁹＋α²¹⁴x⁸＋α¹⁴⁷x⁷＋α²⁴x⁶＋α⁹⁹x⁵＋α¹⁵⁰x⁴＋α³⁹x³＋α²⁴³x²＋α¹⁶³x＋α¹³⁶
• f(x)をg(x)で割った余りが誤り訂正コード語列になる。
• でも、多項式同士の割り算の余りの求め方は通常の算術と同様ではなく、以下のようなイメージである。
• 1-H型の場合だとコード語数総数である26個の箱を用意する。箱には番号25番～0番の順にふってある。これらの箱一式を FX と呼ぶことにする。
• 箱の番号はf(x)の多項式のxの指数と同じである。
• 箱の番号25～順にデータコード語を入れていく
• 32, 68, 35, 115, 10, 82, 127, 0, 236 　が25番から17番までに収まる。
• もう一そろい同様に25～0番の番号を振った箱を用意する。これらの箱をGXと呼ぶことにする。
• GX箱には対応するxの指数の場所に生成多項式 g(x)の係数を入れていく。
• 17番～0番まで、1,α⁴³,α¹³⁹,α²⁰⁶,α⁷⁸,α⁴³,α^239,,α¹²³,α²⁰⁶,α²¹⁴,α¹⁴⁷,α²⁴,α⁹⁹,α¹⁵⁰,α³⁹,α²⁴³,α¹⁶³,α¹³⁶
• FX箱の現在値の入っている先頭の箱は25番である。その箱にはいっている値は32でその対応するガロア体の指数は5である。そこでGX箱の先頭の箱番号は１７である。箱の番号を合わせるためにGX箱をそれぞれ６個シフトそれぞれ、αの指数に５を加算する。この箱一式をGX' とする。
• 25番～8番まで、α⁵,α⁴⁸,α¹⁴⁴,α²¹¹,α⁸³,α⁴⁸,α^244,,α¹²⁸,α²¹¹,α²¹⁹,α¹⁵²,α²⁹,α¹⁰⁴,α¹⁵⁵,α⁴⁴,α²⁴⁸,α¹⁶⁸,α¹⁴¹
• これをFX箱と排他論理和をとったものをFX箱に入れる。
• FXの25番の 32 に対し GX' の25番のα⁵は32 だから、その排他的論理和は 0 になる。
• 同様に24番以降の箱も排他的論理和を取る。今FXの24番は68である。GX'の24番はα⁴⁸でこれは70である。これらの排他的論理和は 2 である。 
• 結果FX箱の中は２５番は空となり２４番以降の箱に値が残っている。
• これを繰り返していくとFXの箱は２５番から１７番まで空となる。
• 最後に１６番から０番に残ったものが誤り訂正コード語列である。

やれやれ、これで、誤り訂正コードの算出ができます。
ちなみに、最初ここのプログラミングでちょっとしたミスをしていたのですが、
そうすると、QRイメージをリーダー読み取ると、違う文字に変わってしまったり
しました。結構大変でした。