QRコードの仕組み

2025/05/11 12:46 投稿

QRコードのエンコード・デコードの仕組みを解説する。

関連ページ

• 有限体
• 誤り訂正符号 - BCH符号・RS符号
• QRコードの仕組み (本ページ)
• QRコード生成ツール

目次

• QRコードの経緯
• 構造
  • バージョン
  • 構成要素
• Format/Version Informationのエンコード
  • Format Information
  • Version Information
• データのエンコード
  • データコード語の構成
  • ブロック分割
  • RS符号化
  • コード語の配置
  • マスク
• 参考
  • 解説
  • 実装例

QRコードの経緯

QRコード(Quick-Response code)は、1994年にデンソー(現・デンソーウェーブ)が発明した2次元コード。
デンソーの製造現場で、従来のバーコードに代わる大容量かつ読み取り効率の高いコードが求められたことをきっかけに開発された。QRコードには次のような特徴がある。

• 1次元コードであるバーコードに比べて格納できる情報の量が多い
• Finder Patternという独特なパターンを用いることでコードの検出を容易にし、高速な読み取りを実現
• 符号理論に基づいた誤り訂正能力を備え、コードの汚れによる情報欠損に対して堅牢性がある

これらの特長により、QRコードは製造・流通業界に急速に普及した。その後、カメラ付き携帯電話の登場に伴い、スマートフォン決済や電子チケットなど身近な場面でも広く活用されるようになり、現在では日常生活に不可欠な技術となっている。

QRコードの例 (バージョン9)

2012年のパズルゲーム「FEZ」に登場するQRコードを利用した仕掛け

構造

QRコードには初期の仕様であるモデル1と、大型化に対応したモデル2が存在する。現在はモデル1が使用されることは滅多にないので、この投稿ではモデル2に限って解説を行う。

また、データ圧縮方式には「数値モード」・「英数字モード」・「8ビットバイトモード」・「漢字モード」の種類が存在するが、ここでは8ビットバイトモードのみを使う前提で解説する。
UTF-8でエンコードしたバイト列を8ビットバイトモードでQRコードにエンコードすることで、英数字と漢字を含むUnicodeの文字列を自由に表現することができる。

バージョン

QRコードの大きさは後述のQuiet Zone(外側の白い部分)を除いた部分のセルの数で表現される。(セルのことを正式には「モジュール」と言うが、直感的ではないのでここではセルと呼ぶことにする)
最小のQRコードは21x21の大きさで、このサイズをバージョン1(あるいは1型)と呼ぶ。バージョン2は25x25、バージョン3は29x29と、バージョンが1上がるごとに一辺が4セルずつ増えていく。最大のバージョンは40で、サイズは177x177。

バージョン1のQRコードの例 (21x21)

バージョン40のQRコードの例 (177x177)

構成要素

Quiet Zone (クワイエットゾーン)

Quiet Zoneは、QRコードの外側に存在する余白領域。上下左右それぞれに4セル分確保する必要があると定められている。

Quiet Zone

Finder Pattern (位置検出パターン)

Finder Patternは、QRコードの左上・右上・左下に配置される特徴的なパターン。
このパターンはQRコードの検出のために利用される。読み取り機は1:1:3:1:1の白黒のパターンを検出することによってFinder Patternの位置を特定し、3つのFinder Patternの位置関係からQRコードが存在する領域を推定する。

1:1:3:1:1という比率は、開発当時にあらゆる印刷物を調べて最も使われていない比率であったことから、誤認識が少ないという理由で採用されたらしい。

Finder Pattern

Alignment Pattern (位置合せパターン)

Alignment Patternは、QRコード内にほぼ等間隔に配置されるパターン。
QRコードの歪みを補正するために利用される。

Alignment Patternはバージョン2から6までは2x2個配置し(ただしFinder Patternと被る部分は描画しない)、以降はバージョンが7上がるごとに縦横に1つずつ配置個数を増やしていく。また、バージョン1の場合は例外的にAlignment Patternを1つも配置しない。

下図はバージョン9の例。3x3の格子状に6個のパターンを配置している。

Alignment Pattern

