講義「情報理論」

講義「情報理論」

第９回 通信路のモデル

情報理工学部門 情報知識ネットワーク研究室 喜田拓也

非等長情報源系列の符号化（おさらい）

1, 0 を確率 0.2, 0.8 で発生する無記憶定常情報源 𝑆𝑆 を考える．

𝑆𝑆 から発生する系列を４つ選び，ハフマン符号化を行う．

(0.8)

0

1

0 1

(0.64)

0.16

0 1

0.512 0.128

情報源系列を分割する分節木

各ブロックの平均長 𝑛𝑛 は 𝑛𝑛 = 1 × 0.2 + 2 × 0.16

+3 × 0.128 + 3 × 0.512

= 2.44

情報源

系列 確率 ハフマン 符号

0 0 0 0.512 0

0 0 1 0.128 100 0 1 0 0.16 101 1 0 0 0.2 11

0.488

1 1

0 1 0

0

0.288 1.0

右の符号の平均符号長 𝐿𝐿𝐿 ＝ 1.776 よって 1 記号あたりの

平均符号長 𝐿𝐿 は 𝐿𝐿 ＝ 1.776

2.44 = 0.728

ひずみが許される場合の情報源符号化（おさらい）

この定理は， 1 情報源記号あたりの平均符号長を，速度・ひずみ

関数 𝑅𝑅 𝐷𝐷 にいくらでも近づく符号化法の存在を示している

具体的な符号化方法はあるのか？

ひずみのない場合に比べてはるかに難しい！

定理 ［ひずみが許される場合の情報源符号化定理］

平均ひずみ 𝑑𝑑 を 𝐷𝐷 以下に抑えるという条件の下で，任意の正数 𝜀𝜀 に対して，情報源 𝑆𝑆 を 1 情報源記号あたりの平均符号長 𝐿𝐿 が

𝑅𝑅 𝐷𝐷 ≤ 𝐿𝐿 < 𝑅𝑅 𝐷𝐷 + 𝜀𝜀

となるような 2 元符号へ符号化できる．しかし，どのような符号化を 行っても， 𝑑𝑑 ≤ 𝐷𝐷 である限り， 𝐿𝐿 をこの式の左辺より小さくすることは できない．

教科書【例

5.8

今日の内容

6.1 通信路の統計的表現

6.2 記憶のない定常通信路

6.3 加法的 2 元通信路

もう一度，情報理論の問題について

情報理論が取り組む４つの問題

【問題１】 できるだけよい情報源符号化法（復号法）を見出すこと

【問題２】 情報源符号化の限界を知ること

【問題３】 できるだけよい通信路符号化法（復号法）を見出すこと

【問題４】 通信路符号化の限界を知ること

デジタル 情報源

情報源 符号化

あて先

2元通信路 通信路

符号化

情報源 復号

通信路 復号 符号化

復号

誤りや ひずみ

通信路の統計的表現

雑音のある離散的通信路の定義：

時点毎に一つの記号が入力され，一つの記号が出力される 出力は入力から一意的に定まるのではなく，確率的に決まる！

𝑃𝑃

𝑦𝑦

, 𝑦𝑦

, … , 𝑦𝑦

𝑥𝑥

, 𝑥𝑥

, … , 𝑥𝑥

= [𝑋𝑋

= 𝑥𝑥

, 𝑋𝑋

= 𝑥𝑥

, … , 𝑋𝑋

= 𝑥𝑥

の条件の下で 𝑌𝑌

= 𝑦𝑦

, 𝑌𝑌

= 𝑦𝑦

, … , 𝑌𝑌

= 𝑦𝑦

となる確率 ] 入力 𝑋𝑋

, 𝑋𝑋

, … , 𝑋𝑋

に対する 𝑌𝑌

, 𝑌𝑌

, … , 𝑌𝑌

の確率分布

入力アルファベット 𝐴𝐴 = 𝑎𝑎

, 𝑎𝑎

, … , 𝑎𝑎

出力アルファベット 𝐵𝐵 = 𝑏𝑏

, 𝑏𝑏

, … , 𝑏𝑏

通信路

Communication channel

|𝐴𝐴| = |𝐵𝐵| = 𝑟𝑟 のときは， 𝑟𝑟 元通信路（ 𝑟𝑟 -ary channel ）という

𝑋𝑋

𝑌𝑌

記憶のない定常通信路 （ memoryless channel ）

各時点の出力の現れ方が，その時点の入力には関係するが，

