文字列照合アルゴリズム

1
北海道大学
Hokkaido University
情報エレクトロニクス学科共通科目・2年次・第1学期〔必修科目〕
講義「情報理論」
第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に1ビット誤りが生じた受信語w’xを受け取っても、
w’x内の3ビットの多数決により訂正可能
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) は、この通信路を介して伝送される
1記号あたりの平均情報量
 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
[例]2元対称通信路の通信路容量

ビット誤り率が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
情報理論 講義資料