【問1】

アルファベット $\{s_1, s_2, s_3, s_4, s_5, s_6\}$ 上の無記憶情報源 $S$ の符号化に関して，以下の問いに答えよ。ただし，符号語アルファベットを $\{0, 1\}$ とする。

1. 無記憶情報源 $S$ に関して，各符号語長を $3, 3, 3, 2, 2, 2$ とする符号が瞬時に復号可能になり得るかどうかを述べよ。なり得る場合，瞬時に復号可能な符号の一例を示せ。
2. 無記憶情報源 $S$ に関して，各符号語長を $3, 3, 3, 3, 2, 2$ とする符号が瞬時に復号可能になり得るかどうかを述べよ。なり得る場合，瞬時に復号可能な符号の一例を示せ。
   以後の問いにおいて， 無記憶情報源 S に関して，その確率分布が

$$P(s_1) = 0.18, \, P(s_2) = 0.2, \, P(s_3) = 0.3, \, P(s_4) = 0.13, \, P(s_5) = 0.11, \, P(s_6) = 0.08$$

であるとする．次の問いに 答えよ 3. 無記憶情報源 $S$ に関して，その確率分布が以下のように与えられるとする：
ハフマン符号化により符号化せよ。 4. ハフマン符号化により得られた符号の平均符号長を求めよ。

DeepSeekV3

1. 各符号码长为 $3, 3, 3, 2, 2, 2$ 时，是否可以瞬时解码？

计算克拉夫特不等式：

$$2^{-3} + 2^{-3} + 2^{-3} + 2^{-2} + 2^{-2} + 2^{-2} = \frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4} = \frac{3}{8} + \frac{3}{4} = \frac{9}{8} > 1$$

不满足克拉夫特不等式，因此无法构建瞬时编码。

2. 各符号码长为 $3, 3, 3, 3, 2, 2$ 时，是否可以瞬时解码？

计算克拉夫特不等式：

$$2^{-3} + 2^{-3} + 2^{-3} + 2^{-3} + 2^{-2} + 2^{-2} = \frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{4} + \frac{1}{4} = \frac{4}{8} + \frac{2}{4} = 1$$

满足克拉夫特不等式，因此可以构建瞬时编码。

例如：

• $s_5$: 00
• $s_6$: 01
• $s_1$: 100
• $s_2$: 101
• $s_3$: 110
• $s_4$: 111

此编码满足前缀条件，因此是瞬时可解码的。

3. 哈夫曼编码

给定概率分布：

$$P(s_1) = 0.18, \, P(s_2) = 0.2, \, P(s_3) = 0.3, \, P(s_4) = 0.13, \, P(s_5) = 0.11, \, P(s_6) = 0.08$$

按照哈夫曼编码步骤，合并过程如下：

1. 合并 $s_6$ (0.08) 和 $s_5$ (0.11)，得到新节点 0.19。
2. 合并 $s_4$ (0.13) 和 $s_1$ (0.18)，得到新节点 0.31。
3. 合并 0.19 和 0.31，得到新节点 0.5。
4. 合并 $s_2$ (0.2) 和 $s_3$ (0.3)，得到新节点 0.5。
5. 最后合并 0.5 和 0.5，得到根节点 1.0。

根据树的结构，哈夫曼编码如下：

• $s_3$: 0
• $s_2$: 10
• $s_4$: 110
• $s_1$: 1110
• $s_5$: 11110
• $s_6$: 11111

4. 哈夫曼编码的平均码长

根据上述编码，计算平均码长：

$$L = 0.3 \times 1 + 0.2 \times 2 + 0.13 \times 3 + 0.18 \times 4 + 0.11 \times 5 + 0.08 \times 5$$

$$L = 0.3 + 0.4 + 0.39 + 0.72 + 0.55 + 0.4 = 2.76 \text{ 比特/符号}$$