booth算法超详细讲解

BoothRecoding[Lastmodified11:53:37AMonSaturday,8May]Boothmultiplicationisatechniquethatallowsforsmaller,fastermultiplicationcircuits,byrecodingthenumbersthataremultiplied.Itisthestandardtechniqueusedinchipdesign,andprovidessignificantimprovementsoverthelongmultiplicationtechnique.ShiftandAddAstandardapproachthatmightbetakenbyanovicetoperformmultiplicationistoshiftandadd,ornormallongmultiplication.Thatis,foreachcolumninthemultiplier,shiftthemultiplicandtheappropriatenumberofcolumnsandmultiplyitbythevalueofthedigitinthatcolumnofthemultiplier,toobtainapartialproduct.Thepartialproductsarethenaddedtoobtainthefinalresult:.0010110100110010110010110000000000000010110011010001Withthissystem,thenumberofpartialproductsisexactlythenumberofcolumnsinthemultiplier.ReducingtheNumberofPartialProductsItispossibletoreducethenumberofpartialproductsbyhalf,byusingthetechniqueofradix4Boothrecoding.Thebasicideaisthat,insteadofshiftingandaddingforeverycolumnofthemultipliertermandmultiplyingby1or0,weonlytakeeverysecondcolumn,andmultiplyby±1,±2,or0,toobtainthesameresults.So,tomultiplyby7,wecanmultiplythepartialproductalignedagainsttheleastsignificantbitby-1,andmultiplythepartialproductalignedwiththethirdcolumnby2:PartialProduct0=Multiplicand*-1,shiftedleft0bits(x-1)PartialProduct1=Multiplicand*2,shiftedleft2bits(x8)Thisisthesameresultastheequivalentshiftandaddmethod:PartialProduct0=Multiplicand*1,shiftedleft0bits(x1)PartialProduct1=Multiplicand*1,shiftedleft1bits(x2)PartialProduct2=Multiplicand*1,shiftedleft2bits(x4)PartialProduct3=Multiplicand*0,shiftedleft3bits(x0)Theadvantageofthismethodisthehalvingofthenumberofpartialproducts.Thisisimportantincircuitdesignasitrelatestothepropagationdelayintherunningofthecircuit,andthecomplexityandpowerconsumptionofitsimplementation.Itisalsoimportanttonotethatthereiscomparativelylittlecomplexitypenaltyinmultiplyingby0,1or2.Allthatisneededisamultiplexerorequivalent,whichhasadelaytimethatisindependentofthesizeoftheinputs.Negating2'scomplementnumbershastheaddedcomplicationofneedingtoadda1totheLSB,butthiscanbeovercomebyaddingasinglecorrectiontermwiththenecessary1sinthecorrectpositions.Radix-4BoothRecodingToBoothrecodethemultiplierterm,weconsiderthebitsinblocksofthree,suchthateachblockoverlapsthepreviousblockbyonebit.GroupingstartsfromtheLSB,andthefirstblockonlyusestwobitsofthemultiplier(sincethereisnopreviousblocktooverlap):Figure1:Groupingofbitsfromthemultiplierterm,foruseinBoothrecoding.Theleastsignificantblockusesonlytwobitsofthemultiplier,andassumesazeroforthethirdbit.Theoverlapisnecessarysothatweknowwhathappenedinthelastblock,astheMSBoftheblockactslikeasignbit.Wethenconsultthetable2-3todecidewhattheencodingwillbe.BlockPartialProduct00000011*Multiplicand0101*Multiplicand0112*Multiplicand100-2*Multiplicand101-1*Multiplicand110-1*Multiplicand1110Table1:Boothrecodingstrategyforeachofthepossibleblockvalues.SinceweusetheLSBofeachblocktoknowwhatthesignbitwasinthepreviousblock,andthereareneveranynegativeproductsbeforetheleastsignificantblock,theLSBofthefirstblockisalwaysassumedtobe0.Hence,wewouldrecodeourexampleof7(binary0111)as:0111block0:110Encoding:*(-1)block1:011Encoding:*(2)InthecasewheretherearenotenoughbitstoobtainaMSBofthelastblock,asbelow,wesignextendthemultiplierbyonebit.00111block0:110Encoding:*(-1)block1:011Encoding:*(2)block2:000Encoding:*(0)Thepreviousexamplecanthenberewrittenas:001011,multiplicand010011,multiplier11-1,boothencodingofmultiplier1111110100,negativetermsignextended00101100101100001,errorcorrectionfornegation0011010001,discardingthecarriedhighbitOnepossibleimplementationisintheformofaBoothrecoderentity,suchastheoneinfigure2-16,withitsoutputsbeingusedtoformthepartialproduct:Figure2:BoothRecoderanditsassociatedinputsandoutputs.Infigure2,ThezerosignalindicateswhetherthemultiplicandiszeroedbeforebeingusedasapartialproductTheshiftsignalisusedasthecontroltoa2:1multiplexer,toselectwhetherornotthepartialproductbitsareshiftedleftoneposition.Finally,thenegsignalindicateswhetherornottoinvertallofthebitstocreateanegativeproduct(whichmustbecorrectedbyadding1atsomelaterstage)Thedescribedoperationsforboothrecodingandpartialproductgenerationcanbeexpressedintermsoflogicaloperationsifdesiredbut,forsynthesis,itwasfoundtobebettertoimplementthetruthtablesintermsofVHDLcaseandif/then/elsestatements.SignExtensionTricksOncetheBoothrecodedpartialproductshavebeengenerated,theyneedtobeshiftedandaddedtogetherinthefollowingfashion:[PartialProduct1][PartialProduct2]00[PartialProduct3]0000[PartialProduct4]000000Theproblemwithimplementingthisinhardwareisthatthefirstpartialproductneedstobesignextendedby6bits,thesecondbyfourbits,andsoon.Thisiseasilyachievableinhardware,butrequiresadditionallogicgatesthanifthosebitscouldbepermanentlykeptconstant.11111110100000001011000101100001,errorcorrectionfornegation0011010001Fortunately,thereisatechniquethatachievesthis:Invertthemostsignificantbit(MSB)ofeachpartialproductAddanadditional'1'totheMSBofthefirstpartialproductAddanadditional'1'infrontofeachpartialproductThis