文字列照合アルゴリズム

1
北海道大学
Hokkaido University
情報エレクトロニクス学科共通科目・２年次・第１学期〔必修科目〕
講義「情報理論」
第11回
第7章通信路符号化の限界(1)
通信路符号化の基礎概念
通信路容量
2015/06/19
情報理論講義資料
北海道大学 Hokkaido University
2
通信路符号の基礎概念(1)
xの符号語
受信語
A
x’ Σ
wx
w’x A
b0b1・・・bkbk+1・・通信路符 a0a1・・・anan+1・・ r元通 a0a1・・・anan+1・・通信路 b b ・・・b b ・・
0 1
k k+1
号化
信路
復号
Σ:q元アルファベット
A:r元アルファベット



∈
∈
∈
Σ
∈
x
通信路符号化の目的: 信頼性の向上そのために→冗長性を付加
長さkのブロックx∈Σkを長さnの符号語wx∈Anに符号化
qk < rn : 符号語としてAnの一部のみ使用 (冗長性の付加）
[例]Σ={0,1}, k=1,A＝{0,1},n=3 とすれば、A3 は次の 23＝8 個の系列の集合となる
A3＝{000, 001, 010, 011, 100, 101, 110, 111}
この内、000 と 111 の二つだけを符号語として用いる
0 → 000,
1 → 111
このとき、送った符号語wxに１ビット誤りが生じた受信語w’xを受け取っても、
w’x内の３ビットの多数決により訂正可能
001, 010, 100 → 0,
110, 101, 011 → 1
2015/06/19
情報理論講義資料
北海道大学 Hokkaido University
3
通信路符号の基礎概念(2)


通信路符号（または符号）：An の中から選ばれた系列の集合 C
図は通信路符号による誤り訂正の概念図
受信空間
誤った復号
×
Ω2
復号領域
Ω1
正しく復号
w1
w4
×
Ω4
w3
×
推定不可能な
誤り検出
An
w2
符号語
Ω3
×
受信語
図（通信路符号の）復号の概念図
2015/06/19
情報理論講義資料
北海道大学 Hokkaido University
4
情報速度と冗長度



符号C(⊆An)に含まれる符号語の数をM（=qk)とする。
符号語を等確率で用いると、符号語の平均情報量はlog2Mビットとなるから
log2 M
R＝
（ビット／記号）
n
の速度で情報を伝達できることになる。この R をこの符号の情報伝送速度
または単に情報速度と呼ぶ。情報速度Rを用いれば、符号語数 M は
M＝2nR
An に含まれる rn 個の系列すべてを符号語とすれば、情報速度は最大値
Rmax ＝ (log2 rn) / n ＝ log2 r
となる。R＜Rmax とすることで、誤りの訂正や検出が可能となる。
情報速度 R の符号 C に対し、
すべての系列を使うと
誤りを検知できない
η＝R / Rmax
を、C の効率または符号化率（code rate）と呼ぶ。
これは、0＜η＜1 を満たす。また、
ρ＝1－η
冗長度≒信頼性
冗長度と効率はTrade-off
を C の冗長度という。
2015/06/19
情報理論講義資料
北海道大学 Hokkaido University
5
最尤復号法(1)



符号語 w1, w2,…, wM に対する復号領域 Ω1, Ω2,…, ΩM の定め方は？
PC：正しく復号される確率
最尤復号法=
(符号語が等確率で送られるとき)PC を最大にするような復号領域の定め方
符号語 wi を送ったとき
正しく復号される確率は
誤った復号
Ann
PC(wi)＝ ∑ P( y | wi )
となる。ただし
Ω2
y∈Ωi
Ω1
P( y | wi )：wi を送ったとき
y が受信される確率
とする。
2015/06/19
×
w2
w1
×
w3
正しく復号
×
推定不可能な
誤り検出
Ω3
情報理論講義資料
北海道大学 Hokkaido University
6
最尤復号法(2)

どの符号語が送られてくる確率も等しく 1/M であると仮定すると
正しく復号される確率PCは
M
PC＝∑ 1 ×PC(wi)＝1
i＝1 M
M
∑ ∑ P( y | wi)
Mi＝1
y∈Ωi
と書ける。これを最大にするには、
Ωi={y∈An | P( y | wi)≧P(y | wj) for all j＝1,…,M}
×
wi
×
×
×
×
×
y×
×
wj
×
とすればよい。実際、Ωi に属するある y に対し、
P( y | wi)＜P( y | wj)
となったとすれば、この y を Ωj に移すことで、P( y | wj)－P( y | wi)＞0 だけPC が増加。


y を受け取ってwi を推定する問題とすれば、P(y | wi) はwiの尤度である。
尤度を最大化する復号法を最尤度復号法（maximum likelihood decoding）と呼ぶ。
最尤度復号法は、各符号語が等確率で送られるとき、正しく復号される
確率 PC を最大とするという意味で、最良の復号法である。しかし、すべての
符号語 wi に対し、P(y | wi) を計算し比較しなければならず、符号語数 M が
大きい場合には、実用的ではない。
2015/06/19
情報理論講義資料
北海道大学 Hokkaido University
7
通信路容量の定義(1)
入力アルファベット
X
A＝{a1,a2,…,ar}の元
pi＝PX(ai)
記憶のない
定常通信路
Y
出力アルファベット
B＝{b1,b2,…,bs}の元
qj＝PY(bj)
通信路行列
T＝[pi j ], pi j ＝P(bj | ai )
図6.1 記憶のない定常通信路のモデル
相互情報量 I(X; Y) は、この通信路を介して伝送される
１記号あたりの平均情報量
 X と Y の間の相互情報量 I(X; Y) は

