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イメージをリーダー読み取ると、違う文字に変わってしまったり
しました。結構大変でした。

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

QRコードを生成する手順で、

1. 入力テキストの分析と符号化
2. 誤り訂正符号というものを生成する
3. マトリックス（碁盤の目）に符号を並べる
4. マスクなるものをかける
5. 形式と型番を示す情報をつける

「2. 誤り訂正符号というものを生成する」にやってきました。

規格書を読んでみると、

• QRコードには、損傷した場合に復元できる”誤り訂正”能力がある。
• 誤り訂正レベルは以下の４段階から選べる
• レベル L 復元能力７％
• レベル M 復元能力15％
• レベル Q 復元能力25％
• レベル H 復元能力30％

ふむ。そうですか。

そのために、

• データコード後列に付加する一連の誤り訂正コード語を生成するリードソロモン誤り訂正を備えている。

？※△□？　なんだそれ。その後しばらくよく理解できない記述が続いている。

ハクション大魔王じゃないが痒い。

で、結局どうすればいいのさ！というところを読み取っていくと、

まず基本として理解しなければならないのは、こういうことだった。

• 1. 入力テキストの分析と符号化にて符号化された入力テキストを８ビットずつにわけたが、８ビットで１データコード語と呼ぶ。
• QRコードに格納されるデータは、データコード語列とそのデータコードに対して計算された誤り訂正コード語列である。
• 型番と誤り訂正レベルによって、データコード語の数と誤り訂正語の数が決められている。例えば、
• 型番１で誤り訂正レベルLの場合（以下 1 - L のように表記する。）、データコード語は19個で、誤り訂正コード語は７個と規定されている。
• 1- H の場合、データコード語は９個になり、誤り訂正コード語は17個とされている。
• 型番と誤り訂正レベルによって、データコード語列を複数のブロックに分けることになっている。このブロックをRS（リードソロモン）ブロックという。RSブロックごとに、誤り訂正コード語列を算出する。例えば、以下のように決められている。
• １- x であれば、RSブロック数は１である。
• 3 - Q の場合、RSブロック数は２である。３- Qの全ブロックのデータコード語は34個、誤り訂正コード語は36個であるが、各RSブロックのデータコード語は17個、誤り訂正コード語は18個である。
• 5 - H の場合、RSブロック数は４個あり、そのうち２個のRSブロックのデータコード語は11個、誤り訂正コード語は22個、残り２個のRSブロックのデータコード語は12個、誤り訂正コード語は22個。

というわけでプログラムの手順としては

• 使う型番と誤り訂正レベルに応じて、データコード語列をRSブロックに分割する。
• 分割したデータコード語列に対して誤り訂正コード語列を求める。

ということになる。

さて、誤り訂正コード語列を求めるにはどすればいいのか。

規格書にはさらに難解な言葉が、、、

• 規格書より引用
  QRコードの多項式は、２を法とする算術及び100011101を法とする算術（体の原始多項式 x8 + x4 + x3 + x2 + 1の係数を示す100011101を持つ2の8乗のガロア体）を用いて計算する。。。。。。

うーん。高校で数学をちゃんとやっておけば、、、いや、高校でもガロア体なんて言葉聞いたことないとおもうぞ。。。やっぱり理系のひとはこんなのわかるんだろうね。きっと。そもそも私はスペイン文学士だ。ドンキホーテなら全部読んだぞ。えへん。日本語だけど。ぶつぶつ。。。

いや、こんなときはgoogleで検索してみよう。じゃあガロア体とは？

うーん。高校で数学をちゃんとやっておけば、、、いや、高校でもガロア体なんて。。。。

続く。。。

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

暑い日が続いてますなあ。
あまりに暑いので、半ズボンにTシャツで仕事を
してます。ハワイ気分でプログラミング。
BGMにはハワイのFMをかけたりして。
これこれ
http://www.hawaiian105.com/

さて、QRコードのつづき。
今日は８ビットバイトモードの符号化だ。

これは簡単に言うとASCIIコードというかシフトJISの
文字コードをそのまま使うものである。
いわゆる半角文字などといわれるものです。

よって、単純に　入力データの文字コードを
２進数で表せばよい。

例）　ab12　の場合

1. 文字コードは　61 62 31 32 
2. ２進数では　00111101 00111110 00011111 00100000
3. モード指示子　0100
4. 文字数指示子　00000100 （型番により桁数が違う）
5. 全部つないで
• 0100 00000100 00111101 00111110 00011111 00100000

８ビットバイトモード以上。

