QR コード

QR コードの形

QR コードは暗いモジュールと明るいモジュールの正方形の格子です。バージョン $v$（1〜40）の大きさは $17+4v$ モジュール角で、まわりに 4 モジュールの余白を空けます[1][2]。格子の一部は、読み取り機が位置と向きと大きさを知るための決まった模様（機能パターン）です。

残りがデータの領域で、文字列から作った符号語を置きます。

文字列をビット列にする

文字列は文字の種類に合ったモードで符号化します[2]。使える文字が少ないモードほど、1 文字に使うビットが少なくなります。

漢字モードは、Shift_JIS の符号から 0x8140（0xE040 以上は 0xC140）を引き、上位のバイトに 0xC0 を掛けて下位のバイトを足した値を 13 ビットで書きます[2]。モード指示子・文字数・データの後に、次の順でビット列を埋めます。

1. 終端0000（容量が足りなければ短く）
2. 端数8 の倍数になるまで 0
3. 埋め草11101100 と 00010001 を交互に

できたビット列を 8 ビットずつ区切ったものがデータの符号語です。

リード・ソロモン符号

誤り訂正語はリード・ソロモン符号で作ります[3][4]。符号語は 8 ビットなので、256 個の元からなる有限体 GF(2⁸) の上で計算します。足し算と引き算はビットごとの XOR で、掛け算は既約多項式 $x^8+x^4+x^3+x^2+1$（0x11D）を法とする多項式の積です。原始元 $\alpha =2$ の累乗 ${\alpha }^0,{\alpha }^1,\dots ,{\alpha }^{254}$ が、0 以外の 255 個の元を一度ずつ通ります。

データの符号語 $d_0,\dots ,d_{k-1}$ を多項式の係数とみると、誤り訂正語 $n$ 語は次の割り算の余りです。

データと誤り訂正語を並べた多項式 $C(x)=D(x)x^n-E(x)$ は $g(x)$ で割り切れるので、${\alpha }^0,\dots ,{\alpha }^{n-1}$ で 0 になります。$n$ 語の誤り訂正語で、どこが壊れたか分からない誤りを $n/2$ 語まで直せます。

バージョンとレベルが大きいと、データを複数のブロックに分け、ブロックごとに誤り訂正語を付けます。置くときは、各ブロックの 1 語目、2 語目…と交互に並べ、続けて誤り訂正語も交互に並べます[2]。1 か所の汚れが 1 つのブロックに集まりにくくなります。

配置とマスク

符号語のビットは、右下の角から 2 列ずつ、上・下に折り返しながら、機能パターンと形式情報の所を避けて置きます。縦のタイミングの列（6 列目）は飛ばします[2]。余ったモジュール（バージョンにより 0・3・4・7 個）は 0 です。

次に、データの領域を 8 種のどれかの模様（マスク）で反転します。$x$ は列、$y$ は行の番号で、条件が成り立つモジュールを反転します。

8 種それぞれで形式情報まで書いた格子のペナルティを求め、いちばん小さいものを使います[2][5]。

N1

行・列に同じ色が 5 つ以上続く: 5 つで 3、1 つ増えるごとに 1

N2

同じ色の 2 × 2 の塊: 1 つにつき 3

N3

ファインダーに似た 1:1:3:1:1 の並びで、片側に明るい 4 モジュールが続くもの: 1 つにつき 40

N4

暗いモジュールの割合が 50 % から 5 % ずれるごとに 10

形式情報とバージョン情報

形式情報は 15 ビットです。誤り訂正のレベル 2 ビット（L 01・M 00・Q 11・H 10）とマスクの番号 3 ビットの 5 ビットに、BCH(15, 5) 符号の検査 10 ビットを足し、101010000010010 と XOR します[2]。検査ビットは、5 ビットを 10 ビット左へずらして生成多項式 $x^{10}+x^8+x^5+x^4+x^2+x+1$ で割った余りです。正しい 32 通りの符号どうしは 7 ビット以上違う（このツールのテストで総当たりで確かめた）ので、3 ビットまでの誤りなら最も近い符号に決められます[4]。バージョン 7 以上は、バージョン 6 ビットに BCH(18, 6) の 12 ビットを足したバージョン情報も置きます。

読み取りと誤り訂正

