研究活動‎ > ‎情報技術班‎ > ‎

特集:あなたも描ける! JIS X0510準拠 QRコード®超入門

※此の頁は四月馬鹿の日に勢いで作ってしまったものです。(2011/04/01)

はじめに

 近年、私達の身の回りにはQRコードが溢れています。広告に、製品に、文庫本の背に、企業の屋上に。
 しかし、私達はQRコードを直接に読むことは出来ず、携帯に頼らねばその情報を入手出来ません。これは正に、情報による知的疎外の相貌が立ち現われていると謂うべき事態でしょう。
 この状況を打開する方法は単純明快、私達自身がQRコードを読み、描けば良いのです。
 本頁がそうした勇猛果敢に現代社会へ挑戦する人々の助けとなれば、無上の喜びであります。
 さて、本頁はJIS規格X0510:2004に準拠して書かれていますが、入門という事もありデータは英数字に限定し、本来必須ですがマスク処理の評価も省いてあります。もっと色々なデータを扱い、美しいQRコードを描きたい! という好学の士と呼ぶべき読者の方々には続篇「あなたも描ける! JIS X0510準拠 QRコード®完全マスター」をお勧めします。
 尚、JIS規格に於ける用語は一般に用いられるものと一部異なっており、その場合は「セル(モジュール)」のように括弧内に規格上の用語を記述しました。また、QRコード®は、株式会社デンソーウェーブの登録商標ですが、規格化されたQRコードについてデンソーウェーブは保有する特許の権利行使を行わないことを宣言しています。

データの決定

 まず、QRコードにするデータを決めます。ここでは、英数字という事で"WE LOVE KIMWIPE"としましょう。この文字数は15です。
 次に誤り訂正レベルを選択します。これはL、M、Q、Hの四段階あり、レベルHが最もQRコードの損傷に対して高い復元能力を持っています。ここでは最も一般的なレベルMにしておきましょう。
表1. 誤り訂正レベル
レベルL 約 7%
レベルM 約 15%
レベルQ 約 25%
レベルH 約 30%

バージョンの選択

 QRコード上の一番小さい"■"や" "一つ一つはセル(モジュール)と呼ばれ、QRコードはセルが正方形に並んだものと謂えます。
 セルの数はバージョン(型番)によって決まり、バージョン1(1型)では21x21セル、バージョン2では25x25セル、という風に縦横4セルずつ増えていき、バージョン40の177x177セルが最大です。
 誤り訂正レベルMで英数字が15文字の条件に適するのは、表2からバージョン1と分かります。
表2. バージョン毎のデータ容量
バージョン 誤り訂正
レベル
データ
ビット数※
英数字
1 L
M
Q
H
152
128
104
72
25
20
16
10
2 L
M
Q
H
272
224
176
128
47
38
29
20
3 L
M
Q
H
440
352
272
208
77
61
47
35
※データビットには後述のモード指示子及び文字数指示子を含む。

データの符号化

 英数字を符号化するには、まず表3に従ってデータを数値列に変換して、二つずつに分けます。
表3. 英数字モードの符号表
文字 文字 文字 文字 文字 文字 文字 文字
0 0 6 6 C 12 I 18 O 24 U 30   36 . 42
1 1 7 7 D 13 J 19 P 25 V 31 $ 37 / 43
2 2 8 8 E 14 K 20 Q 26 W 32 % 38 : 44
3 3 9 9 F 15 L 21 R 27 X 33 * 39
4 4 A 10 G 16 M 22 S 28 Y 34 + 40
5 5 B 11 H 17 N 23 T 29 Z 35 - 41
"WE LOVE KIMWIPE" → (32, 14) (36, 21) (24, 31) (14, 36) (20, 18) (22, 32) (18, 25) (14)

 組になった数字の内、最初の値を45倍にして、二番目の値を足し11ビットの二進数に変換します。最後に一つ残った場合は、6ビットの二進数にします。
(32, 14) 45*32+14 = 1454 10110101110
(36, 21) 45*36+21 = 1641 11001101001
(24, 31) 45*24+31 = 1111 10001010111
(14, 36) 45*14+36 = 666 01010011010
(20, 18) 45*20+18 = 918 01110010110
(22, 32) 45*22+32 = 1022 01111111110
(18, 25) 45*18+25 = 835 01101000011
(14) 14 = 14 001110
 このビット列を繋げて、頭にモード指示子文字数指示子を加えます。
 英数字のモード指示子は0010で、文字数指示子はバージョン1からバージョン9の時9ビットで指定します(文字数指示子のビット長はバージョンやモードにより異なります)。
 文字数は15でしたので、文字数指示子は000001111となります。
 更に、ビット列の最後へ終端パターン0000を加えます。4ビット全てを加えると表2にあるデータビット数を超えてしまう時は、丁度になるよう終端パターンを短縮します。
 以上から、このようなビット列が得られました。

0010 000001111 10110101110 11001101001 10001010111 01010011010 01110010110 01111111110 01101000011 001110 0000

 これを、8ビットのコード語(通常のバイトと同義です)に分割していき、最後が8ビットにならない時は0で埋めます。

