アルゴリズムの仕組み

QRコードの誤り訂正の仕組み:Reed-Solomonの数学をわかりやすく解説

QRコードが破れたり、コーヒーのしみが付いたり、一部がかすれたり、中央を企業のロゴで覆われたりしても、問題なく読み取れるのはなぜでしょうか。その秘密は、Reed-Solomonの多項式による誤り訂正にあります。

同じアドレスを誤り訂正レベルL、M、Q、Hで符号化した4つのQRコード。各レベルがどれだけの損傷を復元できるかを示すため、面積の7、15、25、30パーセントを黒く塗りつぶしている

1. Reed-Solomon誤り訂正とは

1960年に数学者のIrving S. ReedとGustave Solomonが考案したReed-Solomon(RS)誤り訂正は、非二元の巡回誤り訂正アルゴリズムです。宇宙通信(NASAのボイジャー)、CD/DVDなどの光ディスク、衛星放送、そしてQRコードの規格であるISO/IEC 18004で広く使われています。

Reed-Solomon符号は、単純なパリティビットやCRCチェックサムのように誤りを検出するだけではありません。冗長な数学的パリティブロックを生成し、再送を求めることなく損傷したバイトの正確な位置を突き止め、元のデータを復元できます。

2. QRコードの4つの誤り訂正レベル

ISO/IEC 18004規格では、選択可能な4つの誤り訂正(ECC)レベルが定められています。各レベルは、コードが読み取れなくなるまでに、全コード語のうち何パーセントが消えたり隠れたりしても耐えられるかを表しています。

ECCレベル 復元能力 モジュール密度 おすすめの用途
レベルL(低) データの約7% 最も低密度(マスが最も少ない) デジタル画面や、QRコードを小さく保つ必要がある高密度のデータ。
レベルM(中) データの約15% バランスの取れた標準 一般的なURL、パッケージ、チラシ、販促用印刷物の既定値。
レベルQ(クオータイル) データの約25% やや高密度 オリジナルロゴに最適。卓上POPや、摩耗しやすい環境にも。
レベルH(高) データの約30% 最も高密度(マスが最も多い) 屋外看板、産業用タグ、物理的な負荷が大きい環境。

3. ロゴの埋め込みが誤り訂正を活用する仕組み

QRコードの中央にロゴやアイコンを置くと、スキャナーの光学センサーはそのロゴを、表面の物理的な損傷や欠けたモジュールとして解釈します。

誤り訂正レベルQは損傷したデータの最大25%、レベルHは最大30%を復元できるため、Reed-Solomonの数学的なデコーダーがロゴの下に隠れたモジュールを計算し、元のURLを数ミリ秒で復元します。

ロゴ入りQRコードの鉄則:

  • 最大面積:ロゴがQRコード全体の面積の20〜25%を超えないようにしてください。
  • 3つの位置検出パターンを守る:左上、右上、左下の角にある3つの大きな四角い目(位置検出パターン)に、ロゴが重なったり触れたりしないようにしてください。
  • 白い余白を使う:周囲のQRモジュールがロゴの図柄と混ざらないよう、ロゴのまわりには必ず白一色の保護余白を設けてください。
  • レベルQまたはHに自動で切り替え:qr-code.loveでは、オリジナルのロゴをアップロードすると、誤り訂正レベルが自動的にレベルQまたはHに引き上げられます。

4. ガロア体GF(256)における計算の流れ

ブラウザ内で動作するエンコーダーは、256個の元をもつ有限体、GF(28)またはGF(256)と書かれる体の上で計算を行います。各バイトはこの体の元であり、乗算は次の原始多項式を法として定義されます。

P(x) = x8 + x4 + x3 + x2 + 1   (16進数で0x11D)

データのバイト列は多項式D(x)の係数として扱われます。エンジンはこれにxE(Eはそのレベルで必要な誤り訂正コード語の数)を掛け、その結果をレベルごとに決まった生成多項式G(x)で割ります。この割り算の余りがパリティで、E個のバイトとしてデータの後ろに配置されます。

5. ISOの8つのマスクパターンと失点評価

誤り訂正コード語を計算したあと、生のバイナリデータをそのままグリッドに配置すると、黒一色や白一色のモジュールの大きな塊ができたり、カメラの光学センサーを惑わす偽の「位置検出パターン」の形が偶然生じたりするおそれがあります。

これを解決するため、ISO/IEC 18004規格ではグリッド全体に8種類の候補となる数学的なXORマスクパターンを適用します。エンジンは、マスクをかけた各候補を厳密な失点計算式で評価します。

  • 失点1(隣接モジュールの連続):同じ色のモジュールが5個以上連続すると3点、さらに5個を超える1個ごとに1点が加算されます。
  • 失点2(2×2モジュールのブロック):同じ色の2×2の正方形が1つあるごとに3点が加算されます。
  • 失点3(偽の位置検出パターン):1:1:3:1:1に一致するモジュールの並びがあるごとに40点が加算されます。
  • 失点4(明暗比の偏り):50/50のバランスからずれると、その度合いに応じた失点が加算されます。

累計の失点が最も低いマスクパターンが選ばれ、位置検出パターンの周囲にある形式情報のビットにエンコードされます。

6. 実際の使用環境での耐久性

風雨や摩耗にさらされる印刷物では、適切な誤り訂正レベルを選ぶことが非常に重要です。

使用環境 推奨ECC 主な損傷リスク
屋外看板と金属製サイン レベルH(30%) 紫外線による退色、雨だれ、さび、鳥のふん。
レストランの卓上POPとメニュー レベルQ(25%) 食べこぼし、指の汚れ、アルコール消毒液。
商品パッケージとラベル レベルM(15%) 表面の軽い摩擦や取り扱いによるこすれ。
デジタル画面とテレビ放送 レベルL(7%) 物理的な摩耗はゼロ。ピクセル数を最小にすることを優先。

7. バージョンごとのデータと誤り訂正のコード語

各バージョンには、それぞれ8ビットのコード語が決まった数だけあり、そのうちいくつがデータを運び、いくつが復元用のデータを運ぶかをレベルが決めます。最初の3つのバージョンは次のとおりです。

バージョン合計L(データ + 誤り訂正)MQH
12619 + 716 + 1013 + 139 + 17
24434 + 1028 + 1622 + 2216 + 28
37055 + 1544 + 2634 + 3626 + 44

データのコード語がすべて中身のデータになるわけではありません。最初のビットにはモード指示子と文字数が入り、バイトモードではバージョン9までは12ビット、バージョン10以降は20ビットを使います。そのため、レベルLのバージョン1のシンボルに入るデータは19バイトではなく17バイトになります。

レベルHでは、バージョン1から復元用のデータが中身のデータを上回ります。ロゴのオプションがレベルを引き上げるときに行っているのは、この引き換えです。入れられるバイト数は減りますが、その代わりに一部が塗りつぶされても読み取れるシンボルになります。

出典と参考資料

誤り訂正付きのQRコードを作成

お好みのReed-Solomonレベル(L、M、Q、H)を選び、サーバーに一切記録を残さずにブランドロゴを埋め込めます。

オールインワン作成ツールを開く