京都大学 情報学研究科 知能情報学専攻 2021年7月実施 専門科目 S-4

标签：

• Kyoto-University
• Source-Coding

Author

Isidore, 祭音Myyura

Description

大学公表の原題 以下では、実数 $p$ が $0 < p \leq 1$ を満たすときに、$N(p)$ を $N(p) = \lceil -\log_2 p \rceil$ すなわち $-\log_2 p$ 以上の最小の整数、と定義する。 たとえば、$N\left(\frac{1}{5}\right) = 3$, $N\left(\frac{1}{32}\right) = 5$ である。

情報源アルファベットが $\Sigma = \{a_1, a_2, \dots, a_n\}$ であるような記憶のない定常情報源 $S$ を考える。 情報源 $S$ が記号 $a_i$ を発生させる確率を $p_i$ と表し、

$$P_1 = 0, \quad P_i = \sum_{k=1}^{i-1} p_k \quad (i = 2, \dots, n)$$

と定義する。 さらに、$p_1 \geq p_2 \geq \dots \geq p_n > 0$ が成立していると仮定して、$a_i$ の記号 $0$ と $1$ による符号化 $C$ を

$$C(a_i): \; P_i \text{ を2進表現したときの } N(p_i) \text{ 桁目までの } 0 \text{ と } 1 \text{ の列 }$$

と定義する。 たとえば、$P_i = \frac{3}{5}$ かつ $p_i = \frac{1}{5}$ であれば、$\frac{3}{5}$ の 2 進表現は $0.100 \cdots$ であり、$N\left(\frac{1}{5}\right) = 3$ であるから、$C(a_i) = 100$ である。 情報源 $S$ の情報量を $H(S)$, 平均符号長を $\overline{N}$ で表す。

設問 1

記号数が $n = 4$ であり、$p_i \; (i = 1, 2, 3, 4)$ が以下のように与えられている場合に符号 $C(a_1), C(a_2), C(a_3), C(a_4)$ を求めよ。

$$p_1 = \frac{1}{3}, \quad p_2 = \frac{1}{4}, \quad p_3 = \frac{1}{4}, \quad p_4 = \frac{1}{6}$$

設問 2

次の不等式が成立することを符号化 $C$ の定義を用いることによって示せ。

$$H(S) \leq \overline{N} < H(S) + 1$$

設問 3

記号数が $n = 6$ であり、$H(S) = \overline{N}$ が成立するような数列 $p_1, p_2, \ldots, p_6$ をすべて与えよ。 また、与えた数列の中で $p_6$ が最小のものについて、符号 $C(a_1), C(a_2), \ldots, C(a_6)$ を与えよ。

設問 4

$H(S) = \overline{N}$ が成立し、かつ $p_1 = p_2 = \dots = p_k = p_{k+1} = \dots = p_n$ が成立するとき、$C$ がハフマン符号になることを、$C$ をハフマン符号として構成する過程によって示せ。

設問 5

$H(S) = \overline{N}$ が成立し、かつ、ある $k \; (1 < k < n)$ について

$$p_1 = p_2 = \dots = p_k > p_{k+1} = \dots = p_n$$

が成立するとき、$C$ がハフマン符号になることを、$C$ をハフマン符号として構成する過程を与えることにより示せ。

题目描述

对 $0<p\le1$ 定义 $N(p)=\lceil-\log_2p\rceil$。平稳无记忆信源 $S$ 的字母表为 $\Sigma=\{a_1,\ldots,a_n\}$，符号概率为 $p_1\ge\cdots\ge p_n>0$。定义累积概率

$$P_1=0,\qquad P_i=\sum_{k=1}^{i-1}p_k\quad(i=2,\ldots,n),$$

并将 $a_i$ 编为 $P_i$ 的二进制小数展开前 $N(p_i)$ 位，记为 $C(a_i)$。例如 $P_i=3/5,p_i=1/5$ 时， $C(a_i)=100$。令信源熵为 $H(S)$，平均码长为 $\bar N$。

1. 当 $n=4$ 且 $p_1=1/3,p_2=1/4,p_3=1/4,p_4=1/6$ 时，求全部 $C(a_i)$。

2. 由编码定义证明

   $$H(S)\le\bar N<H(S)+1.$$

3. 当 $n=6$ 时，求所有满足 $H(S)=\bar N$ 的概率序列 $p_1,\ldots,p_6$；在这些序列中取 $p_6$ 最小者，给出全部码字。

4. 若 $H(S)=\bar N$ 且所有 $p_i$ 相等，通过展示 Huffman 构造过程证明 $C$ 是 Huffman 码。