00100000 01111101 10101110 11001101 00110001 01011101 01001101 00111001 01100111 11111100 11010000 11001110 00000000

 これは13コード語ですが、バージョン1で誤り訂正レベルがMの時のデータビット数は128ビット=16コード語ですから、3コード語が余ってしまいました。 こんな時は、最後に埋め草コード語1110110000010001を交互に追加して、コード語数が丁度になるように調節します。

00100000 01111101 10101110 11001101 00110001 01011101 01001101 00111001 01100111 11111100 11010000 11001110 00000000 11101100 00010001 11101100

 これでデータが完成しました!

誤り訂正符号の生成

 QRコードで用いられる誤り訂正方式は、リードソロモン符号と呼ばれ、BCH符号という多項式を利用した方式の一種です。
 JIS規格によれば、「QRコードの多項式は、2を法とする算術及び100011101を法とする算術(体の原始多項式x8+x4+x3+x2+1の係数を示す100011101をもつ28のガロア体)を用いて計算する。」と書かれていますが、見かけほど難しい話ではありません。

ガロア拡大体

 まずというのは加法と乗法について閉じている集合(とその演算)を指します。有理数は体を成しますが、整数は乗法に関する逆元が存在しないので体を成しません。特に集合の元が有限ならばガロア体と呼ばれます。
 例えば2を法として0と合同な整数の全てを0、1と合同な整数の全てを1で代表させると、1+1=0のように普通の整数と異なるところもありますが体を成して、元は0と1の二つだけですのでガロア体になります。この2を法としたガロア体をGF(2)と表します。
 今度は28を法としてみると、乗法表で2の段には奇数が現れないので、7/2のような計算は答えが集合に含まれません。即ち、体を成しません。
 しかし、2の指数8と同じ次数で、係数がGF(2)の元である多項式の根をGF(2)に加えると、28のガロア体が構成出来るのです! この多項式は何でもいい訳ではないのですが、原始多項式と呼ばれるものであれば大丈夫です。このようにして出来たガロア体GF(28)は、拡大体と呼ばれます。
 つまりQRコードでは、GF(2)に原始多項式f(x)=x8+x4+x3+x2+1の根を付加したガロア拡大体GF(28)を使っていると謂えます。
 ここでf(x)の根をαとして、その性質を調べてみましょう。
 まず、f(α)=α8432+1=0ですから、-α8432+1となります。しかし係数はGF(2)上の数ですから、1+1=0から-1=1で-α88です。よってα8432+1となります。ここからα8以上の冪は全てα0、α1、…、α7の多項式として表現出来ると分かります。これを多項式表現と呼びます。
 またαの冪の多項式表現におけるα7、α6、…、α0の係数を並べて書くと、これは冪指数により異なる8つのGF(2)の元が並び、これをベクトル表現と呼びます。またベクトル表現の各数を繋げると8ビットの二進数になり、この数を整数表現と呼ぶ事にします。α8432+1ならばベクトル表現は(0 0 0 1 1 1 0 1)、整数表現は十進法で書くと29になります。
 そして、GF(28)の0以外の元は全てαの冪として表現出来るのです。これが原始多項式の根の特徴です。
 以上から、GF(28)の全ての元と0から255の整数を対応させる事が出来ました(GF(28)の0は整数表現も0とします)。
