跳到主要内容

大阪大学 基礎工学研究科 電子光科学 (システム創成専攻) 2021年度 電子光科学 [I-4]

标签：

Author​

祭音Myyura (co-authored with GPT 5.6 SOL)

Description​

情報源アルファベット AA の値を確率分布 PP にしたがってとる確率変数を XX とする。XX が記号 x∈Ax\in A をとる確率を P(x)P(x)、記号 xx の符号語長を l(x)l(x) として、瞬時符号 CC の平均符号語長 L(C)L(C) を

L(C)=∑x∈AP(x)l(x)L(C)=\sum_{x\in A}P(x)l(x)

によって定義する。情報源符号化逆定理によると、瞬時符号の平均符号語長を情報源エントロピー H(X)H(X) より小さくすることはできない。すなわち、L(C)≥H(X)L(C)\ge H(X) が成り立つ。以下の各問に答えよ。ただし、対数の底は省略せずに明示せよ。

(1) 符号アルファベットが B={0,1}B=\{0,1\} の場合に、この定理における H(X)H(X) の定義を書け。

(2) 問 (1) で、この定理の等号が成り立つ情報源（確率分布）の例をひとつあげて、その符号の木を描き、定理の等号が成り立つことを示せ。ただし、情報源記号は 3 つ以上とする。

(3) 符号アルファベットが B={0,1,…,q−1}B=\{0,1,\ldots,q-1\} の場合、q≥3q\ge3 ならば平均符号語長は問 (1) で定義した H(X)H(X) より小さくなり得る。この場合でも、この定理が成り立つためには、H(X)H(X) をどう定義すればよいか書け。

(4) q=3q=3 の場合について、この定理の等号が成り立つ情報源（確率分布）の例をひとつあげて、その符号の木を描き、定理の等号が成り立つことを示せ。ただし、情報源記号は 4 つ以上とする。

Kai​

(1)​

H(X)=−∑x∈AP(x)log⁡2P(x).\boxed{H(X)=-\sum_{x\in A}P(x)\log_2P(x)}.

(2)​

P(a)=1/2P(a)=1/2、P(b)=P(c)=1/4P(b)=P(c)=1/4 とし、符号語を 0,10,110,10,11 とする。

L(C)=12+2⋅14+2⋅14=32=−12log⁡212−2⋅14log⁡214=H(X).L(C)=\tfrac12+2\cdot\tfrac14+2\cdot\tfrac14=\tfrac32 =-\tfrac12\log_2\tfrac12-2\cdot\tfrac14\log_2\tfrac14=H(X).

(3)​

符号語長を qq 元記号の個数で測るので

H(X)=−∑x∈AP(x)log⁡qP(x).\boxed{H(X)=-\sum_{x\in A}P(x)\log_qP(x)}.

(4)​

P(a)=P(b)=1/3P(a)=P(b)=1/3、P(c)=P(d)=P(e)=1/9P(c)=P(d)=P(e)=1/9 とし、符号語をそれぞれ 0,1,20,21,220,1,20,21,22 とする。

L(C)=2⋅13+3⋅19⋅2=43=−2⋅13log⁡313−3⋅19log⁡319=H(X).L(C)=2\cdot\tfrac13+3\cdot\tfrac19\cdot2=\tfrac43 =-2\cdot\tfrac13\log_3\tfrac13-3\cdot\tfrac19\log_3\tfrac19=H(X).
本页目录