それ以外の時点の入力・出力とは独立であるような通信路を，

記憶のない通信路という

さらに，時間をずらしても統計的性質が変わらないとき，これを 記憶のない定常通信路と呼ぶ

記憶のない定常通信路では，入力 𝑋𝑋 が通信路に投入されたとき に出力 𝑌𝑌 が出る条件付確率 𝑃𝑃

(𝑦𝑦|𝑥𝑥) が，すべての時点におい て同一である．したがって，

𝑃𝑃

𝑦𝑦

, … , 𝑦𝑦

𝑥𝑥

, … , 𝑥𝑥

= �

𝑖𝑖=0

𝑛𝑛−1

𝑃𝑃

𝑦𝑦

𝑥𝑥

.

通信路行列と通信路線図

𝑟𝑟 元入力アルファベット 𝐴𝐴 = {𝑎𝑎

, 𝑎𝑎

, … , 𝑎𝑎

} ， 𝑠𝑠 元出力アルファベット 𝐵𝐵 = {𝑏𝑏

, 𝑏𝑏

, … , 𝑏𝑏

} ， 入出力の関係が条件付確率 𝑝𝑝

= 𝑃𝑃

𝑏𝑏

𝑎𝑎

で与えられる記憶のない定常通信路を考える

𝑎𝑎 _𝑖𝑖 𝑏𝑏 _𝑖𝑖

入力 出力

𝑝𝑝 _{𝑖𝑖𝑖𝑖}

𝑇𝑇 =

𝑝𝑝 ₁₁ 𝑝𝑝 ₁₂

𝑝𝑝 ₂₁ 𝑝𝑝 ₂₂ ⋯ 𝑝𝑝 _1𝑠𝑠 𝑝𝑝 _2𝑠𝑠

⋮ ⋱ ⋮

𝑝𝑝 _𝑟𝑟1 𝑝𝑝 _𝑟𝑟2 ⋯ 𝑝𝑝 _{𝑟𝑟𝑠𝑠}

𝑝𝑝

を (𝑖𝑖 , 𝑗𝑗) 要素とする通信路行列

出力側

入力側

𝑎𝑎

𝑎𝑎

𝑎𝑎

・・・・・ ・・・・・・・・

𝑏𝑏

𝑏𝑏

𝑏𝑏

通信路線図

𝑝𝑝

𝑝𝑝

入力側 出力側

例題 6.1

𝑃𝑃(𝑥𝑥 |𝑦𝑦) 𝑦𝑦

𝑏𝑏

𝑏𝑏

𝑏𝑏

𝑥𝑥

𝑎𝑎

0.5 0.2 0.3

𝑎𝑎

0 0.6 0.4

𝑎𝑎

0.8 0.1 0.1

𝑇𝑇 = 0.5 0.2 0.3 0 0.6 0.4 0.8 0.1 0.1 通信路行列 𝑇𝑇

𝑎𝑎

𝑎𝑎

𝑏𝑏

𝑏𝑏

0.3

𝑏𝑏

0.2 0.5

𝑎𝑎

0.80.4 0.1 0.1

通信路線図 Try

6.1

一様な通信路

2 元対称通信路

2 元対称消失通信路

入力アルファベットは {0, 1}

出力アルファベットは {0, 1, ∅ }

（ ∅ は消失を表現）

0

1

0

1 − 𝑝𝑝 1 1 − 𝑝𝑝 𝑝𝑝 𝑝𝑝

0 1

𝑇𝑇 = ^{1 − 𝑝𝑝} _{𝑝𝑝 1 − 𝑝𝑝} ^𝑝𝑝 0 1

0

1

0

1 𝑝𝑝

𝑝𝑝 ∅

𝑝𝑝

𝑝𝑝

1 − 𝑝𝑝

− 𝑝𝑝

0 1

𝑇𝑇 = 0

𝑝𝑝 1

𝑝𝑝 1 − 𝑝𝑝

− 𝑝𝑝 𝑝𝑝

𝑝𝑝

1 − 𝑝𝑝

− 𝑝𝑝 ∅

2

入力に対して 一様

ちょっと休憩

加法的 2 元通信路

入力と出力のアルファベットが共に { 0 , 1 } である 2 元通信路は，

誤りの有無を用いて表すことができる

𝑡𝑡 時点での誤りを確率変数 𝐸𝐸

∈ { 0 , 1 } で表すと，

出力 𝑌𝑌

は入力 𝑋𝑋

に誤り 𝐸𝐸

を加えたものとみなせる 𝑌𝑌