表4. 根の冪乗表
多項式表現 α7 α6 α5 α4 α3 α2 α1 α0 整数表現
α-∞ 0 0 0 0 0 0 0 0 0 0
α0 1 0 0 0 0 0 0 0 1 1
α1 α 0 0 0 0 0 0 1 0 2
α2 α2 0 0 0 0 0 1 0 0 4
α3 α3 0 0 0 0 1 0 0 0 8
α4 α4 0 0 0 1 0 0 0 0 16
α5 α5 0 0 1 0 0 0 0 0 32
α6 α6 0 1 0 0 0 0 0 0 64
α7 α7 1 0 0 0 0 0 0 0 128
α8 α432+1 0 0 0 1 1 1 0 1 29
α9 α543 0 0 1 1 1 0 1 0 58
α10 α6542 0 1 1 1 0 1 0 0 116
α11 α7653 1 1 1 0 1 0 0 0 232
α12 α7632+1 1 1 0 0 1 1 0 1 205
α13 α72+α+1 1 0 0 0 0 1 1 1 135
α14 α4+α+1 0 0 0 1 0 0 1 1 19
α15 α52 0 0 1 0 0 1 1 0 38
α16 α632 0 1 0 0 1 1 0 0 76
α17 α743 1 0 0 1 1 0 0 0 152
α18 α532+1 0 0 1 0 1 1 0 1 45
α19 α643 0 1 0 1 1 0 1 0 90
α20 α7542 1 0 1 1 0 1 0 0 180
α21 α6542+1 0 1 1 1 0 1 0 1 117
α22 α7653 1 1 1 0 1 0 1 0 234
α23 α763+1 1 1 0 0 1 0 0 1 201
α24 α732+α+1 1 0 0 0 1 1 1 1 143
α25 α+1 0 0 0 0 0 0 1 1 3
α26 α2 0 0 0 0 0 1 1 0 6
α27 α32 0 0 0 0 1 1 0 0 12
α28 α43 0 0 0 1 1 0 0 0 24
α29 α54 0 0 1 1 0 0 0 0 48
α30 α65 0 1 1 0 0 0 0 0 96
α31 α76 1 1 0 0 0 0 0 0 192
α32 α7432+1 1 0 0 1 1 1 0 1 157
α33 α52+α+1 0 0 1 0 0 1 1 1 39
α34 α632 0 1 0 0 1 1 1 0 78
α35 α7432 1 0 0 1 1 1 0 0 156
α36 α52+1 0 0 1 0 0 1 0 1 37
α37 α63 0 1 0 0 1 0 1 0 74
α38 α742 1 0 0 1 0 1 0 0 148
α39 α542+1 0 0 1 1 0 1 0 1 53
α40 α653 0 1 1 0 1 0 1 0 106
α41 α7642 1 1 0 1 0 1 0 0 212
α42 α7542+1 1 0 1 1 0 1 0 1 181
α43 α6542+α+1 0 1 1 1 0 1 1 1 119
α44 α76532 1 1 1 0 1 1 1 0 238
α45 α76+1 1 1 0 0 0 0 0 1 193
α46 α7432+α+1 1 0 0 1 1 1 1 1 159
α47 α5+α+1 0 0 1 0 0 0 1 1 35
α48 α62 0 1 0 0 0 1 1 0 70
α49 α732 1 0 0 0 1 1 0 0 140
α50 α2+1 0 0 0 0 0 1 0 1 5
α51 α3 0 0 0 0 1 0 1 0 10
α52 α42 0 0 0 1 0 1 0 0 20
α53 α53 0 0 1 0 1 0 0 0 40
α54 α64 0 1 0 1 0 0 0 0 80
α55 α75 1 0 1 0 0 0 0 0 160
α56 α6432+1 0 1 0 1 1 1 0 1 93
α57 α7543 1 0 1 1 1 0 1 0 186
α58 α653+1 0 1 1 0 1 0 0 1 105
α59 α764 1 1 0 1 0 0 1 0 210
α60 α7543+1 1 0 1 1 1 0 0 1 185
α61 α6532+α+1 0 1 1 0 1 1 1 1 111
α62 α76432 1 1 0 1 1 1 1 0 222
α63 α75+1 1 0 1 0 0 0 0 1 161
α64 α6432+α+1 0 1 0 1 1 1 1 1 95
α65 α75432 1 0 1 1 1 1 1 0 190
α66 α65+1 0 1 1 0 0 0 0 1 97
α67 α76 1 1 0 0 0 0 1 0 194
α68 α743+1 1 0 0 1 1 0 0 1 153
α69 α532+α+1 0 0 1 0 1 1 1 1 47
α70 α6432 0 1 0 1 1 1 1 0 94
α71 α75432 1 0 1 1 1 1 0 0 188
α72 α652+1 0 1 1 0 0 1 0 1 101
α73 α763 1 1 0 0 1 0 1 0 202
α74 α73+1 1 0 0 0 1 0 0 1 137
α75 α32+α+1 0 0 0 0 1 1 1 1 15
α76 α432 0 0 0 1 1 1 1 0 30
α77 α5432 0 0 1 1 1 1 0 0 60
α78 α6543 0 1 1 1 1 0 0 0 120
α79 α7654 1 1 1 1 0 0 0 0 240
α80 α765432+1 1 1 1 1 1 1 0 1 253
α81 α7652+α+1 1 1 1 0 0 1 1 1 231
α82 α764+α+1 1 1 0 1 0 0 1 1 211
α83 α7543+α+1 1 0 1 1 1 0 1 1 187
α84 α653+α+1 0 1 1 0 1 0 1 1 107
α85 α7642 1 1 0 1 0 1 1 0 214
α86 α754+1 1 0 1 1 0 0 0 1 177
α87 α65432+α+1 0 1 1 1 1 1 1 1 127
α88 α765432 1 1 1 1 1 1 1 0 254
α89 α765+1 1 1 1 0 0 0 0 1 225
α90 α76432+α+1 1 1 0 1 1 1 1 1 223
α91 α75+α+1 1 0 1 0 0 0 1 1 163
α92 α643+α+1 0 1 0 1 1 0 1 1 91
α93 α7542 1 0 1 1 0 1 1 0 182
α94 α654+1 0 1 1 1 0 0 0 1 113
α95 α765 1 1 1 0 0 0 1 0 226
α96 α7643+1 1 1 0 1 1 0 0 1 217
α97 α7532+α+1 1 0 1 0 1 1 1 1 175
α98 α6+α+1 0 1 0 0 0 0 1 1 67
α99 α72 1 0 0 0 0 1 1 0 134
α100 α4+1 0 0 0 1 0 0 0 1 17
α101 α5 0 0 1 0 0 0 1 0 34
α102 α62 0 1 0 0 0 1 0 0 68
α103 α73 1 0 0 0 1 0 0 0 136
α104 α32+1 0 0 0 0 1 1 0 1 13
α105 α43 0 0 0 1 1 0 1 0 26
α106 α542 0 0 1 1 0 1 0 0 52
α107 α653 0 1 1 0 1 0 0 0 104
α108 α764 1 1 0 1 0 0 0 0 208
α109 α75432+1 1 0 1 1 1 1 0 1 189
α110 α652+α+1 0 1 1 0 0 1 1 1 103
α111 α7632 1 1 0 0 1 1 1 0 206
α112 α7+1 1 0 0 0 0 0 0 1 129
α113 α432+α+1 0 0 0 1 1 1 1 1 31
α114 α5432 0 0 1 1 1 1 1 0 62
α115 α65432 0 1 1 1 1 1 0 0 124
α116 α76543 1 1 1 1 1 0 0 0 248
α117 α76532+1 1 1 1 0 1 1 0 1 237
α118 α762+α+1 1 1 0 0 0 1 1 1 199
α119 α74+α+1 1 0 0 1 0 0 1 1 147
α120 α543+α+1 0 0 1 1 1 0 1 1 59
α121 α6542 0 1 1 1 0 1 1 0 118
α122 α76532 1 1 1 0 1 1 0 0 236
α123 α762+1 1 1 0 0 0 1 0 1 197
α124 α742+α+1 1 0 0 1 0 1 1 1 151
α125 α54+α+1 0 0 1 1 0 0 1 1 51
α126 α652 0 1 1 0 0 1 1 0 102
α127 α7632 1 1 0 0 1 1 0 0 204
α128 α72+1 1 0 0 0 0 1 0 1 133
α129 α42+α+1 0 0 0 1 0 1 1 1 23
α130 α532 0 0 1 0 1 1 1 0 46
α131 α6432 0 1 0 1 1 1 0 0 92
α132 α7543 1 0 1 1 1 0 0 0 184
α133 α6532+1 0 1 1 0 1 1 0 1 109
α134 α7643 1 1 0 1 1 0 1 0 218
α135 α753+1 1 0 1 0 1 0 0 1 169
α136 α632+α+1 0 1 0 0 1 1 1 1 79
α137 α7432 1 0 0 1 1 1 1 0 158
α138 α5+1 0 0 1 0 0 0 0 1 33
α139 α6 0 1 0 0 0 0 1 0 66
α140 α72 1 0 0 0 0 1 0 0 132
α141 α42+1 0 0 0 1 0 1 0 1 21
α142 α53 0 0 1 0 1 0 1 0 42
α143 α642 0 1 0 1 0 1 0 0 84
α144 α753 1 0 1 0 1 0 0 0 168
α145 α632+1 0 1 0 0 1 1 0 1 77
α146 α743 1 0 0 1 1 0 1 0 154
α147 α53+1 0 0 1 0 1 0 0 1 41
α148 α64 0 1 0 1 0 0 1 0 82
α149 α752 1 0 1 0 0 1 0 0 164
α150 α642+1 0 1 0 1 0 1 0 1 85
α151 α753 1 0 1 0 1 0 1 0 170
α152 α63+1 0 1 0 0 1 0 0 1 73
α153 α74 1 0 0 1 0 0 1 0 146
α154 α543+1 0 0 1 1 1 0 0 1 57
α155 α654 0 1 1 1 0 0 1 0 114
α156 α7652 1 1 1 0 0 1 0 0 228
α157 α7642+1 1 1 0 1 0 1 0 1 213
α158 α7542+α+1 1 0 1 1 0 1 1 1 183
α159 α654+α+1 0 1 1 1 0 0 1 1 115
α160 α7652 1 1 1 0 0 1 1 0 230
α161 α764+1 1 1 0 1 0 0 0 1 209
α162 α75432+α+1 1 0 1 1 1 1 1 1 191
α163 α65+α+1 0 1 1 0 0 0 1 1 99
α164 α762 1 1 0 0 0 1 1 0 198
α165 α74+1 1 0 0 1 0 0 0 1 145
α166 α5432+α+1 0 0 1 1 1 1 1 1 63
α167 α65432 0 1 1 1 1 1 1 0 126
α168 α765432 1 1 1 1 1 1 0 0 252
α169 α7652+1 1 1 1 0 0 1 0 1 229
α170 α7642+α+1 1 1 0 1 0 1 1 1 215
α171 α754+α+1 1 0 1 1 0 0 1 1 179
α172 α6543+α+1 0 1 1 1 1 0 1 1 123
α173 α76542 1 1 1 1 0 1 1 0 246
α174 α7654+1 1 1 1 1 0 0 0 1 241
α175 α765432+α+1 1 1 1 1 1 1 1 1 255
α176 α765+α+1 1 1 1 0 0 0 1 1 227
α177 α7643+α+1 1 1 0 1 1 0 1 1 219
α178 α753+α+1 1 0 1 0 1 0 1 1 171
α179 α63+α+1 0 1 0 0 1 0 1 1 75
α180 α742 1 0 0 1 0 1 1 0 150
α181 α54+1 0 0 1 1 0 0 0 1 49
α182 α65 0 1 1 0 0 0 1 0 98
α183 α762 1 1 0 0 0 1 0 0 196
α184 α742+1 1 0 0 1 0 1 0 1 149
α185 α542+α+1 0 0 1 1 0 1 1 1 55
α186 α6532 0 1 1 0 1 1 1 0 110
α187 α76432 1 1 0 1 1 1 0 0 220
α188 α752+1 1 0 1 0 0 1 0 1 165
α189 α642+α+1 0 1 0 1 0 1 1 1 87
α190 α7532 1 0 1 0 1 1 1 0 174
α191 α6+1 0 1 0 0 0 0 0 1 65
α192 α7 1 0 0 0 0 0 1 0 130
α193 α43+1 0 0 0 1 1 0 0 1 25
α194 α54 0 0 1 1 0 0 1 0 50
α195 α652 0 1 1 0 0 1 0 0 100
α196 α763 1 1 0 0 1 0 0 0 200
α197 α732+1 1 0 0 0 1 1 0 1 141
α198 α2+α+1 0 0 0 0 0 1 1 1 7
α199 α32 0 0 0 0 1 1 1 0 14
α200 α432 0 0 0 1 1 1 0 0 28
α201 α543 0 0 1 1 1 0 0 0 56
α202 α654 0 1 1 1 0 0 0 0 112
α203 α765 1 1 1 0 0 0 0 0 224
α204 α76432+1 1 1 0 1 1 1 0 1 221
α205 α752+α+1 1 0 1 0 0 1 1 1 167
α206 α64+α+1 0 1 0 1 0 0 1 1 83
α207 α752 1 0 1 0 0 1 1 0 166
α208 α64+1 0 1 0 1 0 0 0 1 81
α209 α75 1 0 1 0 0 0 1 0 162
α210 α643+1 0 1 0 1 1 0 0 1 89
α211 α754 1 0 1 1 0 0 1 0 178
α212 α6543+1 0 1 1 1 1 0 0 1 121
α213 α7654 1 1 1 1 0 0 1 0 242
α214 α76543+1 1 1 1 1 1 0 0 1 249
α215 α76532+α+1 1 1 1 0 1 1 1 1 239
α216 α76+α+1 1 1 0 0 0 0 1 1 195
α217 α743+α+1 1 0 0 1 1 0 1 1 155
α218 α53+α+1 0 0 1 0 1 0 1 1 43
α219 α642 0 1 0 1 0 1 1 0 86
α220 α7532 1 0 1 0 1 1 0 0 172
α221 α62+1 0 1 0 0 0 1 0 1 69
α222 α73 1 0 0 0 1 0 1 0 138
α223 α3+1 0 0 0 0 1 0 0 1 9
α224 α4 0 0 0 1 0 0 1 0 18
α225 α52 0 0 1 0 0 1 0 0 36
α226 α63 0 1 0 0 1 0 0 0 72
α227 α74 1 0 0 1 0 0 0 0 144
α228 α5432+1 0 0 1 1 1 1 0 1 61
α229 α6543 0 1 1 1 1 0 1 0 122
α230 α76542 1 1 1 1 0 1 0 0 244
α231 α76542+1 1 1 1 1 0 1 0 1 245
α232 α76542+α+1 1 1 1 1 0 1 1 1 247
α233 α7654+α+1 1 1 1 1 0 0 1 1 243
α234 α76543+α+1 1 1 1 1 1 0 1 1 251
α235 α7653+α+1 1 1 1 0 1 0 1 1 235
α236 α763+α+1 1 1 0 0 1 0 1 1 203
α237 α73+α+1 1 0 0 0 1 0 1 1 139
α238 α3+α+1 0 0 0 0 1 0 1 1 11
α239 α42 0 0 0 1 0 1 1 0 22
α240 α532 0 0 1 0 1 1 0 0 44
α241 α643 0 1 0 1 1 0 0 0 88
α242 α754 1 0 1 1 0 0 0 0 176
α243 α65432+1 0 1 1 1 1 1 0 1 125
α244 α76543 1 1 1 1 1 0 1 0 250
α245 α7653+1 1 1 1 0 1 0 0 1 233
α246 α7632+α+1 1 1 0 0 1 1 1 1 207
α247 α7+α+1 1 0 0 0 0 0 1 1 131
α248 α43+α+1 0 0 0 1 1 0 1 1 27
α249 α542 0 0 1 1 0 1 1 0 54
α250 α6532 0 1 1 0 1 1 0 0 108
α251 α7643 1 1 0 1 1 0 0 0 216
α252 α7532+1 1 0 1 0 1 1 0 1 173
α253 α62+α+1 0 1 0 0 0 1 1 1 71
α254 α732 1 0 0 0 1 1 1 0 142
α255 1 0 0 0 0 0 0 0 1 1
 この表は誤り訂正符号の計算に必須なので、絶対書けるようにしましょう。

