FSH2007ST6/QR(1) - PukiWiki

QRコードについて(その1)

形式情報の配置場所

形式情報部分(黄色の部分)は15ビットの2進数列で, データ部分(水色と緑色の部分)にかけるマスクの種類, 誤り訂正に用いる方法についての情報が保存されています. 形式情報15ビットは, QRコード中の位置検出パターンのすぐ横に配置されています. 最上位ビットが(14), 最下位ビットが(0)に配置されます. 縦と横に2つ同じデータを配置します. 図中の黒い部分と白い部分は位置検出パターンで固定です. バーコードの大きさにより多少異なりますが, 上の左右2つと下の左の大きなパターンは全てのバーコードで同じです. 黄色の部分に形式情報が, 水色と緑色の部分にデータが入ることにより, 白または黒になります.

QRcode2.png

排他的論理和(xor)

排他的論理和は2つの2進数に対する演算で各桁で 1+1=0 となる足し算です. 0+0=0, 0+1=1+0=1 です. 下の例を参照して下さい.

       100101010100000  ← A
   xor 101010000010010  ← M
   -------------------
       001111010110010  ← B
       001111010110010  ← B
   xor 101010000010010  ← M
   -------------------
       100101010100000  ← A

A xor M = B のとき, B xor M = A となります.

Aを送信データ, Mを暗号の鍵, Bを暗号データと考えてみましょう. AさんとBさんで鍵Mを共有し, Aさんが発信時にMをxorしてBさんに送り, Bさんは受け取った後, Mをxorして元の送信データAを復元すると考えると理解しやすいかもしれません. 暗号の鍵(M)を知らない人は, 通信途中のデータBを読んでも, 送信データAを得ることは出来ません.

このxorをする数Mのことをマスクと呼ぶこともあります. QRコードの形式情報は, 全てM=10101000010010 のマスクがかけてあります. 従って元の形式情報の値を知るためには, バーコードから直接読んだ値にMをxorする必要があります. QRコードの場合のマスク処理は, 暗号のためではなく, 0(白)ばかりや, 1(黒)ばかりが固まらないようにマスクをかけます. 白や黒が固まっていると機械読取でのエラーが発生しやすくなるからです.
例えば, 下のQRコードの例にある西日本TVのHPのQRコードの形式情報部分にある読み込みデータの値は, 上のAにあるビット列です. これにMをxorする(マスクを除去する)とBのビット列が得られます. これが, 西日本TVのHPのQRコードの形式情報の元の値です.

誤り訂正 (誤り検査)

0と1の2つの数しかない世界( と呼ばれる)を考え, その元を係数に持つ多項式を考えます. 全ての計算が結果を2で割った余りになります. 例えば, 1+1=0 となります. ではなく, になります.

ビット列 に対して, 多項式 を対応させます. この多項式をR[x]と書くことにします.

QRコードでは, の原始既約多項式と呼ばれる 特別な多項式 を用います.

  1. QRコードの形式情報からマスク除去(Mとxor)した元の形式情報の値を求めます.
  2. 元の形式情報の値に対応する多項式R[x]を求めます.
  3. R[x]を の原始既約多項式で割った余りは必ず0になります.
    (注意. 割り算の計算も の元を係数に持つ多項式と考えて行います.)
  4. もし読み込み時にエラーがあると, 上記の多項式を割った余りが0にならずに, 余りとして多項式が出てきます. この多項式を調べることで, 5箇所までの誤り検出と2箇所までの誤り訂正が可能です.
  5. 誤りが1箇所の場合は, を原始既約多項式 で割った余りと等しくなりますので, 下の表により誤り位置がわかります.
誤り位置( )剰余多項式
1
x
x + 1

(例) 実際のQRコードの形式情報を検査する.

西日本TVのHPのQRコードを読み取った形式情報A=100101010100000を検査してみます.

  1. (マスク除去) 前節と同じで A xor M で B=001111010110010 を求めます.
  2. R[x]は となります.
  3. を計算すると ですが, 2で割った余りの世界 の元を係数に持つ多項式と思えば, 2は0に, 3は1になりますのでR[x]と同じです.
    (実際には多項式の割り算を筆算で行うのと同様な方法で の世界で多項式の割り算を行います.(下を参照))
  4. このことは, R[x]が の原始既約多項式 で割り切れていること(割った余りが0であること), すなわち, 読み込み時の誤りがないことを検査出来たことを表わしています.
        1 1 1 0 0 1 1 1 0
      |--------------------------
10011 | 1 1 1 1 0 1 0 1 1 0 0 1 0 
        1 0 0 1 1
        ---------
          1 1 0 1 1 0 1 1 0 0 1 0
          1 0 0 1 1
          ---------
            1 0 0 0 0 1 1 0 0 1 0
            1 0 0 1 1
            ---------
                  1 1 1 1 0 0 1 0
                  1 0 0 1 1
                  ---------
                    1 1 0 1 0 1 0
                    1 0 0 1 1
                    ---------
                      1 0 0 1 1 0
                      1 0 0 1 1
                      ---------
                              0

QRコードサンプル

以下のホームページに掲載してあった, QRコードを拡大してみました.

ハイレベル合宿に戻る


添付ファイル: fileQRcode2.png 453件 [詳細] file形式情報.jpg 264件 [詳細] file明善高校.gif 460件 [詳細] file九大数理.jpg 396件 [詳細] file九州大学.jpg 426件 [詳細] fileTNCテレビ.gif 380件 [詳細]

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSSPDF
Last-modified: 2009-08-07 (金) 02:51:58 (3514d)