講義「情報理論」

講義「情報理論」

第１１回 通信路符号化の限界(2)

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

2019/7/24

通信路符号化の考え方 （おさらい）

通信路符号化は，入力される 𝑞𝑞 元記 号列を長さ 𝑘𝑘 毎に区切り，各ブロック に長さ 𝑛𝑛 の等長な 𝑟𝑟 元記号列を割り 当てることで行う

符号語どうしが受信空間（ 𝐴𝐴 ^𝑛𝑛 ）内で 十分に離れていれば，受信語に少し の誤りが含まれていても，それに近い 符号語へと推定できる

2

通信路 符号化

通信路 通信路 復号

長さ 𝑘𝑘

𝒙𝒙 ∈ Σ ^𝑘𝑘

長さ 𝑘𝑘

𝒙𝒙 ^′ ∈ Σ ^𝑘𝑘

長さ 𝑛𝑛

𝒘𝒘 _𝒙𝒙 ∈ 𝐴𝐴 ^𝑛𝑛

長さ 𝑛𝑛

𝒘𝒘 _𝒙𝒙 ^′ ∈ 𝐴𝐴 ^𝑛𝑛

冗長性 を付加

元の系列

符号語 受信語 を推定

通信路容量 （おさらい）

記憶のない定常通信路の通信路容量（定理 7.1 より）

𝐶𝐶 = max _𝑃𝑃

𝑋𝑋

∈𝐏𝐏 𝐼𝐼 𝑋𝑋; 𝑌𝑌

（単位は，ビットあるいはビット / 通信路記号）

2 元対称通信路の通信路容量： 𝐶𝐶 = 1 − ℋ 𝑝𝑝 通信路に記憶がある場合の通信路容量

拡大情報源を考える．すなわち，長さ 𝑛𝑛 の入力系列を 𝑋𝑋 _𝑛𝑛 ， 出力系列を 𝑌𝑌 _𝑛𝑛 とし， 𝑃𝑃 _{𝑋𝑋𝑛𝑛} を 𝑋𝑋 _𝑛𝑛 の確率分布とすれば，

𝐶𝐶 = lim _{𝑛𝑛→∞ 𝑃𝑃} max

𝑋𝑋𝑛𝑛

∈𝐏𝐏

1

𝑛𝑛 𝐼𝐼 𝑋𝑋 ^𝑛𝑛 ; 𝑌𝑌 _𝑛𝑛 .

加法的 2 元通信路の通信路容量： 𝐶𝐶 = 1 − 𝐻𝐻 𝐸𝐸

𝑝𝑝 は ビット誤り率

誤り源のエントロピー

𝐻𝐻(𝐸𝐸) （ビット / 記号）

今日の内容

7.3 通信路符号化定理

7.4 通信システム全体としての情報伝達の限界

4

通信路容量と情報速度の関係

通信路を使って伝送できる， 1 記号あたりの情報量の最大値は，

その通信路の通信路容量 𝐶𝐶 （ビット / 記号）

ある通信路符号化により，通信路に入力される符号語の 1 記号 あたりの平均情報量は，その符号の情報速度 𝑅𝑅 （ビット / 記号）

𝑅𝑅 を 𝐶𝐶 と比べて，どのくらい低くすれば良いだろうか？

それで，どのくらい信頼性を向上できるのか？

情報速度 𝑅𝑅 で符号化

送信側

𝐴𝐴 ＝ {𝑎𝑎

, 𝑎𝑎

, … , 𝑎𝑎

} 𝑝𝑝

＝ 𝑃𝑃

𝑎𝑎

受信側

𝐵𝐵 ＝ {𝑏𝑏

, 𝑏𝑏

, … , 𝑏𝑏

} 𝑞𝑞

＝ 𝑃𝑃

𝑏𝑏

通信路

（通信路容量 𝐶𝐶 ）

𝑋𝑋 𝑌𝑌

𝑝𝑝

= 𝑃𝑃 𝑏𝑏

𝑎𝑎

情報速度 𝑅𝑅 ＜ 通信路容量 𝐶𝐶 ならよさそうだ！

通信路符号化定理（定理 7.4 ）

6

定理 7.4 ［通信路符号化定理］

通信路容量 𝐶𝐶 である通信路に対し， 𝑅𝑅 < 𝐶𝐶 であれば，

情報速度 𝑅𝑅 の符号で復号誤り率がいくらでも小さいも のが存在する．しかし， 𝑅𝑅 > 𝐶𝐶 であれば，そのような 符号は存在しない．