データを多項式で表現する

 前章で作成したデータは、1コード語が8ビットでしたから、表4を用いて1コード語とGF(28)のαの冪を一対一で対応させることが出来ます。
コード語 整数表現 αの冪指数
00100000 32 5
01111101 125 243
10101110 174 190
11001101 205 12
00110001 49 181
01011101 93 56
01001101 77 145
00111001 57 154
01100111 103 110
11111100 252 168
11010000 208 108
11001110 206 111
00000000 0 -
11101100 236 122
00010001 17 100
11101100 236 122
 ここで、データを多項式F(x)として表現します。この最低次数は誤り訂正コード語数と同じになるようにします。表5のRSブロック数が2以上だといくつかの多項式に分けますが、バージョン1では分ける必要はありません。

F(x) = α5x25 + α243x24 + α190x23 + α12x22 + α181x21 + α56x20 + α145x19 + α154x18 + α110x17 + α168x16 + α108x15 + α111x14 + α236x12 + α17x11 + α236x10

 この表記は乗法には便利ですが、誤り訂正符号の計算には加法も必要であり、加法については二進法の整数表現にした方が便利なので

F(x) = 00100000x25 + 01111101x24 + 10101110x23 + 11001101x22 + 00110001x21 + 01011101x20 + 01001101x19 + 00111001x18 + 01100111x17 + 11111100x16 + 11010000x15 + 00000000x14 + 11101100x12 + 00010001x11 + 11101100x10

