Booth algorithm

《Booth algorithm》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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