= 𝑋𝑋

⨁𝐸𝐸

,

𝐸𝐸

= � 0 誤りなし

1 誤り発生

入力

0 →

0

入力

0 →

1 0 ⊕ 1 = 1

1 →

0 1 ⊕ 1 = 0

1 →

1

入力

𝑋𝑋

⊕

誤 り 源

𝑆𝑆

出力

𝑌𝑌

𝐸𝐸

𝑌𝑌

= 𝑋𝑋

⨁𝐸𝐸

2

図 6.3 加法的 2 元通信路モデル

ランダム誤り通信路

加法的 2 元通信路の誤り源 𝑆𝑆

が， 1 , 0 をそれぞれ確率 𝑝𝑝, 1 − 𝑝𝑝 で発 生させる記憶のない定常 2 元情報源とする．このとき， 0 から 1 への 誤りも， 1 から 0 への誤りも，他の時点の入出力とは無関係に確率 𝑝𝑝 で発生する．これは 2 元対称通信路に他ならない

このような誤りをランダム誤り（ random error ）という

誤りの発生確率 𝑝𝑝 をビット誤り率（ bit error rate ）と呼ぶ

入力

𝑋𝑋

⊕

1,0

𝑝𝑝, 1 − 𝑝𝑝

出力

𝑌𝑌

𝐸𝐸

∈ { 0 , 1 } 𝑌𝑌

= 𝑋𝑋

⨁𝐸𝐸

2

0

1

0

1 − 𝑝𝑝 1 1 − 𝑝𝑝 𝑝𝑝 𝑝𝑝

2

バースト誤り通信路

誤りが一度生じると，その後しばらくの間は連続して誤りが発生する と考えるモデル（誤り源に記憶がある代表的なモデル）

密集して生じる誤りをバースト誤り（ burst error ）と呼ぶ 例えば，誤り源から発信される系列が次のようになる

00000001111111000011110000 ・・・

入力

𝑋𝑋

⊕

記憶のある誤り源

（

1

出力

𝑌𝑌

𝐸𝐸

∈ { 0 , 1 }

𝑌𝑌

= 𝑋𝑋

⨁𝐸𝐸

2

s

s

0 / 1 − 𝑃𝑃 1 / 𝑃𝑃 0 / 𝑝𝑝

1 / 1 − 𝑝𝑝

図

6.4

𝑃𝑃

⇒バースト発生頻度が増大

𝑝𝑝

⇒バーストが短くなる

ソリッドバースト誤りの平均長

誤り系列における 1 の連続（ 1 のラン）を任意に一つ取り出す その長さが ℓ となる確率 𝑃𝑃

ℓ を求めると，

𝑃𝑃

ℓ = (1 − 𝑝𝑝)

𝑝𝑝 ℓ = 1, 2, ・・・

となる

バースト誤りの長さ（バースト長）の 平均値 ℓ は次のようになる

ℓ = ∑

ℓ𝑃𝑃

(ℓ)

= 𝑝𝑝 ∑

ℓ 1 − 𝑝𝑝

=

.

バースト長の分布の例

𝑝𝑝 = 0.1

最初の

1

1

ℓ – 1

最後に

0

手計算で求まります

・・・ 001111100 ・・・

ℓ

ソリッドバースト誤り源のビット誤り率（例題 6.2 ）

図 6.4 の誤り源の状態遷移行列 𝛱𝛱 は

𝛱𝛱 = 1 − 𝑃𝑃 𝑃𝑃

𝑝𝑝 1 − 𝑝𝑝

である．定常分布を 𝒘𝒘 = 𝑤𝑤

, 𝑤𝑤

とすると， 𝒘𝒘𝛱𝛱 = 𝒘𝒘 および 𝑤𝑤

+ 𝑤𝑤

= 1 から，

𝑤𝑤

= 𝑝𝑝

𝑃𝑃 + 𝑝𝑝 , 𝑤𝑤

= 𝑃𝑃

𝑃𝑃 + 𝑝𝑝 .

よって，誤り源の出力 𝐸𝐸 が 1 となる確率 𝑃𝑃

1 を求めると 𝑃𝑃

1 = 𝑤𝑤

𝑃𝑃 + 𝑤𝑤

1 − 𝑝𝑝 = 1

𝑃𝑃 + 𝑝𝑝 𝑝𝑝𝑃𝑃 + 𝑃𝑃 1 − 𝑝𝑝

= 𝑃𝑃

𝑃𝑃 + 𝑝𝑝 .

