後半第６回講義資料 Second part, Lecture notes 6

通信工学概論

Introduction to Communication Engineering

後半第６回講義資料

Second part, Lecture notes 6

情報量

Shannon Entropy

豊橋技術科学大学

Toyohashi University of Technology

電気・電子情報工学系

Department of Electrical and Electronic Information Engineering

准教授 竹内啓悟

Associate Professor Keigo Takeuchi

情報とは何か？(What is information?)

情報理論では、情報が何を表現しているかは議論しない。

情報を表現するのに必要な文字列の長さを議論する。

In information theory, we do not discuss what information represents. We discuss the length of a string required for representing the information.

Q1：豊橋技術科学大学を卒業しましたか？(Did you graduated from TUT?)

A1：0

Q2：あなたは今日の朝食でご飯を食べましたか？(Did you eat rice this morning? )

A1：1

A1の方が重要な質問に対する答えであるが、質問はどちらも二択なので、

答えの情報量はどちらも同じとみなす。

A1 is an answer to more important question than A2. However, the answers have the same amount of information as each other since both questions are two choices.

はい(Yes)=0、いいえ(No)=1

算術符号化(Arithmetic coding)

0または1を取る長さ２の二進系列𝑺を考える。ただし、各位置で0が発生する 確率を2/3とし、異なる位置の数字は独立に発生するものとする。

Consider a binary sequence 𝑺 of length 2 that takes 0 or 1. Assume that 0 occurs with probability 2/3in each position and that 0 or 1 occurs independently in different positions.

区間分割(Interval division)

0 2 1

3

0𝑎 0𝑏 1𝑎 1𝑏

0 4 1

9

6 9

8 9

00 01 10 11

系列の発生確率が対応する区間の長さに等しくなるように分割する。

The occurrence probability of each sequence is equal to the length of the corresponding interval.

算術符号化(Arithmetic coding)

符号化(Encoding)

各入力系列𝒔に対して、𝑚_𝒔 = − log₂ ℙ 𝑺 = 𝒔 + 1とする。 𝒔の符号語とし て、対応する区間の中点の２進数表現を𝑚_𝒔ビットで打ち切ったものを選ぶ。

⌈𝑎⌉は実数𝑎以上の最小の整数(⌈𝑎⌉is the minimum integer greater than or equal to 𝑎.) For each input sequence 𝒔, let 𝑚_𝒔 = ⌈− log₂ℙ(𝑺 = 𝒔)⌉ + 1. As a codeword of 𝒔, we select the sequence obtained by truncating the binary representation of the midpoint in the corresponding interval up to 𝑚_𝒔 bits.

復号

Decoding

各符号語が対応する区間に入っていれば、復号できる。(詳細省略)

If each codeword is included into the corresponding interval, decoding is possible.

平均符号長𝔼[𝐿](Average code length 𝔼[𝐿])

𝔼 𝐿 = ෍

𝒔

𝑚_𝒔ℙ 𝑺 = 𝒔 ≤ − ෍

𝑖=1,2

෍

𝑠_𝑖=0,1

ℙ(𝑆_𝑖 = 𝑠_𝑖)log₂ ℙ(𝑆_𝑖 = 𝑠_𝑖) + 2 𝑺 = 𝑆₁𝑆₂、𝒔 = 𝑠₁𝑠₂とすると、ℙ 𝑺 = 𝒔 = ℙ 𝑆₁ = 𝑠₁ ℙ(𝑆₂ = 𝑠₂)なので、

For 𝑺 = 𝑆₁𝑆₂ and 𝒔 = 𝑠₁𝑠₂, we have ℙ 𝑺 = 𝒔 = ℙ 𝑆₁ = 𝑠₁ ℙ(𝑆₂ = 𝑠₂). Thus,

不等式の導出で 𝑎 ≤ 𝑎 + 1を使った。(In the derivation of the inequality, 𝑎 ≤ 𝑎 + 1 has been used.)

算術符号化(Arithmetic coding)

符号語が対応する区間に含まれていることを確認せよ。

Confirm that each codeword is included into the corresponding interval.

入力、符号語、区間を入力の発生確率が大きい順にそれぞれ𝒔⁽¹⁾, … , 𝒔⁽⁴⁾、 𝑐₁, … , 𝑐₄、 𝐿₁, 𝑅₁ , … , [𝐿₄, 𝑅₄)とする。𝑐_𝑖 > 𝐿_𝑖を証明したい。

𝐿_𝑖 + 𝑅_𝑖

2 − 𝑐_𝑖 < ෍

𝑗=𝑚𝒔(𝑖)+1

