東大 情報理工学系研究科 電子情報学専攻 専門科目 2022年度 院試 過去問 解答例・解説（全5問）

時間移動の扱い

有限時間だけ続くランプ波は，単なる $t u(t)- (t-T)u(t-T)$ ではなく，終了後に値を $0$ へ戻す項も必要である。この項を落とすと，$t\ge T$ で入力が一定値のまま残り，電流波形の後半がまったく別のものになる。

概形の確認

$0<t<1$ では入力電圧が増えるため電流は上昇する。ただしインダクタにより立ち上がりは滑らかで，$i(0)=0$ である。$t=1$ 以降は電源が切れるので，蓄えられた磁気エネルギーが抵抗で消費され，$e^{-t}$ 型に減衰する。$t=1$ で電流が連続になる点は，インダクタ電流が瞬時に飛ばないことの確認にもなる。

CPIは全命令あたりでそろえる

キャッシュミス率は命令アクセス・データアクセスの種類ごとに与えられることが多い。CPIに加えるときは，必ず「1命令あたり何回そのミスが起こるか」に直す。データアクセスは全命令の一部だけなので，$0.60$ を掛ける点が失点しやすい。

ページテーブルの支配項

単純な1段ページテーブルは，実際に使うページ数ではなく仮想ページ番号の全範囲に比例する。32 bit 仮想空間ではまだ計算しやすいが，64 bit ではこの方式が現実的でないことが，多段化や逆引き方式の動機である。

素朴法の平均計算量

最悪時は各開始位置で $m$ 回近く比較するため $O(nm)$ である。しかしランダム列では早い段階で不一致が起こりやすく，1開始位置あたりの期待比較回数は等比級数で有界になる。ここでは $k\ge2$ なので，期待値が $2$ 未満に収まることが本質である。

DFAの状態の意味

状態を「何文字一致したか」とだけ覚えるのではなく，「次に利用できる最長接尾辞の長さ」として作るのがポイントである。状態 $3$ から入力 $1$ で状態 $1$ に戻るのは，すでに読んだ末尾の $1$ が新しい一致の先頭として使えるからである。

ハッシュ法の注意

ハッシュ値が一致しても列が一致するとは限らない。したがって答案では，候補をハッシュで絞ったあとに実比較で確認する，または衝突確率を評価する，という一言が必要である。

16QAMの平均エネルギー

16QAMでは最小距離そのものではなく，各信号点の原点からの距離の二乗を平均する。格子点が $\pm B/2,\pm 3B/2$ にあるため，1軸平均が $5B^2/4$ になる。この計算を $B^2$ や $2B^2$ と誤ると，後の誤り率の引数もずれる。

最近傍近似

高SNRでは，遠い信号点へ誤判定される確率は最近傍への確率に比べて小さい。そのため最近傍だけを数えればよい。16QAMは点の位置により最近傍数が異なるので，角・辺・内側に分けて平均する。

理想低域フィルタの二つの効果

$H(\omega)$ は通過帯域では振幅 $1$ で，位相だけが $-\omega t_d$ である。これは時間領域では遅延を表す。帯域外では $0$ なので，矩形パルスの高周波成分が切られ，出力の立ち上がり・立ち下がりにリンギングが出る。

正弦積分への変形

矩形パルスのフーリエ変換は sinc 型である。帯域制限後の逆変換では有限区間で $\sin(\cdot)/\omega$ を積分するため，正弦積分関数が自然に現れる。変数を $\tau=t-t_d$ と置くと，遅延の効果を式全体の平行移動として見通しやすい。