Alignment Patternは上下左右の端のパターンがFinder Patternと整列するように配置され、その間にほぼ等間隔になるように残りのパターンが配置される。
左右(あるいは上下)の端同士のパターンの中心座標の差を\(a\)とし、Alignment Patternの配置数を\(b\)x\(b\)とすると、Alignment Patternは中心座標の間隔が\(\frac{a}{b-1}\)以上の最小の偶数、つまり\(2\left\lceil \frac{1}{2}\frac{a}{b-1} \right\rceil\)となるように右(下)から配置される。その結果、左端(上端)では間隔が他の部分より短くなる場合がある。

例えば、下図はバージョン16の場合のAlignment Patternの例だが、\(a = 81-13 = 68\)、\(b=4\)なので中心座標の間隔は\(2\left\lceil \frac{1}{2}\frac{a}{b-1} \right\rceil = 2\left\lceil \frac{1}{2}\frac{68}{3} \right\rceil = 24\)となる。68の間隔を右(下)から24ずつ区切ると最後に20余るので、左端(上端)の間隔だけは20になる。

Alignment Pattern (バージョン16)

Timing Pattern (タイミングパターン)

Timing Patternは、Finder Patternを結ぶように白黒を交互に繰り返すパターン。
QRコード内の座標を決定するために利用される。

Timing Pattern

Separator (分離パターン)

Separatorは、Finder Patternとその他の領域を分離する余白。

Separator

常に黒となる部分

図の位置にある1セルは常に黒になるよう定められている。特に名称は定められていない。

常に黒となる部分

Format Information (形式情報)

Format Informationは、後述の誤り訂正レベルとマスクパターンを記録する15-bitの値。
下図のようにSeparatorに隣接する位置に配置され、縦方向と横方向に同一の情報を2箇所に書き込む。(黒=1, 白=0)

Format Information

Format Informationの配置順 (0が下位ビットで14が上位ビット)

Format Informationの内容は次の3つの部分で構成される。詳細は後述。

• 誤り訂正レベル指示子 (2-bit)
  
  • L=01, M=00, Q=11, H=10を書き込む
• マスクパターン参照子 (3-bit)
  
  • マスクパターン0～8をそのまま2進数で書き込む
• 上記合計5-bitに対するBCH符号の誤り訂正ビット (10-bit)
  
  • 生成多項式は10100110111

Version Information (型番情報)

Format Informationはバージョンの情報を記録する領域。この領域はバージョン7以上のQRコードにのみ存在する。
下図のようにSeparatorに隣接する位置に配置され、Format Informationと同様に2箇所に同じ内容を書き込む。

Version Information

Version Informationの配置順 (0が下位ビットで17が上位ビット)

Version Informationの内容は次の2つの部分で構成される。詳細は後述。

• バージョン情報 (6-bit)
• バージョン情報6-bitに対するBCH符号の誤り訂正ビット (12-bit)
  
  • 生成多項式は1111100100101

符号語領域 (データと誤り訂正符号)

これまでに説明した領域を除いた残りの領域全体が「データ」と「誤り訂正符号」を書き込む領域となる。

書き込みたいデータのビット列を8ビットずつのコード語に区切り、コード語の集合を並び替えてからブロックに分割し、ブロックごとにRS符号化し、データコード語と誤り訂正コード語を適切な順番で書き込む。詳しくは後述する。

データと誤り訂正符号

この領域の容量は次の表の通り。
データと誤り訂正符号は8ビット単位の大きさの「コード語」として扱われるので、bit数で表されるコード容量を8で割った余りはデータの保存に使うことはできない。この余りのビット数のことを残余ビットと言う。
また次の表には、仕様で定められたブロック数とブロックごとの誤り訂正コード語数も記載する。

容量が最大となるのはバージョン40・誤り訂正レベルLの場合で、(8ビットバイトモードの場合) \(3706-25\times30 - 3 = 2953\) Byteのデータを格納することができる。(差し引いた3 Byte分は、8ビットバイトモードを指定する1Byteとデータの長さを指定する2Byte)

Format/Version Informationのエンコード

Format Information

