運算器設計與實現

定點數乘/除法部分第四章

(2/3)第4章“定點數乘/除法”部分作業：P136

4-8,4-9,4-10Homework運算器部分內容提要一.定點數加/減法二.定點數乘/除法三.定點數邏輯運算四.浮點數的運算

--定點數加/減法運算方法及實現--定點數加/減法運算中的溢出問題--定點數乘法算法及實現--定點數除法算法及實現--邏輯運算及實現--位移運算及實現--浮點數運算及實現二.定點數乘/除法

定點數乘法運算方法乘法的組合電路實現（乘法陣列）乘法的時序電路實現Menuofthetopic定點數乘法算法及實現

--原碼乘法--補碼乘法（Booth算法）MultiplicationExample(unsigned)

1011Multiplicand(11dec)×1101Multiplier(13dec) 101100001011 1011 10001111productof24-bitnumbersisan8-bitnumberPartialproducts

Workoutpartialproductforeachdigit

-ifmultiplierbitis1copymultiplicand(placevalue)otherwisezeroTakecarewithplacevalue(column)AddpartialproductsneeddoublelengthresultProduct(143dec)二進制乘法運算手工計算過程：

定點數乘法運算方法whenmultiplyingbyapowerof2compilerwillSubstitutealeftforamultiply

設：X=XsXnXn-1…X3X2X1

Y=YsYnYn-1…Y3Y2Y1則，X×Y=(Xs

Ys)|(XnXn-1….X3X2X1)×(YnYn-1…Y3Y2Y1)

定點原碼的一位乘法硬件計算過程：將乘法轉換成多次兩組數相加A=A3A2A1A0B=B3B2B1B0PartialProductAccumulationMultiplicandMultiplier

乘法的組合電路實現4x4arrayofmultiplier（絕對值相乘）12Adders,iffulladders,thisis6gateseach=72gates,16gatesformthepartialproductstotal=88gates!

乘法陣列(快速乘法)MultiplicationHardwareVersion1

64-bitMultiplicandreg,64-bitALU,64-bitProductreg,

32-bitMultiplierregInitialize:product=0乘法的時序電路實現（原碼）MultiplicationAlgorithmVersion11.TestMultiplier01a.Addmultiplicandtoproductandplacetheresultinproduct2.Shiftthemultiplicandregisterleft1bit.DoneYes:32repetitionsStart32ndrepetition?No:<32repetitions3.Shiftthemultiplierregisterright1bit.Multiplier0=1Multiplier0=04-BitMultiplierExample:4x3=12FourcyclestocompletionCycleMultiplierMultiplicandProductInitialize00110000010000000000Cycle0,Multiplier[0]=100010000100000000100Cycle1,Multiplier[0]=100000001000000001100Cycle2,Multiplier[0]=000000010000000001100Cycle3,Multiplier[0]=000000100000000001100Product=0Fori=0to3doIfMultiplier[0]=1thenProduct=Product+MultiplicandShiftrighttheMultiplierShiftlefttheMultiplicand

Multiplication=addition+shiftExample:MultiplicationVersion1ObservationsonMultiplicationVersion1

1/2bitsinProductreg,always0

=>1/2of64-bitadderiswasted

=>1/2ofMultiplicandiswastedInsteadofshiftingMultiplicandtoleft,

shiftProductregtoright?MultiplicationHardwareVersion2

32-bitMultiplicandreg,32-bitALU,64-bitProductreg,

32-bitMultiplierregProductMultiplierMultiplicand32-bitALUShiftRightWriteControltest32bits32bits64bitsShiftRightMultiplicationAlgorithmVersion21.TestMultiplier01a.Addmultiplicandtothelefthalfoftheproductandplacetheresultinthelefthalfoftheproductregister2.Shifttheproductregisterright1bit.DoneYes:32repetitionsStart32ndrepetition?No:<32repetitions3.Shiftthemultiplierregisterright1bit.Multiplier0=1Multiplier0=04-BitMultiplierExample:4x3=12FourcyclestocompletionCycleMultiplierMultiplicandProductInitialize0011010000000000Cycle0,Multiplier[0]=10001010001000000

