，

電子情報学専攻専門
令和元年8月19日（月）15時00分〜17時30分実施

問題数5題（このうち3題を選択して解答すること）

注意
1．指示があるまで，

2．

この問題を開いてはならない。

この問題冊子の本文は表紙・空白ページを除き全部で5頁ある。落丁，乱丁，印刷不鮮
明なものがあれば申し出ること6

3． 3題を選択して解答せよ。5題中どの'3題を選択してもよい。 1枚の答案用紙に1つの問題の解答を書くこと。必要があれば裏面を使用してよい。

4．答案用紙上部左側に解答した問題の番号を書くこと。また解答用紙上部右側の記入欄に受験番号を必ず記入すること。答案の提出前に， これらを記入したかを必ず確認すること。

5．答案は必ず3題分を提出すること。解答した問題が3題未満であっても3題のそれぞれについて問題番号と受験番号を記入した答案用紙を提出のこと。
6．解答は日本語または英語で記述すること。

7．

この問題冊子と計算用紙は，試験終了後回収する。持ち帰ってはならない。

0一①aりダノノ︶』

︑

1、

Ｉ
『／第1問図に示す，定電圧電源（電圧E),スイッチ（記号SW),ダイオード（記号D), コイル（インダクタンスL), コンデンサ（キャパシタンスC),端子で構成される昇圧回路を考える．時刻をtとし，コイルを流れる電流をj(t),端子の両端の電圧を''(t)とする（それぞれの方向は図を参照のこと)．また，ダイオードの順方向電圧は無視でき，時刻t=0でi(0)=0,"(0)=Eとする．
このとき，以下の問いに答えよ．

(1) t=0からTbの時間，スイッチを短絡させる． o≦t<Zbについて, '(t)を求めよ．

(2) t=zbに，スイッチを開放する．スイッチを開放してからj(t)が0に戻るまでの時間を踊とする．妬≦t<Tb+TIにおけるi(t)を求めゥ Tiも求めよ．