という表記も使います。ここで例えば"00010001"は、GF(28)の多項式"α4+1"(の係数)を表す記号に過ぎない事に注意してください。
表5. 誤り訂正特性
バージョン 誤り訂正
レベル
誤り訂正
コード語数
RSブロック数 RSブロック※
1 L
M
Q
H
7
10
13
17
1
1
1
1
(26, 19, 2)
(26, 16, 4)
(26, 13, 6)
(26, 9, 8)
2 L
M
Q
H
10
16
22
28
1
1
1
1
(44, 34, 4)
(44, 28, 8)
(44, 22, 11)
(44, 16, 14)
3 L
M
Q
H
15
26
36
44
1
1
2
2
(70, 55, 7)
(70, 44, 13)
(35, 17, 9)
(35, 13, 11)
※(総コード語数, データコード語数, 誤り訂正数)
表6. 誤り訂正コードの生成多項式G(x)
誤り訂正
コード語数
生成多項式
7 x787x6229x5146x4149x3238x2102x+α21
10 x10251x967x846x761x6118x570x464x394x232x+α45
13 x1374x12152x11176x10100x986x8100x7106x6104x5130x4218x3206x2140x+α78
 そして、この多項式を表6に示す生成多項式G(x)で割ります。規格書を参照する場合、正誤表によると誤り訂正コード語数10の生成多項式にα46x7の項が抜けているので注意してください。バージョン1で誤り訂正レベルがMの時、誤り訂正コード語数は10なので、

