R03-B-問1

問1

入力アルファベットと出力アルファベットがともに $\{1,2,3,4\}$ である無記憶な通信路 $W(y|x)$ の通信路行列が

$$\left(\begin{array}{cccc}0.5& 0.5& 0& 0\\ 0& 0.5& 0.5& 0\\ 0& 0& 0.5& 0.5\\ 0.5& 0& 0& 0.5\end{array}\right)$$

で与えられているとする。ただし、$(i,j)$ 成分は $W(j|i)$ を表す。この通信路の通信路容量を求めよ。また、それを達成する入力分布をすべて求めよ。

中文翻译

输入字母表和输出字母表均为 $\{1,2,3,4\}$ 的无记忆信道 $W(y|x)$ 的信道矩阵为

$$\left(\begin{array}{cccc}0.5& 0.5& 0& 0\\ 0& 0.5& 0.5& 0\\ 0& 0& 0.5& 0.5\\ 0.5& 0& 0& 0.5\end{array}\right)$$

其中矩阵的第 $(i,j)$ 元素表示 $W(j|i)$。计算此信道的信道容量，并找出达到此容量的所有输入分布。

---

o1

本解答将分成以下几个层次来阐述:

1. 问题背景与符号
2. 信道的结构分析
3. 容量计算的步骤
4. 达到容量的输入分布
5. 结论与总结

问题背景与符号

给定一个无记忆离散信道 (DMC)，其输入字母与输出字母均为 $\{1,2,3,4\}$。通信路(信道)的转移概率矩阵为

$$W=\left(\begin{array}{cccc}0.5& 0.5& 0& 0\\ 0& 0.5& 0.5& 0\\ 0& 0& 0.5& 0.5\\ 0.5& 0& 0& 0.5\end{array}\right),$$

其中矩阵第 $i$ 行第 $j$ 列元素 $W(j|i)$ 表示当输入符号为 $i$ 时，输出符号为 $j$ 的条件概率。
我们的目标是:

1. 求该信道的容量 $C$。
2. 求达到该容量的所有输入分布 $p(x)$。

---

信道的结构分析

从矩阵可知，对于输入符号 $x$ 和输出符号 $y$:

• 当 $x=1$ 时，$y=1$ 或 $2$ 的概率各为 0.5。
• 当 $x=2$ 时，$y=2$ 或 $3$ 的概率各为 0.5。
• 当 $x=3$ 时，$y=3$ 或 $4$ 的概率各为 0.5。
• 当 $x=4$ 时，$y=1$ 或 $4$ 的概率各为 0.5。
  从输出端来看:
• 输出 $y=1$ 可能来自 $x=1$ 或 $x=4$；
• 输出 $y=2$ 可能来自 $x=1$ 或 $x=2$；
• 输出 $y=3$ 可能来自 $x=2$ 或 $x=3$；
• 输出 $y=4$ 可能来自 $x=3$ 或 $x=4$。
  每个输入符号分到两个不同输出符号，各占 0.5 的概率，说明条件熵 $H(Y|X)$ 在所有可能的输入分布下都是一样的。我们将在下面的容量计算步骤中更明确地看出这一点。

---

容量计算的步骤

要找信道容量 $C$，我们需要最大化互信息 $I(X;Y)$，即

$$C=\underset{p(x)}{\max }I(X;Y)=\underset{p(x)}{\max }[H(Y)-H(Y\mid X)].$$

1. 计算 $H(Y|X)$
   对于任意给定的输入符号 $x$，输出 $y$ 的概率分布都有 2 个可能值，各自 0.5。因此单个输入符号对应的输出熵为 $$H(Y\mid X=x)=-(0.5\log 0.5+0.5\log 0.5)=1\text{ (比特)}.$$ 无论 $x=1,2,3,4$，都是同样的 1 比特。因此 $$H(Y\mid X)=\sum _{x}p(x)H(Y\mid X=x)=1.$$
2. 最大化 $H(Y)$
   由于 $I(X;Y)=H(Y)-H(Y|X)$，要使得 $I(X;Y)$ 最大，等价于在满足 ${\sum }_{x}p(x)=1$ 的约束下，使 $H(Y)$ 尽量大。
   令输入分布 $p(x)=(p_1,p_2,p_3,p_4)$。则输出 $y$ 的分布为: $$\begin{array}{rl}p(y=1)& =0.5p_1+0.5p_4,\\ p(y=2)& =0.5p_1+0.5p_2,\\ p(y=3)& =0.5p_2+0.5p_3,\\ p(y=4)& =0.5p_3+0.5p_4.\end{array}$$ 对于 4 元输出，$H(Y)$ 的最大值是输出分布为均匀时取得，即 $$p(y=1)=p(y=2)=p(y=3)=p(y=4)=\frac{1}{4}.$$ 于是可得一组方程: $$\{\begin{array}{l}{p}_1+p_4=1/2,\\ p_1+p_2=1/2,\\ p_2+p_3=1/2,\\ p_3+p_4=1/2,\\ p_1+p_2+p_3+p_4=1.\end{array}$$ 可以解得一家族解(令 $\alpha =p_1$): $$\begin{array}{rl}& p_1=\alpha ,\\ & p_2=\frac{1}{2}-\alpha ,\\ & p_3=\alpha ,\\ & p_4=\frac{1}{2}-\alpha ,\end{array}\text{其中 }0\le \alpha \le \frac{1}{2}.$$ 这说明在 $\alpha \in [0,\frac{1}{2}]$ 的整个区间内，都能使输出分布均匀为 $1/4$，从而达到最大熵。
3. 计算信道容量 $C$
   当输出分布均匀时，$H(Y)=\log 4=2\text{ 比特}$。而 $H(Y|X)=1$。因此最大互信息为 $$I(X;Y{)}_{\max }=H(Y)-H(Y\mid X)=2-1=1\text{ (比特)}.$$ 由此可得该信道容量 $$C=1\text{ 比特/符号}.$$

---

达到容量的输入分布

如上所述，为了让 $p(y=1)=p(y=2)=p(y=3)=p(y=4)=1/4$，输入分布需要满足:

$$(p_1,p_2,p_3,p_4)=(\alpha ,\frac{1}{2}-\alpha ,\alpha ,\frac{1}{2}-\alpha ),$$

其中 $0\le \alpha \le \frac{1}{2}$。这是一条连续的分布族，而不只是唯一的点分布。
也就是说，只要输入遵从下列形式之一:

$$p(1)=\alpha ,p(2)=\frac{1}{2}-\alpha ,p(3)=\alpha ,p(4)=\frac{1}{2}-\alpha ,(0\le \alpha \le \frac{1}{2}),$$

都能使输出分布均匀，从而达到 $I(X;Y)=1$ 比特的最大值。

---

总结

• 信道容量 $C$: $$C=1\text{ 比特}.$$
• 能达到该容量的所有输入分布: $$p(x=1)=p(x=3)=\alpha ,p(x=2)=p(x=4)=\frac{1}{2}-\alpha ,0\le \alpha \le \frac{1}{2}.$$
• 核心原因:
  该信道对于每个输入符号输出都是二选一 (各 0.5)，因此条件熵 $H(Y|X)$ 始终为 1 比特。要最大化互信息，需要最大化输出熵 $H(Y)$，即让 $Y$ 在 4 个符号上分布均匀。满足相应线性方程后，可得到一族输入分布使得 $Y$ 均匀，从而互信息达到最大 1 比特。
  以上即为本题的详细解答和关键知识点。