t = ⌊ \frac{n - k}{2} ⌋

計算の裏側

汚れたQRコードが読めるのはなぜか、誤り訂正の30%が指すもの

Why a dirty QR code can still be read

同じ144セルの汚れでも、固めると読め、散らすと読めない。

汚れても読めるのは、データに検査の語を足してあるから。ハミング符号の3つの検査からリード・ソロモン符号の投票へ進み、塗りつぶす実験で「30%」が面積でなく語の数だと確かめる。

種類: 計算の裏側
公式: 2 本
人物: リチャード・ハミング、I・S・リード、G・ソロモン、クロード・シャノン、原昌宏
作成日: 2026-10-31
更新日: 2026-10-31
執筆・監修: 佐々木航

二項定理とパスカルの三角形シャノンの情報エントロピー

場面

真ん中を塗っても読める

QRコードの真ん中を黒く塗りつぶしても、まだ読める。白黒の小さな四角、セルが縦横に37個並ぶQRコードを、誤り訂正のレベルHで作る。中央の15×15セルを塗ると、面積の16.4%が消える。それでも、筆者がこの図を読み取りプログラムのjsQRに渡すと、60回とも元の文字列が返ってきた。

ところが、隅にある7×7セルの四角を1つ塗ると、100回のうち1回も読めない。面積はわずか3.6%である。

汚れても読めるのは、データのほかに検査のための数が書き込まれていて、壊れた部分を計算で元に戻せるからだ。直せる量は、検査の数の半分まで。隅の四角はこの計算の外にあり、欠けるとjsQRは計算を始める前に止まる。

デンソーウェーブは、いちばん強いレベルHについて「コードワードの約30%が復元可能」と案内している。では、この30%は何の30%なのだろうか。塗って数え直すと、面積とは別のものだと分かる。

考え方

偶数か奇数かで番号を読む

QRコードの誤り訂正はリード・ソロモン符号で、ハミング符号は使っていない。それでも入口には、ハミング符号がいちばん向いている。検査の結果が壊れた場所を指す考え方が、むき出しで見えるからだ。

0と1の列に1ビット足して1の個数を偶数にそろえておくと、1ビット壊れたときに個数が奇数になる。このパリティ検査では、壊れたことは分かっても、場所までは分からない。

そこで、範囲の違う検査を3つ重ねる。7個のビットに1から7の番号を付け、4の位が1の番号（4, 5, 6, 7番）を検査 $α$ 、2の位が1の番号（2, 3, 6, 7番）を検査 $β$ 、1の位が1の番号（1, 3, 5, 7番）を検査 $γ$ とする。どのビットが壊れても、奇数になった検査を1、偶数を0と書いて3つ並べると、壊れた番号の2進数がそのまま読める。

1, 2, 4番を検査に使えば、残る3, 5, 6, 7番にデータを入れられる。

式

1011を送って5番を壊す

データ1011を手で符号にして、1ビット壊してみる。

データを3, 5, 6, 7番に置く。
$X_{3} = 1, X_{5} = 0, X_{6} = 1, X_{7} = 1$
3つの検査の和が偶数になるように、4, 2, 1番を決める。
$X_{4} = 0, X_{2} = 1, X_{1} = 0$
1番から順に並べて送る。
$X_{1} X_{2} \dots X_{7} = 0110011$
5番が反転し、0110111が届く。3つの和を計算する。
$α : X_{4} + X_{5} + X_{6} + X_{7} = 3, β : X_{2} + X_{3} + X_{6} + X_{7} = 4, γ : X_{1} + X_{3} + X_{5} + X_{7} = 3$
奇数を1、偶数を0に直して並べると、5番を指す。5番を反転すれば0110011に戻る。
$α β γ = 10 1_{(2)} = 5$
壊れたのが3番と5番の2か所なら、無事な6番を指す。
$α β γ = 11 0_{(2)} = 6$

シミュレーション

3つの円をたたく

円の中の区画が、7個のビットにあたる。たたくとビットが反転し、1の個数が奇数になった円に斜線が入る。斜線の円がすべて重なり、ほかの円の外にある区画が、指された番号である。「自動で直す」を切って3番と5番をたたき、「指された番号を直す」を押すと、違うビットは3か所に増え、検査はもう気づかない。直せるのは1ビットまでである。

考え方

