Galois Field in Auto Factory

自動車工場の
ガロア体

QRコードはどう動くか

その誕生を地元新聞も経済新聞も記事にしなかった。2年後、『コードの情報を白黒の点の組み合わせに置き換える』と最下段のベタ記事で初めて紹介された時、その形を思い浮かべることができる読者はいなかった。いま、説明の必要すらない。QRコードはなぜ開発され、どう動くのだろうか。

QRコードは、自動車生産ラインの切実な要請と非自動車部門の技術者の「世界標準の発明をしたい」という野心の微妙な混交の下、1990年代前半の日本電装(現デンソー)で開発された。

トヨタグループの生産現場では、部品名と数量の記された物理的なカンバンが発注書、納品書として行き来することで在庫を管理する。そのデータ入力を自動化するバーコード(NDコード)を開発したのがデンソーだ。

バブル全盛の1990年ごろ、空前の生産台数、多様な車種・オプションに応えるため、部品も納入業者も急激に増え、NDコードが限界を迎えていた。63桁の数字しか記録できなかったからだ。複数のコードを並べ、人手でスキャンする負担が無視できなくなっていた。

デンソーは当時、バーコードリーダー(読み取り装置)で圧倒的なシェアを持っていた。「バーコードをなんとかしてほしい」と西尾工場(西尾製作所)から相談を受けたのは、しかし、バーコード担当ではない原昌宏さんだった。輸出書類の文字を自動で読み取るOCR(光学的文字認識装置)を開発していた。1992年、デンソー独自の二次元コードを開発したいと上司に提案する。直線上の濃淡を読み取るバーコードと違い、画像処理のノウハウがあった。

先行する欧米の二次元コードに欠けていた、油などの汚れに強く、読み取りが速いことを最重要目標とした。特許を行使せず、誰もが自由に使えるようにすることも早い段階で決めた。1994年に規格が完成、QRコードとして発表する。デンソー屈指の発明の第一報を書かなかった当時の担当記者を弁護するとしたら、まだ実物がなかったからだ。翌年、安城の高棚工場でテスト機器の実地運用が始まった。

QRコードの仕組み

開発されたQRコードはどのような仕組みで動くのか。簡単なコードを具体的に解読してみよう。

読み取りソフトウエアは、カメラから画像を取り込むと、一瞬のうちに以下のようなデータ処理を行う。

まず、画像から切り取られた格子模様からコードのバージョン(型番)を割り出す。型番は縦横に格子(セル)が21あるバージョン1から、177セルのバージョン40まである。この例では、一辺のセル数がなので、バージョンであることがわかる。

次に、このコードで使われた設定(フォーマット情報)を読み出す。フォーマット情報は、QRコードの特徴である3つの正方形(切り出しシンボル)の脇に配置されている。規格で定められたリストと見比べ、白黒パターンが最も似ているものを選ぶ。一致しない場合でも許容するのは、読み誤りがあるかも知れないからだ。

この例では、設定は反転マスク、訂正レベルだと分かる。

反転マスクは、コードが読みやすくなるように適用されている一種の化粧で、データを読むためには剥ぎとらなければならない。設定にしたがってマスクで白黒を反転させると、QRコードの「素顔」は以下のようになる。

最後に、右下から2行ごとに8セルずつ取り出し、二進数の数字として解釈する。

こうして得られた数が、コードに組み込まれたデータの本体だ。

しかし、話はまだ入り口なのだ。

我々は普段、どのような数の足し算や掛け算をしても、結果がもはや数ではなくなってしまうことを心配することはない。数は無限にあるからだ。ところが200年ほど前、フランスの数学者が(おかしな日本語だが)数の数に限りがある場合でも足し算や掛け算が安心してできる「別の数」の存在に気がついた。彼の名をつけてガロア体(有限体)と呼ばれている。

有限の数の世界

数に限りがある数など、およそ役に立たない。ある数に1を足し続けると、そのうち未使用の数がなくなって元の数を再利用するしかなくなる。足すと元に戻ってしまうなら、大小の比較にさえ使えない。この数を使った預金口座は、積み立てを続けていくといつか残高がゼロになってしまうことになる。

だが、それ以外の点では完璧な数だ。例えば、数が8個しかない世界では以下のような足し算と掛け算が成り立つ。