00100000Cycle1,Multiplier[0]=1000001000110000000110000Cycle2,Multiplier[0]=00000010000011000Cycle3,Multiplier[0]=00000010000001100Product=0Fori=0to3doIfMultiplier[0]=1thenProduct=Product(lefthalfoftheproductregister)+MultiplicandShiftrighttheMultiplierShiftrighttheMultiplicand

Example:MultiplicationVersion2EliminateMultiplierregisterbycombiningwithProductregasshiftedrightObservationsonMultiplicationVersion2Product(Multiplier)Multiplicand32-bitALUWriteControl32bits64bitsShiftRight“HI”“LO”MultiplicationHardwareVersion3

32-bitMultiplicandreg,32-bitALU,64-bitProductreg,(shiftright)

0-bitMultiplierregMultiplicationAlgorithmVersion31.TestProduct01a.Addmultiplicandtothelefthalfoftheproductandplacetheresultinthelefthalfoftheproductregister2.Shifttheproductregisterright1bit.DoneYes:32repetitionsStart32ndrepetition?No:<32repetitionsProduct0=1Product0=04-BitMultiplierExample:4x3=12FourcyclestocompletionProduct=MultiplierFori=0to3doIfMultiplier[0]=1thenProduct=Product(lefthalfoftheproductregister)+MultiplicandShiftrightProductExample:MultiplicationVersion3MultiplyingNegativeNumbersThisdoesnotwork!Solution1ConverttopositiveifrequiredMultiplyasaboveIfsignsweredifferent,negateanswerSolution2Booth’salgorithmExampleofMultiplicationofSign-Magnitude(Solution1)●

MultiplyingMagnitudeoftwonumbersasaboveandtheresultisMagnitudeoftheresult●

SignoftheresultissignbitoftheMultiplicandXORsignbitoftheMultiplierShortcomingsofSign-MagnitudeMultiplication●CumbersomeMultiplier--Needtoconsiderbothsignandmagnitude

已知

x=–0.1110y=0.1101求[x?

y]原解：數值部分的運算0.00000.11100.11100.00000.11100.1110部分積初態z0=0

部分積乘數說明0.011101.0001101.01101100.101101101，得

z4邏輯右移邏輯右移1101=0.01111，得

z10110=0.00111，得

z21011=0.10001，得

z31101=Example:②數值部分按絕對值相乘①乘積的符號位

x0

y0=10=1x*?

y*=0.10110110∴[x

?

y]原

=1.10110110特點:絕對值運算邏輯移位

結果:用移位的次數判斷乘法是否結束Example:

x

?

y

=-0.10110110MultiplicationVersion3forSign-Magnitude

SearchingforwaystospeedupthebasicmultiplystepTrickyencodingschemetoreducethenumberofstagesinabinarymultiplierConsiderstwobitsatatimeratherthanone—thiscutsthenumberofmultiplierstepsinhalfEachstepisslightlymorecomplexcomparedtothesimplemultiplier,butisalmostasfastasthebasicmultiplierstagethatitreplaces

Booth算法

Recodingtospeedupthecalculation(Solution2)BoothMultiplier:anIntroductionRecodeeach1inmultiplieras“+2-1”Convertssequencesof1to10…0(-1)Mightreducethenumberof1’s0 0 1

1

1

1

1

1 0 0

+1 -1

+1 -1

+1 -1

+1 -1

+1 -1

+1 -10 1 0 0 0 0 0 -1 0 0–1+1000001111Recoding(Encoding)ExampleIfyouusethelastrowinmultiplication,youshouldgetexactlythesameresultasusingthefirstrow(afterall,theyrepresentthesamenumber!)

0 1

101

1

1000100(+1-1)

(+1-1)

(+1-1)

(+1-1)