通信路容量を超えない情報速度でなら，

いくらでも精度よく通信できる

ような符号法がある！！

※ Shannon の第 2 符号化定理とも呼ばれる

※でも具体的な符号の構成方法は分かっていない・・・

通信路符号化定理の意味するところ

ビット誤り率が 0.1 である 2 元対称通信路があるとする．

この通信路の通信路容量 𝐶𝐶 は

𝐶𝐶 = 1 − ℋ 0.1 ≈ 0.531 （ビット / 記号）．

2 元記号列を長さ 𝑘𝑘 のブロックに区切って，長さ 𝑛𝑛 の 2 元符号化する．

この符号の情報速度 𝑅𝑅 は 𝑅𝑅 = 𝑘𝑘/𝑛𝑛 となるが，定理より，

𝑘𝑘 𝑛𝑛 ⁄ < 0.531

となるような (𝑛𝑛, 𝑘𝑘) に対し，ほとんど誤りなく情報を伝達できる符号 が存在する．

つまり，元の系列の 𝑛𝑛 𝑘𝑘 ⁄ = 1 0.531 ⁄ ≈ 1.88 倍の長さになるように 冗長性を付加すれば， 10 ビットに平均して 1 回起こるビット誤りを，

ほとんどすべて訂正することができるような符号が存在する．

※ 実際の通信路のビット誤り率はもっと小さいので，必要な冗長性はごく小さい

通信路符号化定理の証明 （前半の概要）

定理は，符号の存在だけ保証している．

Shannon はこれをランダム符号化 (random coding) を用いて証明．

ランダム符号化とは，受信空間から独立な無作為復元抽出を 𝑀𝑀 回繰り返すことにより 𝑀𝑀 個の符号語を選ぶ符号化法である．

証明は，ランダム符号化によって作られる符号 C の復号誤り率 𝑃𝑃 _𝑒𝑒 (C) の期待値 𝐸𝐸 _C 𝑃𝑃 _𝑒𝑒 C を求め，情報速度 𝑅𝑅 と通信路容量 𝐶𝐶 に 対して， 𝑅𝑅 < 𝐶𝐶 のとき符号長 𝑛𝑛 を 𝑛𝑛 → ∞ とすれば， 𝐸𝐸 _C 𝑃𝑃 _𝑒𝑒 C → 0 となることを示すことによる．

これが示されれば，復号誤り率が期待値以下となるような符号は 必ず一つは存在する．この事実から定理の前半は証明される．

※ 詳しくは教科書 7.6 節を参照

8

通信路符号化定理の証明 （後半）

情報速度が 𝑅𝑅 > 𝐶𝐶 の符号で，復号誤り率 𝑃𝑃 _𝑒𝑒 をいくらでも 小さくできるものが存在すると仮定する．

すると，実際に， 𝑅𝑅 にいくらでも近い速度で情報を伝達す ることができる．

すなわち，通信路容量 𝐶𝐶 を超えた情報速度で情報を送 ることができることになる．

通信路容量の定義からこれは不可能である．

よって，そのような符号は存在しない．【証明終】

ちょっと休憩

10

もう一度，通信システムのモデル

エントロピー 𝐻𝐻(𝑆𝑆) （ビット／情報源記号）の情報源 𝑆𝑆 ， 通信路容量 𝐶𝐶 （ビット／通信路記号）の通信路を考える

情報源から情報源記号が毎秒 𝛼𝛼 個発生し，通信路では毎秒 𝛽𝛽 個の

𝛼𝛼 記号／秒

𝛽𝛽 記号／秒

与えられた情報源と通信路に対しどれだけ良い通信ができるか？

𝐻𝐻 (𝑆𝑆)

𝐶𝐶

この通信システムで伝送できる限界は？

このとき，情報源から発生する秒あたりの情報量は，

𝓡𝓡 = 𝛼𝛼𝐻𝐻(𝑆𝑆) （ビット／秒）．

一方，秒あたり通信路容量は

𝐂𝐂 = 𝛽𝛽𝐶𝐶 （ビット／秒）．

したがって，

𝓡𝓡 < 𝐂𝐂

ならば任意に小さい誤り率で通信することができる．しかし，

𝓡𝓡 > 𝐂𝐂

の場合は，ひずみが生じてしまう．

12

𝓡𝓡 > 𝐂𝐂 の場合どのくらいひずむのか？

