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=\underset{n\to \infty }{\lim }\underset{P_{X^n}\in {\mathcal{P}}_n}{\max }\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=\underset{n\to \infty }{\lim }\underset{P_{X^n}\in {\mathcal{P}}_n}{\max }\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.75p+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)$。