QR コードについて
２年Ｄ組

小野 悠花
佐藤 真生
齋藤龍之介

佐藤住吉須田悠都慧斗
怜要約
QR コードは私たちの身の周りにたくさんある。例えば、LINE や店の商品、インターネット上の情報など、私たちの生活に欠くことのできないものである。また、バーコードよりも圧倒的に情報量が多く、ある程度の汚れならば復元可能である。その理論を支えているのは、代数学の符号理論や暗号理論で、2 進法が大きく関わっていることを知った。そこで、私たちは自分たちで情報を符号化し、誤り訂正符号を求め、QR コードの作成を試みた。

１．研究の動機と目的
膨大な情報の中から自分が必要としている情報を見つけ出すのは困難である。そんなとき私たちの生活を支えているものとしてバーコードや QR コードがあげられる。私たちは特に QR コードに興味をもった。QR コードは、スマートフォンで簡単に読み込めるためバーコードよりも日常生活において必要不可欠であり、数学的要素が含まれているため自分たちでも作成できないか考えたことが本研究の動機である。
また、私たちは QR コードの特徴として次の 3 点に着目した。第 1 に QR コードを作成する過程において 2 進数や 16 進数の計算が活用されていることがある。第 2 に折り曲げたり、汚れ、擦れおよび破れなどによってコードの一部が読めなくなった場合でもある程度なら自動的に誤りを訂正して、読むことができることがある。第 3 に QR コードはバーコードと比較すると 10 倍から 100 倍の情報量を保存することができ、スマートフォンでも読み取れるため、バーコードのように読み取り機器にコストをかけなくても済むという以上の 3 点に着目した。これらを踏まえて自分たちで QR コードを作成し、符号化した情報を読み取ることが本研究の目的である。

２．QR コードの作成に必要な知識
QR コードを作成するにはさまざまな知識が必要となる。その中でも QR コードを塗る際に必要となる知識について説明する。
第 1 に、「誤り訂正コード」について説明する。
「誤り訂正コード」とは、誤り、つまり汚れや損傷などを検出し、訂正を行う符号のことである。QR コードを作る際に「真実為原」を符号化したデータのコードの後に並べるコードである。
第 2 に、「RS 符号」について説明する。
「RS 符号」は、複雑な計算手順が必要であるが、誤り訂正能力が高く、連続した複数ビットの訂正に強い符号である。本研究では、「誤り訂正コード」を求めるために、総コード 26、データコード数 13、誤り訂正数 6 のときの「RS 符号」をいう。
第 3 に、「BCH 符号」について説明する。
「BCH 符号」は、複雑な計算手順が必要なく、符号化、暗号化されたデータを元のデータに復元することができる符号である。主に QR コードの形式情報に用いられる。
第 4 に、「ビット」について説明する。
「ビット」とは QR コードの作成において、最小の情報量で表されるものである。主に（01101100）などの「0」や「1」のような単位である。

第 5 に、「シフト JIS 漢字コード」について説明する。日本で決められた漢字 1 つ 1 つに割り振られた 16 進数の符号のことであり、「10」は「A」、「16」は「G」などのように対応している。例えば、「真」は(905E)で表され、9×163 +0×162+5×161+14×1 の意味である。
第 6 に、「漢字コード」について説明する。
「漢字コード」は（1000）で定められており、QR コードに入力される情報に漢字が含まれている場合に活用されるものである。

３．QR コードの作成の基本設定
QR コードを作成する際に、どのような情報を用いて、どのような誤り訂正レベルにするかを考えた。
まず、QR コードで表す情報として由利高校の校訓である「真実為原」を採用した。理由としては、情報量を多くすると、その分自分たちで行う計算量が増えるため、できるだけ最小の情報量で自分たちに関わりの深い 4 文字に設定した。次に、誤り訂正レベルについて考えた。今回は、参考文献の誤り訂正レベルが Q（全体の 25％復元可能）だったため作成する QR コードも誤り訂正レベル Q にした。理由としては、完成させることを第一の目的としたためである。

４．QR コードの作成
QR コードの作成手順として、幸山(2008)を参考にして、本研究でも次のように 3 つの段階に分けてQR コードを作成した。

STEP1

符号化

STEP2

マスク処理

STEP3

モジュールの配置

図１ 符号化STEP1 の「符号化」とは、「真実為原」をシフト JIS 漢字コードに読み替える段階である。
「真」は(905E)、「実」は(8EC0)、「為」は(88D7)、「原」は（8CB7）となる。次に、それぞれから16 進数のもとで（8140）を引き、その上位バイトに(C0)を掛ける。そして、その結果と下位バイトを足す（図 1）。最後に、その値を 13 ビットの 2 進数に変換すると以下のように圧縮変換される。

「真」は（0101101011110）、「実」は（0101001000000）、「為」は(0010111010111)、「原」は(0100010110100)

