東京大学 工学系研究科 電気系工学専攻 2022年度 問題3 情報工学I

Author

donguri0912

Description

I

情報理論に関する以下の問に答えよ．無記憶情報源 \(X = \{0,1\}\) における \(i\) 番⽬ (ただし \(i = 1,2,3,\cdots\)) の信号を \(X_i\) とし，\(X_i = 0\) となる確率を \(p,X_i = 1\) となる確率を \(1 - p\) とする．近似値として \(\log_23 = 1.6 ,\log_25 = 2.3 ,\log_27 = 2.8\) を⽤いてよい．

(1) \(p = 0.75\) のときのエントロピー \(H(X)\) を求めよ．

(2) \(p = 0.75\) のとき, \(X\) の連続した \(2\) つの信号をひとまとめにした \(\{00,01,10,11\}\) の \(4\) 値を効率よく符号化したい．符号化の例を示し，そのときの平均符号長を求めよ．

\(X\) を⼊⼒とする無記憶通信路 \(C\) を考える．その出⼒を \(Y = \{0,1\}\), \(i\) 番⽬の出⼒信号を \(Y_i\) したとき，\(80\)% の確率で \(Y_i = X_i\) となるが，\(20\)% の確率で \(X_i\) にかかわらず \(Y_i = 1\) となる．

(3) \(p = 0.75\) のときのエントロピー \(H(Y)\) を求めよ．また，相互情報量 \(I(X;Y)\) を求めよ．

(4) \(I(X;Y)\) を最⼤化する \(p\) は \(0.5\) より⼤きいか⼩さいか答えよ．根拠も簡潔に述べよ．

II

信号処理に関する以下の問に答えよ．時間 \(t\) および⾓周波数 \(\omega\) は実数，\(j\) は虚数単位であり，複素数 \(a\) の複素共役を \(a^*\) と表す．また，複素関数 \(x(t)\) のフーリエ変換 \(X(\omega)\) とそのフーリエ逆変換を次式で定義する．

\[ \begin{align} X(\omega) &= \mathcal{F}[x(t)] = \int_{-\infty}^{\infty} x(t)e^{-j\omega t}dt \tag{i}\\ x(t) &= \mathcal{F}^{-1}[X(\omega)] = \frac{1}{2\pi}\int_{-\infty}^{\infty}X(\omega)e^{j\omega t} d\omega \tag{ii} \end{align} \]

(1) \(\mathcal{F}^{-1}[X^*(\omega)] = x^*(-t)\) が成り立つことを示せ.

(2) \(x(t)\) が実関数のとき，\(X^*(\omega) = X(-\omega)\) が成り立つことを示せ.

アナログフィルタ Aのインパルス応答を実関数 \(f(t)\) で表す．\(A\) の応答が因果律を満たすことから，\(t < 0\) において \(f(t) = 0\) である．また，\(F(\omega) = \mathcal{F}[f(t)]\) の実部および虚部をそれぞれ \(F_1(\omega),F_2(\omega)\) とおくと，\(F(\omega) = F_1(\omega) + jF_2(\omega)\) である．

(3) \(f_1(t) = \mathcal{F}^{-1}[F_1(\omega)]\) を，\(f(t)\) を⽤いて表せ．

(4) \(f_2(t) = \mathcal{F}^{-1}[F_2(\omega)]\) を，\(f(t)\) を⽤いて表せ．

(5) \(F_1(\omega)\) が既知で \(F_2(\omega)\) が未知のとき，フーリエ変換とフーリエ逆変換を⽤いることで \(F_1(\omega)\) から \(F_2(\omega)\) を求めることができる．その⼿続きを \(3\) ⾏程度で説明せよ．必要に応じて図や式を⽤いても良い．

ある実信号 \(s_1(t)\) の⾓周波数帯域が \(|\omega| \le \omega_B\) である，すなわち，\(|\omega| > \omega_B\) のとき \(\mathcal{F}[s_1(t)] = S_1(\omega) = 0\) とする．この信号により⾓周波数 \(\omega_C (\gg) \omega_B\) の搬送波を変調する状況を考える．

