通信工学概論
Introduction to Communication Engineering

第７回講義資料
Lecture notes 7

情報量
Shannon Entropy

豊橋技術科学大学
Toyohashi University of Technology

電気・電子情報工学系
Department of Electrical and Electronic Information Engineering

准教授 竹内啓悟
Associate Professor

Keigo Takeuchi
1情報とは何か？(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

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

Q2：あなたは今日の朝食でご飯を食べましたか？(Did you eat rice this morning? )A1：1
A1の方が重要な質問に対する答えであるが、質問はどちらも二択なので、答えの情報量はどちらも同じとみなす。
A1 is an answer to more important question than A2. However, the answers have thesame amount of information as each other since both questions are two choices.

2

複数の確率変数(Multiple random variables)
３個の離散確率変数(𝑋𝑋, 𝑌𝑌, 𝑍𝑍)を同時に取り扱いたい。
Treat three discrete random variables (𝑋𝑋, 𝑌𝑌, 𝑍𝑍) jointly.

同時確率(Joint probability)

三つの離散確率変数(𝑋𝑋, 𝑌𝑌, 𝑍𝑍)が(𝑥𝑥, 𝑦𝑦, 𝑧𝑧)を取る確率𝑝𝑝𝑥𝑥,𝑦𝑦,𝑧𝑧 ≥ 0を定める。
Determine the probability 𝑝𝑝𝑥𝑥,𝑦𝑦,𝑧𝑧 with which three discrete random variables (𝑋𝑋, 𝑌𝑌, 𝑍𝑍) take (𝑥𝑥, 𝑦𝑦, 𝑧𝑧).

ℙ 𝑋𝑋 = 𝑥𝑥, 𝑌𝑌 = 𝑦𝑦, 𝑍𝑍 = 𝑧𝑧 = 𝑝𝑝𝑥𝑥,𝑦𝑦,𝑧𝑧 ,� 𝑝𝑝𝑥𝑥,𝑦𝑦,𝑧𝑧 = 1(𝑥𝑥,𝑦𝑦,𝑧𝑧)

ただし、総和は(𝑥𝑥, 𝑦𝑦, 𝑧𝑧)が取りうるすべての組み合わせに関して取られる。
The summation is over all possible combinations of (𝑥𝑥, 𝑦𝑦, 𝑧𝑧).

例７.１(Example 7.1)

三つの確率変数は(0, 0, 0)、(0, 0, 1)、(0, 1, 0)、(0, 1, 1)、(1, 0, 0)、(1, 0, 1)、(1, 1, 0)、(1, 1, 1)を確率1/8で取る。

The three random variables take (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), 1, 1, 1
with probability 1/8.

3

周辺確率(Marginal probability)ℙ 𝑋𝑋, 𝑌𝑌 = � ℙ(𝑋𝑋 , 𝑌𝑌, 𝑍𝑍 = 𝑧𝑧),𝑧𝑧ℙ 𝑋𝑋 = � ℙ(𝑋𝑋 = 𝑥𝑥, 𝑌𝑌 = 𝑦𝑦)𝑦𝑦

総和は𝑧𝑧または𝑦𝑦が取りうるすべての値に関して取られる。
The summation is over all possible values of 𝑧𝑧 or 𝑦𝑦.

他の確率変数の組み合わせに関する周辺確率も同様に定義される。
We define marginal probability with respect to the other combinations of the random variables similarly.

周辺確率の計算(Computation of the marginal probability)
例７.１の場合に周辺確率を計算する。(Compute marginal probability in Example 7.1.)
1ℙ 𝑋𝑋 = 0, 𝑌𝑌 = 0 = ℙ 𝑋𝑋 = 0, 𝑌𝑌 = 0, 𝑍𝑍 = 0 + ℙ 𝑋𝑋 = 0, 𝑌𝑌 = 0, 𝑍𝑍 = 1 =4
同様に、
1ℙ 𝑋𝑋 = 0, 𝑌𝑌 = 1 = ℙ 𝑋𝑋 = 1, 𝑌𝑌 = 0 = ℙ 𝑋𝑋 = 1, 𝑌𝑌 = 1 =Similarly,
4
さらに、

Furthermore,

1ℙ 𝑋𝑋 = 0 = ℙ 𝑋𝑋 = 0, 𝑌𝑌 = 0 + ℙ 𝑋𝑋 = 0, 𝑌𝑌 = 1 =24

条件付き確率(Conditional probability)ℙ(𝑋𝑋, 𝑌𝑌, 𝑍𝑍),ℙ 𝑌𝑌, 𝑍𝑍 𝑋𝑋 =ℙ(𝑋𝑋)ℙ(𝑋𝑋, 𝑌𝑌, 𝑍𝑍)ℙ 𝑍𝑍 𝑋𝑋, 𝑌𝑌 =ℙ(𝑋𝑋, 𝑌𝑌)

他の確率変数の組み合わせに関する条件付き確率も同様に定義される。
We define conditional probability with respect to the other combinations of the random variables similarly.

条件付き確率の計算(Computation of the conditional probability)
例７.1の場合に条件付き確率を計算する。
Compute conditional probability in Example 7.1.

ℙ(𝑋𝑋 = 0, 𝑌𝑌 = 0, 𝑍𝑍 = 0) 1=
ℙ 𝑌𝑌 = 0, 𝑍𝑍 = 0 𝑋𝑋 = 0 =ℙ(𝑋𝑋 = 0)
4ℙ(𝑋𝑋 = 0, 𝑌𝑌 = 0, 𝑍𝑍 = 0) 1=
ℙ 𝑍𝑍 = 0 𝑋𝑋 = 0, 𝑌𝑌 = 0 =ℙ(𝑋𝑋 = 0, 𝑌𝑌 = 0)2

この場合、In this case,ℙ 𝑍𝑍|𝑋𝑋, 𝑌𝑌 = ℙ(𝑍𝑍)

5

独立性(Independence)
同時確率が各確率変数の周辺確率の積に分解されるとき、確率変数(𝑋𝑋, 𝑌𝑌, 𝑍𝑍)は独立と呼ばれる。

Random variables (𝑋𝑋, 𝑌𝑌, 𝑍𝑍) are said to be independent if the joint probability is decomposed into
the product of the individual marginal probability of the random variables.

注意
Remarkℙ 𝑋𝑋, 𝑌𝑌, 𝑍𝑍 = ℙ 𝑋𝑋 ℙ 𝑌𝑌 ℙ(𝑍𝑍)ℙ 𝑋𝑋, 𝑌𝑌 = ℙ 𝑋𝑋 ℙ 𝑌𝑌 , ℙ 𝑋𝑋, 𝑍𝑍 = ℙ 𝑋𝑋 ℙ 𝑍𝑍 , ℙ 𝑌𝑌, 𝑍𝑍 = ℙ 𝑌𝑌 ℙ(𝑍𝑍)ℙ 𝑋𝑋, 𝑌𝑌, 𝑍𝑍 = ℙ 𝑋𝑋 ℙ 𝑌𝑌 ℙ(𝑍𝑍)

独立性の意義(Significance of independence)(𝑋𝑋, 𝑌𝑌, 𝑍𝑍)が独立のとき、条件付き確率は条件に依存しない。

If (𝑋𝑋, 𝑌𝑌, 𝑍𝑍) is independent, the conditional probability does not depend on any conditioning.

ℙ 𝑌𝑌, 𝑍𝑍 𝑋𝑋 =ℙ(𝑋𝑋, 𝑌𝑌, 𝑍𝑍) ℙ 𝑋𝑋 ℙ 𝑌𝑌 ℙ(𝑍𝑍)== ℙ 𝑌𝑌 ℙ 𝑍𝑍 = ℙ(𝑌𝑌, 𝑍𝑍)
ℙ(𝑋𝑋)
ℙ(𝑋𝑋)

二番目と四番目の等号は、独立性の定義から従う。

The second and fourth equalities follow from the definition of the independence.

6期待値(Expectation)
決定論的な関数𝑓𝑓(𝑥𝑥, 𝑦𝑦, 𝑧𝑧)に対して、(For a deterministic function 𝑓𝑓 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 ,)𝔼𝔼 𝑓𝑓 𝑋𝑋, 𝑌𝑌, 𝑍𝑍= � 𝑓𝑓 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 ℙ(𝑋𝑋 = 𝑥𝑥, 𝑌𝑌 = 𝑦𝑦, 𝑍𝑍 = 𝑧𝑧)(𝑥𝑥,𝑦𝑦,𝑧𝑧)

総和は(𝑥𝑥, 𝑦𝑦, 𝑧𝑧)が取りうるすべての組み合わせに関して取られる。
The summation is over all possible combinations of (𝑥𝑥, 𝑦𝑦, 𝑧𝑧).

条件付き期待値(Conditional expectation)

決定論的な関数𝑔𝑔(𝑦𝑦, 𝑧𝑧)とℎ(𝑧𝑧)に対して、(For deterministic functions 𝑔𝑔 𝑦𝑦, 𝑧𝑧 and ℎ(𝑧𝑧),)
𝔼𝔼 𝑔𝑔 𝑌𝑌, 𝑍𝑍 𝑋𝑋 = 𝑥𝑥 = � 𝑔𝑔 𝑦𝑦, 𝑧𝑧 ℙ(𝑌𝑌 = 𝑦𝑦, 𝑍𝑍 = 𝑧𝑧|𝑋𝑋 = 𝑥𝑥)(𝑦𝑦,𝑧𝑧)𝔼𝔼 ℎ 𝑍𝑍 𝑋𝑋 = 𝑥𝑥, 𝑌𝑌 = 𝑦𝑦 = � ℎ 𝑧𝑧 ℙ(𝑍𝑍 = 𝑧𝑧|𝑋𝑋 = 𝑥𝑥, 𝑌𝑌 = 𝑦𝑦)𝑧𝑧

総和は(𝑦𝑦, 𝑧𝑧)または𝑧𝑧が取りうるすべての組み合わせに関して取られる。
The summation is over all possible combinations of (𝑦𝑦, 𝑧𝑧) or 𝑧𝑧.

7

連続確率変数の場合(Case of continuous random variables)
３個の連続確率変数(𝑋𝑋, 𝑌𝑌, 𝑍𝑍)を同時に取り扱いたい。
Treat three continuous random variables (𝑋𝑋, 𝑌𝑌, 𝑍𝑍) jointly.

離散の場合の確率と総和をそれぞれ確率密度関数と積分に置き換える。
Replace the probability and summation in the discrete case with a probability density function andan integral, respectively.

同時確率(Joint probability)(𝑋𝑋, 𝑌𝑌, 𝑍𝑍)が３次元空間内の集合𝐴𝐴に入る確率は以下で定義される。

We define the probability with which (𝑋𝑋, 𝑌𝑌, 𝑍𝑍) is included into a set 𝐴𝐴 in the 3-dimensional space.

ℙ 𝑋𝑋, 𝑌𝑌, 𝑍𝑍 ∈ 𝐴𝐴 = �𝑥𝑥,𝑦𝑦,𝑧𝑧 ∈𝐴𝐴

𝑝𝑝𝑋𝑋,𝑌𝑌,𝑍𝑍 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑

ただし、同時確率密度関数𝑝𝑝𝑋𝑋,𝑌𝑌,𝑍𝑍 (𝑥𝑥, 𝑦𝑦, 𝑧𝑧)は以下を満たす。
Here, the joint probability density function 𝑝𝑝𝑋𝑋,𝑦𝑦,𝑍𝑍 (𝑥𝑥, 𝑦𝑦, 𝑧𝑧) satisfies the following:

�∞

�∞

∞

� 𝑝𝑝𝑋𝑋,𝑌𝑌,𝑍𝑍 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 = 1−∞ −∞ −∞

8

連続確率変数の場合(Case of continuous random variables)
周辺確率密度関数(Marginal probability density functions)∞

𝑝𝑝𝑋𝑋,𝑌𝑌 𝑥𝑥, 𝑦𝑦 = � 𝑝𝑝𝑋𝑋,𝑌𝑌,𝑍𝑍 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 𝑑𝑑𝑑𝑑 ,∞−∞

𝑝𝑝𝑋𝑋 𝑥𝑥 = � 𝑝𝑝𝑋𝑋,𝑌𝑌 𝑥𝑥, 𝑦𝑦 𝑑𝑑𝑑𝑑

𝑝𝑝𝑋𝑋,𝑌𝑌,𝑍𝑍 (𝑥𝑥, 𝑦𝑦, 𝑧𝑧),
𝑝𝑝𝑌𝑌,𝑍𝑍|𝑋𝑋 𝑦𝑦, 𝑧𝑧 𝑥𝑥 =𝑝𝑝𝑋𝑋 (𝑥𝑥)𝑝𝑝𝑋𝑋,𝑌𝑌,𝑍𝑍 (𝑥𝑥, 𝑦𝑦, 𝑧𝑧)
𝑝𝑝𝑍𝑍|𝑋𝑋,𝑌𝑌 𝑧𝑧 𝑥𝑥, 𝑦𝑦 =𝑝𝑝𝑋𝑋,𝑌𝑌 (𝑥𝑥, 𝑦𝑦)−∞

条件付き確率密度関数(Conditional probability density functions)

独立性(Independence)

同時確率密度関数が各確率変数の周辺確率密度関数の積に分解されるとき、確率変数(𝑋𝑋, 𝑌𝑌, 𝑍𝑍)は独立と呼ばれる。

Random variables (𝑋𝑋, 𝑌𝑌, 𝑍𝑍) are said to be independent if the joint probability density function
is decomposed into the product of the individual marginal probability density functions of therandom variables.

𝑝𝑝𝑋𝑋,𝑌𝑌,𝑍𝑍 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 = 𝑝𝑝𝑋𝑋 𝑥𝑥 𝑝𝑝𝑌𝑌 𝑦𝑦 𝑝𝑝𝑍𝑍 (𝑧𝑧)9

連続確率変数の場合(Case of continuous random variables)
期待値(Expectation)
決定論的な関数𝑓𝑓(𝑥𝑥, 𝑦𝑦, 𝑧𝑧)に対して、(For a deterministic function 𝑓𝑓 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 ,)𝔼𝔼 𝑓𝑓 𝑋𝑋, 𝑌𝑌, 𝑍𝑍

=�

∞

�∞

∞

� 𝑓𝑓 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 𝑝𝑝𝑥𝑥,𝑦𝑦,𝑧𝑧 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑−∞ −∞ −∞

条件付き期待値(Conditional expectation)
決定論的な関数𝑔𝑔(𝑦𝑦, 𝑧𝑧)とℎ(𝑧𝑧)に対して、(For deterministic functions 𝑔𝑔 𝑦𝑦, 𝑧𝑧 and ℎ(𝑧𝑧),)
𝔼𝔼 𝑔𝑔 𝑌𝑌, 𝑍𝑍 𝑋𝑋 = 𝑥𝑥 = �∞∞� 𝑔𝑔 𝑦𝑦, 𝑧𝑧 𝑝𝑝𝑌𝑌,𝑍𝑍|𝑋𝑋 𝑦𝑦, 𝑧𝑧 𝑥𝑥 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑−∞ −∞∞

𝔼𝔼 ℎ 𝑍𝑍 𝑋𝑋 = 𝑥𝑥, 𝑌𝑌 = 𝑦𝑦 = � ℎ 𝑧𝑧 𝑝𝑝𝑍𝑍|𝑋𝑋,𝑌𝑌 𝑧𝑧 𝑥𝑥, 𝑦𝑦 𝑑𝑑𝑑𝑑−∞

10

期待値の性質(Properties of expectation)
連続確率変数を仮定するが、離散の場合にも同じ性質が成り立つ。
Continuous random variables are assumed. However, the same properties hold for the discrete case.

一貫性(Consistency)
同時確率密度関数𝑝𝑝𝑋𝑋,𝑌𝑌,𝑍𝑍 に関する𝑋𝑋の期待値は、周辺確率密度関数𝑝𝑝𝑋𝑋に関する𝑋𝑋の期待値と一致する。

The expectation of 𝑋𝑋 with respect to a joint probability density function 𝑝𝑝𝑋𝑋,𝑌𝑌,𝑍𝑍 is equal to that of 𝑋𝑋with respect to the corresponding marginal probability density function 𝑝𝑝𝑋𝑋 .

∵ 𝔼𝔼 𝑋𝑋 = �∞�∞∞

� 𝑥𝑥𝑝𝑝𝑋𝑋,𝑌𝑌,𝑍𝑍 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑−∞ −∞ −∞

=�∞−∞𝑥𝑥 �∞∞∞� 𝑝𝑝𝑋𝑋,𝑌𝑌,𝑍𝑍 𝑥𝑥, 𝑦𝑦, 𝑧𝑧 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 𝑑𝑑𝑑𝑑 = � 𝑥𝑥𝑝𝑝𝑋𝑋 𝑥𝑥 𝑑𝑑𝑑𝑑

−∞ −∞

−∞

最後の等号は、周辺確率密度関数の定義から従う。
The last equality follows from the definition of the marginal probability density function.

∎11期待値の性質(Properties of expectation)
線形性(Linearity)
実数𝑎𝑎と𝑏𝑏に対して、(For real numbers 𝑎𝑎 and 𝑏𝑏,)

𝔼𝔼 𝑎𝑎𝑎𝑎 + 𝑏𝑏𝑏𝑏 = 𝑎𝑎𝑎𝑎 𝑋𝑋 + 𝑏𝑏𝑏𝑏[𝑌𝑌]

𝑋𝑋と𝑌𝑌に関する何の条件も不要なことに注意∵

Note that 𝑋𝑋 or 𝑌𝑌 does not require any conditions.

積分の線形性から、(From the linearity in integral,)𝔼𝔼 𝑎𝑎𝑎𝑎 + 𝑏𝑏𝑏𝑏 = �= 𝑎𝑎 �∞∞∞

�

∞

−∞ −∞

𝑎𝑎𝑎𝑎 + 𝑏𝑏𝑏𝑏 𝑝𝑝𝑋𝑋,𝑌𝑌 𝑥𝑥, 𝑦𝑦 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑

� 𝑥𝑥𝑝𝑝𝑋𝑋,𝑌𝑌 𝑥𝑥, 𝑦𝑦 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 + 𝑏𝑏 �

−∞ −∞

∞

∞

� 𝑦𝑦𝑝𝑝𝑥𝑥,𝑦𝑦 𝑥𝑥, 𝑦𝑦 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 = 𝑎𝑎𝑎𝑎 𝑋𝑋 + 𝑏𝑏𝑏𝑏[𝑌𝑌]−∞ −∞最後の等号は、期待値の一貫性から従う。

The last equality follows from the consistency in expectation.

∎12期待値の性質(Properties of expectation)
確率変数の積(Product of random variables)
𝑓𝑓と𝑔𝑔を決定論的な関数とする。(Let 𝑓𝑓 and 𝑔𝑔 denote deterministic functions.)(𝑋𝑋, 𝑌𝑌)が独立ならば、(If (𝑋𝑋, 𝑌𝑌) is independent,)

𝔼𝔼 𝑓𝑓 𝑋𝑋 𝑔𝑔(𝑌𝑌) = 𝔼𝔼 𝑓𝑓(𝑋𝑋) 𝔼𝔼[𝑔𝑔(𝑌𝑌)]積の場合は、無条件で期待値の分解はできない。
In the case of the product, the expectation cannot be decomposed with no conditions.

∵

独立性の定義𝑝𝑝𝑋𝑋,𝑌𝑌 𝑥𝑥, 𝑦𝑦 = 𝑝𝑝𝑋𝑋 𝑥𝑥 𝑝𝑝𝑌𝑌 (𝑦𝑦)から、From the definition of the independence 𝑝𝑝𝑋𝑋,𝑌𝑌 𝑥𝑥, 𝑦𝑦 = 𝑝𝑝𝑋𝑋 𝑥𝑥 𝑝𝑝𝑌𝑌 (𝑦𝑦),∞∞𝔼𝔼 𝑓𝑓 𝑋𝑋 𝑔𝑔(𝑌𝑌) = �� 𝑓𝑓 𝑥𝑥 𝑔𝑔(𝑦𝑦)𝑝𝑝𝑋𝑋,𝑌𝑌 𝑥𝑥, 𝑦𝑦 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑

−∞ −∞
∞∞

=�

� 𝑓𝑓 𝑥𝑥 𝑔𝑔(𝑦𝑦)𝑝𝑝𝑋𝑋 𝑥𝑥 𝑝𝑝𝑌𝑌 𝑦𝑦 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑−∞ −∞∞∞= � 𝑓𝑓(𝑥𝑥)𝑝𝑝𝑋𝑋 𝑥𝑥 𝑑𝑑𝑑𝑑 � 𝑔𝑔(𝑦𝑦)𝑝𝑝𝑌𝑌 𝑦𝑦 𝑑𝑑𝑑𝑑 = 𝔼𝔼 𝑓𝑓(𝑋𝑋) 𝔼𝔼[𝑔𝑔(𝑌𝑌)] ∎−∞−∞

13

算術符号化(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/3 in each position and that 0 or 1 occurs independently in different positions.

区間分割(Interval division)000∗00490123691∗
10891111系列の発生確率が対応する区間の長さに等しくなるように分割する。
The occurrence probability of each sequence is equal to the length of the corresponding interval.
14算術符号化(Arithmetic coding)
符号化(Encoding)
各入力系列𝒔𝒔に対して、𝑚𝑚𝒔𝒔 = − log 2 ℙ 𝑺𝑺 = 𝒔𝒔 + 1とする。 𝒔𝒔の符号語として、対応する区間の中点の２進数表現を𝑚𝑚𝒔𝒔 ビットで打ち切ったものを選ぶ。

For each input sequence 𝒔𝒔, let 𝑚𝑚𝒔𝒔 = ⌈− log 2 ℙ(𝑺𝑺 = 𝒔𝒔)⌉ + 1. As a codeword of 𝒔𝒔, we select the sequenceobtained by truncating the binary representation of the midpoint in the corresponding interval up to 𝑚𝑚𝒔𝒔 bits.

⌈𝑎𝑎⌉は実数𝑎𝑎以上の最小の整数(⌈𝑎𝑎⌉ is the minimum integer greater than or equal to 𝑎𝑎.)

復号Decoding

各符号語が対応する区間に入っていれば、復号できる。(詳細省略)
If each codeword is included into the corresponding interval, decoding is possible.

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

𝑺𝑺 = 𝑆𝑆1 𝑆𝑆2 、𝒔𝒔 = 𝑠𝑠1 𝑠𝑠2 とすると、ℙ 𝑺𝑺 = 𝒔𝒔 = ℙ 𝑆𝑆1 = 𝑠𝑠1 ℙ(𝑆𝑆2 = 𝑠𝑠2 )なので、For 𝑺𝑺 = 𝑆𝑆1 𝑆𝑆2 and 𝒔𝒔 = 𝑠𝑠1 𝑠𝑠2 , we have ℙ 𝑺𝑺 = 𝒔𝒔 = ℙ 𝑆𝑆1 = 𝑠𝑠1 ℙ(𝑆𝑆2 = 𝑠𝑠2 ). Thus,

𝔼𝔼 𝐿𝐿 = � 𝑚𝑚𝒔𝒔 ℙ 𝑺𝑺 = 𝒔𝒔 ≤ − � � ℙ(𝑆𝑆𝑖𝑖 = 𝑠𝑠𝑖𝑖 )log 2 ℙ(𝑆𝑆𝑖𝑖 = 𝑠𝑠𝑖𝑖 ) + 2
𝒔𝒔𝑖𝑖=1,2 𝑠𝑠𝑖𝑖 =0,1

不等式の導出で 𝑎𝑎 ≤ 𝑎𝑎 + 1を使った。(In the derivation of the inequality, 𝑎𝑎 ≤ 𝑎𝑎 + 1 has been used.)15算術符号化(Arithmetic coding)
符号語が対応する区間に含まれていることを確認せよ。
Confirm that each codeword is included into the corresponding interval.

入力、符号語、区間を入力の発生確率が大きい順にそれぞれ𝒔𝒔(1) , … , 𝒔𝒔(4) 、
𝑐𝑐1 , … , 𝑐𝑐4 、 𝐿𝐿1 , 𝑅𝑅1 , … , [𝐿𝐿4 , 𝑅𝑅4 )とする。𝑐𝑐𝑖𝑖 > 𝐿𝐿𝑖𝑖 を証明したい。
(𝑖𝑖)
(𝑖𝑖)
𝑚𝑚𝒔𝒔(𝑖𝑖) を２進数表現𝑐𝑐𝑖𝑖 = 0. 𝑏𝑏1 ⋯ 𝑏𝑏𝑚𝑚 (𝑖𝑖) のビット長とすると、𝑐𝑐𝑖𝑖 の定義から、
Let 𝒔𝒔(1) , … , 𝒔𝒔(4) , 𝑐𝑐1 , … , 𝑐𝑐4 , and𝒔𝒔

𝐿𝐿1 , 𝑅𝑅1 , … , [𝐿𝐿4 , 𝑅𝑅4 ) 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. 𝑏𝑏1 ⋯ 𝑏𝑏𝑚𝑚 (𝑖𝑖) . From the definition of 𝑐𝑐𝑖𝑖 ,𝒔𝒔∞
𝐿𝐿𝑖𝑖 + 𝑅𝑅𝑖𝑖ℙ(𝑺𝑺 = 𝒔𝒔(𝑖𝑖) )(𝑖𝑖) +1−𝑚𝑚 (𝑖𝑖)−𝑗𝑗−−logℙ𝑺𝑺=𝒔𝒔2− 𝑐𝑐𝑖𝑖 < � 2 = 2 𝒔𝒔 = 2≤2

𝑗𝑗=𝑚𝑚𝒔𝒔(𝑖𝑖) +1

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

2∵ − 𝑎𝑎 ≤ −𝑎𝑎 for 𝑎𝑎 > 0

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

𝐿𝐿𝑖𝑖 + 𝑅𝑅𝑖𝑖 ℙ 𝑺𝑺 = 𝒔𝒔(𝑖𝑖)
𝐿𝐿𝑖𝑖 + 𝑅𝑅𝑖𝑖 𝑅𝑅𝑖𝑖 − 𝐿𝐿𝑖𝑖−=−= 𝐿𝐿𝑖𝑖
𝑐𝑐𝑖𝑖 >
2222∎16情報量(The amount of information)
エントロピー(Entropy)
離散確率変数𝑋𝑋に対して、𝑋𝑋のエントロピー𝐻𝐻(𝑋𝑋)を以下で定義する。
For a discrete random variable 𝑋𝑋, the entropy 𝐻𝐻(𝑋𝑋) of 𝑋𝑋 is defined as

𝐻𝐻 𝑋𝑋 = − � ℙ 𝑋𝑋 = 𝑥𝑥 log 2 ℙ 𝑋𝑋 = 𝑥𝑥 ,𝑥𝑥0 log 2 0 = 0

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

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

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

12𝔼𝔼 𝐿𝐿𝑁𝑁 ≤ − � ℙ 𝑆𝑆1 = 𝑠𝑠 log 2 ℙ 𝑆𝑆1 = 𝑠𝑠 + → 𝐻𝐻 𝑆𝑆1 as 𝑁𝑁 → ∞𝑁𝑁
𝑁𝑁
𝑠𝑠=0,117情報量(The amount of information)
逆定理(Converse theorem)
いかなる符号化をしても、平均符号長𝔼𝔼[𝐿𝐿𝑁𝑁 ]は以下の不等式を満たす。
For any coding method, the average code length 𝔼𝔼[𝐿𝐿𝑁𝑁 ] satisfies the following inequality:

1lim 𝔼𝔼[𝐿𝐿𝑁𝑁 ] ≥ 𝐻𝐻(𝑆𝑆1 )𝑁𝑁→∞ 𝑁𝑁

証明は情報理論の講義を参照(Learn Information Theory for the proof.)
順定理と逆定理を合わせて、情報源符号化定理と呼ぶ。
The combination of the direct and converse theorems is called source coding theorem.

エントロピーの意味(Meaning of the entropy)
エントロピーは、独立同一分布する無限に長いビット系列を圧縮したときの圧縮率の理論限界に等しい。
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.
18

エントロピーの計算(Computation of entropy)
例７.１(Example 7.1)
離散確率変数𝑋𝑋は、確率𝑝𝑝で0を取り、確率1 − 𝑝𝑝で1を取るとする。𝑋𝑋のエントロピーを計算せよ。さらに、エントロピーが最大になる 𝑝𝑝 を答えよ。
A discrete random variable 𝑋𝑋 takes 0 and 1 with probability 𝑝𝑝 and 1 − 𝑝𝑝, respectively.
Compute the entropy of 𝑋𝑋. Furthermore, answer 𝑝𝑝 maximizing the entropy.

𝐻𝐻 𝑋𝑋 = −ℙ 𝑋𝑋 = 0 log 2 ℙ 𝑋𝑋 = 0 − ℙ 𝑋𝑋 = 1 log 2 ℙ(𝑋𝑋 = 1)
= −𝑝𝑝 log 2 𝑝𝑝 − 1 − 𝑝𝑝 log 2 1 − 𝑝𝑝 ≡ ℎ(𝑝𝑝)The function ℎ(𝑝𝑝) takes the maximum 1
at 𝑝𝑝 = 1/2.

1ℎ(𝑝𝑝)

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

𝑂𝑂1/2
𝑝𝑝119

演習(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 𝑋𝑋.

20