Ruby / Rails以外の開発一般

2025.08.15

QRコードはなぜ読み間違えないのか

kazz

シェア
ツイート
ブックマーク
LINE

QRコードは人力で読めるのか

夏記事の執筆にあたりQRコードをしくみを実際に読みながら解説してみるのは面白いのでは？と考えた次第ですが、この世の中にはQRコードを人力で読める変態ものすごい能力のある人たちがいらっしゃり、これさえ見ればQRコードがなぜ読めるのかは丸わかりとなります。

このほかにも QRコードを人力で読み取る #ネタ - Qiita、QRコードを自力で読み取ってみる｜Kaido などなど良記事がたくさんあり、いまさら基本的なQRコードの仕組みを解説してもn番煎じ感が否めないわけであります。

そんな中QRコードでは誤り訂正符号として リード・ソロモン法 なる符号が使われているとのことなので、これなら手垢が付いていないはずだということで解説してみたいと思います。

誤り訂正符号とは

そもそも誤り訂正符号とは、データ伝送に発生する誤りを自動的に検出・訂正するための技術です。送信したいデータに冗長なデータ(パリティ)を加えることで、受信した際にはパリティをヒントに正しいデータを復元することができます。
例えばQRコードが光の反射具合で一部読めなかったり汚れていて白と黒を誤って読んでしまったとしても正しくデータが読めるのはこのためです。

QRコードにおける誤り訂正能力

QRコードの誤り訂正能力は4つのレベルがあり、レベルLで約7%の復元能力、レベルMで約15%、レベルQで約25%、レベルHが最大で約30%となります。
復元レベルに応じてQRコードの見た目も変わり、復元能力が高いほどQRコードの目が細かくなっていきます。
詳しくは QRコードの誤り訂正機能とは？概要から活用方法まで徹底解説 | QR WORLDで解説されています。

リード・ソロモン符号

リード・ソロモン符号はQRコードに限らず、CD/DVD/Blu-rayなどの光学ディスクや地上デジタル放送などに広く用いられる誤り訂正符号です。特に連続して起こるビット誤りに強いのが特徴となります。

本来送りたいデータと、このデータからうまく算出したパリティを付け加えることで受け取ったデータにある程度の誤りがあっても、受け取った側で訂正することができます

ガロア体(有限体)と演算

リード・ソロモン符号では、ガロア体という我々のよく知る世界とはちょっと異なる世界で演算を行います。

使用できる文字種: { 0, $\alpha^{0}$ , $\alpha^{1}$ , $\alpha^{2}$ , $\alpha^{3}$ , $\alpha^{4}$ , $\alpha^{5}$ , $\alpha^{6}$ } の計8種類
掛け算のルール:
- $\alpha^{i} × 0 = 0$ (0は何を掛けても0)
- $\alpha^{i}\alpha^{j} = \alpha^{\mod(i+j, 7)}$ (掛け算は指数の和の7で割った余り)
- $\alpha^{0} × \alpha^{i} = \alpha^{i}$ であるので $\alpha^{0}=1$ とする( $\alpha^0$ が乗算の単位元)
足し算のルール:
- $\alpha^{i} + 0 = \alpha^{i}$ (0で足しても変わらない。0が加算の単位元)
- $\alpha^{i} + \alpha^{i} = 0$ (同じものを足すと0になる)
- $\alpha +1 = \alpha^{3}$ 　(文字の2次式で表現から和を求められるように設定)

このルールでは、 $\alpha^4,\alpha^5,\alpha^6$ は以下のようにも表現できます。

$\begin{aligned}\alpha^4 &= \alpha^3\alpha = (\alpha + 1) \alpha\\ &= \alpha^2+\alpha\end{aligned}$
$\begin{aligned}\alpha^5 &= \alpha^4\alpha = (\alpha^2 + \alpha)\alpha = \alpha^3+\alpha^2 \\ &= \alpha + 1 + \alpha^2 \end{aligned}$
$\begin{aligned}\alpha^6 &= \alpha^5\alpha = (\alpha^2 + \alpha + 1)\alpha = \alpha^3 + \alpha^2 + \alpha = (\alpha+1)+\alpha^2+\alpha \\ &= \alpha^2+1 \end{aligned}$

