資源描述：
《Booth algorithm》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、Booth'sAlgorithmExampleCS440PointstorememberWhenusingBooth'sAlgorithm:Youwillneedtwiceasmanybitsinyourproductasyouhaveinyouroriginaltwooperands.Theleftmostbitofyouroperands(bothyourmultiplicandandmultiplier)isaSIGNbit,andcannotbeusedaspartofthevalue.TobeginDecidewhichop
2、erandwillbethemultiplierandwhichwillbethemultiplicandConvertbothoperandstotwo'scomplementrepresentationusingXbitsXmustbeatleastonemorebitthanisrequiredforthebinaryrepresentationofthenumericallylargeroperandBeginwithaproductthatconsistsofthemultiplierwithanadditionalXlea
3、dingzerobitsExampleIntheweekbyweek,thereisanexampleofmultiplying2x(-5)Forourexample,let'sreversetheoperation,andmultiply(-5)x2Thenumericallylargeroperand(5)wouldrequire3bitstorepresentinbinary(101).SowemustuseATLEAST4bitstorepresenttheoperands,toallowforthesignbit.Let's
4、use5-bit2'scomplement:-5is11011(multiplier)2is00010(multiplicand)BeginningProductThemultiplieris:11011Add5leadingzerostothemultipliertogetthebeginningproduct:0000011011Step1foreachpassUsetheLSB(leastsignificantbit)andthepreviousLSBtodeterminethearithmeticaction.Ifitisth
5、eFIRSTpass,use0asthepreviousLSB.Possiblearithmeticactions:00?noarithmeticoperation01?addmultiplicandtolefthalfofproduct10?subtractmultiplicandfromlefthalfofproduct11?noarithmeticoperationStep2foreachpassPerformanarithmeticrightshift(ASR)ontheentireproduct.NOTE:ForX-bito
6、perands,Booth'salgorithmrequiresXpasses.ExampleLet'scontinuewithourexampleofmultiplying(-5)x2Remember:-5is11011(multiplier)2is00010(multiplicand)Andweadded5leadingzerostothemultipliertogetthebeginningproduct:0000011011ExamplecontinuedInitialProductandpreviousLSB00000110
7、110(Note:Sincethisisthefirstpass,weuse0forthepreviousLSB)Pass1,Step1:Examinethelast2bits00000110110Thelasttwobitsare10,soweneedto:subtractthemultiplicandfromlefthalfofproductExample:Pass1continuedPass1,Step1:Arithmeticaction(1)00000(lefthalfofproduct)-00010(mulitplicand
8、)11110(usesaphantomborrow)Placeresultintolefthalfofproduct11110110110Example:Pass1continuedPass1,Step2:ASR(ari
