R04-B-問1

問1

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

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

で定める．ただし, $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{array}{ll}0& (d(X,Y)=0)\\ \frac{1}{k}& (d(X,Y)=1)\\ 0& (d(X,Y)\ge 2)\end{array}$$

其中 $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{array}{ll}0,& d(X,Y)=0,\\ \frac{1}{k},& d(X,Y)=1,\\ 0,& d(X,Y)\ge 2,\end{array}$$ 其中哈明距离 $$d(X,Y)=\sum _{i=1}^k|X_i-Y_i|.$$

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

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

---

思路解析

1. 理解信道性质：
   对任意输入 $X\in \{0,1{\}}^k$，有且只有 $k$ 个可能输出 $Y$（每个与 $X$ 在 1 个比特处不同），并且这些输出都是等概率 $\frac{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}$，再乘上信道传输概率 $\frac{1}{k}$，可以得到

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

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

     $$H(Y)={\log }_2\left(2^k\right)=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\left(k\right).}$$