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

标签：

• Tokyo-University
• Markov-Source-Stationary-Distribution
• Entropy-Rate
• Huffman-Coding
• Source-Extension
• Continuous-Time-Fourier-Transform
• Ideal-Low-Pass-Impulse-Response
• Dirac-Comb-Fourier-Transform
• Sampling-Theorem-and-Aliasing

Author

donguri0912

Description

I.

情報理論に関する以下の問に答えよ．$3$ つの状態 $\{s_0,s_1,s_2\}$ を持つマルコフ情報源を $S$ とする．各試⾏で $S$ は以下の式で与えられる遷移確率⾏列 $T$ に従って次の状態に遷移する．

$$\begin{aligned} T = \begin{bmatrix} p(s_0|s_0) & p(s_1|s_0) & p(s_2|s_0) \\ p(s_0|s_1) & p(s_1|s_1) & p(s_2|s_1) \\ p(s_0|s_2) & p(s_1|s_2) & p(s_2|s_2) \\ \end{bmatrix} = \begin{bmatrix} 0.3 & 0.7 & 0 \\ 0.3 & 0.5 & 0.2 \\ 0.8 & 0 & 0.2 \\ \end{bmatrix} \end{aligned}$$

遷移の間，$S$ は次の状態を出⼒する．必要に応じて以下の近似を⽤いてよい:

$$\log_23 = 1/58,\log_25 = 2.32,\log_27 = 2.81$$

(1) $S$ の状態遷移図を描け．

(2) 試⾏を⼗分な回数繰り返した後，それぞれ状態 $s_0,s_1,s_2$ になる確率 $P_0,P_1,P_2$ を求めよ。

(3) $S$ の全体のエントロピーを求めよ．(2)で定義される $P_0,P_1,P_2$ を⽤いて回答に⽰せ．

(4) $S$ の連続する $2$ つの出⼒に対して符号語を割り当てることを考える。

• (4-i) 最も効率の良い符号を設計せよ。
• (4-ii) (4-i)で設計した符号の符号化効率について、定量化する⽅法について述べよ．

II.

信号処理に関する以下の問に答えよ．連続時間信号 $f(t)$ のフーリエ変換 $F(\omega)$ は，$t(-\infty < t < \infty)$ を時間，$\omega$ を⾓周波数，$j$ を虚数単位とすると

$$\begin{align} F(\omega) = \int_{-\infty}^{\infty}f(t)e^{-j\omega t}dt \tag{i} \end{align}$$

で与えられる．その逆フーリエ変換は

$$\begin{align} f(t) = \frac{1}{2\pi}\int_{-\infty}^{\infty} F(\omega)e^{j\omega t}d\omega \tag{ii} \end{align}$$

で与えられる．単位インパルス関数 $\delta(t)$ は