情報源 𝑆𝑆 の速度・ひずみ関数を 𝑅𝑅(𝐷𝐷) （ビット／情報源記 号）とすると，平均ひずみが 𝐷𝐷 以下という条件の下で，秒 あたりの情報量を

𝓡𝓡 𝐷𝐷 = 𝛼𝛼𝑅𝑅 𝐷𝐷 まで落とすことができる．

このとき， 𝓡𝓡 𝐷𝐷 _∗ = 𝐂𝐂 を満たす 𝐷𝐷 _∗ を考える．すると， 𝐷𝐷 _∗ より も 𝜀𝜀 だけ多くの平均ひずみを許せば，情報速度

𝓡𝓡 𝐷𝐷 _∗ ＋ 𝜀𝜀 < 𝓡𝓡 𝐷𝐷 _∗ = 𝐂𝐂 の符号化を作ることができる．

すなわち，情報源 𝑆𝑆 からの情報を， 𝐷𝐷 _∗ に任意に近い平均

ひずみで送ることができる．

通信システム全体としての情報伝達の限界

14

定理 7.6

情報速度 𝓡𝓡 （ビット／秒）で発生する情報を通信路容量 𝐂𝐂 （ビット

／秒）の通信路を介して送るとき，

𝓡𝓡 < 𝐂𝐂

であれば，任意に小さい誤り率で情報を伝送できる．また，

𝓡𝓡 > 𝐂𝐂

であれば，情報源の速度・ひずみ関数が

𝓡𝓡 𝐷𝐷 _∗ = 𝐂𝐂 （ビット／秒）

を満たす 𝐷𝐷 _∗ に対し， 𝐷𝐷 _∗ に任意に近いひずみで情報を伝送できる

が， 𝐷𝐷 _∗ より小さい平均ひずみでは伝送できない．

例題 7.3

1, 0 を 0.2, 0.8 の確率で発生する記憶のない情報源の出力系列を，

ビット誤り率が 0.1 の2元対称通信路を通して送る．情報源は1秒に1 記号を発生し，通信路も1秒に1記号を伝送する．このとき，

𝓡𝓡 = ℋ 0.2 ≈ 0.7219 （ビット／秒）, 𝐂𝐂 = 1 − ℋ 0.1 ≈ 0.5310 （ビット／秒）.

𝓡𝓡 > 𝐂𝐂 なので，ひずみなしには通報を送れない．

ひずみ測度として 𝑑𝑑 𝑥𝑥, 𝑦𝑦 = � 0 ; 𝑥𝑥 = 𝑦𝑦

1 ; 𝑥𝑥 ≠ 𝑦𝑦 を用いる．

このとき，速度・ひずみ関数は右図の 𝑝𝑝 = 0.2 の場合となる．これより 𝐷𝐷 _∗ = 0.0293 が求まる．

∵ 𝛼𝛼𝑅𝑅 𝐷𝐷

= 𝐂𝐂 ⟹ 𝑅𝑅 𝐷𝐷

= 0.5310

⟹ ℋ 0.2 − ℋ 𝐷𝐷

= 0.5310

⟹ ℋ 𝐷𝐷

= 0.7219 − 0.5310 = 0.1909

⟹ 𝐷𝐷

= ℋ

0.1909 = 0.0293 .

速度・ひずみ関数 𝑅𝑅(𝐷𝐷)

p=0.5 p=0.2 p =0.1

R(D)

0.0293 D 0.531

すなわち，

𝛼𝛼 = 𝛽𝛽 = 1

今日のまとめ

通信路符号化定理

通信路符号化定理（ Shannon の第 2 符号化定理）

ランダム符号化法による証明 符号語長が有限の場合の限界

信頼性関数 通信の限界

通信の理論的限界 次回

（具体的な）通信路符号化法について

16

符号長 𝑛𝑛 が有限のときの 𝑃𝑃 _𝑒𝑒 の収束の速さ

符号長 𝑛𝑛 を無限大にすると，いくらでも復号誤り率を小さくできる．

𝑛𝑛 が有限のとき，復号誤り率 𝑃𝑃 _𝑒𝑒 はどのように 0 に近づくだろうか？

定理 7.5

記憶のない通信路に対し，ランダム符号化による符号長 𝑛𝑛 ，情報 速度 𝑅𝑅 の符号 C の復号誤り率 𝑃𝑃 _𝑒𝑒 の期待値 𝐸𝐸 _C 𝑃𝑃 _𝑒𝑒 (C) は，

