東大 情報理工学系研究科 電子情報学専攻 専門科目 2024年度 院試 解答例・解説

定常応答はインピーダンスで一気に処理する

直列回路なので電流は全素子で共通である。したがって、抵抗成分 $R$ とリアクタンス $\omega L-1/(\omega C)$ をベクトル和として扱えば、実効値の計算は 「電圧実効値をインピーダンスの大きさで割る」だけで済む。ここで振幅と実効値を混同すると $\sqrt{2}$ の係数を落としやすい。

共振条件の意味

電流を最大にするには抵抗以外の見かけの抵抗を消せばよい。コイルのリアクタンスとコンデンサのリアクタンスが等しく逆符号になる点が直列共振である。共振時にも抵抗 $R$ は残るので、電流は無限大ではなく $V_0/(\sqrt{2}R)$ になる。

過渡応答の検算

ステップ入力直後はコイル電流が急に変化できないため $i(0)=0$ となり、求めた式も $\sin 0=0$ でこれを満たす。また減衰振動の場合、指数因子により $t\to\infty$ で電流は0へ向かう。直流定常状態ではコンデンサが開放相当になるので、これも物理的に正しい。

Mealy型として考える

出力は「直前の記号」と「現在入力」の組に依存するので、出力が状態だけで決まるMoore型よりも、入力と状態で出力が決まるMealy型として考えるのが自然である。直前1記号を状態にすれば2文字列の判定に必要な情報は過不足なく保存される。

状態簡単化の見方

状態 $A$ と $D$ は、どの入力を入れても出力列が同じで、しかも次状態も同じ記号に移る。したがって将来の振る舞いで区別できず、同じ状態にまとめられる。状態表を作った後、行を比較して等価状態を探すのが最も確実である。

回路化の注意

次状態は現在入力だけで決まるため、状態更新部は非常に単純である。一方、出力 $Z$ は状態と入力の組で決まる。カルノー図では未使用状態 $11$ をドントケアにしてもよいが、ここでは使わずに上式のまま実装しても十分に簡単である。

固定長はスライディングウィンドウ

長さが固定されている場合、隣り合う窓は $k-1$ 個の要素を共有する。毎回最初から足し直すのではなく、左端を引いて右端を足すだけで次の和が得られる。この観察だけで $O(nk)$ から $O(n)$ へ下がる。

長さ制約なしはKadane法

現在位置で終わる最良部分列が、前の最良部分列を延長すべきか、それとも現在要素から始め直すべきかを比較する。負の寄与を背負い続けない、という発想が本質である。

長さ $k$ 以上は最小累積和を見る

末尾を固定すると、部分列和を最大化するには開始直前の累積和を最小にすればよい。ただし長さ $k$ 以上という制約があるので、使ってよい累積和は $i-k$ 以前に限られる。この制限を $C[i-k]$ が吸収している。

畳込み符号は状態機械として読む

シフトレジスタの中身が状態であり、入力ビットを1つ入れるたびに状態が1段ずつ進む。出力は入力と状態の排他的論理和で決まるため、状態遷移表またはトレリスに落とせば機械的に計算できる。

Viterbi復号の採点ポイント

復号では、各時刻で「受信2ビット」と「各枝の出力2ビット」のHamming距離を加算し、各状態に到達する最小距離経路だけを残す。最終時刻で最小距離の経路をたどり直せば、最尤の入力列が得られる。今回の最小距離は1なので、1ビット誤りを訂正した復号になっている。

パラメータのトレードオフ

符号化率を高くすると冗長ビットが少なくなり伝送効率は上がるが、誤り訂正能力は弱くなる。拘束長を長くするとより長い入力履歴を利用できるので自由距離を大きくしやすい一方、Viterbi復号の状態数が指数的に増え、遅延と計算量が大きくなる。

定常分布を先に出す

マルコフ情報源では、単独の0と1の確率は遷移確率そのものではない。長時間平均でどちらの状態にいるかを表す定常分布を先に求める必要がある。今回の情報源は0が続きやすいため、定常分布も0に大きく偏る。

エントロピー率

記号ごとの周辺エントロピーではなく、現在状態が分かったときの次記号の不確かさを定常分布で平均する。これはマルコフ性を利用した圧縮の理論限界であり、今回の約0.58 bit/source symbolが平均符号長の下限の目安になる。

ブロック化とHuffman符号

等長ブロックでは頻度の高い $00$ に短い符号語を割り当てられるので、単純な1ビット表現より短くなる。さらに非等長記号列では長い0の連続を1記号として扱えるため、この情報源の偏りをよりよく利用できる。方式dがエントロピー率に最も近いのはそのためである。