Format Informationの内容は次の3つの部分で構成される。

• 誤り訂正レベル指示子 (2-bit)
  
  • L=01, M=00, Q=11, H=10を書き込む
• マスクパターン参照子 (3-bit)
  
  • マスクパターン0～8をそのまま2進数で書き込む
• 上記合計5-bitに対するBCH符号の誤り訂正ビット (10-bit)
  
  • 生成多項式は10100110111

またこれら3つの部分を結合した後、ビット列が全て0にならないようにマスクパターン101010000010010とのXOR演算を行って最終的なFormat Informationの値とする。

誤り訂正ビットは後述のBCH符号の組織符号化で実装されているが、実際は次の表のように32通りのパターンしかないので、QRコードを生成する際は予め計算した値を参照して書き込めば良い。

具体例

誤り訂正レベルが「Q」で、マスクが「5」の場合の例を見てみよう。

誤り訂正レベルQに対応するビット列は11、マスク5に対応するビット列は101なので、エンコードするデータは11101になる。データの各桁を\(\mathbb{F}_2\)係数多項式の各次数の係数と見なすと、データに対応する多項式は

\begin{align} a(x) &= 1\cdot x^4 + 1\cdot x^3 + 1\cdot x^2 + 0\cdot x + 1 \\ &= x^4+x^3+x^2+1 \end{align}

となる。

生成多項式は10100110111なので、同様に多項式で表すと

\begin{align} g(x) &= x^{10}+x^8+x^5+x^4+x^2+x+1 \end{align}

となる。

BCH符号の組織符号化ではこの場合、\(g(x)\)と同じ次数である\(x^{10}\)を\(a(x)\)に掛けて、\(g(x)\)で割った余り\(r(x)\)を求める。
通常の2進数の割り算ではなく\(\mathbb{F}_2\)上の係数に対する演算なので、\(1+1=0\)となることから桁の繰り上がり・繰り下がりが発生しないことに注意して、次のように計算する。

\begin{align} 11011\, \\ 10100110111 \enclose{longdiv}{111010000000000} \\ \underline{10100110111} \phantom{0000}\, \\ 10011101110 \phantom{000}\, \\ \underline{10100110111} \phantom{000}\, \\ 11101100100 \phantom{0}\, \\ \underline{10100110111} \phantom{0}\, \\ 10010100110 \, \\ \underline{10100110111} \, \\ 0110010001 \, \\ \end{align}

計算結果から、余り\(r(x)\)の2進数表示は0110010001であることがわかる。

得られた\(r(x)\)を用いて

\begin{align} w(x):=a(x)x^{10}-r(x) \end{align}

と定義すると\(w(x)\)は\(g(x)\)で割り切ることができ、目的のBCH符号となる。
\(\mathbb{F}_2\)係数では足し算と引き算は同じ結果になるので、\(w(x)=a(x)x^{10}+r(x)\)とも表すことができる。よって、\(w(x)\)を2進数で表す場合、元のデータと\(r(x)\)を繋げて111010110010001とすれば良い。

Format Informationでは最後に101010000010010とのXOR演算を行うので、最終的な値は010000110000011となる。

\begin{align} 111010110010001 \\ \underline{+ \phantom{0} 101010000010010} \\ 010000110000011 \end{align}

Version Information

Version Informationの内容は次の2つの部分で構成される。

• バージョン情報 (6-bit)
• バージョン情報6-bitに対するBCH符号の誤り訂正ビット (12-bit)
  
  • 生成多項式は1111100100101

Format Informationのようなマスク処理(XOR演算)は行わない。

計算済みの誤り訂正符号全体は次の表の通り。

計算例はFormat Informationと同様。

データのエンコード

符号語領域に書き込む値のエンコード方法を解説する。
ここではUTF-8でエンコードしたデータを8ビットバイトモードで書き込む場合に限定して考える。

データコード語の構成

QRコードの符号語領域には8-bit単位で値が書き込まれるが、それらの値には「データコード語」・「誤り訂正コード語」の2種類がある。