r
s
i＝1
j＝1
I(X; Y)＝∑ pi ∑ pi j log2(pi j /qj )
と書ける。ただし、
r
qj＝∑ pi pi j
T＝[pi j ] と
p1,…, pr から
計算できる
i＝1

この通信路で最大限どれだけの情報量が伝送できるだろうか？
2015/06/19
情報理論講義資料
北海道大学 Hokkaido University
8
通信路容量の定義(2)


T＝[pi j] は与えられるので、相互情報量 I(X; Y) は p1,…, pr に
依存して増減する。
入力確率分布を p＝( p1, p2,…, pr ) と置く。このとき、
C＝max{ I(X; Y) }
P
をこの通信路の通信路容量（channel capacity）と呼ぶ。

単位は、ビット（またはナット、ハートレー）。
あるいは、1記号あたりの情報量ということを明示するために
ビット/通信路記号などと書く。
通信路に記憶がある場合には、相互情報量の場合と同様、拡大の手法を
用いれば求められる。すなわち、長さ n の入力系列を Xn、出力系列を Yn
とし、pn を Xn の確率分布とすれば
C＝ lim
n→∞
max{I(Xn; Yn)/n }
pn
により定義される。
2015/06/19
情報理論講義資料
北海道大学 Hokkaido University
9
記憶のない一様通信路の通信路容量

入力について一様な記憶のない通信路の通信路容量を求める。まず、
I(X; Y)＝H(Y)－H(Y | X)
について、第2項目の H(Y | X) は
H(Y | X)＝∑ P(x) (－ ∑ P(y | x) log2P(y | x))
x
r
s
i＝1
s
j＝1
y
＝－∑ pi ∑ pi j log2 pi j
＝－∑ p1 j log2 p1 j
j＝1
入力に対して一様なので、
任意の i について2番目の和
は同じ値をとる
と書ける。したがって、通信路容量は、
C＝max{ I(X; Y) }＝max{ H(Y)－H(Y | X) }
P
s
P
＝max{ H(Y) }＋∑ p1 j log2 p1 j
P
通信路だけに
依存する部分
≦0
j＝1
となる。さらに、出力についても一様な場合（2重に一様な場合）、
入力の確率分布を p1＝p2＝・・・＝pr とすると、出力の確率分布も
q1＝q2＝・・・＝qs となり、H(Y) はその最大値 log2s をとる。したがって、
s
C＝log2s＋∑ p1 j log2 p1 j
j＝1
2015/06/19
情報理論講義資料
北海道大学 Hokkaido University
10
[例]２元対称通信路の通信路容量

ビット誤り率がpの2元対称通信路を考える。通信路行列は
1－p p
C
T＝
p 1－p
1
であり、2重に一様だから、通信路容量C は
C＝1＋ p log2 p ＋ (1－p)log2(1－p) 0.8
＝1－H(p)
0.6
となる（図）。
p＝0 では、誤りは全く生じないから、
0.4
C＝1（ビット/記号）となる。
p＝0.5 では、通信路の出力は入力と
0.2
独立になってしまい、情報は全く伝わらず
C＝0 となる。
0.2
0.4
0.6
0.8
1
p＝1 では、0 は必ず 1 になり、1 は必ず
p
0 になるから、出力側で 1, 0 を逆にすれば
図 2元対称通信路の通信路容量
全く誤りなく情報が伝達される。ゆえに、
C＝1（ビット/記号）となる。
2015/06/19
情報理論講義資料
北海道大学 Hokkaido University
11
加法的2元通信路の通信路容量
誤りの発生は入力とは独立

図のような加法的2元通信路を考える。
誤り源
記憶のない通信路の場合、X と Y の
E
相互情報量は、誤り源E を用いれば、
Y＝X  E
X
I(X; Y)＝H(Y)－H(Y | X)
＝H(Y)－H( X  E | X)
図加法的2元通信路
＝H(Y)－H(E | X)
通信路のみに依存する部分
＝H(Y)－H(E)
と書ける。よって通信路容量 C を求めるには、入力X の確率分布に関し、
H(Y) を最大にすればよい。ところが、PX(0)＝PX(1)＝1/2 とすれば、
E がどのようなものであっても、PY(0)＝PY(1)＝1/2 となる。このとき、
H(Y) はその最大値 1 をとる。したがって、通信路容量は
C＝1－H(E)
記憶のある場合にも
となる。
C=1−H(SE)
誤りがない場合に
誤り源の
が成り立つ。
伝達し得る最大の
エントロピーH(E)
⊕
2015/06/19
情報量
（ビット/記号）
情報理論講義資料
北海道大学 Hokkaido University
12
[例]誤り源がマルコフ情報源の場合

誤り源が図のマルコフモデルで
表されるものとする。このような誤り源SE 0 / 0.9
s0
のエントロピーは、
H(SE)＝P(s0)H(0.1)＋P(s1)H(0.8)
1 / 0.1
1 / 0.8
s1
0 / 0.2
図6誤り源のモデル
として求まる。ここに、 P(s0), P(s1) は
状態 s0, s1 の定常確率であり、それぞれ、2/3, 1/3 となる。これから、
H(SE)＝2/3×0.4690 ＋ 1/3×0.7219
＝0.5532
を得る。したがって、通信路容量C は、
C＝1－0.5532＝0.4467 （ビット/記号）
となる。
この通信路のビット誤り率は 1/3 なので、もし通信路に記憶がなく、
ランダムに誤りを発生するのであれば、C1＝1－H(1/3)＝0.0817（ビット/記号）
であり、0.4467 よりはるかに小さい。
2015/06/19
情報理論講義資料

Download Report