QRコードの概要

符号化（エンコード）

エラー訂正の概要

エラー訂正に必要な「行列」の解説

「行列」を使ってエラー訂正をしよう

リード・ソロモン符号とエラー訂正の方法

多項式の割り算

リード・ソロモン符号の作り方

ガロア理論と体

QRコードを作ろう

QRコードメーカー

QRコードメーカー(javascript)

独極・QRコード担当の「あじな」です。
今回、具体的なQRコードの模様が登場します。
具体的なマークが出てくるとゴールが近くなったんだなぁと一人感動しております。

これまでの復習 [表示する]

QRコードは株式会社デンソーが作ったもので、スマホや携帯で読み取れる
QRコードは「小さな白と黒の四角でできている」「多少汚れても大丈夫」という特徴がある
白黒の四角を使うのは、コンピュータにわかりやすくさせるため
QRコードは「機能パターン」と「符号化領域」で出来上がっている
「機能パターン」は、「クワイエットゾーン」「位置検出パターン」「位置検出パターンの分離パターン」「タイミングパターン」「位置合わせパターン」の5種類
「符号化領域」は「形式情報」「型番情報」「データ領域」の3種類
「形式情報」は「エラー訂正レベル」と「マスクパターン参照子」で決まり、「\(4 \times 8=32\)」種類のパターンがある
「型番情報」は「QRコードのバージョンによって決まり、40種類ある
「データ領域」は「データ」と「エラー訂正情報」で出来上がる
QRコードはバージョンが1～40まである。一辺の大きさは、「QRコードのバージョン(1～40)\( \times \)4\( + \)17」
「エラー訂正レベル」は「L(7%の汚れまで)」「M(15%の汚れまで)」「Q(25%の汚れまで)」「H(30%の汚れまで)」の4種類ある。
「エラー訂正レベル」が「L」だと「QRコード」で表現できるデータの量は最大で、「H」のときに最小になる。
「1bit」とは白・黒、1・0のような2種類の情報を表すことができる能力のことで、文字を増やすと「2bit(4種類)」「3bit(8種類)」と表現できる種類が増える
日常の言葉を「エンコード」して「コード(符号)」に置き換え、「コード(符号)」を「デコード」して日常の言葉に戻す
QRコードの「エンコード」方式は「数字モード」「英数字モード」「漢字モード」「8bitモード」の4種類
どの「エンコード」方式でも、データは「モード指示子」＋「文字数指示子」＋「データ」＋「終端パターン」＋「埋め草ビット」＋「埋め草ワード」となる
QRコードには「白」と「黒」を読み間違えても、元の情報を復元する「エラー訂正」能力が備わっている
「エラー訂正」は読み取れた(聞き取れた)言葉から最も近い「ありえそうな単語」を推測すること
「エラー訂正力が強い」ということは、「あえて使っていない単語が多い」ということと同じで、効率性は悪い
1,0でできている符号では「ハミング距離(2つの符号間で1と0が異なる箇所の個数)」があり、符号間で最も「ハミング距離」が小さいものを「最小距離」と呼ぶ
使える「単語」を制限すると「最小距離」は大きくなる
「最小距離」の半分までのエラーであれば訂正することができる
「単語」を「符号化」したものに、適当な「1」や「0」を後ろにつけると「最小距離」が大きい「エラー訂正機能付符号」になる
「エラー訂正機能付符号」を作る際は「符号」に「行列(生成行列)」を掛け算する。
「QRコード」は「リード・ソロモン符号」と呼ばれる方法で「エラー訂正機能付符号」を作る
「行列」は数字を並べただけのもので、もともとは「連立方程式」の係数だけ抜き取ってならべたもの
「行列」の「足し算」「引き算」は各「行列」の要素同士を「足し算」「引き算」したもの
「行列」の「掛け算」は、左の「行列」から「行」を取り出し、右の「行列」から「列」を取り出して、それぞれの要素を掛け算して足し合わせる
左の「行列」の大きさが「a行b列」で、右の「行列」の大きさが「b行c列」だった時、「掛け算」結果の行列は「a行c列」になる
「行列」の「掛け算」は順番を変えると結果も変わる
「掛け算」しても結果を変えない行列を「単位行列」と呼び、「掛け算」すると結果が「単位行列」になる行列を「逆行列」と呼ぶ
「行列」の特徴を表している「数字」を「行列式」と呼ぶ。「行列式」は「正方行列」だけが持っている
「並び替え」は「置換」によってい表すことができ、偶数回の「置換」でできる「並び替え」を「遇置換」、奇数回の「置換」でできる「並び替え」を「奇置換」という
「行列式」は各列から数字を選択し「掛け算」し、符号をつけた(「遇置換→(+)」「奇置換→(-)」たものを全ての選択パターンで足し合わせる。
「列」で計算しても、「行」で計算しても結果は同じ
「全てが0の列」、もしくは、「すべてが0の行」があれば「行列式」は「0」
「列」を入れ替えたら「行列式」の符号が変わる。「行」を入れ替えても「行列式」の符号が変わる。
全く同じ「行」が2個以上あれば「行列式」は「0」。全く同じ「列」が2個以上あっても「行列式」は「0」
ある「行列」の「行列式」は、その「行列」の1つの「列」(もしくは「行」)を2つに分割して、2つの「行列」の「行列式」の「足し算」にすることができる
ある「行」に違う「行」を「足し引き」しても、「行列式」の結果は変わらない。ある「列」に違う「列」を「足し引き」しても、「行列式」の結果は変わらない。
ある「行(もしくは列)」を「定数倍」した「行列」の「行列式」は、「定数倍」する前の「行列」の「行列式」に定数をかけたものと同じ
2つの「行列」を「掛け算」した結果の「行列」の「行列式」と、それぞれの「行列」の「行列式」を「掛け算」した結果は同じ\(( \left| \boldsymbol{A} \times \boldsymbol{B} \right| = \left| \boldsymbol{A} \right| \times \left| \boldsymbol{B} \right| )\)
「連立方程式」の係数を抜き出した「行列」の「行列式」の値が「0」になるということは、元の「連立方程式」が「不良設定問題」である
「逆行列」は「正方行列」かつ「行列式」の値が「0」でない「行列」だけに存在する
「\((-1)^{(i+j)} \times (元の行列からi行目とj列目を取り去った行列) \)」を「余因子行列」と呼ぶ
「行列式」は「余因子展開」を使うと、1サイズ小さい「行列」の「行列式」の「足し算」に展開することができる
「逆行列」は「(元の「行列」の「行列式」の逆数)\(\times\)(x行・y列目の要素が＜元の行列のy行・x列目を取り除いた「余因子行列」の「行列式」＞となる「行列」)」
「階段行列」は上の行から、左側(0の部分を除きます)を1にして、その行より下の行の左側が0になるように適当な数字をかけて足し算・引き算するというのを繰り返して作る
「ランク」はその「行列」の中の独立した行(または列)の数で、「連立方程式」の係数を「行列」にした場合、未知数の数より「ランク」が低ければ「不良設定問題」となる
「符号」のサイズが1行n列、「エラー訂正付符号」のサイズが1行m列のとき、「生成行列」はn行m列になる
「QRコード」で利用される「エラー訂正機能付符号」は「リード・ソロモン符号」と呼ばれるもの
「検査行列」を「エラー訂正機能付符号」に「掛け算」すると結果は「ゼロ行列」になる。逆に「ゼロ行列」にならないと、読み取った「エラー訂正機能付符号」が間違っている
エラー訂正機能のスペックは「n(「エラー訂正機能付符号」の「長さ」)」、「k(実質的に単語を表現する桁数)」、「d(「エラー訂正機能付符号」の間の「最小距離」)」の3つ
エラー訂正機能のスペックの「n(「エラー訂正機能付符号」の「長さ」)」は「検査行列」の行数と同じ
エラー訂正機能のスペックの「k(「実質的に単語を表現する桁数)」は「検査行列」をn行m列だとすると、「n-(検査行列のランク)」となる
同じ仲間の「エラー訂正機能付符号」を2つ用意すると、それらを「引き算」した結果も同じ仲間の「エラー訂正機能付符号」の1つになる
「エラー訂正機能付符号」軍団の中の「最小距離」は、その「エラー訂正機能付符号」軍団の中で最も小さい「ハミング重み」と同じになる
エラー訂正機能のスペックの「d(「エラー訂正機能付符号」の間の「最小距離」)」は「(「検査行列」の「ランク」)+1」以上となる
「シングルトン限界式」は「d(「エラー訂正機能付符号」の間の「最小距離」)」が「n(「エラー訂正機能付符号」の「長さ」)-k(実質的に単語を表現する桁数)+1」以下になること
リード・ソロモンの「検査行列」は、x行y列の要素が\(\alpha^{(x-1)(y-1)}\)で、xはn行まで、yは2t列までの「行列」
リード・ソロモンの「検査行列」のランクは2t
リード・ソロモンの「検査行列」の特徴は、「エラー訂正機能付符号」の「長さ」はn、実質的に単語を表現する桁数)はn-2t、「エラー訂正機能付符号」の間の「最小距離」は2t+1
「ヴァンデルモンド行列」の行列式は、行列の要素に同じ値のものがなければ「0」にはならない。
受信符号に検査行列を掛け算した結果は、発生したエラーに検査行列を掛けたものと同じになる、「\(\boldsymbol{Y} \times \boldsymbol{H} = \boldsymbol{E} \times \boldsymbol{H}\)」
「\(\boldsymbol{Y} \times \boldsymbol{H} = \boldsymbol{E} \times \boldsymbol{H}\)」を展開すると、方程式の数がn個、未知数が2t個の連立方程式になる
リード・ソロモン符号の解き方は、「01.エラーの発生個数」「02.エラーの発生位置」「03.エラーの内容」の3ステップ
\(\begin{vmatrix} S_0 & S_1 & \ldots & S_{j-1} \\ S_1 & S_2 & \ldots & S_{j} \\ \vdots & \vdots & \ddots & \vdots \\ S_{j-1} & S_{j} & \ldots & S_{ 2j-2 } \\ \end{vmatrix}\)という行列式の\(j\)の値を\(t\)から1つずつ減らしていき、初めて行列式の値が「0」以外になった時の\(j\)がエラーの発生個数になる。
エラーが発生している位置に対応する\(\alpha\)の「逆数」(つまり、\(\alpha^{-p_0},\alpha^{-p_1},\cdots ,\alpha^{-p_{j-2}},\alpha^{-p_{j-1}}\)を入力したときだけ「0]を出力する関数を、\(\boldsymbol{Y} \)と\(\boldsymbol{H}\)の情報から作ることができ、エラーの位置を求めることができる
エラーの位置が分かった状態であれば、元の「\(\boldsymbol{Y} \times \boldsymbol{H} = \boldsymbol{E} \times \boldsymbol{H}\)」を普通の連立方程式のように解くことができ、「エラーの内容」を求めることができる
多項式を多項式で割り算することができ、割り算した商を\(Q(x)\)、余りを\(R(x)\)とすると、「\(f(x) = g(x)Q(x) + R(x)\)」と書ける
次数が\(f\)の多項式を次数が\(g\)の多項式で割り算すると余りの多項式の次数は\(g\)未満になる
多項式\(f(x)\)の解(\(f(a)=0\)となる\(a\)の値）を使うと、\(f(x)=(x-a)R(x)\)と因数分解できる（剰余の定理）
多項式\(f(x)\)は\(f(x) = (x-a_1)(x-a_2)(x-a_3) \cdots (x-a_{(n-2)})(x-a_{(n-1)})(x-a_{n})\)と因数分解できる（ただし、\(a\)は複素数になることもある）
\(x_0\)～\(x_{(n-1)}\)を係数にもつ\(n-1\)次の多項式\((f(z)=z^0 x_0 + z^1 x_1 + z^2 x_2 + \cdots + z^{(n-3)} x_{(n-3)} + z^{(n-2)} x_{n-2} + z^{(n-1)}x_{(n-1)})\)を\((z-\alpha^0)(z-\alpha^1)(z-\alpha^2) \cdots (z-\alpha^{(2t-3)})(z-\alpha^{(2t-2)})(z-\alpha^{(2t-1)})\)で割り切ることができれば、\(x_0\)～\(x_{(n-1)}\)はリード・ソロモン符号
メッセージ多項式\((m(z)=z^0 m_0 + z^1 m_1 + z^2 m_2 + \cdots + z^{(k-3)} m_{(k-3)} + z^{(k-2)} m_{(k-2)} + z^{(k-1)}m_{(k-1)})\)に\(z^{2t}\)を掛けて、\((z-\alpha^0)(z-\alpha^1)(z-\alpha^2) \cdots (z-\alpha^{(2t-3)})(z-\alpha^{(2t-2)})(z-\alpha^{(2t-1)})\)で割り算した余り\(R(z)\)の多項式の係数を、元のメッセージ符号に付け加えると、リード・ソロモン符号になる
「01.加法と乗法が定義されている」「02.演算が閉じている」「03.結合法則が成り立つ」「04.単位元がある」「05.逆元がある」「06.可換である」の6個のルールを満たす集合を「体」と呼ぶ
「体」であれば、その集合はここで解説している符号化やエラー訂正の理論がそのまま適用できる
QRコードは8桁の多項式(\(ax^7+bx^6+cx^5+dx^4+ex^3+fx^2+gx+h\)を要素とする「体」を使ってリード・ソロモン符号の計算をする
QRコードは「01.文字決め」「02.エラー訂正レベル決め」「03.符号化方式決め」「04.バージョン決め」「05.枠つくり」「06.符号化」「07.リード・ソロモン計算」「08.書き込み」「09.マスク適用」の段階を経て作る。

前回までのおさらい

前回の解説では、以下のようなお話になっておりました。

Step	やること	今回のサンプル
Step1	QRコードに入れる文字を決める	QRコードを独学でマスター
Step2	エラー訂正レベル決める	エラー訂正レベルM
Step3	符号化方式を決める	8bitモード
Step4	QRコードのバージョンを決める	バージョン2
Step5	バージョンにあった枠を作る	(今回解説します)
Step6	文字を符号化する
Step7	「符号」から「リード・ソロモン符号」を計算する
Step8	データをQRコードのデータ領域に書き込む
Step9	マスク適用する

枠を作るステップ

まずは、QRコードの解説連載の初期のころに解説した「機能パターン」を書いていきましょう。
「機能パターン」は、「クワイエットゾーン」「位置検出パターン」「位置検出パターンの分離パターン」「タイミングパターン」「位置合わせパターン」の5種類があるのでしたよね。
それぞれについて書いていきましょう。

まずは格子枠を書く

QRコードの1辺の四角の数「QRコードのバージョン(1～40)\( \times \)4\( + \)17」でした。そして、今回、バージョン2を作ろうとしているので、「\( 2 \times 4 + 17 =25\)」となります。
というわけで、さっそく書いてみましょう。
(但し、この枠線は最後には消すのでもし紙に書く場合は、枠線は消しゴムで消せるシャーペン等で書いて、その後の色塗りはサインペン等で書きましょう）
このサイト上では、鉛筆で書くわけにはいかないので、HTML5のCanvasという機能を使って書いていきます。
サンプルに沿って表示するようにしておりますが、皆さんが自由に触って変更できるようにしておきますので、いろいろ試してみてくださいね。(いつか、このプログラム自体の解説もしたいですね)
それでは、早速枠を作ってみましょう。
「QRコードメーカー」のページを開いて、「枠を描く」ボタンを押してください。
灰色の枠がでたと思います。ちなみに、「QRコードに入れる文字」「エラー訂正レベル」は好きに変更できます。（符号化方式やQRコードのバージョンは自動的に変わります)
この枠は、最終的には消しますがガイドとして表示させます。そして、今後、左上の四角を「(1,1)」と呼びます。そこから右に進むごとに「(1,2)」、「(1,3)」と表現していきます。ちなみに、「(1,1)」から下にいくと、「(2,1)」、「(3,1)」となっていきます。

位置検出パターン

これぞQRコードのマークって感じのやつです。
「7セル×7セル」の正方形を、QRコードの左上、右上、左下に配置します。
各パターンの左上の位置を\((x,y)\)とすると、上辺に当たる「\((x,y),(x+1,y),(x+2,y),(x+3,y),(x+4,y),(x+5,y),(x+6,y)\)」を黒にして、左端にあたる・・・。ええい！面倒くさい！
この画像を見てください！

QRコードのサイズを、「\((X_max,Y_max)\)」とすると、この上のパターンを「\((1,1))\)」、「\((X_max-6,1)\)」、「\((1,Y_max-6)\)」の位置に配置します。
早速、「QRコードメーカー」で試してみましょう。「位置検出パターンを描く」ボタンを押してみてください。

位置検出パターンの分離パターン

お次は、「位置検出パターンの分離パターン」ですね。（覚えてます？）
「位置検出パターン」を囲むように白の四角で囲みます。
では、「QRコードメーカー」の「位置検出パターンの分離パターンを描く」ボタンを押してみてください。

タイミングパターン

どんどんいきますよ。次はタイミングパターンですね。
QRコードの上部と左部に白黒のパターンを描いていきます。
では、例によって「QRコードメーカー」の「タイミングパターンを描く」ボタンを押してみてください。

位置合わせパターン

機能パターンの最後は「位置合わせパターン」です。
このパターンはQRコードのバージョン2以上から現れるパターンですね。
バージョンによってパターンの数・位置が微妙に違うので、こちらの表からQRコードのバージョンにあったパターンの数・位置を探し出してください。
それでは、「QRコードメーカー」の「位置合わせパターンを描く」ボタンを押してみてください。

形式情報

さて、これで全ての機能パターンを描くことができました。