𝐸𝐸 _C 𝑃𝑃 _𝑒𝑒 (C) ≤ 2 ^{−𝑛𝑛𝐸𝐸}

^𝑅𝑅

を満たす．ただし， 𝐸𝐸 _𝑟𝑟 (𝑅𝑅) は次式で定義される．

𝐸𝐸 _𝑟𝑟 𝑅𝑅 ＝ _𝑃𝑃 max

𝑋𝑋

,0≤𝜌𝜌≤1 𝐸𝐸 ₀ 𝜌𝜌, p － 𝜌𝜌𝑅𝑅

ここに， 𝑃𝑃 _𝑋𝑋 は入力アルファベット上の分布であり，

𝐸𝐸 ₀ 𝜌𝜌, 𝑝𝑝 = − log ₂ ∑ _{𝑦𝑦∈𝐵𝐵} ∑ _{𝑥𝑥∈𝐴𝐴} 𝑃𝑃 _𝑋𝑋 𝑥𝑥 𝑃𝑃 𝑌𝑌 𝑋𝑋 𝑦𝑦 𝑥𝑥

^1+𝜌𝜌 である．

𝜌𝜌 は冗長度

Gallager 関数

ランダム符号化

指数

符号長 𝑛𝑛 ，情報速度 𝑅𝑅 の最適な符号法は？

では，最も良い符号の収束速度はいくらなのか？

𝑃𝑃 _𝑒𝑒 ^∗ (𝑛𝑛, 𝑅𝑅) を長さ 𝑛𝑛 ，情報速度 𝑅𝑅 の符号の中での復号誤り率の最小 値とする．それを達成する符号の収束速度 𝐸𝐸 𝑅𝑅 は，

𝐸𝐸 𝑅𝑅 = lim _{𝑛𝑛→∞} −log ₂ 𝑃𝑃 _𝑒𝑒 ^∗ 𝑛𝑛, 𝑅𝑅 𝑛𝑛 ⁄

で与えられる．これは信頼度関数（ reliability function ）と呼ばれる．

しかし，そのような符号の実際的な構成方法は知られていない．

LDPC

: Robert G. Gallager (1963

)

ターボ符号

: C. Berrou, A. Glavieux, P. Thitimajshima (1993

)

信頼度関数を計算するのは，一般には難しい．

系 7.1

記憶のない通信路において，復号誤り率 𝑃𝑃 _𝑒𝑒 が，

𝑃𝑃 _𝑒𝑒 ≤ 2 ^{−𝑛𝑛𝐸𝐸}

^𝑅𝑅

を満たす長さ 𝑛𝑛 ，情報速度 𝑅𝑅 の符号が存在する．

限界に迫る

符号化！

2 元対称通信路に対する信頼度関数

𝑝𝑝 をビット誤り率とするとき，

𝑝𝑝 ₁ ^∗ = 𝑝𝑝 ⁄ 𝑝𝑝 + 1 − 𝑝𝑝

となる 𝑝𝑝 ₁ ^∗ を求め， 𝑅𝑅 ₀ = 1 − ℋ 𝑝𝑝 ₁ ^∗ と おけば， 0 ≤ 𝑅𝑅 ≤ 𝑅𝑅 ₀ となる情報速度 𝑅𝑅 に対しては

𝐸𝐸 𝑅𝑅 = 1 − 𝑅𝑅 − 2 log ₂ 𝑝𝑝 + 1 − 𝑝𝑝 . また， 𝑅𝑅 ₀ ≤ 𝑅𝑅 ≤ 𝐶𝐶 = 1 − ℋ 𝑝𝑝 となる 𝑅𝑅 に 対しては，まず，

𝑅𝑅 = 1 − ℋ 𝑝𝑝 ^∗

を満たす 𝑝𝑝 ^∗ 𝑝𝑝 < 𝑝𝑝 ^∗ < 𝑝𝑝 ₁ ^∗ を求め，

𝐸𝐸 𝑅𝑅 = 𝑝𝑝 ^∗ log ₂ ^𝑝𝑝 _𝑝𝑝

+ 1 − 𝑝𝑝 ^∗ log ₂ ^1−𝑝𝑝 _1−𝑝𝑝

とすればよい．右図に， 𝑝𝑝 = 0.01 のときの 𝐸𝐸(𝑅𝑅) を示す．

2 元対称通信路の 信頼度関数

𝐸𝐸(𝑅𝑅)

𝑅𝑅

𝑝𝑝

は

𝑅𝑅 の関数