この世界でも、我々が小中学校で習った算数(加減乗除)がそのまま成り立つ。足し算や掛け算の順序を変えても答えは同じ。掛けると1になる逆数もある。足してから掛けても掛けてから足しても同じという分配法則を思い出す人も多いだろう。

もっとも、役に立たない数を計算できたとしても役に立たないことに変わりはない。QRコードから読み出した数字はこのような数、正確には数が256個しかないガロア体の数だ。

リード・ソロモン符号

そもそも、白黒二進数の数字として読み出された一連の数字はどう作られたのだろうか。QRコードでは、数の読み違いがあっても訂正できるよう、データがリード・ソロモン符号で符号化されている。

同符号ではまず、符号化したい数を係数とする多項式を作る。記録したいデータがだとすると、多項式は以下のようになる。

このときにデータの数が数が256個しかないガロア体の数に読み替えられる。白黒8セルの組み合わせは256種類しかないから過不足がない。

次に、例えば間違いを最大個まで訂正したい場合、を順に増やしながら個(訂正数の2倍)だけ掛け合わせた多項式を作っておく。

このを割った余りの多項式を求める。係数の計算には当然、ガロア体のルールを使わなければならない。

最後に、から余りを引く。

これが印刷される数になる。元のデータに、余りの多項式の係数が続いていることに気づくだろう。

誤り検知:係数に間違いはないか

具体例のQRコードから8セルずつ取り出した数字も同じ手順で作られたはずだ。多項式に戻すと以下のようになる。

この多項式に、を作るときに使った項を代入した結果は「シンドローム」と呼ばれる。式が正確ならば、シンドロームはゼロになる。そうなるように事前に余りを引いておいたのだ。すべてのシンドローム(この場合は個)がゼロになるというテストに合格すれば、式に誤りはないとみなされる。

ゼロでないシンドロームが一つでもある場合、係数のどこかに間違いがあることになる。この具体例でも読み取りエラーが起きていたようだ。

次の問題は、どの係数がどれだけ間違っているのかを逆算することだ。ヒントは上記のシンドロームのリストしかない。

誤り訂正:係数を直す

すべてのシンドロームを係数に持つ多項式をシンドローム多項式という。

リード・ソロモン符号では、読み取りエラーが起きた位置を教えてくれる多項式と、誤差を教えてくれる多項式の間には、シンドローム多項式を巻き込んで「で割り切れる」という関係がある。この方程式の解き方はいくつもあるが、ユークリッド復号法と呼ばれる手法が最も有名だ。最大公約数を求めるユークリッド互除法(高校で習う)のように、の割り算を繰り返し、2つの多項式を導き出す。この場合、結果は以下のようになる。

一つ目の多項式を代入してゼロになった時、多項式のの係数にエラーがあることを意味する。そして、その誤差はだ。具体的には以下のようになる。

こうして読み取りエラーの位置と誤差が分かった。読み取ったデータの多項式は、最終的に以下のように訂正される。

数が256個しかないガロア体だったことを忘れてはいけない。二番目の修正箇所はになる。

デジタル社会の基盤技術

リード・ソロモン符号は、CDやDVD、ハードディスク、USBメモリー、地上波デジタル放送、光ファイバー、惑星探査機の通信装置など、さまざまなデジタル機器で使われている。デジタルの「正確で劣化しない」というイメージは、0と1の世界だからではない。誤り訂正符号が乱れたデータを人知れず修正している結果だ。

QRコードの誤り訂正機能は、トヨタグループの豊田中央研究所の若い技術者2人が担当した。全く畑違いで、符号理論の教科書を読むことから始め、手計算でガロア体を習得したという。その結果、そのまま教科書に戻すことができるほどオーソドックスな誤り訂正機構が採用されることになった。

デジタル社会に不可欠な基盤技術であるガロア体は通常、半導体の回路の中に隠れ、我々には見えない。カンバンに載る、視認可能で大容量、正確な記録手段という製造現場のニーズが、数学者だけのものだった奇妙な数の世界を目に見えるかたちで示してくれる、類まれな発明を産んだ。