G(x) = x10 + α251x9 + α67x8 + α46x7 + α61x6 + α118x5 + α70x4 + α64x3 + α94x2 + α32x + α45

です。まずF(x)の主項(最高次の項)はα5x25なので、これを打ち消すためにG(x)へα5x15を掛けてG1(x)とします。

G1(x) = α5x15G(x) = α5x25 + αx24 + α72x23 + α51x22 + α66x21 + α123x20 + α75x19 + α69x18 + α99x17 + α37x16 + α50x15

 これを二進整数表現で表せば

G1(x) = 00100000x25 + 00000010x24 + 01100101x23 + 00001010x22 + 01100001x21 + 11000101x20 + 00001111x19 + 00101111x18 + 10000110x17 + 01001010x16 + 00000101x15

となり、これをF(x)に足すと最高次の項が消えます(GF(2)の加法を思い出せば1+1=0です)。

R1(x) = F(x) + G1(x) = 01111111x24 + 11001011x23 + 11000111x22 + 01010000x21 + 10011000x20 + 01000010x19 + 00010110x18 + 11100001x17 + 10110110x16 + 11010101x15 + 11001110x14 + 11101100x12 + 00010001x11 + 11101100x10

 以下同様にして、

R0(x) = 01111111x24 + 11001011x23 + 11000111x22 + 01010000x21 + 10011000x20 + 01000010x19 + 00010110x18 + 11100001x17 + 10110110x16 + 11010101x15 + 11001110x14 + 11101100x12 + 00010001x11 + 11101100x10
R1(x) = 01110000x23 + 11111110x22 + 00111101x21 + 11001010x20 + 11100101x19 + 11000011x18 + 01001011x17 + 10000111x16 + 01000110x15 + 01110110x14 + 11101100x12 + 00010001x11 + 11101100x10
R2(x) = 11111001x22 + 00101110x21 + 11010001x20 + 11111000x19 + 01111101x18 + 11010011x17 + 01101111x16 + 10010010x15 + 10001101x14 + 10000011x13 + 11101100x12 + 00010001x11 + 11101100x10
R3(x) = 01110111x21 + 11010111x20 + 11011000x19 + 11001001x18 + 11101111x17 + 01011111x16 + 01011011x15 + 10100101x14 + 01001100x13 + 11111100x12 + 00010001x11 + 11101100x10
R4(x) = 11100010x20 + 10111111x19 + 00101000x18 + 11100010x17 + 10001110x16 + 01000100x15 + 11001101x14 + 11010010x13 + 11110011x12 + 11101111x11 + 11101100x10
R5(x) = 00011100x19 + 10010111x18 + 11110111x17 + 01101010x16 + 10110110x15 + 01011100x14 + 10100001x13 + 10100100x12 + 00100011x11 + 01101000x10
R6(x) = 01011111x18 + 00111010x17 + 10100101x16 + 11110110x15 + 11111101x14 + 10000111x13 + 10011110x12 + 00010110x11 + 10011111x10 + 11101001x9
R7(x) = 10000011x17 + 11111001x16 + 10010001x15 + 11001110x14 + 11100101x13 + 01000100x12 + 10010011x11 + 00101000x10 + 00110000x9 + 10111101x8
R8(x) = 10000100x16 + 01000011x15 + 01011010x14 + 11001101x13 + 00100011x12 + 01001101x11 + 01110101x10 + 10000001x9 + 00110010x8 + 01001010x7
R9(x) = 00001100x15 + 11111100x14 + 10100011x13 + 00011011x12 + 01000101x11 + 00101100x10 + 01011100x9 + 11001001x8 + 00110001x7 + 00110111x6
R10(x) = 00110101x14 + 11010010x13 + 11010001x12 + 10111011x11 + 01100001x10 + 11110011x9 + 01101010x8 + 01000111x7 + 11100101x6 + 01100101x5
R11(x) = 01001110x13 + 11100101x12 + 01101101x11 + 01110000x10 + 00100110x9 + 11010111x8 + 11001111x7 + 10001000x6 + 11011001x5 + 01101011x4
R12(x) = 10000101x12 + 01001111x11 + 10001101x10 + 11000100x9 + 10011110x8 + 11000010x7 + 11001011x6 + 01011100x5 + 00001010x4 + 11110000x3
R13(x) = 11011000x11 + 11101001x10 + 00110101x9 + 11001001x8 + 00001101x7 + 11001100x6 + 11011110x5 + 10000000x4 + 00010110x3 + 11110110x2
R14(x) = 01101010x10 + 10010100x9 + 01111100x8 + 10110111x7 + 11110010x6 + 10111111x5 + 00111001x4 + 11001001x3 + 11101110x2 + 11010100x
R15(x) = 10110001x9 + 00010100x8 + 00000110x7 + 11010000x6 + 00001000x5 + 01011110x4 + 11000100x3 + 00110100x2 + 10110001x + 11010110

 R15(x)は9次式で、これ以上G(x)で割れません。よってこれが最終的な剰余R(x)です。

