跳到主要内容

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

标签：

Author​

donguri0912

Description​

I​

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

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

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

XX を⼊⼒とする無記憶通信路 CC を考える．その出⼒を Y={0,1}Y = \{0,1\}, ii 番⽬の出⼒信号を YiY_i したとき，8080% の確率で Yi=XiY_i = X_i となるが，2020% の確率で XiX_i にかかわらず Yi=1Y_i = 1 となる．

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

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

II​

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

X(ω)=F[x(t)]=∫−∞∞x(t)e−jωtdtx(t)=F−1[X(ω)]=12π∫−∞∞X(ω)ejωtdω\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) F−1[X∗(ω)]=x∗(−t)\mathcal{F}^{-1}[X^*(\omega)] = x^*(-t) が成り立つことを示せ.

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

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

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

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

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

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

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

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

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(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)=H(0.8p)−pH(0.2)I(X;Y) = H(Y) - H(Y|X) = \mathcal{H}(0.8p) - p\mathcal{H}(0.2)

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

ddpI(X;Y)=−0.8log⁡0.8p−0.8log⁡e2+0.8log⁡(1−0,8p)+0.8log⁡e2−H(0.2)=0.8log⁡1−0.8p0.8p−H(0.2)=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=10.8(H(0.2)20.8+1)=10.8(0.720.8+1)<10.8(20.7+1)=10.8(22.3−1.6+1)=10.8(5/3)+1=0.47<0.5p = \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

よって最大となる pp は 0.50.5 より小さい。ただし、HH の筆記体はエントロピー関数。

II​

(1)​

F−1[X∗(ω)]=12π∫X∗(ω)ejωtdω={12π∫X(ω)ejω(−t)dω}∗=x∗(−t)\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∗(ω)={∫x(t)e−jωtdt}∗=∫x(t)e−j(−ω)tdt=X(−ω)X^*(\omega) = \bigg\{\int x(t)e^{-j\omega t}dt\bigg\}^* = \int x(t)e^{-j(-\omega) t}dt = X(-\omega)

(3)​

f1(t)=F−1[F(ω)+F∗(ω)2]=F−1[F(ω)]+F−1[F∗(ω)]2=f(t)+f∗(−t)2=f(t)+f(−t)2f_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)​

f2(t)=F−1[F(ω)−F∗(ω)2j]=F−1[F(ω)]−F−1[F∗(ω)]2j=f(t)−f∗(−t)2j=f(t)−f(−t)2jf_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<0t < 0 において、f(t)=0f(t) = 0 となることから、t>0t > 0 において (3) より

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

f(t)={2F−1[F1(ω)],t>0F−1[F1(ω)],t=00,t<0f(t) = \left\{ \begin{array}{ll} 2\mathcal{F}^{-1}[F_1(\omega)], & t > 0 \\ \mathcal{F}^{-1}[F_1(\omega)], & t = 0 \\ 0, & t < 0 \\ \end{array} \right.

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

(6)​

D(ω)=F[s1(t)cos⁡ωCt]=S1(ω)∗{12δ(ω−ωC)+12δ(ω+ωC)}=12S1(ω−ωC)+12S1(ω+ωC)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)

ただし、∗* は畳み込み積分である。

帯域は、∣ω−ωC∣≤ωB|\omega - \omega_C| \le \omega_B または ∣ω+ωC∣≤ωB|\omega + \omega_C| \le \omega_B に広がり、簡単化すると、

−ωB≤ω−ωC≤ωB-\omega_B \le \omega - \omega_C \le \omega_B または −ωB≤ω+ωC≤ωB-\omega_B \le \omega + \omega_C \le \omega_B

ωC≫ωB\omega_C \gg \omega_B より 0≤ωC−ωB≤ω≤ωC+ωB0 \le \omega_C - \omega_B \le \omega \le \omega_C + \omega_B または −(ωC+ωB)≤ω≤−(ωC−ωB)≤0-(\omega_C + \omega_B) \le \omega \le -(\omega_C - \omega_B) \le 0　

よって ωC−ωB≤∣ω∣≤ωC+ωB\omega_C - \omega_B \le |\omega| \le \omega_C + \omega_B

(7)​

U(ω)=F[s1(t)cos⁡ωCt+s2(t)sin⁡ωC]=12{S1(ω−ωC)+1jS2(ω−ωC)}+12{S1(ω+ωC)−1jS2(ω+ωC)}U(\omega) = \mathcal{F}[s_1(t)\cos\omega_C t + 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\}

ここで S2(ω)=jsgn(ω)S1(ω)S_2(\omega) = jsgn(\omega)S_1(\omega) とすると、

U(ω)={S1(ω−ωC)+S1(ω+ωC),ωC<∣ω∣≤ωC+ωB12S1(0),∣ω∣=ωC0,ωC−ωB≤∣ω∣<ωCU(\omega) = \left\{ \begin{array}{ll} 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{array} \right.

となる。

よって、 F−1[jsgn(ω)]=−1πt\mathcal{F}^{-1}[jsgn(\omega)] = -\frac{1}{\pi t} であるから、s2=F−1[S2(ω)]=−s1(t)∗1πts_2 = \mathcal{F}^{-1}[S_2(\omega)] = -s_1(t) * \frac{1}{\pi t} とすればよい。

本页目录