• 符号語
  
  • データコード語 - 書き込みたいデータの実体が格納されている。符号語領域の前半に書き込む。
  • 誤り訂正コード語 - RS符号で実装された誤り訂正符号。符号語領域の後半に書き込む。

データコード語の列は次のように構成される。

• モード指示子
  
  • ここでは「8ビットバイトモード」を指定する4-bit値「0100」(0x4)で固定
• 文字数指示子
  
  • データビット列の長さ(バイト数)を表すビット列
  • 8ビットバイトモードでは文字数指示子の長さはバージョン9以下のとき8-bit、バージョン10以上のとき16-bitになる
• データビット列
  
  • QRコードに保存したいデータ (ここでは文字列をUTF-8でエンコードしたビット列)
• 終端パターン
  
  • 4-bit値「0000」(0x0)でデータの末端を表す
  • 残り容量が4-bit未満のときは桁数に合わせて短縮することが可能。特に残り容量が丁度0-bitのときは終端パターン自体を省略することが可能。8ビットバイトモードの場合はこの時点での残り容量は必ず4-bit以上となるので、「0000」で固定と考えて良い。
• 埋め草ビット
  
  • ここまでのデータの長さが8の倍数にならないとき、8の倍数になるように埋め草ビット「0」を必要な数だけ追加する。8ビットバイトモードの場合はここまでのデータの長さは必ず8の倍数になるので、埋め草ビットが発生することはない。
• 埋め草コード語
  
  • データ容量に対する残りの部分は「11101100」(0xEC)・「00010001」(0x11)を繰り返して埋める。

例

バージョン5・誤り訂正レベルHで、データが文字列「QRコード」の例を考える。

バージョン5なので上に掲載した表から、コード語の容量は134。
ブロック数は4で、各ブロックに22個の誤り訂正コード語があるので、データコード語の容量は134 - 4･22 = 46である。

文字列「QRコード」をUTF-8でエンコードすると、16進数で「51 52 E382B3 E383BC E38389」と表される11バイトの値になる。したがって文字数指示子の値は11となるが、今はバージョン3なので11を8桁の2進数で表して00001011(=0x0B)とする。

これらをまとめるとデータコード語は最終的に次の表のように構成され、16進数で「40 B5 15 2E 38 2B 3E 38 3B CE 38 38 90 EC 11 EC 11 EC 11 EC 11 EC 11 EC 11 EC 11 EC 11 EC 11 EC 11 EC 11 EC 11 EC 11 EC 11 EC 11 EC 11 EC」となる。

ブロック分割

データコード語(の配列)が得られたら、次にデータコード語を規定されたブロック数に分割する。
余りが出る場合は、後ろのブロックが1つ多くのコード語を含むように分ける。

例

バージョン5・誤り訂正レベルHで、データが文字列「QRコード」の例を考える。
この例では前節で確かめたように、データコード語の容量は46である。ブロック数は4なので、46個のデータコード語は次のように11・11・12・12個に分割される。

RS符号化

各ブロックをRS符号で組織符号化し、規定の長さの誤り訂正コード語を追加する。RS符号化を行うことによって、万が一QRコードの情報に欠損が生じても、欠損した位置を自動的に検出し修正することができるようになる。

QRコードのRS符号化では、\(\mathbb{F}_{2^8}=\mathbb{F}_2[x]/(x^8+x^4+x^3+x^2+1)\)上係数の多項式が用いられる。
\(\mathbb{F}_{2^8}\)の原始元を\(\alpha(x)=x\)とすると、各要素\(y\in\mathbb{F}_{2^8}\)は次の表のように表すことができる。\(\mathbb{F}_{2^8}\)の要素同士の計算は、足し算(=引き算=XOR演算)のときは2進表記を使い、掛け算・割り算には冪乗表記を使うと簡単に結果を求めることができる。

ブロックごとの誤り訂正コード語数が\(h\)のとき、生成多項式は

\begin{align} g(y) &= (y-\alpha^0)(y-\alpha^1)(y-\alpha^2)\cdots (y-\alpha^{h-1}) \end{align}

と定義される。(このとき\(\left\lfloor\frac{h}{2}\right\rfloor\)個までの符号語に誤りが発生しても訂正することができる)