STEP2 の「マスク処理」について述べる。

図 2 圧縮変換「マスク処理」とは、データを配置したときに一方の色が多すぎたり、位置検出パターン(QR コードシンボルの右上、左上、左下に配置されている模様)に似た模様があると読み込みにくくなるためそれを防ぐための操作である。
次に「漢字コード」（1000）、「文字数コード」（00000100）、STEP1 で求めた符号、「終端パターン」（0000）の順に並べる。最後に、「埋め草コード」（11101100）と（00010001）を交互に並べる。実際に並べた

コードは図 2 である。
ここで言う「文字数コード」とは 1 バイトに収納する文字数を指示するものであり、漢字の場合は 1バイト 8 ビットになるようにする。
「終端パターン」とは、符号化したデータの終わりにつけて、データの終わりを指示するものである。
「埋め草コード」とは（11101100）と（00010001）を交互に 8 ビットの 13 バイトになるように並べるコードであり、空いた部分を埋める空コードでもある。

次に、誤り訂正コードを求めるために図 2 のデータをαのべき指数の形に変換する。そのためにガロア体の考え方を用いる。
ガロア体とは、整数を素数で割ったときの余りの集合である。QR コードは原始多項式
Ｆ(x)=x8+x4+x3+x2+1 の係数を示す 100011101 を持つ GF(28)を用いて計算されている。まず、x をαとする。F(α)=α8+α4+α3+α2+1=0 と決められており、それを変換して-α8=α4+α3+α2+1 となる。GF(2)上の数であるから 1+1=0 は -1=1 で表され、-α8=α8 となる。よってα8=α4+α3+α2+1 となる。α8 以上のべきはすべてα０～α７の多項式として表現できる。この多項式を並べて書くと(10100110)のような「0」と「1」を使った 8 ビットの「ベクトル表現」ができる。そして、GF(28)の 0 以外の元(0 と 1)は全てαのべき指数として表現できたため、GF(28)のすべての元とα0 からα225（28=256 を 0 から数えるものとする）の整数を対応させることができる。これにより、1 コード語と GF(28)のα0～α255 の「べき表現」をα7＝10000000 のように対応させることができる。

次に図 2 のデータを多項式 F(x)として表現する。誤り訂正レベルを Q に設定したため総コード語数が 26 となり、x の 25 次から 13 次の和で表される。その際の係数が図 2 のコードとなる。
データの 8 ビットを 1 コードとしたものを係数にして、F(x)を求めると次のようになる。
F(x)=10000000x25+01000100x24+10101111x23+00101001x22+00000000x21+10111010x20+11101000x19+10110100x18+00000000x17+11101100x16+00010001x15+11101100x14+00010001x13

そして、先名(2011)の「GF(28)のべき表現とベクトル表現」の表をもとに「べき表現」αｘ (ただしｘは 0 から 255 の数)に直すとα7＝10000000、α221＝01000100 となり他も同様に変換できる。F(x)を変換した形にすると以下のようになる。
F(x)= α7x25+α221x24+α97x23+α147x22+α0x21+α57x20+α11x19+α20x18+α0x17+α122x16+α100x15+α122x14+α100x13

次に誤り訂正コードを作る。誤り訂正レベルによって生成多項式が定められている。本研究では訂正コードの語数が 13 なので決められた生成多項式は以下のようになる。

G(x)=(x-1)(x-α)(x-α2)(x-α3)(x-α4)(x-α5)(x-α6)(x-α7)(x-α8)(x-α9)(x-α10)(x-α11)(x-α12)=x13+α74x12+α152x11+α176x10+α100x9+α86x8+α100x7+α106x6+α104x5+α130x4α218x3+α206x2+α140x+α78

F(x)÷G(x)の割り算を行い、余りを求める。初めの項がα７x25 なのでα７x12 と F(x)を掛けると G1(x)が求められる。

G1(x)=α7x25+α81x24+α159x23+α183x22+α107x21+α93x20+α107x19+α113x18+α111x17+α137x16+α225x15+α213x14+α147x13+α85x12

次に G1(x)のべき表現をベクトル表現に直すと以下のようになる。
G1(x)=10000000x25+11100111x24+01110011x23+11000100x22+01101000x21+10110110x20+01101000x19+00011111x18+11001110x17+10011110x16+00100100x15+11110010x14+00101001x13+11010110x12

これを F(x)に足すと最高次の項が消えて、次数が 1 つ減る。

F(x)+G1(x)=10100010x24+11011100x23+11101101x22+01101000x21+00001100x20+10000000x19+10101011x18+11001110x17+01110010x16+00110101x15+00011110x14+00111000x13+11010110x12
同様な計算をくり返し行い、次数を下げていくと、最終的に以下の式が求められる。