放物線は3点で決まる

何個も直すには、どうすればよいのか。1960年6月、I・S・リードとG・ソロモンは5ページの論文で、多項式を使う答えを示した。

データ $k$ 個を係数にして $k - 1$ 次の多項式 $P (x)$ を作り、 $x$ を $n$ 通りに変えた値を書き込む。 $k = 3$ なら放物線だ。放物線は3点で決まるので、8点書けば5点が余分になる。

8点のうち2点が壊れた放物線。実線の正しい放物線は無事な6点を通り、破線の別の放物線は壊れた2点と無事な2点を通る。

論文の復号は、文字どおり投票である。8点から3点を選ぶ組は $(3 8) = 56$ 通りあり、組ごとに放物線が1本決まる。2点壊れても、無事な6点だけでできる $(3 6) = 20$ 組は正しい放物線に票を入れる。間違った放物線は壊れた2点と無事な2点を通るのがせいぜいで、 $(3 4) = 4$ 票しか集まらない。ここで数えているのは、二項定理の係数そのものだ。3点壊れると10対10で並び、どちらが正しいか決められない。

図は実数で描いたが、論文は有限体の上で計算する。足し算も掛け算も決まった個数の値の中で閉じるので、丸めの誤差が出ない。

式

直せる数は余分な点の半分

投票の理屈を、一般の $n$ と $k$ で書き直す。

違う2つの多項式の差は $k - 1$ 次以下で、0ではない。根は $k - 1$ 個までなので、値が一致する点も $k - 1$ か所までである。
$P (x) - Q (x) = 0 の根は k - 1 個まで$
したがって、違うデータから作った2つの列は、 $n$ か所のうち少なくとも次の数だけ違う。
$d = n - k + 1$
$e$ か所壊れた列は、元の列から $e$ か所、ほかの列から少なくとも $d - e$ か所離れている。元の列がいちばん近いのは、 $e < d - e$ のときである。
$e \leq ⌊ \frac{d - 1}{2} ⌋ = ⌊ \frac{n - k}{2} ⌋$
壊れた場所が分かっている消失なら、その点を捨てても $k$ 点残れば多項式が決まる。
$f \leq n - k$
場所の分からない誤り $e$ か所と消失 $f$ か所がまざると、条件は次の形になる。
$f + 2 e \leq n - k$

つまり、場所を探す手間の分だけ、誤りは消失の2倍の余分を使う。

シミュレーション

31で割った余りの模型

これは本物のQRコードではなく、31で割った余りの世界に単純にした模型である。データ9個を係数にした多項式の値を、 $x = 1$ から $n$ まで並べた。レベルを切り替えると $n$ は11, 13, 19, 26に変わり、上限は1, 2, 5, 8個になる。レベルHの $n = 26$ 、 $k = 9$ だけは、いちばん小さい21×21セルのQRコード、バージョン1のレベルHと同じ数にした。

点の列をたたいて壊すと、上限までは必ず戻り、1つ超えると戻らない。「壊れた場所が分かる」を入れると、上限は $n - k$ まで伸びる。「いちばん悪く壊す」は、 $P (x)$ と8か所で同じ値をとる別の多項式に合わせて壊す設定で、上限を1つ超えると別のデータに化ける。検査が17個と奇数のレベルHだけは、9個で直せないと分かり、10個で化ける。

考え方

本物は割り算の余りを足す

本物のQRコードは8ビットを1つの単位にする。デンソーウェーブのいうコードワード、日本の規格のいうコード語で、ここからは語と呼ぶ。計算は $x^{8} + x^{4} + x^{3} + x^{2} + 1$ で作る256個の要素の有限体 $GF (256)$ の上で進む。

形も1960年の論文とは違う。データの語を係数にした多項式 $d (x)$ を生成多項式 $g (x)$ で割り、余りを検査の語として後ろに足す。

g (x) = i = 0 \prod n - k - 1 (x - 2^{i}), c (x) = d (x) x^{n - k} + (d (x) x^{n - k} mod g (x))

$2^{i}$ は $GF (256)$ の掛け算で求める。この形は、ISO/IEC 18004:2015と一致する日本の規格、JIS X 0510:2018に定められている。 $c (x)$ は $g (x)$ で割り切れるから、 $x = 2^{i}$ を代入すると0になる。バージョン1のレベルHの実物でも17個の値はすべて0で、1語変えると17個とも0でなくなった。この17個が、ハミング符号の $α β γ$ にあたる。