(+1-1)

(+1-1)+10-1+100-100+1-100BoothMultiplicationExample6×14PrincipleoftwoscomplementinBoothMultiplication

①Y=∑(Yi+1–Yi)2-ii=0nproof：PrincipleoftwoscomplementinBoothMultiplication

proof：Booth’sAlgorithm:ImplementationApproachCurrentBitBittotheleft ExplanationExampleOp 0 1Beginsrunof1s0001111000sub 1 1Middleofrunof1s0001111000none 1 0Endofrunof1s0001111000add 0 0Middleofrunof0s0001111000none●OriginallyforSpeed(whenshiftisfasterthanadd,itisadvantageoustoreplaceaddsandsubswithshifts)●Basicidea:replaceastringof1sinmultiplierwithaninitialsubtractforrightmost1inarunof1’s,thenlateraddbacka1forthebittotheleftofthelast1intherun011110beginningofrunendofrunmiddleofrun補碼一位乘法（Booth乘法）設：被乘數[X]補=Xs.X1X2…Xn，乘數[Y]補=Ys.Y1Y2…Yn在乘數的最低位之后增加一位附加位Yn+1，它的初值為0，增加附加位不會影響運算結果。每次運算取決于乘數相鄰兩位Yi、Yi+1的值，把它們稱為乘法的判斷位。根據校正法的統一表達式推出：由乘數相鄰兩位的比較結果（Yi+1-Yi）來確定運算操作。1位Booth算法

Booth乘法規則如下：①參加運算的數用補碼表示；②符號位參加運算；③乘數最低位后面增加一位附加位Yn+1，其初值為0；④由于每求一次部分積要右移一位，所以乘數的最低兩位Yn、Yn+1的值決定了每次應執行的操作；判斷位YnYn+1

操作

00原部分積右移一位

01原部分積加[X]補后右移一位

10原部分積加[-X]補后右移一位

11原部分積右移一位⑤移位按補碼右移規則進行；⑥共需做n+1次累加，n次移位，第n+1次不移位。1位Booth算法1位Booth算法流程1bitBooth’sExample14-BitMultiplierExample:2x7=14FourcyclestocompletionWhenx=+0.0011y=–0.1011;[x·y]補=?0.00001.11011.11010.00111.11010.00111.11011.010100.000111.1101110.0001111

1.11011111[x]補

=0.0011[y]補

=1.0101[–x]補

=1.1101+[–x]補1.111011010

1+[x]補0.0000111010+[–x]補

1.11101111010.0000111110+[–x]補+[x]補∴

[x·y]補

=1.11011111done1bitBooth’s

Example2Answer:1bitBoothMultipliercircuitfortwoscomplement

規則：當乘數由1位符號位和n(奇數)位數值位組成時，做(n+1)/2次運算，最后一次操作僅右移1位。當數值位n為偶數時，有2種方法:(1)取1位符號位，在乘數最后補一個0，使乘數的數值位成為奇數，做n/2+1次運算，最后一次操作僅右移1位。

(2)取2位符號位，做n/2+1次運算，最后一次不必再進行右移操作。2bitBooth’sAlgorithm根據布斯算法，將兩步合并成一步，可推導出補碼2位乘法的公式多位Booth算法可以加快運算速度！2bitBooth’sExample

4-BitMultiplierExample:2x7=14FourcyclestocompletionMenuofthetopic定點數除法算法及實現

定點數除法運算方法除法的組合電路實現（除法陣列）除法的時序電路實現--原碼除法--補碼除法除法比乘法復雜，尤其是對負數情況的處理更加復雜！0011111011110110010011101100111010111011100Quotient（商）Dividend（被除數）Remainder（余數）PartialRemainders（部分余數）Divisor

（除數）DivisionofUnsignedBinaryIntegers（Basedonlongdivision）Seehowbiganumbercanbesubtracted,creatingquotientbitoneachstepBinary=>1*divisoror0*divisor二進制除法運算手工計算過程：將除法轉換成多次兩組數相減whendivisionbyapowerof2compilerwillSubstitutearightforadivisor