∞

2^−𝑗 = 2^{−𝑚𝒔(𝑖)} = 2^{− − log2 ℙ 𝑺=𝒔(𝑖) +1} ≤ ℙ(𝑺 = 𝒔^(𝑖)) 2

𝑚_𝒔(𝑖)を２進数表現𝑐_𝑖 = 0. 𝑏₁^(𝑖) ⋯ 𝑏_𝑚

𝒔(𝑖)

(𝑖) のビット長とすると、𝑐_𝑖の定義から、

Let 𝒔⁽¹⁾, … , 𝒔⁽⁴⁾, 𝑐₁, … , 𝑐₄, and 𝐿₁, 𝑅₁ , … , [𝐿₄, 𝑅₄)denote the inputs, codewords, and intervals arranged in descending order with respect to the input occurrence probability, respectively. Prove 𝑐_𝑖 > 𝐿_𝑖. Let 𝑚_𝒔(𝑖) be the bit length of the binary representation 𝑐_𝑖 = 0. 𝑏₁^(𝑖)⋯ 𝑏_𝑚

𝒔(𝑖)

(𝑖) . From the definition of 𝑐_𝑖,

区間の長さ𝑅_𝑖 − 𝐿_𝑖 = ℙ 𝑺 = 𝒔^(𝑖) を使うと、

Using the interval length 𝑅_𝑖 − 𝐿_𝑖 = ℙ 𝑺 = 𝒔^(𝑖) yields

∵ − 𝑎 ≤ −𝑎 for 𝑎 > 0

𝑐_𝑖 > 𝐿_𝑖 + 𝑅_𝑖

2 − ℙ 𝑺 = 𝒔^(𝑖)

2 = 𝐿_𝑖 + 𝑅_𝑖

2 − 𝑅_𝑖 − 𝐿_𝑖

2 = 𝐿_𝑖 ∎

情報量(The amount of information)

長さ𝑁の独立同一分布する入力ビット系列𝑺 = 𝑆₁ ⋯ 𝑆_𝑁の場合に 算術符号化を適用すると、平均符号長𝔼[𝐿_𝑁]は以下を満たす。

Applying the arithmetic coding to an independent and identically distributed input bit sequence 𝑺 = 𝑆₁⋯ 𝑆_𝑁 of length 𝑁, we find that the average code length 𝔼[𝐿_𝑁] satisfies

1

𝑁𝔼 𝐿_𝑁 ≤ − ෍

𝑠=0,1

ℙ 𝑆₁ = 𝑠 log₂ ℙ 𝑆₁ = 𝑠 + 2

𝑁 → 𝐻 𝑆₁ as 𝑁 → ∞ エントロピー(Entropy)

離散確率変数𝑋に対して、𝑋のエントロピー𝐻(𝑋)を以下で定義する。

For a discrete random variable 𝑋, the entropy 𝐻(𝑋) of 𝑋 is defined as

𝐻 𝑋 = − ෍

𝑥

ℙ 𝑋 = 𝑥 log₂ ℙ 𝑋 = 𝑥 , 0 log₂ 0 = 0

総和は𝑥の取りうる値全体に及ぶ。(The summation is over all possible values of 𝑥.)

順定理(Direct theorem)

情報量(The amount of information)

エントロピーの意味(Meaning of the entropy)

逆定理(Converse theorem)

いかなる符号化をしても、平均符号長𝔼[𝐿_𝑁]は以下の不等式を満たす。

For any coding method, the average code length 𝔼[𝐿_𝑁] satisfies the following inequality:

𝑁→∞lim 1

𝑁𝔼[𝐿_𝑁] ≥ 𝐻(𝑆₁)

証明は情報理論の講義を参照(Learn Information Theory for the proof.)

エントロピーは、独立同一分布する無限に長いビット系列を圧縮した ときの圧縮率の理論限界に等しい。

The entropy is equal to the theoretical limit of the compression rate in compressing an infinitely long bit sequence that has independent and identically distributed elements.

エントロピーはデータの本質的な情報量（不確かさ）を表す。

The entropy means the amount of essential information (uncertainty) on data.

順定理と逆定理を合わせて、情報源符号化定理と呼ばれる。

The combination of the direct and converse theorems is called source coding theorem.

その他の情報量(The other amount of information)

𝑌が与えられたときの離散確率変数𝑋の条件付きエントロピーを以下で定義する。

The conditional entropy of a discrete random variable 𝑋 given 𝑌 is given by

𝐻 𝑋 𝑌 = 𝔼 𝐹 𝑌 ,

