東京大学 工学系研究科 電気系工学専攻 2019年8月実施 問題3 情報工学I

标签：

• Tokyo-University
• Channel-Capacity
• Finite-State-Channel-with-Memory
• Z-Transform
• Infinite-Impulse-Response-Filter-Transfer-Function-and-Realization

Author

donguri0912

Description

I

Answer the following questions on information theory. Suppose that we transmit information by using a time-discrete communication channel $C$, whose input and output are designated as $X \in \{-1,1\}$ and $Y \in \{-1,1\}$, respectively. The input and output relation of the $i$-th communication via $C$ is represented as $Y_i = Z_i \times X_i(i = 1,2,\cdots)$, where $\times$ means the multiplication of integers. $Z_i \in \{-1,1\}$ is an internal state of the channel at the $i$-th communication, and its value can change depending on the current or past states of the input and on the past states of the output. Both sender and receiver are unable to observe the value of $Z_i$ directly although they can have knowledge about how $Z_i$ changes depending on the input and output. Use the logarithm base $2$ for your answers of the following questions. You may also use the following approximations upon necessity: $\log_23 = 1.585$, $\log_25 = 2.322$, $\log_27 = 2.807$.

(1) Let $X_i$ be an ideally independent random variable that takes $X_i = 1$ with probability $\mu$ and $X_i = -1$ with probability $1 - \mu$. Assume that $Z_i$ becomes $1$ with probability $1$ when $X_i = 1$ and that it takes either $1$ or $-1$ with equal probability when $X_i = -1$.

• (1-i) Obtain the entropies $H[X]$ and $H[Y]$ and the conditional entropy $H[Y|X]$ of $C$.
• (1-ii) Obtain the channel capacity of $C$.

(2) Assume that $Z_1$ takes either $1$ or $-1$ with equal probability and that, for $i \ge 2$, the value of $Z_i$ becomes the same as the previous output value $Y_{i-1}$ with probability $1$ as $Z_i = Y_{i-1}$.Obtain the maximum bits that can be transmitted by using this channel $n$ times.

(3) Assume that $Z_1$ takes either $1$ or $-1$ with equal probability when $i$ is odd and that $Z_i$ keeps its previous value with probability $1$ as $Z_i = Z_{i-1}$ when $i$ is even.Obtain the channel capacity of $C$ and show a code that can achieve the capacity.

(4) Assume that $Z_1 = 1$ with probability $1$ and that, for $i \ge 2$, the value of $Z_i$ becomes the same as the previous input value $X_{i-1}$ with probability $1$ as $Z_i = X_{i-1}$. Let $X_i$ be an ideally independent random variable that takes $X_i = 1$ with probability $\mu$ and $X_i = -1$ with probability $1 - \mu$.Calculate the probability $q$ that $Y_i = 1$ at the stationary state for sufficiently large $i$.

II

Answer the following questions on signal processing. Consider the two infinite impulse response systems shown in Figs. $1$ and $2$. $x_1(n)$ and $y_1(n)$ are the input and output signal sequences of system $1$ in Fig. $1$, respectively, and represent the signal values at time $nT(T > 0)$ for $n = 0,1,\cdots$.Similarly, $x_2(n)$ and $y_2(n)$ are the input and output sequences of system $2$ in Fig. $2$. The circuits consist of adders, coefficient multipliers, and delays, whose respective functions are described in Fig. $3$.

(1) Obtain the impulse response of system $1$, $h_1(n)$, and its $z$-transform $H_1(z)$.

(2) Calculate the frequency response of system 1 and explain the filtering function of this system on the input signal.

(3) Obtain the parameter values of $a,b$ and $c$ that makes system $2$ equivalent to system $1$.

(4) Draw an equivalent circuit of system $2$ that has a smaller number of delays than the original system $2$ shown in Fig. $2$.

题目描述

本题分为信息论和信号处理两部分。

I. 设离散时间通信信道 $C$ 的输入、输出均取 $\{-1,1\}$，第 $i$ 次通信满足 $Y_i=Z_iX_i$。内部状态 $Z_i\in\{-1,1\}$ 可依赖当前或过去的输入以及过去的输出，但收发双方不能直接观测它，只知道其演化规律。所有对数以 $2$ 为底，可按需使用题中给出的对数近似值。

1. 当各 $X_i$ 独立且 $\Pr(X_i=1)=\mu$，并且 $X_i=1$ 时 $Z_i=1$、$X_i=-1$ 时 $Z_i$ 等概率取 $\pm1$，求 $H[X]$、$H[Y]$、$H[Y\mid X]$，进而求信道容量。
2. 当 $Z_1$ 等概率取 $\pm1$，且 $i\ge2$ 时恒有 $Z_i=Y_{i-1}$，求使用该信道 $n$ 次最多能够传输的比特数。
3. 每个奇数时刻的 $Z_i$ 等概率取 $\pm1$，每个偶数时刻保持前一时刻状态，即 $Z_i=Z_{i-1}$。求信道容量，并给出达到该容量的编码。
4. 当 $Z_1=1$，且 $i\ge2$ 时 $Z_i=X_{i-1}$；各输入仍独立并满足 $\Pr(X_i=1)=\mu$。求充分大 $i$ 时稳态下 $\Pr(Y_i=1)=q$。

II. 对图 1、图 2 所示的两个无限冲激响应离散系统，输入输出分别为 $x_1(n),y_1(n)$ 与 $x_2(n),y_2(n)$，电路由图 3 定义的加法器、系数乘法器和延时器组成。