5. 若 $H(S)=\bar N$，且对某个 $1<k<n$， $p_1=\cdots=p_k>p_{k+1}=\cdots=p_n$，通过给出 Huffman 构造过程证明 $C$ 是 Huffman 码。

Kai

設問1

$$C(a_1) = 00,\;C(a_2) = 01,\;C(a_3) = 10,\;C(a_4) = 110,\;$$

設問2

By the definition of $\overline{N}$, we have

$$\overline{N} = \sum_{i=1}^np_iN(p_i),$$

since $-\log_{2}p_{i}\leq N(p_{i}) < -\log_{2}p_{i}+1$, we multiply both sides of the equation by $p_i \ (p_i > 0)$,

$$-p_{i}\log_{2}p_{i}\leq p_{i}N(p_{i}) < -p_{i}\log_{2}p_{i}+p_i$$

hence, using $\sum_{i=1}^n p_i=1$,

$$-\sum_{i=1}^{n}p_{i}\log_{2}p_{i}\leq \sum_{i=1}^{n}p_{i}N(p_{i}) < -\sum_{i=1}^{n}p_{i}\log_{2}p_{i}+1$$

that is

$$H(S)\leq \overline{N} < H(S)+1$$

設問3

等号は各 $p_i$ が $2^{-l_i}$（$l_i$ は整数）となる場合に限る。 $\sum_i2^{-l_i}=1$ を満たす6葉の完全な符号木では、最深葉までの経路の各分岐に少なくとも1葉が必要なので、$l_i\le5$ である。 $1\le l_1\le\cdots\le l_6\le5$ の範囲で和が1となるものを列挙すると、次の5通りを得る。

$$(\frac{1}{2},\frac{1}{4},\frac{1}{8},\frac{1}{16},\frac{1}{32},\frac{1}{32})$$

$$(\frac{1}{2},\frac{1}{4},\frac{1}{16},\frac{1}{16},\frac{1}{16},\frac{1}{16})$$

$$(\frac{1}{2},\frac{1}{8},\frac{1}{8},\frac{1}{8},\frac{1}{16},\frac{1}{16})$$

$$(\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{8},\frac{1}{16},\frac{1}{16})$$

$$(\frac{1}{4},\frac{1}{4},\frac{1}{8},\frac{1}{8},\frac{1}{8},\frac{1}{8})$$

The first sequence is the one that $p_6$ is minimized, the codes $C$ are

$$\{0,10,110,1110,11110,11111\}$$

設問4

設問2の等号条件から、すべての $-\log_2p_i$ が整数である。 一様分布では $p_i=2^{-r}$、$n=2^r$ となり、 $P_i=(i-1)/2^r$ だから $C(a_i)$ は整数 $i-1$ の $r$ 桁の2進表示である。

ハフマン法で、並び順を保って隣り合う記号を2つずつ結合する。 各段階で未結合の最小重みの節点を対にし、左辺に $0$、右辺に $1$ を付ける。 第1段階の重みはすべて $2^{-(r-1)}$ となり、同じ操作を $r$ 段階繰り返すと根に到達する。 この完全二分木の葉は左から $0,1,\ldots,2^r-1$ の $r$ 桁表示となるので、得られる符号は $C$ である。 $n=1$ では符号語は空列となる。

設問5

大きい確率を $2^{-r}$、小さい確率を $2^{-s}$ とおくと、$s>r$ であり、

$$k2^{-r}+(n-k)2^{-s}=1 \quad\Longrightarrow\quad n-k=(2^r-k)2^{s-r}.$$

したがって、小さい確率の記号を元の順序で $2^{s-r}$ 個ずつまとめることができる。 各組で隣り合う最小重みの節点を順に2つずつ結合し、左に $0$、右に $1$ を付ける。 すべての小さい葉について同じ深さの結合を先に行うと、結合対象は常に最小の2節点であり、ハフマン法に従っている。 $s-r$ 段階後には重み $2^{-r}$ の節点が $2^r-k$ 個できる。

これらを最初の $k$ 個の葉の後ろに並べると、重み $2^{-r}$ の節点が計 $2^r$ 個になる。 設問4と同じく隣り合う節点を結合すれば、大きい確率の葉は深さ $r$、小さい確率の葉は深さ $s$ となる。 それぞれの葉までの2進経路は、その葉より前にある確率の和 $P_i$ の先頭 $-\log_2p_i$ 桁に一致する。よって、このハフマン構成で得られる符号は $C$ である。