t=0から，上述の操作(Tb時間短絡し，踊時間開放させる）を冗回繰り返す．Tbおよび乃は定数，沌は1以上の整数とする．

(3) '(zb+zi)=0ならば, i("(Tb+乃))=0であることを定性的に説明せよ．
(4)U("(zb+zi))を求めよ．

E，︑／L(ウ第2問

4ビットの符号付き整数A3..0と2ビットの符号付き整数B1,0について, 4ビットの整数加減算を行って4ビットの符号付き整数"..0を得る回路を設計したい．整数A,B,Yとも2の補数表現を用いるものとする．設計に用いることができる論理ゲートの種類はNOT,AND,OR,XORとし，各論理ゲートは必要なだけの入力数を持つものとする． このとき，以下の問いに答えよ．
(1)AおよびBの最大値と最小値を10進数で示せ．

(2)A+Bを計算してYを得る回路を，論理ゲートを組み合わせて示せ．加算器は桁上げ伝搬方式（リプル・キヤリー．アダー）で構成せよ・入力信号としてJ43..0,B1,0,電源電圧陥DD

接地電圧GNDの中から必要な信号を組み合わせてよい．出力は略..0とせよ．表記を簡略化するために，半加算器と全加算器のゲート構成を示した上で，ブロックとして用いよ．

(3) (2)で設計した回路にオーバフロー検知機構を追加したい.追加されるオーバフロー検知回路をゲートを組み合わせて示せ．入力信号としてJ43..0,B1,0,I@..0から必要な信号を組み合わせてよい.また出力は,ビットの信号Dとし,オーバフロー発生時に,,そうでないときに0を出力するようにせよ．

(4)A‑Bを計算してYを得る回路を，論理ゲートを組み合わせて示せ．加算器は桁上げ伝搬方式で構成せよ・入力信号としてA3..01B1,0'W)D,GNDの中から必要な信号を組み合わせてよい．出力は略..Oとせよ． (2)の半加算器と全加算器のブロックを用いよ．

(5) (4)の演算においてオーバフローが発生する入力パターンを全て示せ．

、

●

●

第3間

班(≧2)未満の全ての非負整数を最低1回ずつ含む要素数Nの配列Aがある．Aの部分配列
AI:=AF. .j‑11 (0≦i<j≦Ⅳ)でM未満の全ての非負整数を最低1回ずつ含むもののうち，長さが最も短いものを見つけたい．ただし，そのような部分配列が複数あるときには，開始位置力撮大のものを求める.例えばⅣ=4,M=2,A=<1,1,0,1>に対してはA;=<0,1)を求める．
以下の問いに答えよ．

(1)Aの各部分配列に対しM未満の非負整数を最低1回ずつ含むか確認し，条件を満たすもの
で長さが最も短く開始位置が最大の部分配列を返すアルゴリズムFIND‑SNIPPETを考える．
FIND‑SNIPPET(N,M,A):
雛αγ＃＝0efzd=N

fori=0toⅣ−1do

forj=j+1toNdo(P)

returnA"

この擬似ｺｰドを回を埋めて完成させよ.ただし,break文を用いてf･重ﾙｰプから抜けてはならない.なお,部分配列A1(0≦j<j≦Ⅳ)中にM未満の全ての非負整数が最低1回ずつ含まれるか確認し,結果を真偽値として返す関数CoNTAIN‑INTEGERs(M,A,j,j)
を用いてよい．

(2)N=4,M=2,A=<1,1,0,1)に対して(1)のアルゴリズムを適用したときのj,j,A:IWt,start,endの値の推移を示せ．

，

FIND‑SNIPPETはAの全ての部分配列を考慮するため'o(N2)の時間計算量を必要とし，Ⅳが大きくなると効率が悪くなる．

(3)FIND‑SNIPPETをO(JV)で実行できるように改善し，その擬似コードを示せ･ただし, (1)のCoNTAIN‑INTEGERsはo(1)で動作すると仮定して用いてよい．

（4） (3)のアルゴリズムにおいて,o(1)で動作するCoNTAIN‑INTEGERsの実現方法を述べよ．

●第4間
図に示すように， 2つのクライアントからサーバへ, IPパケットの転送を行う．転送されるIPパケットは,すべて同じ大きさとする．また， 2つクライアントからルータヘのIPパケットの転送とルータからサーバへのIPパケットの転送はすべて同期しているものとし，単位時間Tごとに，正パケットの転送が行われる．ルータはⅣ個のIPパケットを蓄積可能であるとする． また，2つのIPパケットがルータに到着し，ルータが両方のパケットを保持できない時は，いずれかのIPパケットがランダムに廃棄される．

クライアントユ︑︑︒〆

ダルータ

サーバ

クライアント2(1)2つのクライアントは，両方とも確率α(0≦α≦1)で独立にパケットを生成する.ルータにバッファリングされているIPパケットの数に関する状態遷移図を示せ．

(2) α＝0．5の時の各状態の発生確率を示せ．
(3) (2)において，Ⅳ＝2の時のIPパケットの廃棄確率を示せ．

(4) クライアント1からのIPパケットの転送をストリーム型の正パケットの転送，すなわち定期的にIPパケットを生成・転送するようにシステムを変更する．具体的には, 2Tごとに1個のIPパケットを転送するものとする．なお，クライアント2からの唖パケットの転送は(1)と同様であり，α＝0.5,Ⅳ＝2とする． この時のルータにおけるIPパケットの廃棄確率を示せ．

(5)

クライアント，のストリーム型のIPパケット転送におけるIPパケットの廃棄確率を低下させるために，前方誤り訂正方式を適用する． クライアント1から転送されるべきk個のIP

1パケットに対してp S個(k≧s)の冗長パケットを生成する． これによって，クライアント1からサーバに転送されるん+s個のIPパケットのうちs個以下のIPパケットが廃棄されても，サーバにおいては，クライアント1からのIPパケットの再送を行うことなく脆個のIPパケットを誤りなく復号可能になるものとする．

(趣）クライアント1から送信された脆個のIPパケットが, IPパケットの再送を行うことな
く，サーバで誤りなく復号される確率を数式で示せ．

(b)k=3,8=1の時に，サーバで誤りなくk個のIPパケットが復号される確率を示せ．
さらに，前方誤り訂正がない場合にk個のIPパケットが誤りなく受信される確率を示せ．なお，α＝0.5,Ⅳ＝2とする．

〃

●

第5問

離散時間信号zの出力が，図のような確率密度関数p(")に従うとする.以下の問いに答えよ．
log23=1.58, log25=2.32とする．
p(x)X‑110(1)量子化器Qoは，信号Zの出力のレンジI‑1,11を均等に5分割して; 5レベルの量子化を行う．その量子化出力を入力信号値の小さい方から9,, , ,鯉,95とする．それぞれの出現確率を求めよ．

(2)Qoの量子化出力のエントロピーを求めよ．

(3)Qoの量子化出力を最も効率よく表現する2元符号恥を1つ求めよ．
(4)恥の平均符号長を求めよ．

(5)出力のエントロピーを最大とする5レベル量子化器Q,の量子化の境界di(j=1,2,3,4)を求めよ．壁子化の境界を必̲,,djとした時，壁子化操作Q()は下式で与えられる．
Q(di‑'≦z<di)="．ただし，功=‑‑1,d5=1である．

(6)信号の再生には,各量子化出力砿に対して，対応する量子化区間内の一つの値を量子化代表値として割り当てる．信号値と再生値の平均2乗誤差により，量子化誤差を定義する．量子化器出力砿に対して，量子化誤差を最小化する量子化代表値公は下式で与えられることを示せ．

‐姪 "(鰯'姪 牢)(7)量子化器Q1の公(j=1,2,3,4,5)を求めよ．
I〃心〜I

1I＝I、I』↑︾』､9イ、（〆ー一一p〆

I言延