誤り訂正機能によって修正された数は、規格に従って文字や数字に戻される。QRコードでは、数字モード、英大文字・数字モード、日本語仮名漢字モード、汎用のバイトモード(8ビット)の4種類が規定されている。

以下の例では、最初の4セルがバイトモードであることを示している。それに従って、続くデータを8セル単位で解釈することになる。

バイトを文字として解釈することで「How QR code works.」という文が得られた。QRコードは元データを確率で推定しない。誤読の可能性はほとんどない。

クイックレスポンス

誤り訂正と並んで重視されたのは、どの方向からも高速で情報が読み出せることだった。そのためには、画像から正しい向きで確実にコードを切り出せなければならない。機械の目にも瞬時にQRコードだと分かる目印は何か。5か国語の印刷物を集めて見出した結論が、黒1白1黒3白1黒1のパターンだ。不思議なことに、活字やデザインの中にこのパターンはほとんど現れない。

切り出しシンボルは、どの向きからも見ても中心部分が11311のパターンになる。右上、左上、左下の3か所しかないため、画像の中でコードがどちらを向いているか、簡単に分かる。

現在使われている読み取りソフトはもっと洗練されているが、以下のような原始的な手順でもコードは簡単に取り出すことができる。

1. 撮影した画像を白黒に変換する

2. 上から1ピクセルずつスキャンして、黒1白1黒3白1黒1のパターンを探す。大きなパターンほど切り出しシンボルの有力候補になる

3. 有力候補のうち、似た大きさの3個が右上、左上、左下となるように画像の位置と角度を変換する

見当違いの切り出しも、誤り訂正のおかげでQRコードでないことが即座に分かる。他に候補があれば、切り出し直して復号を試みるだけだ。

11311が発明の真髄であることは、読み出しの際に白黒を反転する作業があった理由にも表れている。反転マスクには以下の8種類が用意されている。

どのパターンを選ぶかの基準の一つに、偶然11311が現れてしまわないことが含まれている。苦心して見つけた黄金パターンを自ら作ってしまうことを避けるのだ。

自動車工場を超えて

新聞が『情報を白黒の点の組み合わせに置き換え、バーコードの約百倍の情報量を持たせる』と生硬な表現で初代リーダー発売を紹介した1996年以降、QRコードはゆっくりと自動車生産の現場に広まっていった。国際標準にも認められ、三菱電機や文具のぺんてるなど他業界でも採用された。しかし、それだけではあなたもこの記事を読んでいないだろう。

2002年のシャープの機種を皮切りに携帯電話に読み取り機能が組み込まれ、一気に普及する。当時の新聞をめくると、動物園のガイド、迷子探し、漁協の産地表示、馬券などの使用例が花開いている。表記もわずか1年ほどで『携帯電話で読むモザイク模様』から『QRコード』に変わった。

エンジン工場の油汚れにも耐えるよう開発された誤り訂正機能にも、想定外の応用が現れた。最大30%の高い訂正率を逆手に取って、コードの中に企業のロゴやメッセージをデザインする広告が登場した。欧米では、メッセージのアドレスを示す油彩画だけの美術展や、角度によって異なるコードに見える立体彫刻の個展が開かれている。

Kyle Trowbridge, 2012 Installation view Politics of Time at Emerson Dorsch
Kyle Trowbridge氏(米マイアミ大学)のインスタレーション。許諾/credit: Politics of Time at Emerson Dorsch(2012)

スマートフォンの普及で詐欺やコンピューターウイルス攻撃に使われるセキュリティの問題も出てきた。少数民族の監視、ワクチンの接種管理、ワクチンパスポート。社会問題を象徴する役回りになった。

QRコードは、日本電装が早くも1995年に商標登録出願し、デンソーウェーブがブランドを守っている。特許と異なり、登録商標には期限がない。そのような巧みな企業戦略さえ色褪せるほど、QRコードは二次元コードの代名詞として世界標準になった。自動車工場を超えて、発明家の野心は達成されたのだ。

主な参考文献: 小川進「QRコードの奇跡」電子情報通信学会「通信ソサイエティマガジン2013秋号」

QRコードはデンソーウェーブの登録商標。本文(技術解説部分を除く)は以下のコード1枚(バージョン40、1817字)に収まるように編集した。(説明不足や飛躍が多いのはこのためです)

本文