R(x) = R15(x) = 10110001x9 + 00010100x8 + 00000110x7 + 11010000x6 + 00001000x5 + 01011110x4 + 11000100x3 + 00110100x2 + 10110001x + 11010110

 即ち誤り訂正コード語は10110001 00010100 00000110 11010000 00001000 01011110 11000100 00110100 10110001 11010110となります。

データの配置

 バージョン1のQRコードの基本配置を下図に示します。青色がデータ領域、桃色は形式情報の領域です。

 データ領域にはまず右下から、4x2セルに1コード語を割り当てて行きます。また、各コード語について最上位ビットから横に四行で各ビットを配置します。端まで行ったら折り返して逆向きに進みます。雰囲気で色分けしたのが下図です。
上向のビット配置
0 1
2 3
4 5
6 7
下向のビット配置
6 7
4 5
2 3
0 1

画像を作るのが面倒なのでテキストブラウザにも配慮してデータを配置したQRコードを文字で示します。
■■■■■■■ □  ■  ■■■■■■■
■     ■ □■    ■     ■
■ ■■■ ■ □■ ■■ ■ ■■■ ■
■ ■■■ ■ □   ■ ■ ■■■ ■
■ ■■■ ■ □     ■ ■■■ ■
■     ■ □  ■■ ■     ■
■■■■■■■ ■ ■ ■ ■■■■■■■
        □■  ■        
□□□□□□■□□ ■■■□□□□□□□□
■■■      ■■■ ■■■■■■ ■
■   ■■■■ ■   ■■■   ■■
■ ■■■      ■ ■■ ■■■ ■
 ■ ■  ■■■      ■ ■  ■
        ■    ■■■   ■ 
■■■■■■■ □  ■■■  ■■■■■
■     ■ □ ■ ■  ■■  ■■
■ ■■■ ■ □  ■■    ■ ■ 
■ ■■■ ■ □■   ■■■ ■   
■ ■■■ ■ □■     ■■■   
■     ■ □■■  ■■  ■■ ■
■■■■■■■ □ ■   ■■ ■   
 更に、セルの偏りを解消するために表7のマスクパターンを適用します。条件の欄での(i, j)は(0, 0)が左上のセルで、条件を満たすセルを反転します。本来は各パターンでどれくらいセルが均等になるか評価するのですが、面倒なので001のパターンを使用します。
表7. マスクパターン
マスクパターン
参照子
条件
000 (i + j) mod 2 = 0
001 i mod 2 = 0
010 j mod 3 = 0
011 (i + j) mod 3 = 0
100 ((i div 2) + (j div 3)) mod 2 = 0
101 (i j) mod 2 + (i j) mod 3 = 0
110 ((i j) mod 2 + (i j) mod 3) mod 2 = 0
111 ((i j) mod 3 + (i + j) mod 2) mod 2 = 0
■■■■■■■ □■■ ■ ■■■■■■■
■     ■ □■    ■     ■
■ ■■■ ■ □ ■   ■ ■■■ ■
■ ■■■ ■ □   ■ ■ ■■■ ■
■ ■■■ ■ □■■■■ ■ ■■■ ■
■     ■ □  ■■ ■     ■
■■■■■■■ ■ ■ ■ ■■■■■■■
        □■  ■        