𝐹 𝑦 = 𝐻 𝑋 𝑌 = 𝑦 = − ෍

𝑥

ℙ 𝑋 = 𝑥 𝑌 = 𝑦 log₂ℙ(𝑋 = 𝑥|𝑌 = 𝑦) 意味(Meaning)

条件付きエントロピーは、𝑌を観測したときの𝑋に関する不確かさを表す。

The conditional entropy means the amount of uncertainty on 𝑋 when 𝑌 has been observed.

相互情報量(Mutual information)

条件付きエントロピー(Conditional entropy)

𝐼 𝑋; 𝑌 = 𝐻 𝑋 − 𝐻(𝑋|𝑌)

𝑌を観測したときに𝑋に関して得られる情報量

連続の場合 (The continuous case)

微分エントロピー(Differential entropy)

連続確率変数𝑋に対して、(For a continuous random variable 𝑋,)

ℎ 𝑋 = − න

−∞

∞

𝑝_𝑋 𝑥 log₂ 𝑝_𝑋 𝑥 𝑑𝑥 , 0 log₂ 0 = 0

微分エントロピーにエントロピーのような操作的な意味はない。

The differential entropy does not have operational meaning such as entropy.

条件付き微分エントロピー(Conditional differential entropy)

ℎ 𝑋 𝑌 = 𝔼 𝑓 𝑌 ,

𝑓 𝑦 = ℎ 𝑋 𝑌 = 𝑦 = − න

−∞

∞

𝑝_𝑋|𝑌 𝑥 𝑦 log₂ 𝑝_𝑋|𝑌(𝑥|𝑦) 𝑑𝑥 相互情報量(Mutual information)

𝐼 𝑋; 𝑌 = ℎ 𝑋 − ℎ(𝑋|𝑌)

離散の場合と同じ意味(The same meaning as the discrete case)

エントロピーの計算(Computation of entropy)

例２.６.１(Example 2.6.1)

離散確率変数𝑋は、確率𝑝で0を取り、確率1 − 𝑝で1を取るとする。𝑋の エントロピーを計算せよ。さらに、エントロピーが最大になる 𝑝 を答えよ。

A discrete random variable 𝑋 takes 0and 1 with probability 𝑝 and 1 − 𝑝, respectively.

Compute the entropy of 𝑋. Furthermore, answer 𝑝 maximizing the entropy.

𝐻 𝑋 = −ℙ 𝑋 = 0 log₂ ℙ 𝑋 = 0 − ℙ 𝑋 = 1 log₂ ℙ(𝑋 = 1)

= −𝑝 log₂𝑝 − 1 − 𝑝 log₂ 1 − 𝑝 ≡ ℎ(𝑝)

関数ℎ(𝑝)は𝑝 = 1/2のときに 最大値1を取る。

The function ℎ(𝑝) takes the maximum 1 at 𝑝 = 1/2.

𝑂 1

1/2 1

ℎ(𝑝)

微分エントロピーの計算(Computation of differential entropy)

連続確率変数𝑋は、区間[0, 𝑎]上 の一様分布に従うとする。

𝑋の微分エントロピーを計算せよ。

A continuous random variable 𝑋 is uniformly distributed on the interval [0, 𝑎].

Compute the differential entropy of 𝑋.

定義から、𝑋の確率密度関数は以下で与えられる。

By definition, the probability density function of 𝑋 is given by

例２.６.２(Example 2.6.2)

𝑝_𝑋 𝑥 = ቊ𝑎⁻¹ for 𝑥 ∈ [0, 𝑎]

0 otherwise よって、(Thus,)

ℎ 𝑋 = − න

0 𝑎1

𝑎 log₂ 1

𝑎 𝑑𝑥 = log₂𝑎 𝑎 < 1のとき、微分エントロピーℎ(𝑋)は負になる。

For 𝑎 < 1, the differential entropy ℎ(𝑋) is negative.

演習(Exercise)

離散確率変数𝑋は、−1、0、1をそれぞれ確率1/6、1/3、1/2で取る。

𝑋のエントロピーを計算せよ。

A discrete random variable 𝑋 takes −1, 0, and 1 with probability 1/6, 1/3, and 1/2, respectively.

Compute the entropy of 𝑋.

連続確率変数𝑋の確率密度関数は、以下で与えられるものとする。

𝑋の微分エントロピーを計算せよ。

The probability density function of a continuous random variable 𝑋 is given as follows.

Compute the differential entropy of 𝑋.

𝑝_𝑋 𝑥 = ቊ𝑒^−𝑥 for 𝑥 ≥ 0 0 otherwise