(6) 実信号 \(d(t) = s_1(t)\cos\omega_Ct\) のフーリエ変換 \(D(\omega) = \mathcal{F}[d(t)]\) を \(S_1(\omega)\) を⽤いて表せ．また，\(D(\omega)\) の⾓周波数帯域が \(\omega_C - \omega_B \le |\omega| \le \omega_C + \omega_B\) となることを示せ．

(7) \(s_1(t)\) が既知であれば，適切な実信号 \(s_2(t)\) を準備し，実信号 \(u(t) = s_1(t)\cos\omega_Ct + s_2(t)\sin\omega_Ct\) を⽣成することで，\(U(\omega) = \mathcal{F}[u(t)]\) の⾓周波数帯域を \(\omega_C \le |\omega| \le \omega_C + \omega_B\) に制限することができる．\(s_1(t)\) から \(s_2(t)\) を求める⼿続きを \(3\) ⾏程度で説明せよ．必要に応じて図や式を⽤いても良い．

Kai

I

(1)

-(0.75 log 0.75 + 0.25 log 0.25) = 0.8

(2)

下図は一例。

───┬─0────────── 0  : 00 = 9/16
   └─1─┬─0────── 10 : 01 = 3/16
       └─1─┬─0── 110: 10 = 3/16
           └─1── 111: 11 = 1/16

平均符号長は

\[ (9/16) + (3/16) * 2 + (3/16) * 3 + (1/16) * 3 = 27/16 = 1.6 \]

(3)

      X        Y
0.25: 1 ─────── 1 : 0.25 + 0.75 * 20% = 0.40
　　         ─┐ 0.75 * 20%
           ／
         ／
0.75: 0 ─────── 0 : 0.75 * 80% = 0.60
Yで、1となる確率は 0.25 + 0.75 * 20% = 0.40
(もしくは 80% * 0.25 + 20% = 0.40か。
最初こう考えたが図で表しづらく他に応用が利かないと思った。)
よって、H(Y) = -(0.4 log 0.4 + 0.6 log 0.6) = 0.94
また、
H(Y|X) = -(0.25 log 100% + (0.75*20%) log 20% + (0.75*80%) log 80%) = 0.53
I(X; Y) = H(Y) - H(Y|X) = 0.41
(H(Y(X)、I(X; Y)は計算機と答えが違う))

(4)

\(I(X;Y) = H(Y) - H(Y|X) = \mathcal{H}(0.8p) - p\mathcal{H}(0.2)\)

これが最大となるのは \(\frac{d}{dp}I(X;Y) = 0\) となるときである。

\[ \frac{d}{dp}I(X;Y) = -0.8\log0.8p - \frac{0.8}{\log_e2} + 0.8\log(1 - 0,8p) + \frac{0.8}{\log_e2} - \mathcal{H}(0.2) = 0.8\log\frac{1 - 0.8p}{0.8p} - \mathcal{H}(0.2) = 0 \]

\[ p = \frac{1}{0.8\bigg(\frac{\mathcal{H}(0.2)}{2^{0.8}} + 1\bigg)} = \frac{1}{0.8\bigg(\frac{0.7}{2^{0.8}} + 1\bigg)} < \frac{1}{0.8(2^{0.7} + 1)} = \frac{1}{0.8(2^{2.3-1.6} + 1)} = \frac{1}{0.8(5/3) + 1} = 0.47 < 0.5 \]

よって最大となる \(p\) は \(0.5\) より小さい。ただし、\(H\) の筆記体はエントロピー関数。

II

(1)

\[ \mathcal{F}^{-1}[X^*(\omega)] = \frac{1}{2\pi}\int X^*(\omega)e^{j\omega t}d\omega = \bigg\{\frac{1}{2\pi}\int X(\omega) e^{j\omega(-t)}d\omega\bigg\}^* = x^*(-t) \]

(2)

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

(3)