Dividend=Quotient×Divisor+Remainder001111011110110010011101100111010111011100Quotient（商）Dividend（被除數）Remainder（余數）PartialRemainders（部分余數）Divisor

（除數）DivisionofUnsignedBinaryIntegers（Basedonlongdivision）二進制除法運算硬件計算過程：111001011＋0011111011恢復余數Divide=sub+shift(divisor)

PartialRemainderRi＞0Quotientibit=1，

Ri+1=2Ri–Divisor

Restoringdivision（恢復余數法）

non-restoringdivision

（不恢復余數法）

PartialRemainderRi＜0Quotientibit=0，

Ri+DivisorRi+1=2(Ri+Divisor)–Divisor=2Ri+Divisor

PartialRemainderRi＞0Quotientibit=1，

Ri+1=2Ri–Divisor

PartialRemainderRi＜0Quotientibit=0，

Ri+1=2Ri+Divisor定點數除法運算方法根據對余數處理方法不同可分為：

除法的組合電路實現DIVIDEHARDWAREVersion164-bitDivisorreg,64-bitALU,64-bitRemainderreg,

32-bitQuotientregRemainderQuotientDivisor64-bitALUShiftRightShiftLeftWriteControl32bits64bits64bitsInitialize:Remainder=Dividend

除法的時序電路實現（原碼）（Basedonlongdivision）2b.RestoretheoriginalvaluebyaddingtheDivisorregistertotheRemainderregister,&placethesumintheRemainderregister.AlsoshifttheQuotientregistertotheleft,settingthenewleastsignificantbitto0.DivideAlgorithmVersion1Takesn+1stepsforn-bitQuotient&Rem.Test

RemainderRemainder<0Remainder≥0SubtracttheDivisorregisterfromtheRemainderregister,andplacetheresultintheRemainderregister.2a.ShifttheQuotientregistertotheleftsettingthenewrightmostbitto1.3.ShifttheDivisorregisterright1bit.DoneYes:n+1repetitions(n=32here)Start:PlaceDividendinRemaindern+1repetition?No:<n+1repetitionsRestoringdivision4-BitDivideExample:x=10010011,y=1011求：x/y解：商=1101余數=0100Remainder=DividendFori=1to5do

SubtracttheDivisorregisterfromtheRemainderregisterIfRemainder≥0thenQuotientrightmostbitto1.elseRestoretheRemainder&Quotientrightmostbitto0.ShiftrighttheDivisorExample:DivideVersion1恢復余數法ObservationsonDivideVersion1

1/2bitsindivisoralways0

=>1/2of64-bitadderiswasted

=>1/2ofdivisoriswastedInsteadofshiftingdivisortoright,

shiftremaindertoleft?1ststepcannotproducea1inquotientbit

(otherwisetoobig)

=>switchordertoshiftfirstandthensubtract,

cansave1iterationDIVIDEHARDWAREVersion232-bitDivisorreg,32-bitALU,64-bitRemainderreg,

32-bitQuotientregRemainderQuotientDivisor32-bitALUShiftLeftWriteControl32bits32bits64bitsShiftLeftInitialize:Remainder=Dividend

DivideAlgorithmVersion23b.

RestoretheoriginalvaluebyaddingtheDivisorregistertothelefthalfofthe

Remainderregister,&placethesuminthelefthalfofthe

Remainderregister.AlsoshifttheQuotientregistertotheleft,settingthenewleastsignificantbitto0.Test

RemainderRemainder<0Remainder≥02.

SubtracttheDivisorregisterfromthe

lefthalfofthe

Remainderregister,&placetheresultinthelefthalfofthe

Remainderregister.3a.

ShifttheQuotientregistertotheleftsettingthenewrightmostbitto1.1.

ShifttheRemainderregisterleft

1bit.DoneYes:nrepetitions(n=32here)