読む側は、形式情報からレベルとマスクを知り、マスクを外し、置いた順に符号語を集めてブロックに戻します。受け取った多項式を $R(x)=C(x)+e(x)$ として、誤り $e(x)$ を次の順で求めます[4]。

1. シンドロームS_i = R(αⁱ)
2. 誤り位置多項式Berlekamp–Massey 法
3. 誤りの位置Chien 探索
4. 誤りの大きさForney の式

$\nu$

誤りの数。$\nu \le n/2$ なら直せる

$X_l={\alpha }^{j_l}$

誤りの位置（$x^{j_l}$ の係数が壊れた）。符号語の番号は、長さ − 1 − $j_l$

$Y_l$

誤りの大きさ。直した値は、読んだ値と $Y_l$ の XOR

$\Lambda (x)$

誤り位置多項式。根の逆数が誤りの位置。Berlekamp–Massey 法は、シンドロームの並びを生む最短の線形帰還シフトレジスタとして求める[6]

• Chien 探索は、$\Lambda ({\alpha }^{-j})$ をすべての位置 $j$ で計算して根を探す[7]
• Forney の式は、生成多項式の根が ${\alpha }^0$ から始まる QR コードの形では、$X_l$ を 1 つ掛けた形になる[8][4]
• 誤りが $n/2$ 語を超えると、$\Lambda$ の次数が上限を超えるか、根の数が次数と合わず、直せないと分かることが多い。まれに別の正しい符号語に近づき、誤った文字列に直してしまう

このツールで決めたこと

• 文字列全体を 1 つのモードで符号化する。モードを途中で切り替えてビット列を短くする最適化と、ECI（文字コードの指定）はしない
• バイトモードは UTF-8 にする。漢字モードの Shift_JIS は、ブラウザの TextDecoder で作った対応表を使う
• 自動のモードは、符号化できるモードのうちビット列がいちばん短いもの。自動のバージョンは、選んだレベルで入る最小のもの
• 「レベルを上げる」は、同じバージョンに入る範囲でいちばん高いレベルにする
• N3 の数え方は Nayuki の実装に合わせ、記号の外の余白も明るいモジュールとして数える[5]
• 読み取りは、モジュールの格子から始める。画像からファインダーを探して格子を読む処理と、消失（位置の分かる誤り）を使う訂正はしない。形式情報は 2 か所のうち近い方で決める
• 誤り訂正実験の道具の大きさ（しみは半径 1.35、こすれは半径 0.75 モジュール）と、ランダムで入れ替える数（8 個）
• 図と表の区分の色

出典

1. QR コードの規格（有料のため、このツールでは直接は参照していない）ISO/IEC 18004:2024, Information technology — Automatic identification and data capture techniques — QR code bar code symbology specification
2. モードと文字数の欄、容量と誤り訂正の表、ブロックの並べ方、配置、マスクとペナルティ、形式情報とバージョン情報Thonky.com, QR Code Tutorial
3. リード・ソロモン符号I. S. Reed and G. Solomon, “Polynomial Codes Over Certain Finite Fields,” Journal of the Society for Industrial and Applied Mathematics, vol. 8, no. 2, pp. 300–304, 1960, doi:10.1137/0108018
4. GF(2⁸) の計算、QR コードの形のリード・ソロモン符号の符号化と復号（シンドローム・Berlekamp–Massey 法・誤りの位置の探し方・Forney の式）Wikiversity, Reed–Solomon codes for coders（CC BY-SA 4.0）
5. 符号化の照合（このツールの出力と、バージョン 1〜40 の模様が一致することをテストで確かめた）とペナルティの数え方Project Nayuki, QR Code generator library（MIT License）
6. Berlekamp–Massey 法J. L. Massey, “Shift-Register Synthesis and BCH Decoding,” IEEE Transactions on Information Theory, vol. 15, no. 1, pp. 122–127, 1969, doi:10.1109/TIT.1969.1054260
7. Chien 探索R. T. Chien, “Cyclic Decoding Procedures for Bose-Chaudhuri-Hocquenghem Codes,” IEEE Transactions on Information Theory, vol. 10, no. 4, pp. 357–363, 1964, doi:10.1109/TIT.1964.1053699
8. Forney の式G. D. Forney, Jr., “On Decoding BCH Codes,” IEEE Transactions on Information Theory, vol. 11, no. 4, pp. 549–557, 1965, doi:10.1109/TIT.1965.1053825