問1

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

$$\begin{pmatrix} 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{pmatrix}$$

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

中文翻译

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

$$\begin{pmatrix} 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{pmatrix}$$

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

---

o1

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

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

问题背景与符号

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

$$W = \begin{pmatrix} 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{pmatrix},$$

其中矩阵第 $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 \;=\; \max_{p(x)}\,I(X;Y) \;=\; \max_{p(x)}\,\bigl[\,H(Y) \;-\; H(Y \mid X)\bigr].$$

1. 计算 $H(Y|X)$
   对于任意给定的输入符号 $x$，输出 $y$ 的概率分布都有 2 个可能值，各自 0.5。因此单个输入符号对应的输出熵为

   $$H(Y \mid X=x) \;=\; -\bigl(0.5 \log 0.5 + 0.5 \log 0.5\bigr) \;=\; 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{aligned} p(y=1) &= 0.5\,p_1 \;+\; 0.5\,p_4,\\ p(y=2) &= 0.5\,p_1 \;+\; 0.5\,p_2,\\ p(y=3) &= 0.5\,p_2 \;+\; 0.5\,p_3,\\ p(y=4) &= 0.5\,p_3 \;+\; 0.5\,p_4. \end{aligned}$$

   对于 4 元输出，$H(Y)$ 的最大值是输出分布为均匀时取得，即

   $$p(y=1) \;=\; p(y=2) \;=\; p(y=3) \;=\; p(y=4) \;=\; \frac{1}{4}.$$

   于是可得一组方程:

   $$\begin{cases} 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{cases}$$

   可以解得一家族解(令 $\alpha = p_1$):

   $$\begin{aligned} &p_1 = \alpha,\\ &p_2 = \tfrac12 - \alpha,\\ &p_3 = \alpha,\\ &p_4 = \tfrac12 - \alpha, \end{aligned} \quad \text{其中 } 0 \;\le\; \alpha \;\le\; \tfrac12.$$

   这说明在 $\alpha \in [0,\tfrac12]$ 的整个区间内，都能使输出分布均匀为 $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,\; \tfrac12-\alpha,\; \alpha,\; \tfrac12-\alpha),$$

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

$$p(1) = \alpha,\quad p(2) = \tfrac12 - \alpha,\quad p(3) = \alpha,\quad p(4) = \tfrac12 - \alpha, \quad (0 \le \alpha \le \tfrac12),$$

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

---

总结

• 信道容量 $C$:

  $$C \;=\; 1 \text{ 比特}.$$

• 能达到该容量的所有输入分布:

  $$p(x=1) = p(x=3) = \alpha,\quad p(x=2) = p(x=4) = \tfrac12 - \alpha,\quad 0 \le \alpha \le \tfrac12.$$

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