00000100x12+11011100x11+11001000x10+01011110x9+11100101x8+01000100x7+10001000x6+01010001x5+01001111x4+11011000x3+00101110x2+00100111x+00001101

最高次数が 12 次のため、これ以上割れない。つまり誤り訂正コードは以下のようになる。

00000100 11011100 11001000 01011110 11100101 01000100 10001000 01010001
01001111 11011000 00101110 00100111 00001101

次に、QR コードの読み込みを確実にし、シンボルにおける白黒をバランス良く配置する操作を行う
ため「マスク処理」を行う。この処理を行うためにマスクパターンを用いる。マスクパターンは、条件によって 8 種類の形がある。この 8 種類のマスクのどれを用いるかはマスク処理後の状態を評価することによって行われるが、参考にしたものが参照子 011 だったため Mask011 を用いた。これを次にMask011={01100001}{10000110}{00011000}{10010010}{01001001}{00100100}{10000110}{00011000}{01100001}{00100100}{10010010}{01001001}{00011000}{01100001}{10000110}{00010001}{10000110}{01001001}{00100010}{01001001}{00100100}{10010010}{00011000}{00100100}{10010010}{01001001}

形式情報コードは、誤り訂正レベルやマスクパターン、誤り訂正コードをもとに計算して 15 ビットで表される数である。縦方向と横方向の 2 回塗る重要なコードである。今回用いた形式情報コードは110110100110111 である。誤り訂正レベルが Q であることから、最初の数は 11 となる。そして、マスクパターン Mask011 を用いたことから次の数は 011 となる。それを続けて 5 桁を表している。しかし、残りの 10 桁については、計算の仕方や本質的な意味を理解できなかったため、池田(2007)の形式情報コードを用いた。

最後に「マスク処理」を行う。圧縮変換で求めた図 2 の 13 のコードと STEP2 の段階で求めた誤り訂正コードの 13 のコードの合計 26 コードを続けて並べる。そして、上記の mask011 のコードを 2 進数のもとで足し算を行うと最終的なコードを求めることができる。実際には mathematica というソフトを使って計算した。以下に示したコードが QR コードに配置される。

11100001

11000011

10110111

10111011

01001001

100111100110111010101100

01100001

11001000

10000011

10100101

00001001

01100101

01011010

11011001

11011000

10101100

01100110

11000001

01110101

11011101

11000000

00001010

10110100

01000100

STEP3 の「モジュールの配置」とは、並べたコードをもとにモジュールと呼ばれるデータ容量に応じた型番に色を塗り、形式

図 3 QR コードの塗り方
ぬりかた

情報コードを配置するという段階である。データ領域にまず右下から、8 つのセルに 1 コード語を割り当てていく。STEP2 で求めたコードを右下から塗り始める。1 を黒、0 を白とする。それぞれ割り当てが決まっており、図 3 の左図の場合は下から上に、右図の場合は上から下に塗る時の順番である。

図 4 作成した QR コード

STEP2 でマスク処理されたコードと形式情報コードを塗ると
図 4 のように「真実為原」の QR コードができる。

５．結果と今後の課題
1 回目に作成した QR コードは失敗したが、2 回目に作成したコードは成功した。
最初に作成したものは QR コードとして携帯に認識はされたが、符号化したはずの「真実為原」という文字は読み取ることができなかった。その原因として、「真実為原」の「真」の漢字コードが間違っており、また「真」の文字を含むほかの 3 文字の途中計算も正確ではなく間違っていたことにより、符号化したコードが本来導くはずだったコードと違ったため読み取りに失敗したということが分かった。
これらのことから「真」の漢字コードを訂正し、すべての文字の計算を最初からやり直した。QR コードを構成し直した結果、「真実為原」という文字を携帯で読み取ることができた。しかし、計算により本来のコードを導くことができたが、それらの計算過程で行われている数学の深い内容や使用されている単語の詳細な意味までは理解することができなかった。以上のことから、今後は単語の詳細な意味を理解した上で、「真実為原」よりも複雑な情報をコード化していきたい。また、今回は参考文献の誤り訂正レベルが Q であったため私たちもそれに従ったが、次は参考文献に載っていなかった誤り訂正レベルを使って QR コードの作成に努めたい。

６．引用・参考文献
池田和興(2007).「例題が語る符号理論」.共立出版.
竹生修己(2010).「よくわかるバーコード・二次元シンボル」.オーム.
Darel,Ｗ,Hardy

Carol,Ｌ,Walker.(2005).「応用代数学入門」.ピアソン・エデュケーション.

先名健一(2011).「符号理論入門」.森北出版.
幸山直人(2016).富山大学公開講座 2008「QR コードを作ろう」.
http://kouyama.sci.u-toyama.ac.jp/main/etc/2008/koukai2008/(閲覧日 6 月 30 日)