QR コードは、なぜ欠けても読めるのか

上の QR コードには https://ugokuzukai.com/ が入っています。マスを指かマウスでなぞると、そのマスが白（または黒）になります。

試すと、いくつかのことに気づきます。

• 少し欠けたくらいでは、読めます。欠けた分は、QR コードが自分で直しています
• 黒いマスを黒で塗っても、何も起きません。読み取りで誤りになるのは、白黒が変わったマスだけです
• 同じ数のマスを欠いても、欠ける場所によって結果が違います。左上・右上・左下の大きな四角を欠くと、すぐに読めなくなります

この「自分で直す」しくみを、誤り訂正といいます。QR コードを作ったデンソーウェーブは、汚れたり破損したりしても、コード自身でデータを復元できると説明しています。誤り訂正には、リード・ソロモン符号という方法を使っています。

予備の数字を足すと、間違いが直せる

リード・ソロモン符号の考え方を、短い数字の列で試します。

5つの数字 3・1・4・1・5 を送るとします。数字だけを送ると、途中で1つが書き換わっても、受け取った側は気づけません。そこで、予備の数字を足して送ります。

• 予備 A：5つの数字の合計
• 予備 B：それぞれの数字に「何番目か」を掛けてから足した合計

数字を1つ書き換えると、予備とのずれが出ます。

予備が A だけのときは、「どこかが違う」ことしか分かりません。合計は、どの場所の数字が変わっても同じようにずれるからです。

予備を B まで足すと、直せます。1か所が e だけ違うとき、A のずれは e になります。B のずれは「何番目か × e」になります。そこで B のずれを A のずれで割ると、何番目かが出ます。A のずれから、どれだけ違うかも分かります。

「どこが」と「どれだけ」の2つを求めるので、1か所を直すのに、予備が2つ要ります。2か所が違うと、この予備では直せません。図の「2か所を書き換える」の例のように、1か所の間違いと取り違えて、別の数字に直してしまうこともあります。

QR コードのリード・ソロモン符号は、この考えを広げたものです。予備に当たるのが「誤り訂正の符号語」で、その数を増やすほど、直せる場所が増えます。デンソーウェーブの説明でも、1つの符号語を直すには、誤り訂正の符号語が2つ要ります。ただし計算は、ふつうの足し算とかけ算ではありません。リード・ソロモン符号は、有限体と呼ばれる別の数の体系の上で計算します（Reed と Solomon が 1960 年に書いた論文も、題名は「ある有限体の上の多項式符号」です）。

QR コードは、文字をどう「マス」にしているか

QR コードの白黒の四角1つを、この記事では「マス」と呼びます。規格（JIS X 0510）では「モジュール」、デンソーウェーブの説明では「セル」と呼んでいます。

マスの並べ方は、規格で決まっています。図1の QR コードは、次の順で作りました。

1. 文字をバイト（8ビット）の列にする。頭に「どんな種類のデータか」と「何文字か」を付ける
2. 8ビットずつに区切る。この8ビットのまとまりを「符号語」と呼ぶ。決まった数に届くまで、埋め草の符号語を足す。ここまでが「データの符号語」
3. データの符号語をいくつかの「ブロック」に分け、ブロックごとに「誤り訂正の符号語」を計算して付ける
4. 各ブロックから1つずつ順に取り出して、1列に並べ直す
5. 右下の角から、2列ずつ上へ、下へと折り返しながら、符号語のビットをマスに置いていく
6. 「マスク」という決まった模様で、白黒を入れ替える。規格には8種類のマスクがある。位置検出パターンに似た並びや、同じ色の大きな固まりが少なくなるものを選ぶ
7. 誤り訂正レベルと、どのマスクを使ったかを「形式情報」として、決まった場所に置く

図1の下の帯は、手順4で並べ直す前の、ブロックごとの符号語です。塗りつぶした四角がデータの符号語、点線の四角が誤り訂正の符号語です。マスの白黒を変えると、そのマスが入っている符号語に印が付きます。

図1でレベル Q か H を選ぶと、ブロックが2つになります。右下の 7×7 マスを白にすると、誤りの符号語が2つのブロックに分かれて入るのが見えます。手順4で、各ブロックの符号語を交互に並べたからです。

どれだけ欠けても読めるか：L・M・Q・H

誤り訂正レベルは4つあります。デンソーウェーブの説明では、全部の符号語のうち、L は約 7%、M は約 15%、Q は約 25%、H は約 30% を復元できます。

レベルを上げると、誤り訂正の符号語が増えます。同じ文字を入れるには、その分だけ大きな型番が要ります。型番は 1 から 40 まであり、型番1が 21×21 マスで、1つ上がるごとに縦横4マスずつ増えます。図3で L から H に切り替えると、マスが細かくなるのはこのためです。

直せる符号語の数は、規格の表に、型番とレベルの組ごとに書いてあります。図3の数は、その表から出しています。帯の下の黒い線の長さが、直せる数です。データの符号語と誤り訂正の符号語のどちらに誤りがあっても直せます。直せるのは、両方を合わせてこの数までです。

表の数を見ると、誤り訂正の符号語の半分より、少し少ない数しか直さない組があります。たとえば型番1のレベル L は、誤り訂正の符号語が7つあるのに、直すのは2つまでです。残りの符号語は、誤りを直すためではなく、読み違い（誤りが多すぎるときに、別の文字に直してしまうこと）を防ぐために使います。図2の「2か所を書き換える」の例で起きたことを、起きにくくする分です。

約 7%・15%・25%・30% は、符号語で数えた割合です。マスで数えた割合とは違います。1つの符号語は8マスにまたがります。8マス全部が変わっても、1マスだけが変わっても、誤りは符号語1つです。図1の例で、右下の 25 マスの白黒が変わっても、誤りの符号語は5つで済んでいるのはこのためです。

欠ける場所で、結果が変わる

図1をもう一度使います。今度は、欠ける場所を変えて試してください。

読み取りは、順に進みます。前の段で止まると、その先の誤り訂正までたどり着きません。

1. 位置検出パターンを探す。 3つの角にある大きな四角は、ここに QR コードがあるという目印です。白黒の幅が 1:1:3:1:1 になっています。デンソーウェーブによると、この比は、チラシや雑誌などの印刷物を調べて、一番使われていない比を選んだものです。走査線がどの方向から通っても、この比を探せば位置が割り出せます。

図1で、四角の中心の 3×3 マスを白にすると、どの線で見ても 1:1:3:1:1 が崩れます。たった9マスでも、QR コードの場所が分からず、読み取りはここで止まります。四角の外側の角を少し欠いただけなら、中心を通る線の比は崩れないので、読めます。

2. 形式情報を読む。 誤り訂正レベルとマスクの種類が入っています。これが分からないと、マスクを外せず、符号語も取り出せません。形式情報は、同じものが2か所に置いてあります。それぞれにも誤り訂正の符号が付いていて、少しの欠けなら直せます。図1で片方を全部欠いても、もう片方が読めれば先へ進みます。

3. 符号語を取り出して、ブロックごとに直す。 ここで、リード・ソロモン符号が働きます。誤りの符号語が、ブロックごとの上限までなら直せます。1つのブロックでも上限を超えると、読めません。

データの部分は、全体に広く散らばっています。誤り訂正で直せるのは、この部分です。位置検出パターンと形式情報は、データを読む前の段で使うので、データの誤り訂正では直せません。欠けてもよい量が、場所によって違うのはこのためです。

この記事は、うごく図解の AI の編集部が書き、別の AI が出典と照らして確かめました。どう作っているか