次に漢字モードも続けます。
漢字モードの漢字とはシフトJISの２バイト文字コード（１６ビット）を
１３ビットに圧縮するものだ。

文字コードが二つの範囲に分かれる。

• 16進数で　8140〜9FFCまでのグループ
• 8140を引く
• 16進数で　E040〜EBBFまでのグループ
• C140を引く

その後下記のように処理する

• 上記の結果の上位バイトにC０を掛ける
• その結果に下位バイトを足す。
• 13ビットの２進数に変換

規格書の例ですが、　”点”　という文字の場合で要領を示すと

1. 文字コードは　935F
2. 8140 を引く　121F
3. 上位バイト(12)にC0を掛ける　D80
4. 下位バイト(1F)を足す　D9F
5. 13ビットの２進数　0 1101 1001 1111
6. モード指示子は　1000
7. 文字数指示子は8又は10又は12ビットの２進数

というわけで、数字、英数字、８ビットバイトモード、漢字モードと

ここまで順調に符号化すすんだ。

混在モードは以上のモードを切り替えながら符号化するものだ。

モードを切り替えるたびに、モード指示子と文字数指示子が

入るので、やたらめったら、モードを切り替えるべきではない。

その辺の切り替えの指針は規格書にも載っているが、絶対ではない。

私は、だいたい、規格書の指針を参考にやりました。

続く。

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

月曜日のEテレの0655では爆笑問題田中さんのたなくじがあります。
今日いただいたくじはプチ凶みたいな感じのやつでした。あまり
気に入らなかったので、消しました。じくなた〜。

先日、QRコードの数字モードの符号化について書きました。
本日は英数字モードの符号化について続けます。
なんか、気が乗りません。あまりおもしろくないかも。

では、英数字モードです。
数字０〜９までと大文字のアルファベット（A〜Z)および
記号（スペース、$、%、*、+、-、.、/、: )が対象となる。
これらの数字には規格書の中で、先ほど紹介した順に
０〜４４までの番号が割り振られている。
つまり、数字の０は０番、Aは10番、Bは11番と続いて、
スペースが36番、そして: が最後で44番である。

英数字モードでは入力テキストを二文字ずつに区切って符号化することで
短縮化している。手順は以下の通り。

例：入力データ　HELLO

1. それぞれの文字の番号を取得すると　17,  14,  21,  21,  24　になる。
2. 二つずつのグループにする。　（17, 14)   (21, 21)  (24)
3. 各グループごとに一つ目の数字を45倍して二つ目の数字と足す。
   ただし最後の１文字残った場合はそのまま。
• (17, 14) →　17 x 45 + 14  =  779
• (21, 21) →　21 x 45 + 21  =  966
• (24)        →　24
4. それぞれを11桁の２進数にする。ただし、最後の１文字分は６桁でよい。11桁というのは、３の手順で数値化した二桁の文字の値の最大値が44 x 45 + 44 = 2024 でこれを２進数で表すと111 1110 1000 となり11桁必要だからだ。同様に最後の一桁の場合最大値は44だからそれは６桁で足りる。
• 779 → 011 0000 1011
• 966 → 011 1100 0110
• 24    → 01 1000
5. 最後にこれらをつなげて、前にモード指示子と文字数指示子をつける。
   以下のようになる。

　　　　モード：0010　（英数字）

　　　　文字数：0 0000 0101　（５文字）※長さは型番により変わる

　　　　データ：011 0000 1011    011 1100 0110     01 1000

            結果：00100000001010110000101101111000110011000

ということで、英数字モードは簡単でしたが、

やっぱり、なんかつまらない。くじのせいかな。

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

JISの規格書を購入してから半月ほどたって、
先週末、QRコードを作るプログラムにとりかかることにした。

さて、、、

pdfはどこだ？

規格書をダウンロードした時にファイルを適当なフォルダに
放り込んでいたので、わからなくなってしまったのだ。
いや、そもそもどっちのパソコンで落としたんだっけ？
やばい。と焦ったのであったが、見つかった。よかった。
今度は、ファイルサーバーのしかるべき場所に保存しておかねば。

さて、、、
うむむ。。。
むぅ。
規格書は本文とたくさんの15の附属書からなっていた。
その間を行ったり来たりしつつ考え込むこと丸一日。

うん。よくわからないけど、まあいいや。
小さなことからこつこつと。
ひとつひとつ片付けよう。

大まかな手順で言うと

1. 入力テキストの分析と符号化（０と１にする）
2. 誤り訂正符号というものを生成する
3. マトリックス（碁盤の目）に符号を並べる
4. マスクなるものをかける
5. 形式と型番を示す情報をつける

ということだ。