$$\begin{align} \delta(t) = \left\{ \begin{aligned} \infty,\quad t = 0 \\ 0,\quad t \neq 0 \\ \end{aligned} \right. \text{ かつ } \int_{-\infty}^{\infty} \delta(t)dt = 1 \tag{iii} \end{align}$$

で表される．周期 $T$ の周期関数 $g(t)$ の複素フーリエ級数展開は

$$\begin{align} g(t) = \sum_{n = -\infty}^{\infty}c_n e^{j\frac{2\pi}{T}nt},c_n = \frac{1}{T}\int_{-\frac{T}{2}}^{\frac{T}{2}}g(t)e^{-j\frac{2\pi}{T}nt}dt \quad (n:整数) \tag{iv} \end{align}$$

で表される．

(1) 連続実時間信号 $x(t)$ (ただし実数)のフーリエ変換を $X(\omega)$ とする．その複素共役 $X^*(\omega)$ は $X(-\omega)$ と等価であることを⽰せ．

(2) 単位インパルス関数のフーリエ変換を求めよ．

(3) 信号 $x(t)$ をローパスフィルタに⼊⼒し，出⼒信号 $y(t)$ を得るものとし，ローパスフィルタは理想的な周波数応答 $H(\omega)$ を持ち，$\omega_c(>0)$ を遮断周波数としたとき

$$\begin{align} G(\omega) = \left\{ \begin{aligned} &1 ,|\omega| \leq w_c \\ &0, \text{それ以外} \end{aligned} \right. \tag{v} \end{align}$$

であるとする．$x(t)$ が単位インパルスであると仮定したとき，出⼒信号 $y(t)$ を求めよ．さらに，$y(t)$ の波形を描き，$y(0)$ の値，および $y(t) = 0$ となる $t$ の値を⽰すこと．

(4) 周期 $T(>0)$ の周期インパルス列 $d(t)$ は

$$\begin{align} d(t) = \sum_{n = -\infty}^{\infty}\delta(t - nT) \tag{vi} \end{align}$$

のように⽰すことができる．

• (4-i) $d(t)$ の複素フーリエ級数展開を表せ．
• (4-ii) $d(t)$ のフーリエ変換を $D(\omega)$ としたとき，$D(\omega)$ が周期インパルス列からなることを⽰せ．

(5) 連続実時間信号 $x(t)$ を標本化することを考える。

• (5-i) 標本化された信号から $x(t)$ をどのように復元すればよいか，数⾏程度で説明せよ．必要に応じて Eq.(iv) から (vi) を⽤いてよい．
• (5-ii) 標本化された信号から $x(t)$ が復元できるときの条件を⽰せ．

Kai

I.

(1)

(2)

$$\left\{ \begin{aligned} &0.3P_0 + 0.3P_1 + 0.8P_2 = P_0 \\ &0.7P_0 + 0.5P_1 = P_1 \\ &0.2P_1 + 0.2P_2 = P_2 \\ &P_0 + P_1 + P_2 = 1 \\ \end{aligned} \right.$$

これを解いて、$P_0 = \frac{4}{11} , P_1 = \frac{28}{55} , P_2 = \frac{7}{55}$

解き方は次のよう。

$$\left\{ \begin{aligned} &-0.7P_0 + 0.3P_1 + 0.8P_2 = 0 \\ &0.7P_0 - 0.5P_1 = 0 \\ &0.2P_1 - 0.8P_2 = 0 \\ &P_0 + P_1 + P_2 = 1 \\ \end{aligned} \right.$$

これを拡大係数行列にして解く。

$$\begin{bmatrix} -0.7 & 0.3 & 0.8 & 0 & ...\textcircled{1} \\ 0.7 & -0.5 & & 0 & ...\textcircled{2} \\ & 0.2 & -0.8 & 0 & ...\textcircled{3} \\ 1 & 1 & 1 & -1 & ...\textcircled{4} \\ \end{bmatrix}$$

ちなみにここで、各行の一列だけにマイナスがついていることを確認しておくこと。これは簡単なチェックであるが、しなかったせいで永遠に答えが出なかった筆者の反省である。上三角行列を作っていくが、変数が $3$ つの方程式なので、一つ式が余っても良いことに注意しておく。まず、足し引きせずに、

$$\begin{bmatrix} 1 & 1 & 1 & -1 & ...\textcircled{4} \\ & 1 & -4 & 0 & ...\textcircled{3}' & = \textcircled{3} \times 5 \\ -0.7 & 0.3 & 0.8 & 0 & ...\textcircled{1} \\ 0.7 & -0.5 & & 0 & ...\textcircled{2} \\ \end{bmatrix}$$

が作れる。$\textcircled{1} + \textcircled{2}$ をすれば $1$ 列目が $0$ になって、少ない計算で上三角行列の $3$ 行目が簡単に作れそうだなと考えるが、$\textcircled{1}+\textcircled{2}$ は $4$ 列目も $0$ となる。それはつまり(次元の面で) $\textcircled{3}'$ の再生産でありその方向性では $3$ 行目は作れない。(実際 $\textcircled{3}'=-5×(\textcircled{1}+\textcircled{2})$ である。)

よくよく考えてみると、マルコフ遷移だから、$\textcircled{1}\sim\textcircled{3}$ の変形前の連立方程式の左辺の係数は縦に全部足すと全部 $1$ になる。よって(右辺も自明に係数 $1$ だから)、$\textcircled{1}\sim\textcircled{3}$ を縦に足すと全部 $0$ になる。つまり、$\textcircled{1}、\textcircled{2}、\textcircled{3}$ から $2$ つをとって足すと必ずもう一つが出てくるのである。逆に言えば、$\textcircled{1}\sim\textcircled{3}$ 同士の計算をする場合は一方か両方に係数をつけて(掛け算をして)足せばよいということだ。もっとも、それで計算が簡単になるとは限らないが。

この後は、次のように求まる。

$$\begin{bmatrix} 1 & 1 & 1 & -1 & ...\textcircled{4} \\ & 1 & -4 & 0 & ...\textcircled{3}' \\ 0 & 1 & 1.5 & -0.7 & ...\textcircled{2}' & = \textcircled{2}+\textcircled{4} \times 0.7 \\ \end{bmatrix}$$

$$\begin{bmatrix} 1 & 1 & 1 & -1 & ...\textcircled{4} \\ & 1 & -4 & 0 & ...\textcircled{3}' \\ 0 & 0 & 5.5 & -0.7 & ...\textcircled{2}'' & \textcircled{2}' - \textcircled{3}' \\ \end{bmatrix}$$

とまあ、ここではきちんと順を追って書いたが、紙の上だと適当で、字が汚い筆者はそれで計算ミスをしたりする。院試では時間はたっぷりあるから、計算ミスで時間を取られるよりかは一個一個順を追ったほうがいいのかなあと思ったり思わなかったり。

ところで、一番最初の拡大係数行列で「一列だけマイナスになっていることを確認する」というチェックの方法を述べたが、ほかにもチェックの方法はある。一つは、先ほど述べたように $\textcircled{1}\sim\textcircled{3}$ を縦に合計すると $0$ になることを確認すること。もう一つは、$\textcircled{1}\sim\textcircled{3}$ の前の方程式は、状態遷移図上でそれぞれ $s_0\sim s_3$の状態から出ていく確率と入ってくる確率が釣り合った式とも解釈できるため、状態遷移図と照らし合わせて符号と係数もろとも確認するという方法である。

(3)

$$\begin{aligned} H(S) &= -P_0(0.3\log0.3 + 0.7\log0.7) - P_1(0.3\log0.3 + 0.5\log0.5 + 0.2\log0.2) - P_2(0.8\log0.8 + 0.2\log0.2) \\ &= 0.879P_0 + 1.486P_1 + 0.720P_2 \end{aligned}$$

なお、ここで次で定義されるのは一次エントロピーである。

$$H_1(S) = -\sum_{i = 0}^2P_i\log P_i$$

これは無記憶情報源と見たときのエントロピーと同じである。マルコフ情報源は記憶があるから、エントロピーがこれよりも小さくなる。

(4)

(4-i)

面倒くさかったから全て分数&分母を $550$ で統一して書いた。(本番は少数や約分したものを書いた方がいいのだろうか。)

(4-ii)

1情報源記号あたりの平均符号長で測る。
これが(3)のエントロピーに近いほど符号化効率が良い。

情報源記号というのは $s_0,s_1,s_2$ という情報源自体が出す記号のこと。

II.

(1)

$$X^*(\omega) = \{\int x(t) e^{-j\omega t}dt\}^* = \int x(t)e^{-j(-\omega)t}dt = X(-\omega)$$

(2)

$\delta(t)$ の定義より $\int_{-\infty}^{\infty}\delta(t)f(t)dt = f(0)$ となるから、$\int_{-\infty}^{\infty}\delta(t)e^{-j\omega t}dt = 1$

ここで言っている「定義」というのは一般的なディラックのデルタ関数の定義である。ネットでは、この一般的な「定義」からフーリエ変換を導く例はあったが、問題で与えられている $\delta(t)$ の定義から導く例は見つからなかった。問題で与えられている $\delta(t)$ の定義から一般的な「定義」の方を導くのはできないと思うので、与えられている $\delta(t)$ 関係なしに解くべきと判断した。なお、これ以降の回答もこの一般的な定義を使っている。

が、ここまで真面目に解かなくても、単に $1$ とだけ書けばよい問題だったのかも。

(3)

単位インパルスである $x(t)$ のフーリエ変換は $X(\omega) = 1$ である。

$$y(t) = \frac{1}{2\pi}\int_{-\infty}^{\infty}H(\omega)X(\omega)e^{j\omega t}d\omega = \frac{1}{2\pi} \int_{-\omega_c}^{\omega_c}e^{j\omega t}d\omega = \frac{1}{2\pi}\bigg[\frac{e^{j\omega t}}{jt}\bigg]_{\omega_c}^{\omega_c} = \frac{1}{2\pi}\bigg(\frac{e^{j\omega_ct} - e^{-j\omega_ct}}{jt}\bigg) = \frac{\sin\omega_ct}{\pi t}$$

波形は省略 ($t = 0$ で $y(t) = \omega_c/\pi$ となり、$t = k(\pi/\omega_c)$ ( $k$ は整数)) で $y(t) = 0$ となる $\text{sinc}$ 関数

(4)

(4-i)

$-T/2 \le t \le T/2$ において、$d(t) = \sum_{n = -\infty}^{\infty}\delta(t - nT) = \delta(t)$ となる。

$$d_n = \frac{1}{T}\int_{-\frac{T}{2}}^{\frac{T}{2}}d(t)e^{-j\frac{2\pi}{T}nt}dt = \frac{1}{T} \int_{-\frac{T}{2}}^{\frac{T}{2}} \delta(t)e^{-j\frac{2\pi}{T}nt}dt = \frac{1}{T}$$

$$D(t) = \sum_{n = -\infty}^{\infty}d_n e^{j\frac{2\pi}{T}nt} = \sum_{n = -\infty}^{\infty}\frac{1}{T}e^{j\frac{2\pi}{T}nt}$$

(4-ii)

$1$ のフーリエ変換は $2\pi\delta(\omega)$ なので、

$$\begin{aligned} D(\Omega) &= \int_{-\infty}^{\infty}\sum_{n = -\infty}^{\infty}\frac{1}{T}e^{j\frac{2\pi}{T}nt}e^{-j\Omega t}dt \\ &= \sum_{n = -\infty}^{\infty}\frac{1}{T}\int_{-\infty}^{\infty}1 \times e^{j\frac{2\pi}{T}nt} \times e^{-j\Omega t}dt \\ &= \sum_{n = -\infty}^{\infty}\frac{2\pi}{T}\delta\bigg(\Omega - \frac{2\pi}{T}n\bigg) \end{aligned}$$

(4)は $2017$ 年の問題 B(2) と全く同じである。そちらではフーリエ変換表が与えられているため、$1$ のフーリエ変換を断りなしに導入できる。しかしこちらはそもそもデルタ関数の定義しか与えられていないので、$1$ のフーリエ変換がデルタ関数としていいのかは若干不安。 ほかの方法としてはデルタ関数の積分表示を使うと、フーリエ変換を介さずに答えを出せる。が、どちらにせよ問題文にないものを導入しなければならない。

(5)

(5-i)

サンプリング周波数 $2\pi/T、$ 周期 $T$ で標本化したとき、標本化後の信号は $x(t)d(t)$ となる。

これのスペクトルは $x(t)$ のフーリエ変換を $X(\omega)$ として

$X(\omega) * D(\omega) = \sum_{n = -\infty}^{\infty} \frac{2\pi}{T}X(\omega - \frac{2\pi}{T}n)$

となる。元のスペクトル $X(\omega)$ に戻すには $X(\omega)$ の帯域が $|\omega| < \pi/T$ である上で、$X(\omega)*D(\omega)$ を $|\omega| \le \pi/T$ で取り出す必要がある。

つまり、標本化された信号に $\omega_c = \pi/T$ として (3) のローパスフィルタを通すと復元できる。

(5-ii)

(5-i)で言及したように、x(t)の帯域がサンプリング周波数の 1/2 未満である必要がある。

(5-i) が解けなくても、サンプリング定理を説明すればよい。以下ではなく未満とするのが正しそう。