問1

$k$ を正の整数とする．入力アルファベットが $X = \{0, 1\}^k$, 出力アルファベットが $Y = \{0, 1\}^k$ の無記憶な通信路 $W(Y|X)$ を

$$W(Y|X) = \begin{cases} 0 & (d(X, Y) = 0) \\ \frac{1}{k} & (d(X, Y) = 1) \\ 0 & (d(X, Y) \geq 2) \end{cases}$$

で定める．ただし, $d(X, Y)$ は, $X = (X_1, X_2, \dots, X_k)$ と $Y = (Y_1, Y_2, \dots, Y_k)$ の間のハミング距離

$$d(X, Y) = \sum_{i=1}^k |X_i - Y_i|$$

を表す．この通信路の通信路容量を求めよ．

中文翻译

设 $k$ 为正整数. 输入字母表为 $X = \{0, 1\}^k$, 输出字母表为 $Y = \{0, 1\}^k$, 定义如下的无记忆信道 $W(Y|X)$:

$$W(Y|X) = \begin{cases} 0 & (d(X, Y) = 0) \\ \frac{1}{k} & (d(X, Y) = 1) \\ 0 & (d(X, Y) \geq 2) \end{cases}$$

其中 $d(X, Y)$ 表示 $X = (X_1, X_2, \dots, X_k)$ 和 $Y = (Y_1, Y_2, \dots, Y_k)$ 之间的汉明距离:

$$d(X, Y) = \sum_{i=1}^k |X_i - Y_i|$$

求此信道的通信容量.

---

o1

题目回顾

给定一个无记忆通信路 $W(Y \mid X)$，其中：

• 输入字母表：$X = \{0,1\}^k$
• 输出字母表：$Y = \{0,1\}^k$
• 信道的传输概率定义为

  $$W(Y \mid X) = \begin{cases} 0, & d(X, Y) = 0,\\ \tfrac{1}{k}, & d(X, Y) = 1,\\ 0, & d(X, Y) \ge 2, \end{cases}$$

  其中哈明距离

  $$d(X, Y) = \sum_{i=1}^k \lvert X_i - Y_i \rvert.$$

也就是说，输入码字 $X$ 传输后，输出码字 $Y$ 只能与 $X$ 在恰好 1 个比特处不同（且均等概率为 $1/k$），与 $X$ 完全相同或相差 2 个比特以上的情况都不会发生。

要求：求出该通信信道的容量（channel capacity）。

---

思路解析

1. 理解信道性质：
   对任意输入 $X\in\{0,1\}^k$，有且只有 $k$ 个可能输出 $Y$（每个与 $X$ 在 1 个比特处不同），并且这些输出都是等概率 $\tfrac{1}{k}$ 出现。

2. 对称性与均匀输入：
   类似二进制对称信道的思路，对于这样的对称信道，通常可以用均匀分布(Equiprobable)的输入来达到最大互信息，从而求得容量。

3. 计算互信息 $I(X;Y)$：
   令输入分布 $p(X) = 2^{-k}$（即对 $\{0,1\}^k$ 上所有 $X$ 均等）。则

   $$I(X;Y) = H(Y) - H(Y \mid X).$$

   • (a) 计算 $H(Y)$：
     因为对于每个 $Y$，恰好有 $k$ 个 $X$ 使得 $d(X,Y) = 1$，并且每个 $X$ 的先验概率都是 $2^{-k}$，再乘上信道传输概率 $\tfrac{1}{k}$，可以得到

     $$p(Y) = \sum_{X} p(X)\,W(Y \mid X) = \sum_{X: d(X,Y)=1} \tfrac{1}{2^k} \cdot \tfrac{1}{k} = k \cdot \tfrac{1}{2^k} \cdot \tfrac{1}{k} = \tfrac{1}{2^k}.$$

     因此 $Y$ 在 $\{0,1\}^k$ 上也是均匀分布，故

     $$H(Y) = \log_2\bigl(2^k\bigr) = k.$$

     （一句话说明：若随机变量在大小为 $2^k$ 的集合上均匀分布，则其熵为 $k$ 比特。）

   • (b) 计算 $H(Y \mid X)$：
     在给定 $X$ 的情况下，$Y$ 只能在与 $X$ 距离为 1 的 $k$ 个码字里等概率出现，因此

     $$H(Y \mid X) = \log_2(k).$$

     （一句话说明：若事件在 $k$ 种可能中均匀分布，则熵为 $\log_2 k$。）

   • (c) 因此 $I(X;Y)$：

     $$I(X;Y) \;=\; H(Y) - H(Y \mid X) \;=\; k - \log_2(k).$$

4. 信道容量：
   对于对称离散无记忆信道，选择上述均匀输入分布即可达成最大互信息，因此信道容量为

   $$C = k \;-\; \log_2(k).$$

---

最终答案

$$\boxed{ \text{该信道容量为 } k - \log_2\bigl(k\bigr). }$$