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

标签：

Author

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_i$ 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$ 传输信息，其输入和输出分别为 $X\in\{-1,1\}$ 和 $Y\in\{-1,1\}$ 。第 $i$ 次通信的输入输出关系为

Y_i=Z_i\times X_i\qquad(i=1,2,\ldots),

其中 $\times$ 表示整数乘法。 $Z_i\in\{-1,1\}$ 为信道在第 $i$ 次通信时的内部状态，其值可随当前或过去的输入状态以及过去的输出状态而变化。发送方和接收方均不能直接观测 $Z_i$ ，但可以知道它如何随输入、输出变化。以下各问均使用以 $2$ 为底的对数，必要时可使用近似值 $\log_2 3=1.585$ 、 $\log_2 5=2.322$ 、 $\log_2 7=2.807$ 。

(1) 令 $X_i$ 为理想独立随机变量，以概率 $\mu$ 取 $1$ ，以概率 $1-\mu$ 取 $-1$ 。假设当 $X_i=1$ 时， $Z_i$ 以概率 $1$ 取 $1$ ；当 $X_i=-1$ 时， $Z_i$ 等概率取 $1$ 或 $-1$ 。

(1-i) 求信道 $C$ 的熵 $H[X]$ 、 $H[Y]$ 及条件熵 $H[Y\mid X]$ 。
(1-ii) 求信道 $C$ 的容量。

(2) 假设 $Z_1$ 等概率取 $1$ 或 $-1$ ；对于 $i\ge2$ ， $Z_i$ 以概率 $1$ 等于上一次的输出，即 $Z_i=Y_{i-1}$ 。求使用该信道 $n$ 次最多能传输多少比特。

(3) 假设当 $i$ 为奇数时， $Z_i$ 等概率取 $1$ 或 $-1$ ；当 $i$ 为偶数时， $Z_i$ 以概率 $1$ 保持上一次的值，即 $Z_i=Z_{i-1}$ 。求信道 $C$ 的容量，并给出达到此容量的编码。

(4) 假设 $Z_1$ 以概率 $1$ 取 $1$ ；对于 $i\ge2$ ， $Z_i$ 以概率 $1$ 等于上一次的输入，即 $Z_i=X_{i-1}$ 。令 $X_i$ 为理想独立随机变量，以概率 $\mu$ 取 $1$ ，以概率 $1-\mu$ 取 $-1$ 。计算 $i$ 充分大、达到稳态时 $Y_i=1$ 的概率 $q$ 。

II. 信号处理

回答以下信号处理问题。考虑图 1、图 2 所示的两个无限冲激响应系统。 $x_1(n)$ 和 $y_1(n)$ 分别为图 1 中系统 1 的输入、输出信号序列，表示时刻 $nT$ （ $T>0$ ， $n=0,1,\ldots$ ）的信号值。同样， $x_2(n)$ 和 $y_2(n)$ 分别为图 2 中系统 2 的输入、输出序列。电路由加法器、系数乘法器和延时器构成，其各自功能见图 3。

(1) 求系统 1 的冲激响应 $h_1(n)$ 及其 $z$ 变换 $H_1(z)$ 。

(2) 计算系统 1 的频率响应，并说明它对输入信号的滤波功能。

(3) 求使系统 2 与系统 1 等效的参数 $a,b,c$ 。

(4) 画出与系统 2 等效，但延时器数量少于图 2 中原系统 2 的电路。

图1、图2：两个系统；图3：加法器、系数乘法器、延时器

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) \\ &\quad - 0.5(1 + \mu)\log0.5(1 + \mu) \\ &= -0.5(1 - \mu)\log(1 - \mu) \\ &\quad - 0.5(1 + \mu)\log(1 + \mu) \\ &\quad - 0.5(1 - \mu)\log0.5 - 0.5(1 + \mu)\log0.5 \\ &= -0.5(1 - \mu)\log(1 - \mu) \\ &\quad - 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) = \log_2\frac54 \simeq 0.322$

(2)

$Y_1=Z_1X_1$ は $X_1$ と独立なので、第 $1$ 回では情報を送れない。一方、 $i\ge2$ では受信側が

X_i=Y_iY_{i-1}

により $X_i$ を誤りなく復号できる。したがって達成可能な最大値は $n-1$ ビットである（上界は $I(X^n;Y^n)=I(X^n;Y_2^n\mid Y_1)\le H(Y_2^n\mid Y_1)\le n-1$ から従う。 $Y_1$ は入力列全体と独立である）。

(3)

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

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

連続した奇数回目と偶数回目を一つの符号とすると、受信側は

Y_{2k-1}Y_{2k}=X_{2k-1}X_{2k}

を得るので、各組で高々 $1$ ビットを送れる。 $1\ 1、1\ -1$ を符号語にし、復号領域としてそれぞれ $\{1\ 1,-1-1\}$ 、 $\{1-1,-1\ 1\}$ を設ければこの上界を達成する。よって通信路容量は $1/2$ bit/use である。

(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)$ 、 $y_1(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) = 2(0.5)^n u(n)-\delta(n) \end{aligned}

$u(n)$ は単位ステップ関数である。

(2)

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

$z=e^{j\omega T}$ とおくと、

H_1(e^{j\omega T}) = \frac{1 + 0.5e^{-j\omega T}}{1 - 0.5e^{-j\omega T}},\qquad \left|H_1(e^{j\omega T})\right| =\sqrt{\frac{1.25+\cos(\omega T)}{1.25-\cos(\omega T)}}

ゼロ点は $z=-0.5$ 、極は $z=0.5$ である。 $0\le\omega T\le\pi$ で振幅は $3$ から $1/3$ まで単調に減少するので、ローパスフィルタである。

(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$ 。

Author​

Description​

I​

II​

题目描述​

Kai​

I​

(1)​

(1-i)​

(1-ii)​

(2)​

(3)​

(4)​

II​