R05-B-問2

問2

時刻 $t$ の入力 $X_t \in \{0, 1\}$ ($t = 1, 2, \dots$) に対し、入力と独立な誤り源 $S_E$ から発生した記号 $Z_t \in \{0, 1\}$ が加わった値 $Y_t = X_t \oplus Z_t$ が出力される加法的2元通信路 $W$ を考える。ただし、$\oplus$ は排他的論理和を表し、$0 \oplus 1 = 1$、$1 \oplus 1 = 0$ である。誤り源 $S_E$ が、$P(Z_{t+1} = 1 | Z_t = 0) = 0.25$、$P(Z_{t+1} = 1 | Z_t = 1) = 0.5$ となる定常な単純マルコフ情報源である場合について、以下の問いに答えよ。 (1) 誤り源 $S_E$ の定常確率分布を求めよ。 (2) 誤り源 $S_E$ のエントロピーレート $H(S_E)$ を求めよ。 (3) $X^n = (X_1, \dots, X_n)$ が $P(X_t = 1) = \frac{1}{2}$ ($t = 1, 2, \dots, n$) である離散無記憶情報源からの出力であり、$Z^n = (Z_1, \dots, Z_n)$ が定数 $z^n \in \{0, 1\}^n$ に固定されていると仮定する。$Y^n = (Y_1, \dots, Y_n)$ が $P(Y_t = 1) = \frac{1}{2}$ ($t = 1, 2, \dots, n$) である離散無記憶情報源の出力であることを示せ。 (4) 通信路 $W$ の通信路容量は以下の式で定義される。

$$C = \lim_{n \to \infty} \max_{P_{X^n} \in \mathcal{P}_n} \frac{1}{n} I(X^n; Y^n)$$

ただし、$I(X^n; Y^n)$ は $X^n$ と $Y^n$ の間の相互情報量を、$P_{X^n}$ は入力 $X^n$ の確率分布を、$\mathcal{P}_n$ は $\{0, 1\}^n$ 上の確率分布全てからなる集合を表す。このとき、$C = 1 - H(S_E)$ となることを示せ。

中文翻译

对于时刻 $t$ 的输入 $X_t \in \{0, 1\}$ ($t = 1, 2, \dots$)，考虑一个加性二元信道 $W$，其输出为 $Y_t = X_t \oplus Z_t$，其中 $Z_t \in \{0, 1\}$ 是与输入独立的错误源 $S_E$ 产生的符号，$\oplus$ 表示异或运算，$0 \oplus 1 = 1$、$1 \oplus 1 = 0$。假设错误源 $S_E$ 是一个平稳的简单马尔可夫信息源，满足 $P(Z_{t+1} = 1 | Z_t = 0) = 0.25$、$P(Z_{t+1} = 1 | Z_t = 1) = 0.5$，请回答以下问题。 (1) 求错误源 $S_E$ 的平稳概率分布。 (2) 求错误源 $S_E$ 的熵率 $H(S_E)$。 (3) 假设 $X^n = (X_1, \dots, X_n)$ 是 $P(X_t = 1) = \frac{1}{2}$ ($t = 1, 2, \dots, n$) 的离散无记忆信息源的输出，且 $Z^n = (Z_1, \dots, Z_n)$ 固定为常数 $z^n \in \{0, 1\}^n$。证明 $Y^n = (Y_1, \dots, Y_n)$ 是 $P(Y_t = 1) = \frac{1}{2}$ ($t = 1, 2, \dots, n$) 的离散无记忆信息源的输出。 (4) 信道 $W$ 的信道容量定义为

$$C = \lim_{n \to \infty} \max_{P_{X^n} \in \mathcal{P}_n} \frac{1}{n} I(X^n; Y^n)$$

其中，$I(X^n; Y^n)$ 是 $X^n$ 和 $Y^n$ 之间的互信息，$P_{X^n}$ 是输入 $X^n$ 的概率分布，$\mathcal{P}_n$ 是 $\{0, 1\}^n$ 上所有概率分布的集合。证明 $C = 1 - H(S_E)$。

---

解答

(1) 设平稳分布为 $P(Z_t = 0) = p$、$P(Z_t = 1) = 1 - p$，则

$$p = 0.75 p + 0.5 (1 - p) \Rightarrow p = \frac{2}{3}$$

因此，平稳分布为 $P(Z_t = 0) = \frac{2}{3}$、$P(Z_t = 1) = \frac{1}{3}$。 (2) 熵率为

$$H(S_E) = H(Z_{t+1} | Z_t) = \frac{2}{3} H(0.25) + \frac{1}{3} H(0.5) = \frac{2}{3} \times 0.811 + \frac{1}{3} \times 1 = 0.874$$

(3) 由于 $X_t$ 和 $Z_t$ 独立，且 $P(X_t = 1) = \frac{1}{2}$，因此 $P(Y_t = 1) = \frac{1}{2}$。 (4) 由于 $Y_t = X_t \oplus Z_t$，且 $Z_t$ 是独立的，因此 $I(X^n; Y^n) = n - H(S_E)$，从而 $C = 1 - H(S_E)$。