九州大学 システム情報科学府 情報理工学専攻 2022年8月実施 情報理論

标签：

• Kyushu-University
• Differential-Entropy
• Markov-Information-Source
• Entropy-Rate
• Additive-Markov-Noise-Channel
• Channel-Capacity

Author

Yu, 祭音Myyura

Description

出典：九州大学公式問題。

【問 1】

以下の各問いに答えよ．

(1) 区間 $[0, a] (a > 0)$ 上の一様分布に従う確率変数の微分エントロピーを求めよ．

(2) 区間 $[0, a] (a > 0)$ 上で定義された確率密度関数 $p(x)=2x/a^2$ に従う確率変数の微分 エントロピーを求めよ．

【問 2】

時刻 $t$ の入力 $X_t ∈ \{0, 1\}(t = 1, 2,...)$ に対し，入力と独立な誤り源 $S_E$ から発生した記号 $Z_t∈\{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,...,X_n)$ が $P(X_t = 1) = 1/2 (t = 1, 2,...,n)$ である離散無記憶情報源からの出力であり，$Z^n = (Z_1,...,Z_n)$ が定数 $z^n ∈ \{0, 1\}^n$ に固定されていると仮定する $Y^n = (Y_1,...,Y_n)$ が $P(Y_t = 1) = 1/2 (t = 1, 2,...,n)$ である離散無記憶情報源の出力であることを示せ．

(4) 通信路 $W$ の通信路容量は以下の式で定義される．

$$C = \lim_{n \rightarrow \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】回答：

1. 求服从区间 $[0,a]$（$a>0$）上均匀分布的随机变量的微分熵。
2. 求服从区间 $[0,a]$（$a>0$）上概率密度 $p(x)=2x/a^2$ 的随机变量的微分熵。

【问题 2】考虑加性二元信道 $W$。时刻 $t$ 的输入为 $X_t\in\{0,1\}$（$t=1,2,\ldots$），与输入独立的误差源 $S_E$ 产生 $Z_t\in\{0,1\}$，信道输出为 $Y_t=X_t\oplus Z_t$。其中 $\oplus$ 表示异或，例如 $0\oplus1=1$、$1\oplus1=0$。误差源 $S_E$ 是平稳一阶 Markov 信源，满足

$$P(Z_{t+1}=1\mid Z_t=0)=0.25,\qquad P(Z_{t+1}=1\mid Z_t=1)=0.5.$$

回答：

1. 求误差源 $S_E$ 的平稳概率分布。

2. 求误差源 $S_E$ 的熵率 $H(S_E)$。

3. 设 $X^n=(X_1,\ldots,X_n)$ 是离散无记忆信源的输出，且对 $t=1,\ldots,n$ 有 $P(X_t=1)=\frac12$；再把 $Z^n=(Z_1,\ldots,Z_n)$ 固定为任意常量序列 $z^n\in\{0,1\}^n$。证明 $Y^n=(Y_1,\ldots,Y_n)$ 仍是满足 $P(Y_t=1)=\frac12$（$t=1,\ldots,n$）的离散无记忆信源输出。

4. 信道 $W$ 的容量定义为

   $$C=\lim_{n\to\infty} \max_{P_{X^n}\in\mathcal P_n} \frac1n 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)$。

Kai

【問 1】

以下の対数は底 $2$、エントロピーの単位は bit とする。

(1)

$$h(X) = - \int_0^a \frac{1}{a} \log \frac{1}{a} \text{d}x = \log a$$

(2)

$$h(X) = -\int_0^a \frac{2x}{a^2} \log \frac{2x}{a^2} \text{d}x = \log a + \frac{1}{2\ln2} - 1$$

【問 2】

(1)

$$\Pi = \begin{bmatrix} 0.75 & 0.25 \\ 0.5 & 0.5 \end{bmatrix}$$

定常確率分布を $w = (w_0,w_1)$ とすると

$$\left \{ \begin{aligned} &w_0 + w_1 = 1 \\ &w\Pi = w \\ \end{aligned} \Rightarrow w = (\frac{2}{3},\frac{1}{3}) \right.$$

(2)

$$\begin{aligned} H(S_E) &= w_0 \mathcal{H}(0.75) + w_1 \mathcal{H}(0.5) \\ &= \frac{2}{3}[-\frac{3}{4}\log_2(\frac{3}{4}) - \frac{1}{4}\log_2(\frac{1}{4})] + \frac{1}{3} \\ &= \frac{5}{3} - \frac{1}{2}\log_2 3 \end{aligned}$$

(3)

$Z_t = 0$ のとき, $Y_t = X_t \oplus Z_t = X_t \oplus 0 = X_t$

$$P(Y_t = 1) = P(X_t = 1) = \frac{1}{2}$$

$Z_t = 1$ のとき, $Y_t = X_t \oplus Z_t = X_t \oplus 1$

$$P(Y_t = 1) = P(X_t = 0) = 1 - P(X_t = 1) = \frac{1}{2}$$

さらに $z^n$ を固定すると、写像 $x^n\mapsto x^n\oplus z^n$ は各成分ごとの全単射である。したがって $X_1,\ldots,X_n$ の独立性も保たれ、$Y^n$ は一様な無記憶情報源の出力である。

(4)

$$\begin{aligned} I(X^n;Y^n) &=H(Y^n)-H(Y^n\mid X^n)\\ &=H(Y^n)-H(Z^n)\\ &\le n-H(Z^n). \end{aligned}$$

独立な一様入力を選べば、全ての $z^n,y^n$ について (3) より $P(Y^n=y^n\mid Z^n=z^n)=2^{-n}$ である。これを $Z^n$ について平均しても $P(Y^n=y^n)=2^{-n}$ なので、$Y^n$ も一様であり、$H(Y^n)=n$ なので等号が成り立つ。よって

$$\begin{aligned} C &=\lim_{n\to\infty}\left(1-\frac1nH(Z^n)\right)\\ &=1-H(S_E). \end{aligned}$$