1. 求系统 1 的冲激响应 $h_1(n)$ 及其 $z$ 变换 $H_1(z)$。
2. 求系统 1 的频率响应，并说明它对输入信号实现何种滤波。
3. 求使系统 2 与系统 1 等效的参数 $a,b,c$。
4. 画出与系统 2 等效、但使用更少延时器的电路。

Kai

I

(1)

$\mathcal{H}(\cdot)$ はエントロピー関数

(1-i)

$$H[X] = \mathcal{H}(\mu) = -\mu\log\mu - (1 - \mu)\log(1 - \mu)$$

$$\begin{aligned} H[Y] &= \mathcal{H}(0.5(1 - \mu)) \\ &= -0.5(1 - \mu)\log0.5(1 - \mu) - 0.5(1 + \mu)\log0.5(1 + \mu) \\ &= -0.5(1 - \mu)\log(1 - \mu) - 0.5(1 + \mu)\log(1 + \mu) - 0.5(1 - \mu)\log0.5 - 0.5(1 + \mu)\log0.5 \\ &= -0.5(1 - \mu)\log(1 - \mu) - 0.5(1 + \mu)\log(1 + \mu) + 1 \\ \end{aligned}$$

$$H[Y|X] = \mu\mathcal{H}(1) + (1 - \mu)\mathcal{H}(0.5) = 1 - \mu$$

(1-ii)

$$\begin{aligned} &I(X;Y) = H[Y] - H[Y|X] \\ &= -0.5(1 - \mu)\log(1 - \mu) - 0.5(1 + \mu)\log(1 + \mu) + 1 - (1 - \mu) \\ &= -0.5(1 - \mu)\log(1 - \mu) - 0.5(1 + \mu)\log(1 + \mu) + \mu \end{aligned}$$

$$\begin{aligned} \frac{dC_c}{d\mu} &= 0.5\log(1 - \mu) + \frac{0.5}{\log_e2} - 0.5\log(1 + \mu) - \frac{0.5}{\log_e2} + 1 \\ &= 0.5\log\frac{1 - \mu}{1 + \mu} + 1 = 0 \end{aligned}$$

となる時、つまり $\mu = \frac{3}{5}$ で最小となる。

このとき

$$\begin{aligned} I(X;Y)|_{\mu = \frac{3}{5}} &= -0.5\frac{2}{5}\log\frac{2}{5} - 0.5\frac{8}{5}\log\frac{8}{5} + \frac{3}{5} \\ &= -\frac{1}{5}\log2 - \frac{4}{5}\log8 + \log5 + \frac{3}{5} \\ &= 0.322 \end{aligned}$$

よって、求める通信路容量 $C_C = \max_{\mu}I(X;Y) = 0.322$

(2)

$n$ 回目に送信できる最大のビットは $n$ 回目の通信路容量 $C_n$ に等しく、$n$ 回目の通信路はそれぞれ $2$ 元対称通信路として考えられることから $C_n = \max I(X;Y) = \max(H[Y]) - H[Y|X]$ と計算できる。

$n = 1$ のとき、$n - 1$ 回目の $Y$ が分かっているので、$C_n = 1 - \mathcal{H}(1) = 1$ よって、$n$ 回で遅れるビット数は $n - 1$ ビットである。

(3)

通信路は $2$ 元対称通信路として考えられることから、奇数回目の時、

$$C_{\text{奇数回目}} = \max I(X;Y) = \max(H[Y]) - H[Y|X] = 1 - \mathcal{H}(0.5) = 0$$

偶数回目の時、前回の $Z$ が分かっていれば、符号は連続した奇数回目と偶数回目を一つの符号として、$1\ 1、1\ -1$ を符号語にし、復号領域としてそれぞれ $\{1\ 1,-1-1\}$、$\{1-1,-1\ 1\}$ を設ければよい。

(4)

$i$ が十分大きい場合について、$X_i$, $X_{i-1}(=Z_i)$ は独立な確率変数である。よって、$Y_i = 1$ となる確率 $q$ は

$$q = \mu^2 + (1 - \mu)^2 = 2\mu^2 - 2\mu + 1$$

II

(1)

$x_1(n)$、$x_2(n)$ の $z$ 変換を $X_1(z)、Y_1(z)$ となる。

$$\begin{aligned} &Y_1(z) = \frac{1}{1 - 0.5z^{-1}} \times 2X_1(z) - X_1(z) \\ &H_1(z) = \frac{Y_1(z)}{X_1(z)} = \frac{2}{1 - 0.5z^{-1}} - 1\\ &h_1(n) = \delta(n) + 2 \times 0.5^n \end{aligned}$$

$2 \times 0.5^n$ は $u(n)$ をつけても良い。

(2)

$$H_1(z) = \frac{2}{1 - 0.5z^{-1}} - 1 = \frac{1 + 0.5z^{-1}}{1 - 0.5z^{-1}}$$

ゼロ点は $z = 2e^{\pm j\pi}$、極は $z = 2e^0$ である。 よって高周波をカットするローパスフィルタである。

(3)

$x_2(n)$、$y_2(n)$ の $z$ 変換を $X_2(z)$、$Y_2(z)$ とする。

$$\begin{aligned} &Y_2(z) = aX_2(z) + bz^{-1}X_2(z) + cz^{-1}Y_2(z) \\ &(1 - cz^{-1})Y_2(z) = (a + bz^{-1})X_2(z) \\ &\frac{Y_2(z)}{X_2(z)} = \frac{a +_ bz^{-1}}{1 - cz^{-1}} \end{aligned}$$

これが $H_1(z)$ と一致するとき、$a = 1$、$b = 0.5$、$c = 0.5$。

(4)