ビット誤り率

Try

6.2

その他のバースト誤りモデル

ギルバートモデル

Gilbert model

正誤が混在するバースト誤り 状態 B のときは 1 , 0 をそれぞれ ℎ, 1 − ℎ の確率で発生させる バースト長の期待値は 1/𝑝𝑝 ビット誤り率

𝑃𝑃+𝑝𝑝

フリッチマンモデル

Fritchman model

ギルバートモデルの 良状態を増やしたもの

G B

1 − 𝑃𝑃 𝑃𝑃

𝑝𝑝

1 − 𝑝𝑝

図 6.6 ギルバートモデル

誤り発生率

0

ℎ

G B

誤り発生率

0

ℎ

G ・・・・

今日のまとめ

6.1 通信路の統計的表現 6.2 記憶のない定常通信路

通信路行列と通信路線図

2 元対称通信路（ 2 重に一様な通信路）

2 元対称消失通信路（入力に対して一様な通信路）

6.3 加法的 2 元通信路

ランダム誤り通信路 ＝ 2 元対称通信路 バースト誤り通信路（ソリッドバースト）

ギルバートモデル，フリッチマンモデル

次回

通信路符号化の限界に関する理論

通信路にまつわる各種エントロピー

入力記号側のエントロピー：

𝐻𝐻 𝑋𝑋 = − �

𝑖𝑖=1 𝑟𝑟

𝑝𝑝 𝑎𝑎

log

𝑝𝑝 𝑎𝑎

𝐻𝐻 𝑌𝑌 = − �

𝑖𝑖=1 𝑠𝑠

𝑞𝑞 𝑏𝑏

log

𝑞𝑞 𝑏𝑏

𝐻𝐻 𝑋𝑋|𝑌𝑌 = − �

𝑖𝑖=1 𝑟𝑟

�

𝑖𝑖=1 𝑠𝑠

𝑞𝑞 𝑏𝑏

𝑝𝑝 𝑎𝑎

|𝑏𝑏

log

𝑝𝑝 𝑎𝑎

|𝑏𝑏

𝐻𝐻 𝑋𝑋, 𝑌𝑌 = − �

𝑖𝑖=1 𝑟𝑟

�

𝑖𝑖=1 𝑠𝑠

𝑝𝑝 𝑎𝑎

, 𝑏𝑏

log

𝑝𝑝 𝑎𝑎

, 𝑏𝑏

※入力 𝑋𝑋

𝑎𝑎

(𝑖𝑖 = 1, … , 𝑟𝑟)

𝑝𝑝 𝑎𝑎

𝑌𝑌

𝑏𝑏

(𝑗𝑗 = 1, … , 𝑠𝑠)

（付録） Tunstall-Huffman 符号の効率

練習問題 5.3 の条件のとき，タンストール木の大きさ（使う符号語の 数 𝑁𝑁 ）を 𝑁𝑁 = 5 としたときより 𝑁𝑁 = 6 とするほうが，１記号あたりの平 均符号語長が長くなる？

𝑁𝑁 = 5 のとき：

平均ブロック長 𝑛𝑛

= 2.36, ブロックあたりの平均符号長 ℓ𝐿

= 2.304 よって，１記号あたりの平均符号長 ℓ

≅ 0.97627

𝑁𝑁 = 6 のとき：

平均ブロック長 𝑛𝑛

= 2.60, ブロックあたりの平均符号長 ℓ𝐿

= 2.544 よって，１記号あたりの平均符号長 ℓ

≅ 0.97846

＜ あれぇ？

（付録） Tunstall-Huffman 符号の効率

実は，そういうことはありうる！！

何故なら，ハフマン符号が（ブロック毎に）２元符号化しているから

（例えば 3.4 個分の長さの符号語とか作れないから）

Tunstall 木を大きくすると平均ブロック長は長くなるが，ハフマン符

号化したときに１記号あたりの平均符号長が短くなるとは限らない 2001 年に理論的な解析結果が発表されていました！

Serap A. Savari and Wojciech Szpankowski, “On the Analysis of Variable-to- Variable Length Codes”

上記論文内の定理

2:

lim sup

𝑀𝑀→∞

log

𝑀𝑀 ⋅ 𝑅𝑅

𝑀𝑀 ≤ ℋ log

2 log

𝑒𝑒 𝑒𝑒 𝑀𝑀

ℋ

ℋ

𝑀𝑀 𝐿𝐿_𝑀𝑀

0.086ℋ

2