文字列照合アルゴリズム

1
北海道大学
Hokkaido University
情報エレクトロニクス学科共通科目・２年次・第１学期〔必修科目〕
講義「情報理論」
第12回
第7章通信路符号化の限界(2)
通信路符号化定理
通信システム全体としての情報伝達の限界
2015/07/3
情報理論講義資料
北海道大学 Hokkaido University
2
[復習]通信路符号の基礎概念(1)



∈
∈
∈

x’
Σ
∈
xの符号語
受信語
A
A
wx
w’x
b0b1・・・bkbk+1・・通信路符 a0a1・・・anan+1・・ r元通 a0a1・・・anan+1・・通信路
号化
信路
復号
Σ:q元アルファベット
A:r元アルファベット
Σ
x
b0b1・・・bkbk+1・・
通信路符号化の目的: 信頼性の向上そのために→冗長性を付加
長さkのブロックx∈Σkを長さnの符号語wx∈Anに符号化
qk < rn : 符号語としてAnの一部のみ使用 (冗長性の付加）
通信路符号（または符号）：An の中から選ばれた系列の集合 C
受信空間
誤った復号
×
復号領域
正しく復号
Ω1
推定不可能な
誤り検出
2015/07/3
w2
Ω2
w1
×
An
Ω4
w3
×
w4
Ω3
×
符号語
受信語
情報理論講義資料
北海道大学 Hokkaido University
3
[復習]情報速度と冗長度

符号Cの情報（伝達）速度 R：
R＝
log2 M
n
（ビット／記号）
符号Cを用いればどのくらいの速さで(
１記号あたり何ビットの）情報を伝達で
きるか
ただし Mは符号C(⊆An)に含まれる符号語の数
情報速度Rを用いれば、符号語数 M は
M＝2nR
情報速度の最大値
Rmax ＝ (log2 rn) / n ＝ log2 r
(An に含まれる rn 個の系列すべてを符号語とした場合)

R＜Rmax とすることで、誤りの訂正や検出が可能となる。
情報速度Rの符号C の効率(符号化率) η :
η＝R / Rmax
0＜η＜1
C の冗長度 ρ: ρ＝1－η
2015/07/3
情報理論講義資料
北海道大学 Hokkaido University
4
[復習]通信路容量の定義
入力アルファベット
A＝{a1,a2,…,ar}の元
pi＝PX(ai)
X
記憶のない Y
定常通信路
出力アルファベット
B＝{b1,b2,…,bs}の元
qj＝PY(bj)
通信路行列
T＝[pi j ], pi j ＝P(bj | ai )

記憶のない定常通信路の通信路容量(channel capacity) C:
C＝max{ I(X; Y) }
p
(ビット/記号)
ただし、maxはA上のすべての確率分布p＝( p1, p2,…, pr )で考える。

一般の定常通信路の通信路容量C:
その通信路を用いればど
のくらいの速さで(１記号あ
C＝ lim max{I(Xn; Yn)/n }
pn
n→∞
たり何ビットの）情報を伝
ただし、Xn、 Ynは長さ n の入力系列、出力系列を表し、達できるか
maxは Xn のすべての確率分布pnで考える。
2015/07/3
情報理論講義資料
北海道大学 Hokkaido University
5
通信路容量と情報速度の関係についての考察
情報速度R で符号化済み
入力アルファベット
A＝{a1,a2,…,a|A|}の元



ひずみ！
X
通信路
（通信路容量C ）
Y
出力アルファベット
B＝{b1,b2,…,b|B|}の元
通信路が伝送できる1記号あたりの情報量（通信路容量C：ビット／記号）は
通信路の統計的性質（通信路行列）から求められる。
冗長性を付加して情報を伝送した場合に、伝送できる1記号あたりの
情報量（情報速度R：ビット／記号）も分かった。
情報速度R ＜通信路容量C ならば、通信の信頼性を向上できそうだ！
– では、どのくらい信頼性を向上できるのか？
– R を C と比べて、どのくらい低くすれば良いだろうか？
2015/07/3
情報理論講義資料
北海道大学 Hokkaido University
6
通信路符号化定理
定理 7.4 ［通信路符号化定理（Shannonの第2符号化定理）］
通信路容量がC である通信路に対し、R＜C であれば、情報速度Rの符
号で復号誤り率がいくらでも小さいものが存在する。R＞C であれば、
そのような符号は存在しない。
証明
[後半の証明] R＞C であるとき、復号誤り率がいくらでも小さい符号が存在し
たとする。このとき、この通信路を通してR（ビット／記号）にいくらでも近い情報速
度で情報が伝送されることになる。これは通信路容量C は、通信路で伝送しうる
最大の情報速度という定義に矛盾する。
[前半の証明] 略。ランダム符号化（受信空間からの独立な無作為抽出をM(=2nR)
回繰り返すことによりM個の符号語を選択する符号化)によりできる符号の復号誤
り率の平均が、符号語長nをn→∞ とすれば0に近づくことを示す。平均が0に近づ
けば、平均以下のものが必ず存在するので、復号誤り率がいくらでも小さい符号
が存在する。
2015/07/3
情報理論講義資料
北海道大学 Hokkaido University
7
記憶のない通信路のランダム符号化指数


符号長を n→∞ とすると、いくらでも復号誤り率を小さくできることが判った。
それでは、符号長 n が有限であるとき、復号誤り率Pe はどのように 0 に
近づいていくだろうか？
定理 7.5
記憶のない定常通信路において、ランダム符号化により生成された符号
長n、情報速度Rの符号Cの復号誤り率の期待値EC( Pe(C)) は
EC( Pe(C)) ≦ 2－nEr(R)
を満たす。ただし、Er(R) はランダム符号化指数（random coding
exponent)と呼ばれる関数であり、次式で定義される。
Er(R) ＝ max{－ρR＋E0(ρ, p)}
0≦ρ≦1, p
ここに、p＝(p1,…, pr) であり、
s
r
E0(ρ, p)＝－log2 ∑ ∑ pi pij1/(1＋ρ)
である。
2015/07/3
1+ρ
j＝1 i＝1
情報理論講義資料
北海道大学 Hokkaido University
8
信頼性関数
系 7.1
記憶のない定常通信路において、復号誤り率が
Pe ≦ 2－nEr(R)
を満たす長さn,、情報速度Rの符号が存在する。
• ランダム符号化指数Er(R)はランダムに生成した情報速度Rの符号の復号誤
り率の期待値に対して成立
• 信頼性関数(reliability function) E(R):
情報速度Rのもっともよい符号の復号誤り率の収束速度を表す指標
-log 2 Pe* (n, R)
E(R) = lim
n®¥
n
Pe* (n, R) は長さn、情報速度Rの符号における復号誤り率の最
ただし、
小値を表すものとする。
• Er(R)≦E(R) が成立
2015/07/3
情報理論講義資料
北海道大学 Hokkaido University
9
2元対称通信路に対するランダム符号化指数
p をビット誤り率とするとき、
ì
ïï 1- R - 2 log 2 ( p + 1- p)
Er (R) = í *
p*
1- p*
*
ï p log 2 + (1- p )log 2
p
1- p
ïî
ただし
R0＝1－H(p1*)
(0 £ R £ R0 )
(R0 £ R £ C)
p
p =
p + 1- p
Er(R)

*
1
p* (p＜p*＜p1*)は
R＝1－H(p*)
を満たす値。
R
図: 2元対称通信路の
ランダム符号化指数
図に、p＝0.01 のときの Er(R) を示す。
2015/07/3
情報理論講義資料
北海道大学 Hokkaido University
10
通信の限界(1)
α記号／秒
情報源
S
符号化
情報源
符号化
β記号／秒
通信路
符号化
通信路
（通信路容量C ）
復号
あて先
情報源
復号
通信路
復号
図: 通信システムのモデル


情報源と通信路が与えられたとき、どこまで良い通信ができるだろうか？
図の通信システムにおいて、情報源のエントロピーは H(S) （ビット／情報
源記号）であり、通信路容量は C（ビット／通信路記号）である。さらに、情
報源から情報源記号が毎秒α個発生し、通信路では毎秒β個の通信路記
号が伝送されているとする。
2015/07/3
情報理論講義資料
北海道大学 Hokkaido University
11
通信の限界(2)
このとき、情報源からは
R＝αH(S) （ビット／秒）
の速度で情報が発生する。また、通信路容量は秒あたり
C＝βC
（ビット／秒）
となる。もし、
R＜C
ならば、任意に小さい誤り率で通報をあて先まで送ることができる。しかし、
R＞C
の場合は、ひずみが生じる。
 情報源S の速度・ひずみ関数を R(D) （ビット／情報源記号）とし、
αR(D*)＝C
を満たす D* を考える。さらに、εを任意の正数とし、平均ひずみ d が
D*＋ε以下になるという条件の下で、情報源S の出力系列を符号化
するものとする。

2015/07/3
情報理論講義資料
北海道大学 Hokkaido University
12
通信の限界(3)

このとき、1情報源記号あたりの平均符号長が R(D*) ［＞R(D*＋ε)］より
小さくなるような符号化ができる。その際の情報速度をR(D*＋ε) （ビット
／秒）とすると、これは、
R(D*＋ε)＜αR(D*)＝C
を満たす。よって、情報源S からの通報をD* に任意に近い平均ひずみで
送ることができる。
定理 7.6
情報速度R（ビット／秒）で発生する情報を、通信路容量C（ビット／秒）の
通信路を介して送るとき、R＜C であれば、任意に小さい誤り率で情報を伝
送できる。
また、R＞C であれば、情報源の速度・ひずみ関数の値がR(D*)＝C(ビッ
ト/秒)を満たす D* に対し、 D*に任意に近い平均ひずみで情報を伝送できる
が、 D* より小さい平均ひずみでは伝送できない。
2015/07/3
情報理論講義資料
北海道大学 Hokkaido University
13
例題7.3


1, 0 を 0.2, 0.8 の確率で発生する記憶のない情報源からの通報を、
ビット誤り率が0.1 の2元対称通信路を通して送るものとする。
情報源は1秒に1記号を発生し、通信路も1秒に1記号を伝送する。
（すなわち、α＝β＝1）
このとき、
R＝0.7219
（ビット／秒）
C＝0.5310
（ビット／秒）
となる。R＞C であるから、ひずみなしには通報を送れない。
ひずみ測度としてビット誤り率を使うと、この情報源の速度・ひずみ関数は
R(D)=H(PX(1)) − H(D)=H(0.2) − H(D)≒0.7219 − H(D) (ビット/秒)
であるからR(D*)=Cとすれば
H(D*)≒0.7219 − 0.5310=0.1909
よって
D*=H −1(0.1909)=0.0293
したがって復号誤り率の下限は0.0293である。
2015/07/3
情報理論講義資料

Download Report