BCH符号と同様に、(ブロック分割された)データコード語\(a(y)\)に\(y^h\)を掛けて\(g(y)\)で割った余り\(r(y)\)を用いることで、RS符号\(w(y):=a(y)y^h+r(y)\)が得られる。
このとき、\(r(y)\)の係数を羅列したものが(ブロックごとの)誤り訂正コード語となる。

例1

最も単純な例として、バージョン1・誤り訂正レベルLで、データが文字列「QRコード」の場合を考える。

(ブロックごとの)誤り訂正コード語数は7なので、生成多項式は

\begin{align} g(y) &= (y-\alpha^0)(y-\alpha^1)(y-\alpha^2)(y-\alpha^3)(y-\alpha^4)(y-\alpha^5)(y-\alpha^6) \\ \end{align}

となる。この式は、上記の表を参照して例えば

\begin{align} (y-\alpha^5)(y-\alpha^6) &= (y+\alpha^5)(y+\alpha^6) \\ &= y^2 + (\alpha^5 + \alpha^6)y + \alpha^5\alpha^6 \\ &= y^2 + (00100000 \:\mathrm{XOR}\: 01000000)y + \alpha^{11} \\ &= y^2 + 01100000\cdot y + \alpha^{11} \\ &= y^2 + \alpha^{30}y + \alpha^{11} \\ \end{align}

という風に展開していくことができ、最終的に

\begin{align} g(y) &= (y-\alpha^0)(y-\alpha^1)(y-\alpha^2)(y-\alpha^3)(y-\alpha^4)(y-\alpha^5)(y-\alpha^6) \\ &= y^7 + \alpha^{87}y^6 + \alpha^{229}y^5 + \alpha^{146}y^4 + \alpha^{149}y^3 + \alpha^{238}y^2 + \alpha^{102}y + \alpha^{21} \\ &= y^7 + 127y^6 + 122y^5 + 154y^4 + 164y^3 + 11y^2 + 68y + 117 \\ \end{align}

と表すことができる。

データは「40 B5 15 2E 38 2B 3E 38 3B CE 38 38 90 EC 11 EC 11 EC 11」の19コード語となり、多項式で表すと次の通り。

\begin{align} a(y) &= \mathrm{0x40}y^{18} + \mathrm{0xB5}y^{17} + \mathrm{0x15}y^{16} + \mathrm{0x2E}y^{15} + \mathrm{0x38}y^{14} + \mathrm{0x2B}y^{13} + \mathrm{0x3E}y^{12} + \mathrm{0x38}y^{11} + \mathrm{0x3B}y^{10} + \mathrm{0xCE}y^9 + \mathrm{0x38}y^8 + \mathrm{0x38}y^7 + \mathrm{0x90}y^6 + \mathrm{0xEC}y^5 + \mathrm{0x11}y^4 + \mathrm{0xEC}y^3 + \mathrm{0x11}y^2 + \mathrm{0xEC}y + \mathrm{0x11} \\ &= 64y^{18} + 181y^{17} + 21y^{16} + 46y^{15} + 56y^{14} + 43y^{13} + 62y^{12} + 56y^{11} + 59y^{10} + 206y^9 + 56y^8 + 56y^7 + 144y^6 + 236y^5 + 17y^4 + 236y^3 + 17y^2 + 236y + 17 \\ \end{align}

したがって、\(r(y)\)は次のように求めることができる。(\(\mathbb{F}_{2^8}\)上の掛け算・引き算であることに注意)