このように各文字は $\alpha$ の2次多項式としても表現でき、その係数をとれば3ビットの数としても表現可能です。

まとめると以下の表になります。

文字	多項式表現	ビット表現
0	0	000
$\alpha^{0}$	1	001
$\alpha^{1}$	$\alpha$	010
$\alpha^{2}$	$\alpha^{2}$	100
$\alpha^{3}$	$\alpha + 1$	011
$\alpha^{4}$	$\alpha^{2} + \alpha$	110
$\alpha^{5}$	$\alpha^{2} + \alpha + 1$	111
$\alpha^{6}$	$\alpha^{2} + 1$	101

多項式表現により、任意の文字同士の足し算が行えるようになっています。
例えば $\alpha^{3} +\alpha^{4} = (\alpha+1) + (\alpha^2+\alpha) = \alpha^2+1$ となり、上記の表から $\alpha^6$ であることがわかります。

符号化

( $1,\alpha^{1},\alpha^{2},\alpha^{3},\alpha^{4}$ )という文字列を送信してみたいと思います。

始めにメッセージ多項式 $M(x)$ を作ります。これは各桁の文字が係数となる多項式となり、今回なら以下のようになります。

$M(x) = 1x^{4} + \alpha^{1}x^{3} + \alpha^{2}x^{2} + \alpha^{3}x^{1} + \alpha^{4}$

続いて、生成多項式 $G(x)$ を定めます。
これは訂正能力が高いほど次数の高い多項式となり訂正能力が1(1文字の誤りを訂正できる)にしたい場合は以下のようになります。

$G(x) = (x+\alpha)(x+\alpha^{2}) = x^{2} + \alpha^{4}x + \alpha^{3}$

生成多項式は $G(\alpha) = (\alpha+\alpha)(\alpha+\alpha^2)=0 , G(\alpha^2) = (\alpha^2+\alpha)(\alpha^2+\alpha^2)=0$ となるように定めています。

最後に符号多項式 $C(x) = M(x)G(x)$ を求めます。今回では以下のような計算となります。

$\begin{aligned}C(x) = M(x)G(x) = &(x^{4} + \alpha^{1}x^{3} + \alpha^{2}x^{2} + \alpha^{3}x^{1} + \alpha^{4})(x^{2} + \alpha^{4}x + \alpha^{3}) \\ = &x^6 + (\alpha+\alpha^4)x^5 + (\alpha^2+\alpha^5+\alpha^3)x^4 \\ &+ (\alpha^3+\alpha^6+\alpha^4)x^3 + (\alpha^4+\alpha^7+\alpha^5)x^2 + (\alpha^8+\alpha^6)x + \alpha^7 \\ = &x^6 + \alpha^2x^5 + \alpha^5x + 1\end{aligned}$

$M(x)G(x)=x^6 + \alpha^2x^5 + \alpha^5x + 1$ となったので送信すべき文字列は多項式の係数を取って

$( 1,\alpha^{2},0,0,0,\alpha^5,1 )$

となります。

復号

受信文字列の多項式を $R(x)$ とすると、 ( $1,\alpha^{2},0,0,0,\alpha^5,1$ ) を誤りなく受信できていれば、 $R(x)= x^6 + \alpha^2x^5 + \alpha^5x + 1$ となり、 $C(x)=M(x)G(x)$ と一致します。

$\begin{aligned}C(\alpha) &= M(\alpha)G(\alpha) &= M(\alpha)×0 &= 0 \\ C(\alpha^2) &= M(\alpha^2)G(\alpha^2) &= M(\alpha^2)×0 &= 0\end{aligned}$

となるように生成多項式 $G(x)$ を定めていることから、 $C(\alpha)$ と $C(\alpha^2)$ はどちらも 0 となるハズです。この値をシンドロームと呼びます。

