衒思力発電所

QRコード書きませんか

急に工学っぽいことに目覚めたわけではないんだけど，ちょっと前に QR コードの仕様が気になって調べた．

といっても JIS とか ISO から規格書取り寄せると金がかかるので，こちらのサイトにお世話になって．別に規格の全容を把握してライブラリ作ろうとしてるとかそういうわけじゃないので十分．

そして何をどこで間違えたのか，QR コードを手で書けたらかっこよくね？　という変態スキルの魅力に取り憑かれ，最近は専ら現実逃避の手段として QR コードを書こう^*1としていた．

でかいのは無理そうだが，一番小さいバージョン 1 でならさくっと書き上げれるんじゃね？

……と思ったのだけど，結論から言うと，かなり無理です．

アライメントパターンも入らず，インターリーブ配置も必要ないこのサイズの QR コードの作り方は，ざっくり言えば，

(1) 表現するデータをビット列に直す -> (2) RS (Reed-Solomon) 符号をつける -> (3) 配置する -> (4) マスクをかける

という，まぁ当然そうなるわなっていう工程しかないんだけど，(2) がひたすらに鬼門．

符号の作り方なんて，コンピュータで処理するときに高速便利なようになってるわけで，人力計算に向かないのは当然すぎるんだが，それにしても大変だ．

0～255 の整数それぞれを，全く関係ないようにみえる^*2 0～255 の整数に変換できなきゃだめだったり． ……まぁこれは対応を覚えればいいだけなんだけど，無機質な数を無機質な数に対応させる関係を暗記するのは半端ではない難度．

これ今のところ全然覚えれていないので，こちらの表に頼りながら変換してる．

さらに，8bit のビット列同士の xor を最低でも 150 回から計算しなきゃいけない．表面的には 0～255 な 10 進数になってるので， 「199 と 52 の xor は？」 みたいなのを 150 回以上．慣れればある高速化できそうだけど普通の人間には苦痛でしょうがない計算だ．

俺は，19 バイトのデータから 7 バイトの RS 符号を計算するのに 3 時間強かかった．アホである．

ちなみに (1) は ascii コード覚えてる人なら数分でできて，(3) と (4) はがんばれば 30 分くらいかな．^*3

そんなわけで計 5 時間くらいはかかって書いたのがこの左の QR コードだ．手書きしたものをさらにデジカメで撮ってアップという多重劣化……でも多分，お手持ちのケータイで試してもらえば拾えると思う．

工程の最後の方，実際に 21×21 のセルを鉛筆で塗っていく部分はかなりエキサイティングな作業だったし，書き終えたものをケータイにかざして読み取れた瞬間の爽快感といったらないよ．

ただし，やはり RS 符号化を手計算するのは素人にはおすすめしない．10 年分のセンター数学で全て満点取れるくらいの計算力がないと，途中でダウンするか，途中で計算間違いして結果の符号がはちゃめちゃになってせっかく塗っても読み取れないかどっちかである．^*4

ということで興味を持った人向けに，QR コードバージョン 1 のスケルトンおよび， RS 符号を求める部分だけを機械任せにできるプログラムを配布する．^*5

つ■

• matrix1.png
  21×21 の方眼線だけ引いた画像．上級者向け．200dpi くらいで印刷するとえんぴつで塗るのにちょうどいいサイズ．
• matrix2.png
  matrix1.png に加え，7×7 ごとに太線．中級者向け．
• matrix3.png
  matrix1.png に加え，固定パターンを塗り，形式情報を書く部分に薄く着色，さらに 2×4 の矩形を太線で．初心者向け．
• rs.exe
  データをコマンドライン引数として与えると，RS 符号を出力するコンソールアプリケーション．
• rs.d
  rs.exe のソースコード．

rs.exe の使い方．データコードを 10 進表記した列（ここの最下部にある 32 65 205 69 41 220 46 128 236 とか）を，コマンドライン引数として渡す．

C:\unko> rs.exe 32 65 205 69 41 220 46 128 236

すると

[42,159,74,221,244,169,239,150,138,70,237,85,224,96,74,219,61]

のように RS 符号部が出力される．

バージョン 1 のみ対応だけど，その範囲なら，与える引数の数から誤り訂正レベルを決定してくれます．上記では 9 個与えてるからレベル H だけど 19 個与えたらレベル L になる．^*6

日本語話者の中に俺の他にあと一名でも QR コードを手で書いたら面白いんじゃねと思う変な人がいるのかは知らないけどね．

1. 「描く」を使うべきなのかな．でも仮にも「コード」だし「書く」でも…… [↩]
2. 表面的にはの話．実際は GF(2^8) 使って一対一対応させているからめちゃ厳密な関係がある [↩]
3. 適切なマスク選択をすることをはなから諦め適当なマスクをかけるだけの場合．全マスクかけてみて点数計算し，最適なものを選ぶというステップを踏むなら，ここにも数時間かかる． [↩]
4. 俺は一段階ずつプログラムで求めた結果と照合し，確認しながら進めるというチート行為を使った．センター数学 10 年連続満点とか無理． [↩]
5. あとの部分の作り方はこのページを参考にどうぞ． [↩]
6. まぁ生成多項式がハードコーディングしてあったりするひどい手抜きだということはソースみれば一目瞭然なの． [↩]

Trackback URL

コメント (8) to QRコード書きませんか

コメントをどうぞ