\begin{align} 64\,\phantom{00}3\,127\,\phantom{0}24\,234\,106\,221\,183\,132\,141\,\phantom{0}43\,219\,232\,218\,\phantom{0}13\,\phantom{0}19\,221\,111\,188\, \\ 1\,127\,122\,154\,164\,\phantom{0}11\,\phantom{0}68\,117 \enclose{longdiv}{\phantom{0}64\,181\,\phantom{0}21\,\phantom{0}46\,\phantom{0}56\,\phantom{0}43\,\phantom{0}62\,\phantom{0}56\,\phantom{0}59\,206\,\phantom{0}56\,\phantom{0}56\,144\,236\,\phantom{0}17\,236\,\phantom{0}17\,236\,\phantom{0}17\,\phantom{00}0\,\phantom{00}0\,\phantom{00}0\,\phantom{00}0\,\phantom{00}0\,\phantom{00}0\,\phantom{00}0} \\ \underline{\phantom{0}64\,182\,235\,\phantom{0}73\,114\,250\,208\,\phantom{0}12} \phantom{\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000}\, \\ \phantom{000\,00}3\,254\,103\,\phantom{0}74\,209\,238\,\phantom{0}52\,\phantom{0}59 \phantom{\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000}\, \\ \underline{3\,129\,142\,179\,241\,\phantom{0}29\,204\,159} \phantom{\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000}\, \\ 127\,233\,249\,\phantom{0}32\,243\,248\,164\,206 \phantom{\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000}\, \\ \underline{127\,241\,111\,243\,203\,\phantom{0}94\,\phantom{0}87\,208} \phantom{\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000}\, \\ 24\,150\,211\,\phantom{0}56\,166\,243\,\phantom{0}30\,\phantom{0}56 \phantom{\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000}\, \\ \underline{24\,124\,\phantom{00}4\,241\,219\,232\,\phantom{0}46\,140} \phantom{\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000}\, \\ 234\,215\,201\,125\,\phantom{0}27\,\phantom{0}48\,180\,\phantom{0}56 \phantom{\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000}\, \\ \underline{234\,189\,216\,252\,179\,\phantom{0}32\,151\,119} \phantom{\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000}\, \\ 106\,\phantom{0}17\,129\,168\,\phantom{0}16\,\phantom{0}35\,\phantom{0}79\,144 \phantom{\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000}\, \\ \underline{106\,204\,\phantom{0}19\,110\,\phantom{0}87\,201\,\phantom{0}42\,111} \phantom{\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000}\, \\ 221\,146\,198\,\phantom{0}71\,234\,101\,255\,236 \phantom{\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000}\, \\ \underline{221\,\phantom{0}37\,171\,226\,\phantom{0}67\,220\,\phantom{0}10\,\phantom{0}36} \phantom{\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000}\, \\ 183\,109\,165\,169\,185\,245\,200\,\phantom{0}17 \phantom{\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000}\, \\ \underline{183\,233\,184\,140\,\phantom{0}20\,\phantom{0}21\,\phantom{0}32\,\phantom{0}75} \phantom{\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000}\, \\ 132\,\phantom{0}29\,\phantom{0}37\,173\,224\,232\,\phantom{0}90\,236 \phantom{\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000}\, \\ \underline{132\,144\,\phantom{0}62\,192\,\phantom{0}78\,197\,176\,209} \phantom{\,000\,000\,000\,000\,000\,000\,000\,000\,000\,000}\, \\ 141\,\phantom{0}27\,109\,174\,\phantom{0}45\,234\,\phantom{0}61\,\phantom{0}17 \phantom{\,000\,000\,000\,000\,000\,000\,000\,000\,000}\, \\ \underline{141\,\phantom{0}48\,179\,254\,163\,150\,238\,\phantom{0}43} \phantom{\,000\,000\,000\,000\,000\,000\,000\,000\,000}\, \\ 43\,222\,\phantom{0}80\,142\,124\,211\,\phantom{0}58\,236 \phantom{\,000\,000\,000\,000\,000\,000\,000\,000}\, \\ \underline{43\,\phantom{00}5\,130\,189\,129\,\phantom{0}56\,190\,\phantom{0}22} \phantom{\,000\,000\,000\,000\,000\,000\,000\,000}\, \\ 219\,210\,\phantom{0}51\,253\,235\,132\,250\,\phantom{0}17 \phantom{\,000\,000\,000\,000\,000\,000\,000}\, \\ \underline{219\,\phantom{0}58\,170\,153\,188\,230\,143\,\phantom{00}7} \phantom{\,000\,000\,000\,000\,000\,000\,000}\, \\ 232\,153\,100\,\phantom{0}87\,\phantom{0}98\,117\,\phantom{0}22\,\phantom{00}0\phantom{\,000\,000\,000\,000\,000\,000}\, \\ \underline{232\,\phantom{0}67\,\phantom{0}44\,213\,230\,\phantom{0}54\,\phantom{0}31\,157} \phantom{\,000\,000\,000\,000\,000\,000}\, \\ 218\,\phantom{0}72\,130\,132\,\phantom{0}67\,\phantom{00}9\,157\,\phantom{00}0\phantom{\,000\,000\,000\,000\,000}\, \\ \underline{218\,\phantom{0}69\,208\,\phantom{00}3\,\phantom{0}24\,237\,203\,114} \phantom{\,000\,000\,000\,000\,000}\, \\ 13\,\phantom{0}82\,135\,\phantom{0}91\,228\,\phantom{0}86\,114\,\phantom{00}0\phantom{\,000\,000\,000\,000}\, \\ \underline{13\,\phantom{0}65\,120\,108\,\phantom{0}71\,127\,\phantom{0}83\,\phantom{0}51} \phantom{\,000\,000\,000\,000}\, \\ 19\,255\,\phantom{0}55\,163\,\phantom{0}41\,\phantom{0}33\,\phantom{0}51\,\phantom{00}0\phantom{\,000\,000\,000}\, \\ \underline{19\,\phantom{0}34\,125\,230\,\phantom{0}99\,173\,248\,156} \phantom{\,000\,000\,000}\, \\ 221\,\phantom{0}74\,\phantom{0}69\,\phantom{0}74\,140\,203\,156\,\phantom{00}0\phantom{\,000\,000}\, \\ \underline{221\,\phantom{0}37\,171\,226\,\phantom{0}67\,220\,\phantom{0}10\,\phantom{0}36} \phantom{\,000\,000}\, \\ 111\,238\,168\,207\,\phantom{0}23\,150\,\phantom{0}36\,\phantom{00}0\phantom{\,000}\, \\ \underline{111\,\phantom{0}82\,156\,166\,\phantom{0}89\,238\,\phantom{0}99\,211} \phantom{\,000}\, \\ 188\,\phantom{0}52\,105\,\phantom{0}78\,120\,\phantom{0}71\,211\,\phantom{00}0 \, \\ \underline{188\,183\,193\,155\,172\,\phantom{0}80\,246\,\phantom{0}91} \, \\ 131\,168\,213\,212\,\phantom{0}23\,\phantom{0}37\,\phantom{0}91 \, \\ \end{align}