実際にシンドロームを計算してみるとすべて 0 となることがわかり、文字列は誤りなく受信できたことになります。

$\begin{aligned}S_0 = C(\alpha) &= \alpha^6 + \alpha^2\alpha^5 + \alpha^5\alpha + 1 \\ &= \alpha^6 + \alpha^0 + \alpha^6 + 1 \\ &= 1 + 1 = 0\end{aligned}$

$\begin{aligned} S_1=C(\alpha^2) &= (\alpha^6)^{2} + \alpha^2(\alpha^{5})^{2} + \alpha^5(\alpha)^{2} + 1 \\ &= \alpha^5 + \alpha^5 + 1 + 1 = 0\end{aligned}$

復号するためには $M(x) = R(x) / C(x)$ を以下のように求めることになります。

              x⁴  +  αx³  + α²x²  +  α³x   +  α⁴        <-- 商 M(x)
            _________________________________________________
x²+α⁴x+α³ |  x⁶ + α²x⁵ +  0x⁴  +  0x³  +  0x²  +  α⁵x  +  1
            (x⁶ + α⁴x⁵ + α³x⁴)
            _________________
                   αx⁵  + α³x⁴  +  0x³
                  (αx⁵  + α⁵x⁴  + α⁴x³)
                   _________________
                          α²x⁴  + α⁴x³  +  0x²
                         (α²x⁴  + α⁶x³  + α⁵x²)
                          _________________
                                 α³x³  + α⁵x²  +  α⁵x
                                (α³x³  +  x²   + α⁶x)
                                 _________________
                                        α⁴x²  +  αx   +  1
                                       (α⁴x²  +  αx   +  1)
                                        _________________
                                                    0      <-- 余り

$M(x) = x^{4} + \alpha x^{3} + \alpha^{2}x^{2} + \alpha^{3}x + \alpha^{4}$ であるので、係数を取り ( $1,\alpha^{1},\alpha^{2},\alpha^{3},\alpha^{4}$ ) と復号することができました。

エラーの検出と訂正

一方で ( $1,\alpha^{2},0,1,0,\alpha^5,1$ ) と $x^3$ の箇所を誤って受信した場合はどうなるでしょうか

エラーのある受信多項式は、エラー多項式を $E(x)$ とすると、 $R(x) = M(x)G(x) + E(x)$ と表せます。今回の場合は、 $R(x) = x^6 + \alpha^2x^5 + \alpha^5x + 1 + x^3$ であり、 $E(x) = x^3$ であることが求められれば、 $M(x)G(x)$ を復元できることになります。

まず $R(x)$ のシンドローム計算をすると、 $S_0=R(\alpha)=\alpha^3, S_1=R(\alpha^2)=\alpha^6$ となり、誤りが発生していることがわかります。

誤りが発生している次数 i は $\alpha^i = S_1 / S_0$ として求めることができます。
$\alpha^i = \alpha^6 / \alpha^3 = \alpha^3$ であることから、 $x^3$ の係数部分に誤りがあることがわかります
エラーの値は、 $S_0 / \alpha^i$ として求めることができ、この値を計算すると 1 となります

よって、 $E(x) = x^3$ であることがわかったので、 $R(x) + E(x)$ を計算すれば誤りの無い文字列 $M(x)G(x)$ を復元することができました

むすび

QRコードの誤り訂正技術であるリード・ソロモン符号を具体的に計算してみました。
今回の例で用いたガロア体は $GF(2^3)$ を用いましたが、実際のQRコードでは $GF(2^8)$ が採用されているようです。つまり文字としては ( $0,1,\alpha^1,...,\alpha^{254}$ ) の計256個となり、多項式表現は7次式(8ビット)となるようです。

汚れたQRコードを人力で読むのはちょっと無理そうなことがわかりました。
QRコードは(株)デンソーウェーブの登録商標です。

参考

シェア
ツイート
ブックマーク
LINE