1

SpeCialiZedSUbjeCtS
15:00-17:30,MondayjAugustl9,2019
Instructions

1. DonotopenthisbookletbeibI℃theexaminationbegins.

2. Thisbookletcontainsfivepmblems.Thenumberofpagesisfiveexcludingthiscoversheetandblankpages.lfyou6ndmissmgorbadlyprinedpages,askthepoctorfbrexchange.
●

3．

Answerthreeproblems.YbuCanselectanythreeoutofthefive・Yburanswertoeachpmblem
shouldbewrittenonasepalatesheet・YOumayusetheI℃versesideofthesheetifnecessalyy.

4. FillthetoppartsofyourthI己eanswerSheetsasinstructedbelowbBefbresubmittingyouranswer
sheets,makesurethatthemppartsal己correctlyfilled.

専門科目

匿二函

受験番号

1WritetheexamineeNo.

1WritethepmblemNo.

5．

SubmitallthethI℃eanswersheetswiththeexamineenumberandtheproblemnumbel;evenif
youranswerisblank.

6. AnswereitherinJapaneseorinEnglish.

7. ThisbookletandthescratOhpapermustberetumedattheendoftheexamination.
8． ThisEnglishtranslation issUpplemetal andpmvidedfbrconvenienceofapplicants・The
japaneseversionisthe允面nalone.

ｆ

念一

もノ、1｝
I､I

ノJ

L､／』
《0I

︿「←ノ1（I、l ↓、一､
≠"』

「、一1I
ノ塔、I

1､丁●Probleml

COnsideracircuitofanulconverter,consistingofaconstantvoltagesupply(voltageE),.a
gwitdl(denotedWSW),adiode(denotedIWD),acoil(mductanceL),acondenser(capacitanceC),andtmminalsasshownmthengure.Lettbethetime,'(t)bethecurrenbofthecon,and"(t)bcthcvoltagcbctwweenthetcrmmals(asfbrthcdircctions,refbrtothefigurc).Assume
thati(0)=0andu(0)=Eatt=0,andthatthefbrwardvoltageofthediodeisnegligible.
AnswWthe如ⅡowingqU"tions.

(1)LetusshorttheswitchfbrdurationZbhomt=0.Fmdi(t)fbrO≦t<Zb.

(2)Letusopentheswitchatt=Zb.WedenotelyZithedurationfbri(t)toreturntoO.
Fmdi(t)mrTb≦t<Tb+Zi,amdhnd乃．
Werepeattheoperationdescribedabove(shorttheswitchfbrdurationTb,andthenopenit
brdurationZi)'ztimeshomt=0.ZbandZiareconstants,and7Disanintegerlargerthanor
equaltol.

(3)Describequalitativelythatifi(Tb+乃)=0,theni("(TI)+Zi))=0.
(4)Fmd"("(Zb+Zl)).