\(r(y)\)の係数を羅列したものが誤り訂正コード語であり、16進表記で表すと「83 A8 D5 D4 17 25 5B」となる。

例2

バージョン5・誤り訂正レベルHで、データが文字列「QRコード」の例を考える。

ブロックごとの誤り訂正コード語数は22なので、生成多項式は

\begin{align} g(y) &= (y-\alpha^0)(y-\alpha^1)(y-\alpha^2)\cdots (y-\alpha^{21}) \\ &= y^{22} + \alpha^{210}y^{21} + \alpha^{171}y^{20} + \alpha^{247}y^{19} + \alpha^{242}y^{18} + \alpha^{93}y^{17} + \alpha^{230}y^{16} + \alpha^{14}y^{15} + \alpha^{109}y^{14} + \alpha^{221}y^{13} + \alpha^{53}y^{12} + \alpha^{200}y^{11} + \alpha^{74}y^{10} + \alpha^{8}y^9 + \alpha^{172}y^8 + \alpha^{98}y^7 + \alpha^{80}y^6 + \alpha^{219}y^5 + \alpha^{134}y^4 + \alpha^{160}y^3 + \alpha^{105}y^2 + \alpha^{165}y + \alpha^{231} \\ &= y^{22} + 89y^{21} + 179y^{20} + 131y^{19} + 176y^{18} + 182y^{17} + 244y^{16} + 19y^{15} + 189y^{14} + 69y^{13} + 40y^{12} + 28y^{11} + 137y^{10} + 29y^9 + 123y^8 + 67y^7 + 253y^6 + 86y^5 + 218y^4 + 230y^3 + 26y^2 + 145y + 245 \\ \end{align}

