白黒模様の裏に符号を見つめる 佐竹賢治

チラシやウェブでよく見かけるQRコード。白と黒のモザイクのようなマークをカメラで読み込み、簡単にウェブサイトにアクセスするという経験は、携帯電話を持つ多くの人が経験しています。このQRコードに、いったいどうやって正しく情報を載せているのでしょう。

正しさの秘訣は、余分な情報

白と黒のモザイクには、実はコンピュータの中で使われているものと同じ0と1で書かれたデジタル情報が隠されています。
白と黒のパターンをデジタル信号に読み替え、情報を読み取ります。
普通に考えると、撮影がぶれたり、汚れなどで一部が破損していたりと、読み込むための障害が多そうです。
しかし、もともと工場の出荷管理などで素早くデータをとるためにつくられたQRコードは、少しぐらいぶれや破損があっても読み取ることができます。
なぜならQRコードが本来の情報とは余分に、読み取った情報に誤りがないか検出し、訂正するための情報も含んだ「誤り訂正符号」としてできているからなのです。

誤りを教えてくれる割り算

誤り訂正符号にはいくつかの種類がありますが、QRコードの誤り訂正には「巡回符号」が使われています。
たとえば、(0100)という4bitの情報を伝えたい場合には、 (111)という3bitの誤り検出のための情報が付加され、(0100 111)という7bitの巡回符号となります。
111という情報は、このデータを0χ^6+1χ^5+0χ^4+0χ^3+1χ^2+1χ+1=χ^5+χ^2+χ+1のように多項式に置き換えた際に、χ^3+χ+1で割り切れるような0と1の組み合わせになっています。
もし、誤って(1100 111)のようなデータを受け取った場合、1χ^6+1χ^5+〖0χ〗^4+〖0χ〗^3+1χ^2+1χ+1=χ^6+χ^5+χ^2+χ+1をχ^3+χ+1で割り算すると、χ^2+1のあまりが出ます。
このあまりの多項式を確認することで、7文字のうちどのデータが間違って読み込まれたかがわかります。
誤りの場所さえわかれば、その情報を1なら0へ、0なら1へ反転することで、送信されたであろう正しい情報を予測することができるのです。
このしくみを使い、QRコードは最大で全面積の30%まで誤って読み取られても、正しい情報に読み替えることができるのです。

30%の間違いを逆手に取る

ブレも汚れも補正してくれる便利なQRコードを眺めながら佐竹先生が考えたのは、普通とは逆の発想でした。
30％の間違いが許容されるならば、逆にそれをうまく利用して、本来の情報に別の視覚的な情報をつけられないか、と考えたのです。
異なる白と黒のパターンでも、誤り訂正によって同一の情報に読み替えられるものがいくつか存在します。
それらを組み合わせることでイラストを表現するQRコードや、さらには動画のように動くQRコードをつくってみせました。
この内容で実際に特許を取得し、現在はネット広告や大型ディスプレイでの活用ができないかと考えています。

「CDに記録された音楽データなど、符号理論は世の中のいろんなところで使われています。理解すれば、おもしろいことができる」
と、今日も佐竹先生は研究室の学生たちとディスカッションを続けています。
あなたの周りの符号理論にも、アイデアの種が眠っているかもしれません。

QRコードは（株）デンソーウェーブの登録商標です。