違う答えどうしが $n - k + 1$ 語以上離れている点は同じなので、上限の式はそのまま使える。ただ、規格の表はもう少し慎重だ。バージョン1のレベルLは検査の語が7個あるのに、直せる数を2語としている。読み違いを減らすため、3個を誤りの検出に取っておくからである。

では、実際の読み取りプログラムはどこまで直すのか。バージョン1の語をでたらめな値に変え、jsQRに読ませてみた。

レベル	規格の訂正能力	jsQRの上限	案内
L	2語（7.7%）	3語（11.5%）	約7%
M	4語（15.4%）	5語（19.2%）	約15%
Q	6語（23.1%）	6語（23.1%）	約25%
H	8語（30.8%）	8語（30.8%）	約30%

割合は全26語のうちの値で、案内の数字はjsQRの結果より規格の表に近い。検査の語はLから順に7, 10, 13, 17個で、jsQRの上限はその半分の切り捨てである。LとMでは規格より1語多く直す。上限までは200回とも読め、1語超えると200回とも読めず、別の文字列が返ったことは1度もない。

大きいバージョンでは語をブロックに分け、ブロックごとに直す。語はブロックを順に回って並ぶので、固まった汚れは各ブロックに分かれて落ちる。冒頭の37×37セルはバージョン5で、レベルHなら134語が4ブロックに分かれ、全部で44語まで直せる。全40バージョンを規格の表で計算すると、案内の数字を下回るのはバージョン1のレベルQだけである。

ただし、1つのブロックでも上限を超えると全体が読めない。バージョン5のレベルHで40語、つまり29.9%をでたらめに壊すと、読めたのは150回のうち27回だった。30%欠けても必ず読める、という話ではないのだ。

図

30%は面積ではない

バージョン1の21×21セル。番号の付いた四角が26個の語で、1語は8セル。隅の四角などの決まった模様と、点の網の形式情報は語に含まれない。斜線の8×8セルはちょうど8語にあたる。

デンソーウェーブの説明にある復元率は、「全コードワード」に占める割合である。ところが、語の外にもセルがある。バージョン1の441セルのうち語は208セルで、47%しかない。8語は64セルなので、語の数では30.8%でも、面積では14.5%にすぎない。

斜線の8×8セルはちょうど8語に収まり、黒でも白でも200回とも読めた。同じ大きさの四角を横に1セルずらすと10語に触れて200回のうち3〜4回、斜めにずらすと15語に触れて0回になる。汚れが語の境目に合わせて付くことはまずないので、ふつうはずらした側の結果に近くなるだろう。

バージョン5でも、中央の四角を大きくしながら数えた。

レベル	案内	いつも読めた四角	面積	触れた語
L	約7%	7×7	3.6%	12語（9.0%）
M	約15%	11×11	8.8%	21語（15.7%）
Q	約25%	13×13	12.3%	31語（23.1%）
H	約30%	15×15	16.4%	40語（29.9%）

語の割合に直すと案内の数字に近く、面積で数えるとその半分前後にとどまる。四角の縁が語の境目を横切るので、15×15の225セルは28語分の広さなのに、40語に触れるからだ。もっとも、面積の数字はバージョンで変わる。バージョン10のレベルHでは、中央の27×27セル、面積の22.4%（語では28.6%）まで読めた。冒頭の16.4%は、バージョン5の真ん中の四角に限った数字である。

語の外にある隅の四角は、中央3×3を白く抜くだけで100回とも読めない。

式

固めると読め、散らすと読めない

同じ144セルをバージョン5のレベルHに黒く塗ってみる。中央に固めると150回とも読め、語の領域へ1セルずつ散らすと1回も読めない。散らしたセルが、それぞれ別の語を壊すからだ。散らした場合は、二項分布で予測できる。

