QRコードを作ろう！

富山大学公開講座 2008
「QRコードを作ろう！」
～ハミング距離～
講師：幸山直人
富山大学公開講座 2008 「QRコードを作ろう！」
シャノンの情報理論
情報を確率的概念として定義
 情報を定量化するために情報量を定義
（情報量の単位としてビットを導入）
 情報源を定義し、情報源が発する情報量を
計算できること
 通信系のモデルを示し、通信路容量を定義し、
この通信路容量を超えなければ適当な符号
化により誤りなしに伝達が可能であること

誤り訂正符号
富山大学公開講座 2008 「QRコードを作ろう！」
シャノンの通信系のモデル
誤りを訂正するための符号語の付加
情報
情報源
符号語
符号器
誤りの検出と訂正
受信語
通信路
推定情報
復号器
誤りパターン
雑音
あて先
富山大学公開講座 2008 「QRコードを作ろう！」
誤りの検出と訂正の原理
情報
Ak
送信空間
Bn
f
（誤り訂正コード語の付加）
A＝B＝C＝D，k＜n
受信空間
Cn
g
推定情報
Dk
h
（誤り訂正と推定情報の抽出）
（誤りパターンの付加）
富山大学公開講座 2008 「QRコードを作ろう！」
ハミング距離の例
例1：
u＝(0,1,1,0,1,0,1,0,0)
v＝(0,1,0,0,1,0,1,1,0)
9
dH（u,v）＝   (ui , vi ) ＝0+0+1+0+0+0+0+1+0＝2
i 1
例2：
u＝(a,b,d,c,a,d,d,c,b,a)
v＝(b,b,d,c,d,d,d,a,b,d)
10
dH（u,v）＝   (ui , vi ) ＝1+0+0+0+1+0+0+1+1+0＝4
i 1
富山大学公開講座 2008 「QRコードを作ろう！」
ハミング距離の誤りの検出と訂正（1）
t0
t1
t1
dmin
t0
富山大学公開講座 2008 「QRコードを作ろう！」
ハミング距離の誤りの検出と訂正（2）
t2
t1
t1
dmin
富山大学公開講座 2008 「QRコードを作ろう！」
最小距離に関する定理
定理：誤り訂正符号 X（⊂Cn）の最小距離 dmin が
dmin≧2t+1
を満たすなら、符号 Xはt個の誤りを訂正可能な符号である
t
c
r
dmin
c’
t
富山大学公開講座 2008 「QRコードを作ろう！」
ハミング距離による誤り訂正符号（1）
どのように対応させれば良いのだろうか？
Ak
(0)
(1)
A＝B＝{0,1}，k＝1
Bn（＝Cn）
富山大学公開講座 2008 「QRコードを作ろう！」
ハミング距離による誤り訂正符号（2）
A＝B＝{0,1}，k＝1 ，n＝3
(0)→(0,0,0)
(1)→(1,0,0)
A＝B＝{0,1}，k＝1 ，n＝3
(0)→(0,0,0)
(1)→(1,1,0)
(1,0,1)
(0,1,0)
(0,0,0)
(1,1,1)
(0,0,0)
(1,0,0)
(0,0,1)
(0,1,0)
(1,0,0)
(1,1,0)
ハミング距離が1しかなく、
誤りの検出しかできない
(1,1,0)
(0,0,1)
ハミング距離は2あるが、
誤りの検出しかできない
富山大学公開講座 2008 「QRコードを作ろう！」
ハミング距離による誤り訂正符号（3）
A＝B＝{0,1}，k＝1 ，n＝3
(0)→(0,0,0)
(1)→(1,1,1)
最小距離：3
(0,1,0)
(0,1,1)
(1,0,0)
(0,0,0)
(0,0,1)
(1,1,1)
(1,1,0)
誤った受信語は誤りのない受信語（円の中心）
に誤り訂正することができる
(1,0,1)
富山大学公開講座 2008 「QRコードを作ろう！」
ハミング距離による誤り訂正符号（4）
A＝B＝{0,1}，k＝1 ，n＝3
(0)→(0,1,0)
(1)→(1,0,1)
最小距離：3
(0,1,1)
(1,1,1)
(1,1,0)
(0,1,0)
(0,0,0)
(1,0,1)
(1,0,0)
「ハミング距離による誤り訂正符号（3）」に
同型な誤り訂正符号である
(0,0,1)
富山大学公開講座 2008 「QRコードを作ろう！」
ハミング距離による誤り訂正符号（5）
A＝B＝{0,1}，k＝1 ，n＝5
最小距離：3
(0)→(0,0,0,0,0)
(1)→(1,1,1,0,0)
(0,0,0,0,1)
(0,1,0,0,0)
(1,1,1,0,1)
(0,1,1,0,0)
(0,0,0,0,0)
(1,0,1,0,0)
(1,0,0,0,0)
(1,1,1,0,0)
(0,0,1,0,0)
(0,0,0,1,0)
(1,1,1,1,0)
(1,1,0,0,0)
誤った受信語は誤りのない受信語（円の中心）
に誤り訂正することができるが、無駄が多い
富山大学公開講座 2008 「QRコードを作ろう！」
ハミング距離による誤り訂正符号（6）
A＝B＝{0,1}，k＝1 ，n＝5
最小距離：4
(0)→(0,0,0,0,0)
(1)→(1,1,1,1,0)
(0,0,0,0,0)
(1,1,1,1,0)
黒色の点で表された受信語は、(0,0,0,0,0)と(1,1,1,1,0)
からのハミング距離が2の受信語があるため、どちらにも訂正
することができない（誤りの検出はできる）
富山大学公開講座 2008 「QRコードを作ろう！」
ハミング距離による誤り訂正符号（7）
A＝B＝{0,1}，k＝1 ，n＝5
最小距離：5
(0)→(0,0,0,0,0)
(1)→(1,1,1,1,1)
(0,0,0,0,0)
(1,1,1,1,1)
理想的な誤り訂正符号
（同型な誤り訂正符号がたくさんある）
富山大学公開講座 2008 「QRコードを作ろう！」
ハミング距離による誤り訂正符号（8）
誤り訂正符号を効率的に構成できないか？
最小距離はいくつになるのか？
Ak
(0,0)
(0,1)
(1,0)
(1,1)
A＝B＝{0,1}，k＝2
Bn（＝Cn）
富山大学公開講座 2008 「QRコードを作ろう！」
誤り訂正符号を如何に構成するか
誤り訂正符号を効率よく構成したい
⇒ 送信語を計算で求めたい
 最小距離を正確に求めたい
 誤りの検出を計算で行ないたい
 誤りの訂正を計算で行ないたい

線形符号

Download Report