，︑／L(ウE〃0●bProblenl2

IctusdeSignacircuitthatobtainsa4‑bitSignedmtegerl@..olycalculating4‑bitaddia
tion/subtractionofa4苧bitsignedintegerA3.､oanda2‑bitsi邸edintegerB1,0．Theintegers
A,B,andYareexpessedintwwo'scomplement.ThetypeSoflogicgatesthatyoucanusearcNOT,AND,OR,andXOR,eaxhofwhichisequippedwithasmanyinputsasthedesigl
requires・AnsWmthefbnowingquestions.

(1)ShowthemaXimumandmmmmmvaluesofAandBmdecimalfbrm.

(2)ShowacircuitthatcalculatesA+BtoobtainYWcombininglogicgates. Orgamze
theadderas.aripplecarryadder..YoucanusesignalshomA3..0,B1,0,SUpplyvoltage
IbD,andgroundingvoltageGNDasinputs.TheoutputshouldbeI@..0.Tbsmplifythe
digam,usethe"half‑adder''bloclmandthe!$fUll‑adder''blodmaftmshOwinggatelevel
designsofbothblodKs.

(3)Consideraddmganoveraowdetectionmechanismtothecircuitdesignedin(2).ShowtheoveraowdetectioncircuitWcombiningthelogicgates.Youcanusesigna脂丘omA3..01

B,,0,andI@..0asmputs.Theoutputshouldbeal‑bitsignalnamedD; itshouldbe;1'whentheovernowoccurred,or&O'otherwise.

(4)Showacircuitthatcalculates44‑Btoobtainybycombininglogicgates. Organize
theadd()Irasaripplecarryadder.YbUcanusesignalshomA3.0,Bl,o, WbD,andGND

asmputs.Theoutputshouldbe"..0．USethe!{half‑adder''blodKsand6he(lfilll‑adder''bloksin(2).

(5)Showallthemputpatternsthatcuseovernowsfbrthecalculationdesipedm(4).

0◆Problenl3

咽︾︽︾︾錘や一一いｅ・﹄且唾一一ｇ︾︾一恥恥州●ロ日公卿叩岬・唖鋤如．０ｔｌノ酢一合ｅ

皿・知Ｊ︑︑︑９ｈ︒ｔ・麺叩

公．皿如一一弥帥唾批山ｅ・趣一誠皿︒︑●︾

皿雌唖︾︽恥卒睦弛剖

︽一︾︺︐呼蜘睡岬睡︾岬．ｎ唾

一・唖呼柚唖胞呼峨︾㎡唾

銚陛ｌ 麺唖恥皿(1)Consideranalgorithm,FIND-SNIPPET,thatchedKsfbrechsubarrayofAwhetherit
containseaChofthenon-negativeintegerlessthanMatleastonce,andthenreturnstheｊＡ

●ｅ１

９ｄＯｄ

●ぬ口呼Ｏ

ＯⅣｌｔ

Ｎ︑一一Ｉ

ｒｔ一一・２ｆ

函弐Ⅳ印・唖

Ｎ︐

Ｎ ｄｒ雨鈍印釦

ＩＦ

ＭⅣ＋−１

shortestsubarraywiththelargeststaItpositionthatsatishesthecondition.

(P)

returnA"&Fmm

mtocompletethispSeudocodeHere,yoUmustnotexi$加､鴛・蚕loopsusing

breakaZginents.YoucanuseahmctionCoNTAIN‑INTEGERs(M,A,',j)thatcheCks

whetherasubarrayAI(0≦j<j≦Ⅳ)containseachofthenonPnegativeintegersless
thanMatleastonce,andthenretl江nstheresultasatruthvmue.
●(2)ShOwthetransitionofvaluesofj,j,A"l,st@rt,andelzdwhenthealgorithmm(1)isappmcdtolV=4,M=2,andA=<1,1,0,1).

Sm(:cFIND‑SNIPPETconsidcrsallthesUbarraysofA,itrcquiresthctimccomplfpcityofO(jV2)■andbecomesmemcientfbrlargeⅣ．

(3)hnnproVeFIND‑SNIPPETsothatitrunsmO(lV)andshowitspseudocode.Here,youcan
ノ

uscCoNTAIN‑INTEGERswiththcassumptionthatitrunsinO(1).

(4)EDmlamhowtorealizeCoNTAIN‑INTEGERsthatrunsmO(1)fbrthealgorithmm(3).

0Problexn4

Asshownmthengure,正packetsaretransferredhomtwoclientstoaserver.Antramerred､rpaCketsareofthesamesize・ThelPpadfkettransmissionhomthetwwocUentstotherouterandthelPpaCkettransmisSionhPomtheroutertotheserveraresynChronized,andeverylP
paAMtistrammittedmaumt‑timeT. TheroutcrcanstorcJVIPpaCkets.WhentwoIP
paCketsamiveattherouterandtheroutercannotstorebothofthem,eitherofthelPpa"ketsisdiscard(drandomlyClientl､､〆〆

RouterServerClient2(1)Thetwochentsmdependentlygene[atelPpacketswiththesameprobabilitycM(0≦α≦1).
DrawastatetransitiondiagramqssociatedwiththenumberofIPpaCkketsbuHeredmthe
router.

(2)Obtaintheoccurrenceprobabilityofeverystate,whencw=0.5.
●(3)ObtaintheIPpaCketl"sprobab泄可m(2),whenN=2.

(4)LetlEChangethesystemsothatCnentlgeneratesandtransfersstream‑typempaCkets(i.c.,thcIPpamtsarcgcneratedandtransfbrrbdperiodically). Inparticular,ClientltransersonelPpaCketmevery2T.Here,theIPpackettransmissionfromClient2isthesamcaS(1),andcx=0.5andN=2.ObtainthelPpaxkctlosspmbabilityattherouter.

(5)血ordertoreducethelPpaCketlossprobabilityofthestream‑句'peIPpamttransmission
homClientl,afbrarderrorcorrectionmethodisapphed・Chentlgeneratessredundant
IPpaCkets,fbrthek(k≧s)IPpadtetsthatshouldbetransfenedfromClientltothe
servver.WeassumethattheservercancorrectlydecodetheklPpacketswithoutlPpaCket
retransmissionhomCnemlaslongasthenumberofdroppedlPpad"tsinthek+slP
packetssenthomCliemltotheserverbsmallerthanorequaltos.

(a)ObtaintheprObability,withafbrmula,thatklPpacketshOmClientlarecorrectlydecodedWtheserverwithoutlPpaCketretransmmsion.

(b)ObtaintheprobabilitythatkIPpa"ketsfromChentlarecorrectlydecodedWthe
serverwhenk=3ands=1．AIsoobtaintheprObabilitythatkIPpa"ketshom

Chentlarecorrectlyreceivedbytheserverwithoutfbrwarderrorcorrection・H"e,q=0.5andN=2.

9●

Problem50

Theoutputofadiscretetimesipalzfbnowstheprobabilitydensityfunctionp(")shownin
thengure.AnswwerthefbllowingqUestions,Uselog23=1.58andlog25=2.32.
p(x)

X

10-1

(1)AquantizerQoquantizeSsignal"with6velevelslyunifbrmlydividmgtheoutputr皿ge、
1‑1,11 intofvc・ThequantizerouｶputisrepreSentedas9,,QZ,93,94,95homthesmallest
mputsignalrannge.ObtaintheprObabintyofoccurrenceofeachqUantizationoutput.
(2)ObtaintheentrOpyofthequantizationoutputofQo.

(3)Obtainabinarycodeqthatisthemostemcientmrepresentmgthequantizationoutput
ofQo.

(4)Obtainthea('eragecodelengthofq.

(5)Obtainthequantiza#ionbomldariesdi (j=1,2,3,4)ofthenve‑levelqumltizerQ1that
nlaJdmizestheemmpyofitsoutput.QuantizationoperationQ()withthequantization
boundari"di̲,,di"givenWtheequationbelow.

Q(di‑'≦範<di)=qi.
Notethat"=‑1皿dd5=1.

(6)Fbrsignalreconstruction,cachquantizationoutputqiisassignedaqUantizationr(PresenF
tativevaluewithinitscrrespoIidingrannge・TheqUantizationerrorisdennedasthemeansquared(:rrorbetweenthevaluesoftheoriginalandthercconstructionsignals.Showthat
theqUantiZationrepresentativevalueffwhichminimizesthequanntizationmrorfbreaChquanntizationoutputqdisgivenWtheequationbelow.

"j=瞳
姪、"(")dz
p(")dz(7)Obtainfi(j=1,2,3,4,5)ofthequantizerQ1.

へIぐ

二

1I、、｝
、9ノ〈ノI〆一一