\[ f_1(t) = \mathcal{F}^{-1}\bigg[\frac{F(\omega) + F^*(\omega)}{2}\bigg] = \frac{\mathcal{F}^{-1}[F(\omega)] + \mathcal{F}^{-1}[F^*(\omega)]}{2} = \frac{f(t) + f^*(-t)}{2} = \frac{f(t) + f(-t)}{2} \]

(4)

\[ f_2(t) = \mathcal{F}^{-1}\bigg[\frac{F(\omega) - F^*(\omega)}{2j}\bigg] = \frac{\mathcal{F}^{-1}[F(\omega)] - \mathcal{F}^{-1}[F^*(\omega)]}{2j} = \frac{f(t) - f^*(-t)}{2j} = \frac{f(t) - f(-t)}{2j} \]

(5)

\(t < 0\) において、\(f(t) = 0\) となることから、\(t > 0\) において (3) より

\(\mathcal{F}^{-1}[F_1(\omega)] = f_1(t) = f(t)/2 , t = 0\) のとき \(\mathcal{F}^{-1}[F_1(\omega)] = f_1(t) = f(t)\) となる。よって、

$$ f(t) = \left { \begin{aligned} 2\mathcal{F}^{-1}[F_1(\omega)],&t > 0 \ \mathcal{F}^{-1}[F_1(\omega)],&t = 0 \ 0,&t < 0 \ \end{aligned}
\right. $$　

これの逆フーリエ変換 \(F(\omega)\) から \(F_2(\omega) = \frac{F(\omega) - F^*(\omega)}{2j}\) または \(F_2(\omega) = \frac{F(\omega) - F_1(\omega)}{j}\) を計算すればよい。

(6)

\[ D(\omega) = \mathcal{F}[s_1(t)\cos\omega_C t] = S_1(\omega) * \bigg\{\frac{1}{2}\delta(\omega - \omega_C) + \frac{1}{2}\delta(\omega + \omega_C)\bigg\} = \frac{1}{2}S_1(\omega - \omega_C) + \frac{1}{2}S_1(\omega + \omega_C) \]

ただし、\(*\) は畳み込み積分である。

帯域は、\(|\omega - \omega_C| \le \omega_B\) または \(|\omega + \omega_C| \le \omega_B\) に広がり、簡単化すると、

\(-\omega_B \le \omega - \omega_C \le \omega_B\) または \(-\omega_B \le \omega + \omega_C \le \omega_B\)

\(\omega_C \gg \omega_B\) より \(0 \le \omega_C - \omega_B \le \omega \le \omega_C + \omega_B\) または \(-(\omega_C + \omega_B) \le \omega \le -(\omega_C - \omega_B) \le 0\)　

よって \(\omega_C - \omega_B \le |\omega| \le \omega_C + \omega_B\)

#### (7)

\[ U(\omega) = \mathcal{F}[s_1(t)\cos\omega_Ct + s_2(t)\sin\omega_C] = \frac{1}{2}\bigg\{S_1(\omega - \omega_C) + \frac{1}{j}S_2(\omega - \omega_C)\bigg\} + \frac{1}{2}\bigg\{S_1(\omega + \omega_C) - \frac{1}{j}S_2(\omega + \omega_C)\bigg\} \]

ここで \(S_2(\omega) = \text{jsgn}(\omega)S_1(\omega)\) とすると、

\[ U(\omega) = \left \{ \begin{aligned} &S_1(\omega - \omega_C) + S_1(\omega + \omega_C), \omega_C < |\omega| \le \omega_C + \omega_B \\ &\frac{1}{2}S_1(0) , |\omega| = \omega_C \\ &0 , \omega_C - \omega_B \le |\omega| < \omega_C \end{aligned} \right. \]

となる。

よって、\(\mathcal{F}^{-1}[\text{jsgn}(\omega)] = -\frac{1}{\pi t}\) であるから、\(s_2 = \mathcal{F}^{-1}[S_2(\omega)] = -s_1(t) * \frac{1}{\pi t}\) とすればよい。