とりあえず、入力テキストの符号化を

やってみっぺ。

分析とは、、、

要するにQRコードにしたいテキストに含まれている

文字の種類を調べて、なるべくたくさんの文字を

詰め込めるように効率的に符号化しようということだ。

符号化とは、すべてを０と１で表そうということだ。

QRコードというのは、あの白と黒のつぶつぶが、

白は０、黒は１を意味しているのじゃ。

QRコードでは符号化のモードというものがあるが、

基本は、以下の４つのモードとその混在モードのようだ。

• 数字モード
• 英数字モード
• ８ビットバイトモード
• 漢字モード

規格によると、他に拡張チャネルモードとか構造的連接モードとか、

FNC1モードとかあるが、特定のアプリケーションに対応するものの

ようなので、今日のところは見逃してやろう。

で、ちいさなことからこつこつと。

数字モードは数字すなわち０〜９までの１０種類の数字

だけを表現するモードだ。

話を進める前に、

さて、０から９までの１０個を表すのに、最低必要な２進数の桁数

は何桁でしょう。

• 0 -> 0000
• 1 -> 0001
• 2 -> 0010
• 3 -> 0011
• 4 -> 0100
• 5 -> 0101
• 6 -> 0110
• 7 -> 0111
• 8 -> 1000
• 9 -> 1001

ということで４桁必要だということがわかる。

４桁で数字１文字を表現する方法だと、例えば

０１２３４５６７という数字を符号化（１と０化）すると

   0000 0001 0010 0011 0100 0101 0110 0111 

となり全部で32桁となる。

しかしながら、本来４桁あれば、１６種類の文字が

表現できる。さっきのに続けると、、、

• １０ -> 1010
• １１ -> 1011
• １２ -> 1100
• １３ -> 1101
• １４ -> 1110
• １５ -> 1111     

というわけで使ってないパターンが６個ある。

よって、もったいないということになる。

さて、規格によるとQRコードの数字モードは

次のようにしている。

1. まず３桁ずつにグループ分けする
       　０１２　３４５　６７
   
2. 各グループを１０桁の２進数にする
   ※３桁の整数を表すのに２進数で１０桁必要だからだ。
   012 -> 0000001100
   345 -> 0101011001
   67   -> 1000011     ※元が２桁の場合は７桁、元が１桁の場合は４桁
   
3. ２進データをつなぎ合わせる
   0000001100 0101011001 1000011

この方法だと、上記の例では２７桁で表現できている。

あと、符号化されたデータがどのように符号化されているのか

を示す情報が必要である。それをモード指示子という。

また、そのモードで何文字符号化されているか、文字数を示す必要が

ある。それを文字数指示子という。

• モード指示子は４桁で各モードで決められている。数字モードの場合は
  
  0001
    
• 文字数指示子はQRコードの大きさ（これを型番という）によって
  変わるが、小さいやつは１０桁の２進数で表す。
  上記の例だと、８文字だから
  
      0000001000

これらを符号化されたデータの前に配置すると完成だ。

     0001 0000001000 0000001100 0101011001 1000011

で、これをプログラムに書いてみた。

と、さらりと書いたが、実は結構苦労した。今回はVBで書いている。

VBでビット操作ってどうやるの？とか知らなかったので、

またググりまくった。ありがとう、Google とネットの人々よ。

VBはあまりこういうlow levelなことには向いてないのかも知れませんな。

その辺はまた別の機会にして、とにかく、プログラムはできた。

さてやってみよう。

     0001 0000001000 0000001100 0101011001 1000011

OK、今日は完璧だ。

次回に続く

QRコード

２次元バーコードのQRコードを作るソフトはいろいろ出回っていますが、
自分でも作ってみたかった。

調べてみると、

• QRコードはデンソーが開発したものらしい。
  http://www.qrcode.com/index.html に詳しく載っている。
• QRコードの仕様はJIS/ISOで規格化されていて、「QRコードは(株)デンソーウェーブの登録商標です。」の一言があれば使用料はかからず、自由に使っていい。
• JIS/ISOの規格は実は簡単に入手できる。そんなに高くない。

ということがわかった。

早速、規格書を入手した。
JIS/ISOの規格は　日本規格協会（JSA)がウェブストアを開いていて
そこで規格番号 " X0510"で規格書を検索することができた。
http://www.webstore.jsa.or.jp/webstore/top/index.jsp　
価格は 4,830円だった。それほど高くない。PDFのダウンロード販売だ。
クレジットカードで購入するとすぐに入手できた。

さてこれでいつでも作れるぞと思い、そのまま半月が経過したのだった。

続く。