□□□□□□■□□■   □□□□□□□□
■■■      ■■■ ■■■■■■ ■
 ■■■  ■ ■ ■■■   ■■■  
■ ■■■      ■ ■■ ■■■ ■
■ ■ ■■■  ■■■■■■ ■ ■■ 
        ■    ■■■   ■ 
■■■■■■■ □■■   ■■     
■     ■ □ ■ ■  ■■  ■■
■ ■■■ ■ □■■  ■■■■ ■ ■
■ ■■■ ■ □■   ■■■ ■   
■ ■■■ ■ □ ■■■■■   ■■■
■     ■ □■■  ■■  ■■ ■
■■■■■■■ □■ ■■■  ■ ■■■
 ……マスクパターンの選択が悪かった気がしますが、気にしないでおきましょう。

形式情報の付加

 最後に□(桃色)の部分へ誤り訂正レベル指示子とマスクパターン参照子のデータを加えます。誤り訂正レベルはMなので00、マスクパターン参照子は001で、これらを繋げて00001となります。
表8. 誤り訂正レベル指示子
誤り訂正レベル 二進指示子
L 01
M 00
Q 11
H 10
 これを多項式で1と表し、x10を乗じて形式情報用の生成多項式x10+x8+x5+x4+x2+x+1で除算します(これはGF(2)上の多項式です)。

1 x10 = (x10 + x8 + x5 + x4 + x2 + x + 1) + (x8 + x5 + x4 + x2 + x + 1)

 この剰余x8+x5+x4+x2+x+1を10ビットの二進数で0100110111と表し、元のデータと合わせて000010100110111という15桁のビット列にします。
 最後に形式情報のマスクパターン101010000010010とXOR演算して最終的な形式情報のビット列101000100100101を得ます。
 このビット列は下図のように、大文字と小文字の二領域に配置します。図でOとoが最上位ビットです。

■■■■■■■ A     ■■■■■■■
■     ■ B     ■     ■
■ ■■■ ■ C     ■ ■■■ ■
■ ■■■ ■ D     ■ ■■■ ■
■ ■■■ ■ E     ■ ■■■ ■
■     ■ F     ■     ■
■■■■■■■ ■ ■ ■ ■■■■■■■
        G            
ONMLKJ■IH    hgfedcba
                     
      ■              
                     
      ■              
        ■            
■■■■■■■ i            
■     ■ j            
■ ■■■ ■ k            
■ ■■■ ■ l            
■ ■■■ ■ m            
■     ■ n            
■■■■■■■ o            
 これでQRコードの完成です! 携帯電話や、「Psytec QR Code Editor」などのソフトで読み取ってみましょう。私達のキムワイプ愛はそこにあります。
■■■■■■■ ■■■ ■ ■■■■■■■ ■     ■  ■    ■     ■ ■ ■■■ ■ ■ ■   ■ ■■■ ■ ■ ■■■ ■     ■ ■ ■■■ ■ ■ ■■■ ■  ■■■■ ■ ■■■ ■ ■     ■ ■  ■■ ■     ■ ■■■■■■■ ■ ■ ■ ■■■■■■■          ■  ■         ■ ■   ■■ ■     ■  ■ ■ ■■■      ■■■ ■■■■■■ ■  ■■■  ■ ■ ■■■   ■■■   ■ ■■■      ■ ■■ ■■■ ■ ■ ■ ■■■  ■■■■■■ ■ ■■          ■    ■■■   ■  ■■■■■■■ ■■■   ■■      ■     ■   ■ ■  ■■  ■■ ■ ■■■ ■  ■■  ■■■■ ■ ■ ■ ■■■ ■  ■   ■■■ ■    ■ ■■■ ■ ■ ■■■■■   ■■■ ■     ■  ■■  ■■  ■■ ■ ■■■■■■■ ■■ ■■■  ■ ■■■
※周囲に4セル分のクワイエットゾーンを空けるのを忘れないようにしましょう。

参考

[1] 日本工業規格. JIS X 0510:2004. 二次元コードシンボル-QRコード-基本仕様. (及びその正誤表)
[2] デンソーウェーブ. "QRコードの導入 ~バージョンの決定~". QRcode.com. http://www.qrcode.com/qrgene2.html, (accessed 2011-03-22).
[3] 南 敏. 情報理論. 第2版, 産業図書, 1993, 211p., ISBN4-7828-9009-5.

奥付

あなたも描ける! JIS X0510準拠 QRコード®超入門
平成廿三年卯月朔日 初版
OSSHC出版
©OSSHC 2011
ą
i1.png
(1k)
岡崎高校スーパーサイエンス部,
2011/03/31 8:10
ą
i2.png
(1k)
岡崎高校スーパーサイエンス部,
2011/03/31 8:11
ą
i3.png
(2k)
岡崎高校スーパーサイエンス部,
2011/03/31 8:11
Comments