語の領域1,079セルのうち $m$ セルを黒く塗る。もとから黒いセルは半分ほどなので、1ビットが反転する確率は次の値になる。
$b = \frac{m}{2 \times 1079}$
1語は8ビットで、1ビットでも反転すれば壊れる。
$q = 1 - (1 - b)^{8}$
$n$ 語のブロックで $i$ 語壊れる確率は、 ${q + (1 - q)}^{n}$ を二項定理で展開した1つの項である。
$Pr (X = i) = (i n) q^{i} (1 - q)^{n - i}$
$t$ 語まで壊れてもよいので、ブロックが直る確率は和になる。
$Pr (X \leq t) = i = 0 \sum t (i n) q^{i} (1 - q)^{n - i}$
バージョン5のレベルHは33語と34語のブロックが2つずつで、 $t = 11$ である。
$Pr (読める) = Pr (X_{33} \leq 11)^{2} Pr (X_{34} \leq 11)^{2}$

塗ったセル	面積	$q$	予測	読めた回数
49	3.6%	16.8%	97.5%	150
81	5.9%	26.4%	52.6%	81
100	7.3%	31.6%	16.8%	21
144	10.5%	42.4%	0.1%	0

予測は読める確率で、回数は散らして150回試した結果である。固めた場合は、どの行も150回読めた。1語の中で何ビット壊れても1語と数えるので、この符号は固まった汚れに強く、散った汚れに弱い。リードとソロモンも論文で、誤りが固まって「バースト」で起きるときは、ほかの効率のよい符号より望ましいかもしれないと述べた。

考え方

シャノンの限界まで4倍

この強さは、理論の限界からどれほど離れているのか。シャノンは1948年の論文で、雑音のある通信路にも越えられない上限、通信路容量 $C$ があることを示した。0と1が確率 $p$ で入れ替わる通信路なら、上限は次の形になる。

C = 1 - H (p), H (p) = - p lo g_{2} p - (1 - p) lo g_{2} (1 - p)

バージョン5のレベルHは134語のうちデータが46語で、符号化率は $46/134 = 0.343$ である。 $1 - H (p) = 0.343$ を解くと $p = 17.0%$ になる。ビットがばらばらに反転するだけなら、反転の確率が17.0%より小さい限り、この符号化率のまま誤りをいくらでも小さくできる符号が存在する。一方、先の式で読める確率が半分に落ちるのは、反転の確率 $b$ が3.8%のときだ。4倍以上の開きがある。

理由は2つ考えられる。1つ目に、定理はブロックを長くしていった先の話である。直せる語の割合を8/26に保って $q = 20%$ で計算すると、読めなくなる確率は26語で5.9%、255語で0.002%まで下がるが、QRコードの1ブロックは長くても153語である。2つ目に、語の単位で数える符号は、ばらばらの反転に最初から損をしている。QRコードが相手にするのは紙に付いた1つのしみで、シャノンの通信路とは雑音の形が違う。

歴史

止まった計算機と5ページの論文

7ビットのハミング符号は、ハミング自身の論文より先に、シャノンの1948年の論文に載っている。第17節で、7個のブロックに誤りが1個まで入る通信路の上限 $C = 4/7$ をちょうど達成する例として挙げた符号だ。検査 $α$ 、 $β$ 、 $γ$ はこの節の記号で、「R・ハミングの方法で見つけた」と添えてある。

ハミングは1950年4月の『ベル・システム技術雑誌』で、動機を語っている。ベル研究所がアバディーン性能試験場のために作ったリレー計算機2台では、初期には8,900個のリレーに1日2〜3回の故障が起きていた。夜間と週末は無人で動かしていたので、誤りが見つかると計算が止まってしまうことが多い。海軍大学院に残る講義の資料には、「誤りがあるかどうかを見つけられるなら、どこにあるかも見つけられないのか」という着想が記されている。

リードとソロモンの投票は、語が増えると手に負えない。バージョン1のレベルHなら、組の数は $(9 26) = 3, 124, 550$ になる。規格の復号手順は語に $2^{i}$ を代入した値から誤りの場所を求め、ZXingとjsQRのソースコードではユークリッドの互除法を使っている。

QRコードは1994年にデンソーウェーブ（当時はデンソーの一事業部）が発表した。開発にあたったのは原昌宏ら2人で、いちばんの課題は読み取りの速さだった。隅の四角は「切り出しシンボル」といい、白黒の幅の比が1:1:3:1:1になっている。チラシや雑誌の模様を調べ上げ、印刷物で最も使われていない比を選んだ。「帳票などで一番出現率が少ない図形だったからですよ」と原は語っている。

使いどころ

ロゴを置く前に数える