となる。

前節の例からデータコード語は4つに分割され、それぞれ誤り訂正コード語は次の表のようになる。(計算過程は省略)

コード語の配置

これまでの手順で得られたデータコード語と誤り訂正コード語をQRコードに配置する。

データコード語と誤り訂正コード語に次のように番号を振る。(バージョン5・誤り訂正レベルHの例)

このとき、これらのデータコード語を「D1 D12 D23 D35 D2 D13 … D33 D45 D34 D46 E1 E23 … E66 E88」というように縦方向に取り出して並び替える。

こうして得られたコード語の列を、下図のように右下からジグザグに1ビットずつ配置していく。
また、最後に残余ビットが生じた場合は0で埋める。下図では「R」と書かれた左下の領域が残余ビットにあたる。

コード語の配置順 (バージョン5・誤り訂正レベルH)

コード語の配置順 (バージョン5・誤り訂正レベルH, ビット単位)

例

バージョン5・誤り訂正レベルHで、データが文字列「QRコード」の場合、並び替えたコード語は「40 38 11 11…」で、ビット列で表すと「01000000 00111000 00010001 00010001…」となる。上記の順序でジグザグに書き込むと下図のようになる。

マスク前のQRコード (バージョン5・誤り訂正レベルH)

マスク

QRコードの白セル・黒セルの個数のバランスを調整し、更にFinder Patternとの誤認識を防ぐため、符号語領域の白黒を特定パターンで反転させる操作を行う。この操作をマスク処理と言う。

マスクパターンは8種類定められている。左上を\((i,j)=(0,0)\)とした\(i\)行\(j\)列のセル座標に対して、次の条件を満たす座標のセルが反転される。(「/」は余りを切り捨てる割り算を意味し、「%」は剰余演算を意味する)

12x12のマスクパターン (黒が反転させる位置を表す)

8種類のマスクから最適なマスクを選定するため、次のように各マスクのペナルティを計算する。マスク前のQRコードに8種類のマスクをそれぞれ適用し、次の表の4項目に基づいて合計値を計算する。
8種類の内でペナルティが最小のQRコードが最終的なQRコードになる。(ペナルティ最小ではないQRコードも多くの機器では読み取ることは可能)

• 1に関して
  例えば7連続する黒セルが存在するときにその中に含まれる5連続・6連続の黒セルに対して重複してペナルティを課すことはしない。
• 4に関して
  [45%, 55%]のときに0点、[40%, 45%)∪(55%, 60%]のときに10点、…という風にペナルティを課す。

例

バージョン5・誤り訂正レベルHで、データが文字列「QRコード」の例を考える。

マスク前のQRコードの例
灰色の部分は未確定のFormat Information

マスクをそれぞれ適用した結果

それぞれのペナルティは次の表の通りなので、ペナルティの最も小さいマスク5が最終的な出力となる。

ペナルティが最小のQRコード (バージョン5・誤り訂正レベルH)

参考

• QRコードドットコム｜株式会社デンソーウェーブ
• 仕様書
  
  • JIS X 0510 : 2004 二次元コードシンボル－QR コード－ 基本仕様
  • JIS X 0510 : 2018 情報技術−自動認識及びデータ取得技術− QRコード バーコードシンボル体系仕様

解説

• QRコード Deep Dive ーデータ符号化とか誤り訂正とかー #OpenCV - Qiita
• ＱＲコードをつくってみる その１
• 【QRコードの仕組み】誰でもわかる、簡単QRコードの仕様書・作り方・生成・変換方法・仕組みホームページ(HowToMakeQRCode)
• QRコードを極める|独極|独りで基礎から絶対わかる！
• 分かると、実に、おもしろい！ QRコードの仕組み | コリス
• 真心のこもった手づくりQRコードの作り方（本編） - marich1224 のメモ
• JavaScriptで実装してみるQRコードジェネレータ #QRcode - Qiita
• QR code - Wikipedia

実装例

• Creating a QR Code step by step
• Encoding QR codes / Zavier Henry | Observable