マイクロQRコードについて調べる機会があったのですが、マイクロQRコードに関する情報がネットに全然転がっていないのでJIS規格書を読むことになりました。せっかくなのでそこで得た知識をここに書いておきます。
なお、この記事は JIS X 0510 を参考に私の理解した内容を書いています。何か間違い等がございましたらご指摘ください。
この記事は ISer Advent Calender 2022 に参加しています。
目次
用語
まず初めにマイクロQRコードに関する用語を紹介します。（普通のQRコードでも同じです。）
シンボル
完成したマイクロQRコード全体を指してシンボルと呼びます。
モジュール
シンボルを構成する最小単位のドットをモジュールと呼びます。
型番（バージョン）
シンボルの大きさ、すなわち1辺のモジュール数を型番（バージョン）と呼びます。この記事では型番と呼びます。
モード
マイクロQRコードには数字モード、英数字モード、8ビットバイトモード、漢字モードの4つのモードがあり、モードによって文字とビット列の対応が異なります。
また、一つのシンボルの中に複数のモードを混在させることも可能です。
機能パターン
シンボルのうち位置検出パターンなどの、情報が埋め込まれていない部分を機能パターンと呼びます。
形式情報
型番および誤り訂正レベル、マスクパターンについての情報を形式情報と呼びます。
コード語
マイクロQRコードに埋め込まれる情報のことをコード語と呼び、1コード語=8 bitとなっています。（一部例外あり）
コード語はデータコード語と誤り訂正コード語からなります。
型番（大きさ）
マイクロQRコードには4種類の型番が用意されていて、型番が大きくなるほどサイズとデータ量が大きくなります。
型番、誤り訂正レベルごとの各モードにおける最大の文字数は以下の通りとなっています。
シンボルの構造
こちらはM2型のマイクロQRコードです。誤り訂正レベルはL, 数字モードで10文字の情報(0714225731)が格納されています。
モジュールを機能ごとに色分けすると次のようになります。
緑: 位置検出パターン
黄: 分離パターン
青: タイミングパターン
紫: 形式情報
黒: コード語
また、シンボルの外側にはモジュール2つ分のクワイエットゾーンを必要とします。
位置検出パターン、分離パターン、タイミングパターンを総称して機能パターンと呼び、形式情報とコード語の部分を符号化領域と呼びます。
型番が異なる場合は、位置検出パターン、分離パターン、形式情報の大きさは固定で、タイミングパターンとコード語の領域が変化します。
表にまとめると以下のようになります。
ただし、M1型とM3型ではコード語のうち最後の1つが4bitとなります。
データコード語の構造
コード語にはデータコード語と誤り訂正コード語がありますが、まずはデータコード語の構造を説明します。
データコード語は1個以上のセグメントと、終端パターン、埋め草ビット、埋め草コードからなります。
1つのセグメントはモード指示子、文字数指示子、データビット列からなります。
セグメントごとにモードを変えられるので、1つのマイクロQRコードに複数のモードを混在させられるということなのですが、基本的には1個のセグメントになるんじゃないかと思います。
モード指示子
モード指示子はそのセグメントのモードを指定するビット列で、型番により長さが異なります。
M1型の場合は数字モードしかないためモード指示子は存在しません。
例えば、M2型数字モードであれば “0” となります。
文字数指示子
文字数指示子はそのセグメントのデータの文字数を指定するビット列で、型番とモードにより決まった長さの2進数として表します。
文字数指示子の長さは以下の通りです。
例えば、M2型数字モード10文字であれば “1010” となります。
データビット列 – 数字モード
数字モードでは “0” ~ “9” の10種類の文字を使用できます。
入力データからビット列への変換は以下の手順で行います。
①上から3桁ずつのグループに分割する。
②各グループを3桁の10進数から10桁の2進数に変換する。
このとき、最後のグループが1, 2桁になる場合はそれぞれ4, 7桁の2進数に変換します。
例えば、”0714225731″という文字列をビット列に変換すると、
① 071 422 573 1
② 0001000111 0110100110 1000111101 0001
となります。
データビット列 – 英数字モード
英数字モードでは下の表にある通り、数字と英語（大文字のみ）、9種類の記号の合わせて45種類の文字が使用できます。
入力データからビット列への変換は以下の手順で行います。
①上から2桁ずつのグループに分割する。
②各グループを2桁の45進数から11桁の2進数に変換する。
このとき、最後のグループが1桁になる場合は6桁の2進数に変換します。
45進数の文字と10進数の数字の対応関係は以下の表の通りです。
例えば45進数のRは10進数の27に対応します。SPは空白を指します。
例えば、”RIKEDEN”という文字列を変換すると、
① RI KE DE N
(10進数に変換) 1233 914 599 23
② 10011010001 01110010010 01001010111 010111
となります。
データビット列 – 8ビットバイトモード
8ビットバイトモードでは、JIS X 0201に基づく英数字・記号、半角カナを使用できます。
0x00~0x7Fまでの部分は ASCII の文字コードです。0x00~0x1Fにも制御文字などがありますがここでは省略しています。
0xA1~0xDFに半角カナが割り当てられています。
データビット列は各文字コードを2進数8ビットで並べたものとなります。
データビット列 – 漢字モード
漢字モードでは Shift-JIS の文字コードを利用します。ただし、Shift-JIS の文字コードは16ビットで無駄な領域を含んでいるので下記の手順で13ビットに圧縮します。
(a) 0x8140 ~ 0x9FFC の文字
① 文字コードから 0x8140 を減算する。
② 得られた値の上位バイトに 0xC0 を乗算する。
③ ②の結果に下位バイトを加算する。
④ 結果を13ビット2進文字列に変換する。
(b) 0xE040 ~ 0xEBBF の文字
① 文字コードから 0xC140 を減算する。
② 得られた値の上位バイトに 0xC0 を乗算する。
③ ②の結果に下位バイトを加算する。
④ 結果を13ビット2進文字列に変換する。
なぜこのようになっているのかは予想はついていますが、Shift-JIS の説明から必要なので割愛します。Shift-JIS についても調べてみたら面白かったのでいつか記事を書くかもしれません。
例えば、”理系”の場合、
(Shift-JIS 文字コード) 0x979D, 0x8C6E
① 0x979D – 0x8140 = 0x165D, 0x8C6E – 0x8140 = 0x0B2E
② 0x16 * 0xC0 = 0x1080, 0x0B * 0xC0 = 0x0840
③ 0x1080 + 0x5D = 0x10DD, 0x0840 + 0x2E = 0x086E
④ 1000011011101 0010001001110
となります。
終端パターン、埋め草ビット、埋め草コード
終端パターンはデータの終わりを示すためのパターンで、セグメントを並べたビット列の後ろに次の表の通りに0を並べます。
0の個数は、各型番における モード指示子長 + 数字モードの文字数指示子長 となっていて、データ長が 0 のセグメントにより終端を示しているとも言えます。
こうして出来上がったビット列を先頭から8ビットずつ区切ることによってデータコード語とします。ただし、ビット列の長さは型番と誤り訂正レベルによって次のように決まっていて、過不足がある場合には調整を行います。
まず、データビット数を超過している場合は、超過している分だけ終端パターンを削ります。
次に、先頭から8ビットずつ区切ったときに最後のコード語の長さが8に満たない場合は、埋め草ビットとして0を付加して8ビットにします。
最後に、データコード語数が足りない場合は、埋め草コード語 11101100 及び 00010001 を交互に不足している分だけ付加します。
ただし、M1型及びM3型の場合、最後のコード語は4ビット長とし、埋め草コード語として使用する場合は 0000 とします。
余談なのですが、デンソーウェーブの公式サイトに載っている次のM3型マイクロQRコードを人力で解析したところ、データコードの最後2つは 11101100, 0001となっていました。
前者は埋め草コード語で問題ないのですが、後者は埋め草コード語の上位4ビットのように思います。ここは0000が入るのが正しいような気がするのですが、私の解釈が間違っているのでしょうか？いずれにせよデータは含まれていないし誤り訂正も可能なので問題は無いのですが気になります。
誤り訂正コード語
QRコードは RS(リードソロモン)符号によって誤り検出及び誤り訂正をすることが出来ます。
RS符号を求めるにはガロア体GF(2^8)を係数とする多項式の剰余を用いるのですが、かなり複雑な話になるのでここでは割愛します。
こちらのサイトが参考になりました。
データコード語から生成したRS符号を誤り訂正コード語としてデータコード語の後ろに並べることで、コード語の完成です。
コード語の配置
コード語はシンボルの右下から2列ずつジグザグに上下に往復を繰り返していくように並べられます。このとき、データはMSBから順に並べられ1は黒、0は白となります。機能パターンの部分はスキップされます。
下の図で緑の部分は機能パターンであり、青線で囲った部分がデータ語の単位となっています。
ちなみにこの並べ方はQRコードでも同じです。
マスク
シンボルの読取りを確実にするためには、白と黒のモジュールがバランスよく並んでいることが望ましいです。そのため、いくつかのマスクパターンと XOR 演算をしてその中から最適なものを選びます。
XOR 演算は 0⊕x = x, 1⊕x = x となるので、マスクパターンの部分だけ反転する効果があります。
マスクパターンは次の条件によって生成されます。ただし i は行、 j は列を表し、行と列は左上を0とします。div と mod は除算の商と剰余を表します。
例えば、マスクパターン00と11はそれぞれ次のようになります。
どのマスクが良いかの評価は次のように計算され、評価が最も高いものを採用します。
①右の辺と下の辺の黒モジュールの数をSUM1, SUM2とする。
②評価 = MAX(sum1, sum2) * 16 + MIN(sum1, sum2)
形式情報
形式情報は、型番番号3ビット、マスクパターン参照子2ビット、誤り訂正用の BCHコード10ビットからなります。
BCHコードを求めるには次のように計算します。ただし、ここでは多項式の係数は0または1であり、係数の和と積は XORとANDで行います。
①型番番号とマスクパターン参照子の5ビットのそれぞれの数字を係数にもつ多項式f(x)を作る。\\ ②f(x)にx^{10}を乗算する。\\ ③f(x)を生成多項式G(x) = x^{10} +x^8 + x^5+x^4+x^2+x+1で割った余りを求める。\\ ④余りの9次多項式の各係数を10ビットのBCHコードとする。最後に形式情報がすべて0となるのを防ぐために 100010001000101 とXOR演算を行いマスクをかけます。
例えば、M2型誤り訂正レベルL(型番番号001)、マスクパターン10の場合は、
①f(x) = 0*x^4 + 0*x^3 + 1*x^2 + 1*x + 0\\ ②f(x) = x^{12} + x^{11}\\ ③f(x) = (x^{10} +x^8 + x^5+x^4+x^2+x+1)(x^2+x+1) + (x^9+x^8+x^7+x^2+1)\\ ④BCHコード = 1110000101\\ ⑤001101110000101 ⊕ 100010001000101 = 101111111000000\\となります。
完成した15ビットの形式情報はシンボルの形式情報の部分（紫の部分）に左下から右上に向かってMSBから順に配置します。
終わりに
マイクロQRコードの仕組みについて調べたのは、QR時計を作るためでした。PICマイコンでマイクロQRコードのデータを計算して、LEDを光らせています。
よろしければ動画も見て頂けると嬉しいです。