ロゴ入りのQRコードが読めるのは、誤り訂正の余裕を使っているからで、その分だけ汚れに弱くなる。バージョン5のレベルHに11×11セルの白いロゴを置き、さらに語を24個でたらめに壊すと、150回のうち、ロゴなしで146回読めたものが37回に落ちた。規格の式には消失の訂正もあるが、ZXingとjsQRの復号の関数が受け取るのは語の列と検査の語の数だけで、ロゴの場所を渡す口がない。デンソーウェーブもFAQで、イラストを重ねると「ちょっとした汚れや欠けでも読み取りが出来なくなったり」するとして推奨していない。

レベルは環境で選ぶ。デンソーウェーブによれば、一般にはMが多く、工場のように汚れやすい場所ではQかHを選ぶ。強くした分は、入るデータの量で払う。同じバージョン5でも、データの語はLなら108語、Hなら46語で、半分以下だ。周囲には4セル以上の余白も要る。

自分で確かめるなら、次の順がよい。

手元のQRコードを印刷し、中央に付箋の切れ端をのせてスマートフォンで読む。
同じ切れ端を隅の四角に移して読み比べる。
表計算に=1-BINOM.DIST(8,26,0.2,TRUE)と入れ、語が20%の確率で壊れるときに26語のレベルHが読めなくなる確率5.9%を出す。8と0.2を変えると、ほかのレベルと汚れ方を比べられる。

JPEGはどうやって写真を小さくしているのかは、余分を捨てて小さくする話だった。QRコードは逆に余分をわざと足し、真ん中を塗られても読める。ただ、その余分には上限があり、隅の四角までは守ってくれない。

ノート

試した条件

QRコードはNodeのqrcodeで作り、1セル6ピクセルの白黒画像にして、jsQRと@zxing/libraryに直接渡した。文字列は乱数で、マスクは8種類からでたらめに選んだ。本文の回数はjsQRの結果で、中央の四角の表は黒と白で60回ずつ試した。ZXingのJavaScript版は汚れのない図でも1〜6%読めないことがあったが、読めなくなる境目はjsQRとほぼ同じだった。カメラは通しておらず、スマートフォンのアプリも試していないので、撮影の条件によって結果は変わるだろう。ほかの読み取りプログラムが同じ上限で止まるとも限らない。語は256通りあるので、でたらめな列が別の答えの近くに落ちる割合は、レベルLでも100万回に1回を下回る計算である。規格の値はJIS X 0510:2018の表9で読み、語数は全40バージョンでZXingとNayukiの実装に一致した。ISO/IEC 18004の英語の原本は開いていない。

参考文献

デンソーウェーブ「誤り訂正機能について」、「QRコード規格化・標準化」、「FAQ」、「コード領域を確定するためのポイント」、「道のり」
JIS X 0510:2018「情報技術－自動認識及びデータ取得技術－QRコードバーコードシンボル体系仕様」（ISO/IEC 18004:2015と一致。7.5節、表8、表9、附属書A、附属書B。本文は公式の配布元ではない写しで確認）
I. S. Reed, G. Solomon, "Polynomial Codes Over Certain Finite Fields", Journal of the Society for Industrial and Applied Mathematics 8(2) (1960), 300-304. DOI 10.1137/0108018（書誌はCrossref。本文はラトガース大学のサイトにある写しで確認）
R. W. Hamming, "Error Detecting and Error Correcting Codes", Bell System Technical Journal 29(2) (1950), 147-160. DOI 10.1002/j.1538-7305.1950.tb00463.x（書誌はCrossref。本文はイェール大学のサイトにある写しで確認）
C. E. Shannon, "A Mathematical Theory of Communication", Bell System Technical Journal 27 (1948), 379-423, 623-656. DOI 10.1002/j.1538-7305.1948.tb01338.x（第13節・第17節）
R. W. Hamming, Learning to Learn: The Art of Doing Science and Engineering, Session 12: Error-Correcting Codes（海軍大学院に残る講義の資料）
ZXingのソースコードGenericGF.java、ReedSolomonDecoder.java、Version.java
Project Nayuki, QR Code generator library（qrcodegen.pyの生成多項式と語数の表）
試験に使ったnpmのパッケージ: qrcode 1.5.4、jsqr 1.4.0、@zxing/library 0.21.3