nthrepetition?No:<n

repetitionsStart:PlaceDividendinRemainderRestoringdivision4-BitDivideExample:x=10010011,y=1011求：x/y解：商=1101余數=0100Remainder=DividendFori=1to5do

SubtracttheDivisorregisterfromthelefthalfRemainderregisterIfRemainder≥0thenQuotientrightmostbitto1.elseRestoretheRemainder&Quotientrightmostbitto0.ShiftlefttheRemainderExample:DivideVersion2恢復余數法EliminateQuotientregisterbycombiningwithRemainderasshiftedleftStartbyshiftingtheRemainderleftasbefore.ThereafterloopcontainsonlytwostepsbecausetheshiftingoftheRemainderregistershiftsboththeremainderinthelefthalfandthequotientintherighthalfTheconsequenceofcombiningthetworegisterstogetherandtheneworderoftheoperationsintheloopisthattheremainderwillshiftedleftonetimetoomany.ThusthefinalcorrectionstepmustshiftbackonlytheremainderinthelefthalfoftheregisterObservationsonDivideVersion2DIVIDEHARDWAREVersion332-bitDivisorreg,32-bitALU,64-bitRemainderreg,

(0-bitQuotientreg)Remainder(Quotient)Divisor32-bitALUWriteControl32bits64bitsShiftLeft“HI”“LO”DivideAlgorithmVersion33b.RestoretheoriginalvaluebyaddingtheDivisorregistertothelefthalfoftheRemainderregister,&placethesuminthelefthalfoftheRemainderregister.AlsoshifttheRemainderregistertotheleft,settingthenewleastsignificantbitto0.Test

RemainderRemainder<0Remainder≥

02.SubtracttheDivisorregisterfromthe

lefthalfoftheRemainderregister,&placetheresultinthelefthalfoftheRemainderregister.3a.ShifttheRemainderregistertotheleftsettingthenewrightmostbitto1.1.ShifttheRemainderregisterleft1bit.Done.ShiftlefthalfofRemainderright1bit.Yes:nrepetitions(n=32here)nthrepetition?No:<nrepetitionsStart:PlaceDividendinRemainderRestoringdivision4-BitDivideExample:x=10010011,y=1011求：x/y解：商=1101余數=0100Remainder=DividendShifttheRemainderregisterleft1bitFori=1to4do

SubtracttheDivisorregisterfromthelefthalfRemainderregisterIfRemainder≥0thenRemainderrightmostbitto1&elseRestoretheRemainder&Remainderrightmostbitto0.ShiftlefttheRemainderExample:DivideVersion3恢復余數法Thisdoesnotwork!Simplestwayistoremembersigns,makepositive,andcomplementquotientandremainderifnecessaryNote:DividendandRemaindermusthavesamesignNote:QuotientnegatedifDivisorsign&Dividendsigndisagree

e.g.,–7÷2=–3,remainder=–1UsingtwoscomplementdivisionmethodSignofthenumbercanbehandledasmagnitudebitsigneddivision

Remainderofsigneddivision

Therule:Dividend=Quotient×Divisor+Remainder(-7)÷(+2):Quotient=-3,Remainder=-1OR:Quotient=-4,Remainder=+1e.gThedividendandremaindermusthavethesamesigns,nomatterwhatthesignsofthedivisorandquotientExampleofDivisionofSign-Magnitude

Remembersigns,makepositive,andcomplementquotientandremainderifnecessaryNote:DividendandRemaindermusthavesamesign

●QuotientnegatedifDivisorsign&Dividendsigndisagree

Divisor≠0Dividend≠0assumptionDividend＞Divisorintegerfix-pointnumberDividend＜Divisordecimalfix-pointnumber(Solution1)

已知X=-0.01010Y=-0.11001求X/Y⑴符號位單獨運算解：

x0

y0=1

1=0⑵數值部分的運算[|X|]原=[|X|]補=0.01010[|Y|]原=[|Y|]補=0.110