計算機組織與結(jié)構(gòu)電子教案第

東南大學(xué)計算機學(xué)院主講教師：徐造林計算機組織與結(jié)構(gòu)第2章數(shù)據(jù)的表示和運算(續(xù))●運算器是計算機中的執(zhí)行部件，它可以對二進制數(shù)據(jù)進行各種算術(shù)和邏輯運算；運算器也是計算機內(nèi)部數(shù)據(jù)信息的重要通路?！癖局v重點介紹運算器的核心部件——算術(shù)邏輯運算單元ALU的構(gòu)成與工作原理，以及數(shù)據(jù)在運算器中基本運算方法。2.5運算器的基本組成與功能▲運算器是實現(xiàn)對數(shù)值數(shù)據(jù)的算術(shù)運算和邏輯數(shù)據(jù)的邏輯操作。1.算術(shù)邏輯運算單元ALU▲運算器中完成數(shù)據(jù)算術(shù)與邏輯運算的部件稱之為算術(shù)與邏輯運算單元(ALU)；ALU是運算器的核心。▲ALU通常表示為兩個輸入端口，一個輸出端口和多個功能控制信號端的一個邏輯符號?！ㄋ阈g(shù)邏輯運算單元ALU，保存操作數(shù)、結(jié)果、出錯信息和狀態(tài)信息的各種寄存器以及多路轉(zhuǎn)換器、數(shù)據(jù)總線、控制線路等邏輯組件。圖2.5ALU的邏輯符號表示與多路開關(guān)2.通用寄存器組▲

通用寄存器組用于暫時存放參加運算的數(shù)據(jù)和某些中間結(jié)果。▲

在運算器中用來提供一個操作數(shù)并存放運算結(jié)果的通用寄存器稱作為累加器。

通用寄存器的數(shù)量越多，對提高運算器性能和程序執(zhí)行速度越有利；

通用寄存器組是對用戶開放的，用戶可以通過指令去使用這些寄存器。

如：ADDA,Rj3.專用寄存器▲專用寄存器用于記錄指令執(zhí)行過程中的重要狀態(tài)標記，及運算前后數(shù)據(jù)的暫存緩沖等。循環(huán)計數(shù)器，它對程序員是透明的；程序狀態(tài)字(PSW)，它存放著指令執(zhí)行結(jié)果的某些狀態(tài)；它對程序員是開放的；堆棧指針SP(StackPointer)，它指示了堆棧的使用情況；對程序員也是開放的。OF1511109876420DFIFTFSFZFAFCFPF8086/8088標志寄存器FLAG8086/8088標志寄存器8086/8088段寄存器及IP4.控制邏輯▲控制邏輯產(chǎn)生控制信號來控制運算器執(zhí)行多種運算功能。在ALU的輸出端設(shè)置移位線路來實現(xiàn)左移、右移和直送。移位線路是一個多路選擇器。右圖：實現(xiàn)移位功能的多路選擇器5.運算器的組成圖2.6運算器邏輯框圖

ALU數(shù)據(jù)總線控制信號移位器功能控制信號狀態(tài)寄存器狀態(tài)判斷邏輯左移直送右移多路轉(zhuǎn)換器多路轉(zhuǎn)換器

寄存器組6.中央處理器CPU

▲運算器和控制部件合在一起成為中央處理器CPU圖2.7奔騰CPU結(jié)構(gòu)框圖

2.6加法器及定點加減法運算

2.6.1加法器的實現(xiàn)

◆

運算器中各種運算都是分解成加法運算進行的，加法器是計算機中最基本的運算單元。1.二進制加法單元▲

兩個一位二進制數(shù)相加(不考慮低位的進位)，稱為半加。實現(xiàn)半加操作的電路，稱為半加器。1）半加XiYiSiCi

000 0 011 0 1010 110 1表2.8半加運算真值表HAXiYiXiYiSiCiSiCi

圖2.8(a)邏輯圖(b)符號表示

Si和Ci的邏輯表達式：▲考慮低位進位的加法運算就是全加運算，實現(xiàn)全加運算的電路稱為全加器。

根據(jù)真值表，可寫出Fi和Ci的邏輯表達式：

2）全加表2.9

全加運算的真值表Si圖2.9全加器的邏輯圖和符號表示

▲全加器邏輯圖和全加器的符號表示SiSi◆

n個全加器相連可得n位的加法器

1）串行進位或行波進位加法器圖2.10n位加法器2.串行進位與并行進位2）先行進位或并行進位加法器

預(yù)先形成各位進位，將進位信號同時送到各位全加器的進位輸入端?！?/p>

就4位加法器，討論其進位C1、C2、C3和C4的產(chǎn)生條件：①下述條件中任一條滿足就可生成C1=1：

1)X1、Y1均為“1”;2)X1、Y1任一個為“1”，且進位C0為“1”。

可得C1的表達式為：

C1=X1Y1+(X1+Y1)C0②下述條件中任一條滿足，可生成C2=1。

1)X2、Y2均為“1”；

2)X2、Y2任一個為“1”，且進位C1為“1”。

可得C2的表達式為：

C2=X2Y2+(X2+Y2)C1

=X2Y2+(X2+Y2)X1Y1+(X2+Y2)(X1+Y1)C0③同理，可得C3的表達式為：

C3=X3Y3+(X3+Y3)C2=X3Y3+(X3+Y3)[X2Y2+(X2+Y2)X1Y1+(X2+Y2)(X1+Y1)C0]=X3Y3+(X3+Y3)X2Y2+(X3+Y3)(X2+Y2)X1Y1+(X3+Y3)(X2+Y2)(X1+Y1)C0④同理,可得C4的表達式為：

C4=X4Y4+(X4+Y4)C3

=X4Y4+(X4+Y4)[X3Y3+(X3+Y3)X2Y2+(X3+Y3)(X2+Y2)X1Y1+(X3+Y3)(X2+Y2)(X1+Y1)C0]=X4Y4+(X4+Y4)X3Y3+(X4+Y4)(X3+Y3)X2Y2+(X4+Y4)(X3+Y3)(X2+Y2)X1Y1+(X4+Y4)(X3+Y3)(X2+Y2)(X1+Y1)C0

▲

定義兩個輔助函數(shù)：

Pi=Xi+Yi

Gi=XiYi

Pi表示進位傳遞函數(shù)，當(dāng)Xi、Yi中有一個為“1”時，若有低位進位輸入，則本位向高位傳送進位。

Gi表示進位產(chǎn)生函數(shù)，當(dāng)Xi、Yi均為“1”時，本位一定向高位產(chǎn)生進位輸出。

▲

將Pi、Gi代入前面的C1~C4式，可得：

C1=G1+P1C0C2=G2+P2G1+P2P1C0C3=G3+P3G2+P3P2G1+P3P2P1C0

C4=G4+P4G3+P4P3G2+P4P3P2G1+P4P3P2P1C0先行進位產(chǎn)生電路其中Pi=Xi+YiGi=XiYi4位先行進位加法器S3S4S2S1

圖2.114位先行進位的全加器模塊▲組內(nèi)并行，組間串行進位的16位全加器

在各加法單元之間，進位信號是串行傳送的，而在加法單元內(nèi)，進位信號是并行傳送的。S16~13S12~9S8~5S4~1▲組內(nèi)并行，組間并行進位的16位全加器

Cm表示4位加法器的進位輸出，Pm表示4位加法器的進位傳遞輸出，Gm表示4位加法器的進位產(chǎn)生輸出。

Cm=Gm+PmC0

Pm

和Gm分別為：

Pm=P4P3P2P1Gm=G4+P4G3+P4P3G2+P4P3P2G1

應(yīng)用于四個4位先行進位加法器，則有：

Cm1=Gm1+Pm1C0Cm2=Gm2+Pm2Cm1

=Gm2+Pm2Gm1+Pm2Pm1C0Cm3=Gm3+Pm3Cm2=Gm3+Pm3Gm2+Pm3Pm2Gm1+Pm3Pm2Pm1C0

Cm4=Gm4+Pm4Cm3=Gm4+Pm4Gm3+Pm4Pm3Gm2+Pm4Pm3Pm2Gm1+Pm4Pm3Pm2Pm1C0圖2.12組間由先行進位鏈構(gòu)成的16位加法器▲可將并行進位的概念用于更大位數(shù)的加法器上，隨著加法器位數(shù)的增加，加法電路變得越來越復(fù)雜。S16~13S12~9S8~5S4~1◆

ALU是一種能進行多種算術(shù)運算與邏輯運算的組合邏輯電路，它的基本邏輯結(jié)構(gòu)是先行進位加法器。◆

74181型4位ALU中規(guī)模集成電路工作原理能對兩個4位二進制代碼A3A2A1A0和B3B2B1B0進行16種算術(shù)運算（當(dāng)M為低電位時）和16種邏輯運算（當(dāng)M為高電位時），產(chǎn)生結(jié)果F3F2F1F0。

16種運算操作由S3S2S1S0四位控制選擇

Cn是ALU的最低位進位輸入，低電平有效，即Cn=L表示有進位輸入；

Cn+4是ALU進位輸出信號。3.ALU部件▲表2.1074181型4位ALU在正邏輯下的功能表圖2.13(b)74181型ALU邏輯圖Xi=Ai

，Yi=Bi1）ALU實現(xiàn)加法操作的原理▲當(dāng)S3S2S1S0=HLLH，M=L時，ALU實現(xiàn)對A3A2A1A0和B3B2B1B0兩個4位二進制代碼在進位輸入Cn參與下的加法運算；即：Fi=

AiBiCn+i(i=3,2,1,0)

設(shè)Xi=Ai

，Yi=Bi

；可推導(dǎo)Xi、Yi

和Ai、Bi的關(guān)系：Xi+Yi=AiBiXiYi=Ai+BiXiYi=AiBi

ALU就可以改畫成以Xi、Yi為輸入的結(jié)構(gòu)較簡單的單元；

可證明GiPi=XiYi

。

圖3.10是一個由先行進位加法器組成的單元，電路輸出：

Fi=XiYiCn+i=AiBiCn+i。

由圖3.9可知：

Pi=AiBiS2+AiBiS3=Xi+YiGi=Ai+BiS0+BiS1=XiYi圖2.1474181作加法運算時的簡化邏輯圖2）ALU單元實現(xiàn)邏輯運算▲當(dāng)M=H時，由圖3.9可知，進位門13~16均被封鎖，F(xiàn)i=PiGi，位間不發(fā)生關(guān)系，電路執(zhí)行邏輯運算。

S3S2S1S0=HHHH時，F(xiàn)i=PiGi=Ai，即F=A，此時，電路執(zhí)行“傳送A”的操作?！匆陨戏椒ǎ扇娣治?、理解74181的邏輯圖和真值表。

S3S2S1S0=HLLH時，F(xiàn)i=PiGi=AiBi，對輸入數(shù)據(jù)A3A2A1A0和B3B2B1B0執(zhí)行邏輯“同或”(異或非)操作?！髨D是74181ALU在正邏輯下的圖形符號圖2.15用四片74181構(gòu)成的16位ALU▲下圖是用4片74181組成的16位ALU，芯片內(nèi)用先行進位方法，但片間為串行進位?！趫D3.9的74181的邏輯圖中，用先行進位方法產(chǎn)生的進位輸出Cn+4和圖中P、G的輸出信號用表達式：考慮算術(shù)運算，M=LP=P3P2P1P0G=G3+P3G2+P3P2G1+P3P2P1G0Cn+4=GP3P2P1P0Cn=G+PCn=GP+GCn

P稱為片間進位傳遞函數(shù)，G稱為片間進位產(chǎn)生函數(shù)▲根據(jù)74181提供的G、P信號，很容易實現(xiàn)芯片之間的先行進位。▲在圖3.12

中，高三片74181的片間進位輸入可以表示為如下表達式：

Cn+4=G(0)+P(0)Cn=G(0)P(0)+G(0)CnCn+8=G(1)+P(1)Cn+4=G(1)+P(1)(G(0)+P(0)Cn)=G(1)P(1)+G(1)G(0)P(0)+G(1)G(0)Cn

Cn+12=G(2)+P(2)Cn+8=G(2)+P(2)G(1)P(1)+G(1)G(0)P(0)+G(1)G(0)Cn=G(2)P(2)+G(2)G(1)P(1)+G(2)G(1)G(0)P(0)+G(2)G(1)G(0)CnP=P(3)P(2)P(1)P(0)

圖3.16片間先行進位產(chǎn)生電路(74182)G=G(3)P(3)+G(3)G(2)P(2)+G(3)G(2)G(1)P(1)+G(3)G(2)G(1)G(0)▲用四片74181和一片74182芯片組成的16位快速ALU；利用16片74181和5片74182芯片可以組成64位快速ALU。圖2.17四片74181和一片74182構(gòu)成的快速16位ALU2.6.2補碼定點加、減法◆

計算機的一個重要特點是它只能用有限的數(shù)碼位數(shù)來表示操作數(shù)和操作結(jié)果。制定用來表示正、負數(shù)的各種碼制；通過數(shù)據(jù)編碼來簡化數(shù)據(jù)的運算。定點加、減法運算只有在遵守模運算規(guī)則的限制條件下其結(jié)果才是正確的，否則就會出現(xiàn)結(jié)果“溢出”?！粞a碼的加、減法運算公式：

[X+Y]補=([X]補+[Y]

補)MOD2n[X-Y]補=([X]補+[-Y]

補)MOD2n在補碼制方法下，無論X、Y是正數(shù)還是負數(shù)，加、減法運算統(tǒng)一采用加法來處理；[X]補和[Y]補的符號位和數(shù)值位一起參與求和運算，加、減運算結(jié)果的符號位也在求和運算中直接得出?！?/p>

例1：已知[X]補=01001，[Y]補=11100；求[X+Y]補，

[X-Y]補。

解：[-Y]補=00100[X+Y]補=([X]補+[Y]補)MOD25=(01001)MOD25=00101

[X-Y]補=([X]補+[-Y]補)MOD25=(01001+00100)MOD25=01101◆實現(xiàn)補碼加、減法運算的邏輯電路圖2.18加法器的邏輯符號圖2.19減法器的邏輯符號

0，加（ADD）操作1，減（SUB）操作C0＝

Bi*＝Bi⊕C0

圖2.20n位補碼加法器

Cn2.6.3數(shù)據(jù)溢出及檢測

若結(jié)果超過了允許表示的最小負數(shù)時，產(chǎn)生的溢出稱為下溢?！舢?dāng)算術(shù)運算的結(jié)果超出了數(shù)碼位數(shù)允許的數(shù)據(jù)范圍時，就產(chǎn)生溢出。對于n位的二進制碼表示的補碼整數(shù)，它可表示的數(shù)據(jù)范圍為-2n-1~2n-1-1。若結(jié)果超過了允許表示的最大正數(shù)時，產(chǎn)生的溢出稱為上溢；在運算器中應(yīng)設(shè)有溢出判別線路和溢出標志位?！衾?：已知[X]補=01010，[Y]補=01010[X+Y]補=(01010)MOD25=10100溢出◆例3：已知[X]補=10010，[Y]補=00100[X-Y]補=(10010)MOD25=01110溢出[10]10+[10]10=

[20]10>15產(chǎn)生上溢[-14]10-[4]10=

[-18]10<-16產(chǎn)生下溢◆溢出常用的判別方法：①根據(jù)數(shù)據(jù)表示范圍判斷帶符號數(shù)相加時，符號位產(chǎn)生的進位有自動丟棄和指示溢出兩種可能性。

不同符號的數(shù)相加不可能產(chǎn)生溢出。

當(dāng)兩個操作數(shù)符號相同而和數(shù)的符號位與操作數(shù)符號也相同時不可能產(chǎn)生溢出。

只有當(dāng)兩個操作數(shù)符號相同而和數(shù)的符號位與操作數(shù)符號不同時才產(chǎn)生溢出。

OVR＝AnBnSn＋AnBnSn

＝（An⊕Sn）（Bn⊕Sn）圖2.21帶溢出檢測電路的補碼加法器②

兩個補碼數(shù)實現(xiàn)加、減運算時，若最高數(shù)值位向符號位的進位值Cn-1與符號位產(chǎn)生的進位輸出值Cn不相同，表明加減運算產(chǎn)生了溢出OVR；可以表示為：

OVR=Cn-1Cn

OVR=1表示結(jié)果有溢出，OVR=0表示結(jié)果正確。在例1中，求[X+Y]補時：OVR=Cn-1Cn=11=0，結(jié)果正確。在例2中，求[X+Y]補時：OVR=Cn-1Cn=10=1，結(jié)果溢出。在例3中，求[X-Y]補時：OVR=Cn-1Cn=01=1，結(jié)果溢出。③

常用雙符號位方法來判別加、減法運算是否有溢出。兩個正數(shù)雙符號位的運算為00+00=00時，結(jié)果不溢出；兩個正數(shù)雙符號位的運算為00+00+1=01時，結(jié)果上溢；兩個負數(shù)的雙符號位運算為（11+11+1）MOD4=11時，結(jié)果不溢出；兩個負數(shù)的雙符號位的運算為（11+11）MOD4=10時，結(jié)果下溢?！捎媚?補碼運算，其運算結(jié)果的兩個符號位不一致時，產(chǎn)生溢出。＝Sn+1⊕Sn

2.7

定點乘法運算及實現(xiàn)◆乘法運算的實現(xiàn)方法用軟件實現(xiàn)乘法運算；在加法器的基礎(chǔ)上增加一些硬件實現(xiàn)乘法運算；

設(shè)置專用硬件乘法器實現(xiàn)乘法運算。

◆常規(guī)的乘法運算方法筆---紙乘法方法；原碼乘法；帶符號位運算的補碼乘法；◆用組合邏輯線路構(gòu)成的陣列乘法器。2.7.1原碼乘法設(shè)：[X]原=xnxn-1x1x0，[Y]原=ynyn-1y1y0(其中xn

、yn分別為它們的符號位)若[X×Y]原=z2nz2n-1z1z0(z2n為結(jié)果之符號位)

則z2n=xnyn

z2n-1z1z0=(xn-1x1x0)×(yn-1y1y0)類似兩個無符號數(shù)相乘?！粲迷a實現(xiàn)乘法運算時，符號位與數(shù)值位是分開計算的；1.原碼一位乘◆筆---紙乘法方法▲例1.X=1011,Y=1101，X×Y的筆---紙乘法過程： 1011被乘數(shù)X=x3x2x1x0=1011 ×1101乘數(shù)Y=y3y2y1y0=1101

1011X×y0×20 0000X×y1×21 1011X×y2×22 +1011X×y3×2310001111因此X×Y=10001111◆就筆---紙乘法方法，為提高效率而采取的改進措施①每將乘數(shù)Y的一位乘以被乘數(shù)得X×yi后，就將該結(jié)果與前面所得的結(jié)果累加，得到部分積Pi；②將部分積Pi右移一位與X×yi相加；加法運算始終對部分積中的高n位進行；③對乘數(shù)中“1”的位執(zhí)行加法和右移運算，對“0”的位只執(zhí)行右移運算，而不執(zhí)行加法運算；

設(shè)P0=0P1=2-1(P0+X×y0)P2=2-1(P1+X×y1)Pi+1=2-1(Pi+X×yi)(i=0,1,2,3,n-1)……Pn=2-1(Pn-1+X×yn-1)▲上述乘法運算可以歸結(jié)為循環(huán)地計算下列算式：顯然，X×Y=Pn▲對于兩個n位無符號數(shù)乘法的一種可行的算法：1）置計數(shù)器為n；2）清除2n位部分積寄存器；3）檢查乘數(shù)最右位（初始時為最低位），若為“1”，加被乘數(shù)到部分積高n位中；4）將部分積右移一位；5）將乘數(shù)右移一位；6）計數(shù)器減1，結(jié)果不為0，則從3）開始重新執(zhí)行；若結(jié)果為0，則從部分積寄存器讀出乘積?！鴮崿F(xiàn)這種方法的二個定點數(shù)乘法的邏輯電路框圖圖2.22原碼一位乘原理圖

nn圖3.20

兩個定點小數(shù)的乘法操作流程YNyi=1?圖2.23▲例1．已知[X]原=01101,[Y]原=01011

,

z7…z0=1101×1011的計算采用上述乘法流程，實現(xiàn)的具體過程如下：若[X×Y]原=z8z7z0

則z8=00=0CPY說明

000001011

開始，設(shè)P0=0+1101y0=1，+X01101C，P和Y同時右移一位001101101得P1+1101y1=1，+X10011C，P和Y同時右移一位010011110

得P2y2=0，不作加法

C，P和Y同時右移一位

001001111

得P3+1101y3=1，+X10001C，P和Y同時右移一位010001111

得P4z7…z0=10001111[X×Y]原=z8z7…z0=0

10001111=0010001111001101101

得P1為提高乘法的速度，一步求出兩位的部分積?！粼诔朔ㄖ校藬?shù)的每兩位有四種可能的組合：◆原碼二位乘法的思想采用原碼二位乘法，只需增加少量的邏輯線路，就可以將乘法的速度提高一倍。yi+1yi=00—Pi+1=2-2(Pi+0*X)yi+1yi=01—Pi+1=2-2(Pi+1*X)yi+1yi=10—Pi+1=2-2(Pi+2*X)yi+1yi=11—Pi+1=2-2(Pi+3*X)2.原碼二位乘實現(xiàn)+3X有兩種方法：①分+X再+2X來進行，此法速度較低；②以4X-X來代替3X運算，在本次運算中只執(zhí)行-X，而+4X則歸并到下一拍執(zhí)行；

Pi+1=2-2(Pi+3X)=2-2(Pi-X+4X)=2-2(Pi-X)+X?！粲脃i+1、yi和Cowe三位來控制乘法操作觸發(fā)器Cowe用來記錄是否欠下+X，若是，則1Cowe

?！粼a兩位乘法運算規(guī)則表2.11原碼兩位乘法運算規(guī)則yiyi-1Cowe

操作迭代公式000001010011100101110111+X+X+2X+2X-X-X0→Cowe0→Cowe0→Cowe0→Cowe0→Cowe1→Cowe1→Cowe1→Cowe2-2(Pi)2-2(Pi+X)2-2(Pi+X)2-2(Pi+2X)2-2(Pi+2X)2-2(Pi-X)2-2(Pi-X)2-2(Pi)◆對于原碼兩位乘算法的說明：

1）

乘積符號與其絕對值分別處理，即

|Z|=|X|×|Y|=(xn-1···x0)×(yn-1···y0)

zn=xn⊕yn

2）部分積與被乘數(shù)采用三個符號位；3）在實際運算中–X操作以＋[–X]補完成；4）每次按表3.3判斷當(dāng)前兩位乘數(shù)及上一次“欠帳”情況，以決定做什么操作。◆原碼兩位乘法運算過程舉例例1：已知[X]原=0111001,[Y]原=0100111

,

[|X|]補=0111001，[-|X|]補=1000111

；若[X×Y]原=z12z11…z0

則z12=00=0

z11…z0=111001*100111具體過程：PYT說明

000000000100111

0

開始，P0=0，T=01y1y0T=110，-X,T=1111000111P和Y同時右移2位111000111P和Y同時右移2位1111100011110011

得P1+001110010y3y2T=011，+2X,T=0001100011P和Y同時右移2位0000110001111100得P2+001110010y5y4T=100，+2X,T=0

010001010P和Y同時右移2位

0001000101011110得P3z11z0=100010101111因此[X×Y]原=0100010101111=001000101011112.7.2補碼乘法◆考查兩個補碼乘法運算的例子例1：已知X=0.1011，Y=0.0001[X]補=0.1011,[Y]補=0.0001[X×Y]補=0.00001011[X]補×[Y]補=0.00001011

顯然，[X×Y]補=[X]補×[Y]補1.補碼一位乘例2：已知X=0.1011，Y=-0.0001[X]補=0.1011,[Y]補=1.1111[X×Y]補=1.11110101[X]補×[Y]補=1.01010101

顯然，[X×Y]補[X]補×[Y]補▲對兩個正數(shù)來說，它們補碼的乘積等于它們乘積的補碼。若乘數(shù)是負數(shù)時，這種情況就不成立了?！鬊ooth（布斯）乘法相乘二數(shù)用補碼表示，它們的符號位與數(shù)值位一起參與乘法運算過程，得出用補碼表示的乘法結(jié)果?！鳤.D.Booth算法思想：▲Booth算法推導(dǎo)：已知[X]補=xnxn-1……x0,[Y]補=ynyn-1……y0；根據(jù)補碼定義（定點整數(shù)）:[Y]補=2n+1+Y=2n+1yn+Yyn＝，當(dāng)Y≥0，當(dāng)Y＜0Y=[Y]補-2n+1ynX×Y=X×{[Y]補-2n+1yn}=X{yn2n

+

yn-12n-1+……+y121+

y020

-2n+1yn}=X{-yn2n

+

yn-12n-1

+……+y121+

y020}=2n

(yn-1

-yn)X

+

2n-1

(yn-2–yn-1)X

+……

+

21

(y0–y1)X+

20

(0

–y0)X可得出其真值:y-1為增設(shè)的一個附加位，初值為0；[X×Y]補=[2n(yn-1–yn)X

+

2n-1(yn-2–yn-1)X

+……

+

21(y0–y1)X+

20(y-1–y0)X]補令[X×Y]補=[X×Y]’補×2n[X×Y]’補=[(yn-1–yn)X+2-1(yn-2–yn-1)X

+……

+

2-(n-1)(y0–y1)X+2-n(y-1–y0)X]補得到如下遞推公式令[P0]補＝0，有：[P1]補=[2-1(P0+(y-1-y0)×X]補

[P2]補=[2-1(P1+(y0-y1)×X]補

[Pi]補=[2-1(Pi-1+(yi-2-yi-1)×X)]補(i=1~n)[Pn]補=[2-1(Pn-1+(yn-2-yn-1)×X)]補

[X*Y]’補=[Pn+1]補=[Pn+(yn-1-yn)×X]補

(yi-1–yi)X實際上并不做乘法，只要比較相鄰兩位乘數(shù)以決定+X、–X或+0。對乘數(shù)的連續(xù)兩位yi和yi-1進行判斷若yiyi-1=01，則[Pi+1]補=[2-1(Pi+X)]補若yiyi-1=10，則[Pi+1]補=[2-1(Pi–X)]補若yiyi-1=00或11，則[Pi+1]補=[2-1Pi]補一個補碼數(shù)據(jù)的右移是連同符號位右移，且最高位補充符號位的值。在計算機中，對于定點整數(shù)，只要認定小數(shù)點在乘積之末，相當(dāng)于將小數(shù)點右移n位。

是是是否否否圖2.24布斯乘法運算流程圖開始y-1，P0X補碼制的被乘數(shù)Y補碼制的乘數(shù)Cnn

yiyi-1=01?PP+XCn=0P和Y同時右移一位CnCn-1yiyi-1=10?PP-X結(jié)束▲例3：已知[X]補=01101,[Y]補=10110，

[-X]補=10011。用布斯乘法計算[X×Y]補的過程如下PYy-1

說明

00000010110

0

開始，設(shè)y-1=0，[P0]補=0y0y-1=00，P、Y同時右移一位

00000001011

0

得[P1]補y1y0=10，+[-X]補110011P、Y同時右移一位11100110101

1

得[P2]補y2y1=11，P、Y同時右移一位111100110101得[P3]補11110011010

1

得[P3]補y3y2=01，+[X]補001001P、Y同時右移一位000100111010

得[P4]補y4y3=10，+[-X]補11011111101最后一次不右移因此，[X×Y]補=101111110=1101111110▲布斯乘法的算法過程為n+1次的“判斷—加減—右移”的循環(huán)，判斷的次數(shù)為n+1次，右移的次數(shù)為n次?！诓妓钩朔ㄖ?，遇到連續(xù)的“1”或連續(xù)的“0”時，是跳過加法運算，直接實現(xiàn)右移操作的，運算效率高。◆補碼二位乘法可以用布斯乘法過程來推導(dǎo)[Pi+1]補=2-1{[Pi]補

+(yi-1–yi)×[X]補}[Pi+2]補=2-1{[Pi+1]補+(yi–yi+1)×[X]補}[Pi+2]補=2-2{[Pi]補+(yi-1+yi–2yi+1)×[X]補}▲根據(jù)乘數(shù)的兩位代碼yi+1和yi以及右鄰位yi-1的值的組合作為判斷依據(jù)，跳過[Pi+1]補步，即從[Pi]補直接求得[Pi+2]補。2.補碼二位乘乘數(shù)代碼對右鄰位加減判斷規(guī)則操

作

yi+1

yiyi-1

yi-1+yi–2yi+1

[Pi+2]補

表2.12乘數(shù)3位代碼組合構(gòu)成的判斷規(guī)則

00002-2[Pi]補

001+[X]補

2-2{[Pi]補+[X]補}

010+[X]補

2-2{[Pi]補+[X]補}

011+2[X]補

2-2{[Pi]補+2[X]補}

100+2[-X]補

2-2{[Pi]補+2[-X]補}

101+[-X]補

2-2{[Pi]補+[-X]補}

110+[-X]補

2-2{[Pi]補+[-X]補}

11102-2[Pi]補◆設(shè)乘數(shù)[Y]補=ynyn-1……y1y0，導(dǎo)出補碼二位乘法中的計算量。(1)當(dāng)n為偶數(shù)時，乘法運算過程中的總循環(huán)次數(shù)為n/2+1；最后一次不右移。(2)當(dāng)n為奇數(shù)時，為使方法統(tǒng)一，對定點整數(shù)可在數(shù)值位最高位前補一位（正數(shù)補“0”負數(shù)補“1”），定點小數(shù)可在末位補一位“0”，湊成偶數(shù)?！衾?：已知[X]補=00011，[Y]補=11010；[-X]補=11101。用補碼二位乘法計算[X×Y]補的過程。PYy-1

說明0000000110100開始，設(shè)y-1=0，[P0]補=0y1y0y-1=100，+2[-X]補1111010P和Y同時右移二位1111110101101得[P1]補y3y2y1=101，+[-X]補1111011P和Y同時右移二位1111110111011得[P2]補

y4y4y3=111，不做加法最后一次不右移

[X×Y]補=111101110=11111011102.7.3

陣列乘法器◆實現(xiàn)上述執(zhí)行過程的陣列結(jié)構(gòu)的乘法器，稱為陣列乘法器(ArrayMultiplier)

設(shè)兩個四位二進制數(shù)相乘

X×Y，其中X=x3x2x1x0,Y=y3y2y1y0；X和Y都是無符號定點數(shù)。+進位進位圖2.25陣列乘法器單元電路

乘積X×Y=Z圖2.26直接實現(xiàn)定點數(shù)絕對值相乘的陣列乘法器圖2.27偽加器單元

Ci＝XiYi＋YiZi＋XiZi

▲存儲進位加法器（CarrySaveAdder），簡稱CSA

將進位信息暫時保留，留待下一級加法處理。

圖2.284×4陣列乘法器原理圖▲為解決進位問題，采用下圖所示的陣列乘法器圖2.29帶求補級的陣列乘法器框圖

絕對值絕對值Booth算法的乘法運算也可以用陣列乘法器的方法實現(xiàn)，但要求的單元更復(fù)雜。組織結(jié)構(gòu)規(guī)則性強，標準化程度高；適合用超大規(guī)模集成電路實現(xiàn)，且能獲得很高的運算速度。集成電路的價格不斷下降，陣列乘法器在某些數(shù)字系統(tǒng)中(如在信號及數(shù)據(jù)處理系統(tǒng)中)?！絷嚵谐朔ㄆ鞯奶攸c2.8定點除法運算及實現(xiàn)◆在定點運算中，除法的算法主要有比較法、恢復(fù)余數(shù)法和不恢復(fù)余數(shù)法三種。①在小數(shù)除法中，被除數(shù)和除數(shù)應(yīng)滿足如下條件：

0＜|被除數(shù)|＜|除數(shù)|。②在整數(shù)除法中，被除數(shù)和除數(shù)應(yīng)滿足如下條件：

0＜|除數(shù)|≤|被除數(shù)|。③定點整數(shù)除法允許雙字長的被除數(shù)除以單字長的除數(shù)，得到單字長的商和單字長的余數(shù)?！舳c整數(shù)，定點小數(shù)除法的差異；2.8.1原碼除法運算1.比較法（筆-紙方法）的除法步驟：①被除數(shù)與除數(shù)比較，決定上商；若被除數(shù)小，上商0；否則上商1；得到部分余數(shù)。②將除數(shù)右移，再與上一步部分余數(shù)比較，決定上商，并且求得新的部分余數(shù)。③重復(fù)執(zhí)行第②步，直到求得的商的位數(shù)足夠為止。例1：已知兩正數(shù)X=0.10011101，

Y=0.1011X/Y的商為0.1110，余數(shù)為0.0011×2-4商的符號為相除兩數(shù)符號的“異或”值，商的數(shù)值為兩數(shù)的絕對值之商。▲

原碼一位除法規(guī)律原碼一位除法運算與原碼一位乘法運算一樣，要區(qū)分符號位和數(shù)值位兩部分。余數(shù)的符號應(yīng)與被除數(shù)同號；所得的商和余數(shù)是以原碼表示?！粲嬎銠C中實現(xiàn)二個正數(shù)除法時，有幾點不同：①比較運算用減法來實現(xiàn)，由結(jié)果的正負來判斷兩數(shù)的大?。唤Y(jié)果為正，上商1；結(jié)果為負，上商0。②

減法運算時，加法器中兩數(shù)的對齊是用部分余數(shù)左移實現(xiàn)，并與除數(shù)比較；左移出界的部分余數(shù)的高位都是0，對運算不會產(chǎn)生任何影響。③

每一次上商都是把商寫入商值寄存器的最低位，然后部分余數(shù)和商一起左移，騰空商寄存器的最低位以備上新的商。④部分余數(shù)隨商一起左移了n位；所以正確的余數(shù)應(yīng)為2-n·Rn

?！?/p>

采用部分余數(shù)減去除數(shù)的方法比較兩者的大小，當(dāng)減法結(jié)果為負，即上商0時，破壞了部分余數(shù)?？刹扇煞N措施。2.恢復(fù)余數(shù)的除法▲兩個正的定點小數(shù)X和Y，X=0.x1x2xn，Y=0.y1y2yn，求解X/Y的商和余數(shù)的方法：

第1步：R1=X﹣Y若R1<0，則上商q0=0，同時恢復(fù)余數(shù)：R1=R1+Y。若R1>=0，則上商q0=1。q0位不是符號位，而是兩定點小數(shù)相除時的整數(shù)部分；q0=1時，當(dāng)作溢出處理。第2步：若已求得第i次的部分余數(shù)為Ri，則第i+1次的部分余數(shù)為：Ri+1=2Ri﹣Y若Ri+1<0，上商qi=0，同時恢復(fù)余數(shù)：Ri+1=Ri+1+Y。若Ri+1>=0，則上商qi=1。第3步：不斷循環(huán)執(zhí)行第2步，直到求得所需位數(shù)的商為止。例1：已知[X]原=0.1011,[Y]原=1.1101；求[X/Y]原。計算分為符號位和數(shù)值位兩部分[X/Y]原商的符號位：01=1[X/Y]原商的數(shù)值位計算采用恢復(fù)余數(shù)法。運算中的減法操作用補碼加法實現(xiàn)。[-|Y|]補=10011?！謩e標識為X和Y運算過程：部分余數(shù)商說明

0010110000開始R0=XR1=X-Y11111000000R1<0，則q0=0恢復(fù)余數(shù)：R1=R1+Y001011得R101011000002R1（部分余數(shù)和商同時左移）-Y00100100001R2>0，則q1=101001000012R2(左移)-Y00010100011R3>0，則q2=100010100011R3>0，則q2=100101000112R3(左移)-Y11110100110R4<0，則q3=0恢復(fù)余數(shù)：R4=R4+Y00101000110得R401010001102R4(左移)-Y00011101101R5>0，則q4=1可見商的數(shù)值位為1101[X/Y]原=1.

1101，余數(shù)為0.0111*2-4。開始R被除數(shù),Q=0Y除數(shù)CnnR(R)-(Y)(R)<0置溢出標志(或上商“1”)R,Q同時左移一位R(R)-(Y)qn0R(R)+(Y)(R)<0qn0R(R)+(Y)qn1Cn(Cn)-1(Cn)=0結(jié)束是否是是否否圖2.30恢復(fù)余數(shù)除法的運算流程圖3.不恢復(fù)余數(shù)的除法

(加減交替法)▲當(dāng)?shù)趇次的部分余數(shù)為負時，跳過恢復(fù)余數(shù)的步驟，直接求第i+1次的部分余數(shù)?！鴮蓚€正的定點小數(shù)X和Y采用不恢復(fù)余數(shù)除法的基本步驟：第1步：R1=X-Y

若R1<0，則上商q0=0；

若R1>=0，則上商q0=1；q0代表兩定點小數(shù)相除時的整數(shù)部分，當(dāng)q0=1時，將當(dāng)作溢出處理。第2步：若已求得部分余數(shù)Ri，則第i+1次的部分余數(shù)為：若Ri<0，上商qi-1=0，Ri+1=2Ri+Y，上一步中多減去的Y在這一步中彌補回來(+2Y)；若Ri>=0，上商qi-1=1，Ri+1=2Ri-Y，保持原有的除法過程；第3步：不斷循環(huán)執(zhí)行第2步，直到求得所需位數(shù)的商為止。結(jié)束時，若余數(shù)為負值，要執(zhí)行恢復(fù)余數(shù)的操作

Rn=Rn+Y。圖2.31實現(xiàn)兩正定點數(shù)相除的不恢復(fù)余數(shù)除法運算流程[X/Y]原商的數(shù)值位的計算采用不恢復(fù)余數(shù)的除法參加運算的數(shù)據(jù)是[|X|]補和[|Y|]補兩數(shù)，分別標識為X和Y；[-|Y|]補=10011。例1：已知[X]原=0.1011,[Y]原=1.1101

；計算[X/Y]原。計算分為符號位和數(shù)值位兩部分[X/Y]原商的符號位：01=1運算過程如下：

部分余數(shù)商說明

0010110000開始R0=XR1=X-Y11111000000R1<0，則q0=011110000002R1（部分余數(shù)和商同時左移）+Y00100100001R2>0，則q1=101001000012R2（左移）-Y00010100011R3>0，則q2=100010100011R3>0，則q2=100101000112R3（左移）-Y11110100110R4<0，則q3=011101001102R4

（左移）+Y00011101101R5>0，則q4=1商的數(shù)值位為1101[X/Y]原=1.1101；R5與X同號，余數(shù)為0.0111*2-4。n位數(shù)的不恢復(fù)余數(shù)除法需要n次加法運算；對恢復(fù)余數(shù)除法來說，平均需要3n/2次加法運算。4.原碼除法器的組成2.8.2補碼除法運算(1)在補碼除法中，符號位與數(shù)值位同等參與整個除法運算過程，商的符號位在除法運算中產(chǎn)生。(2)部分余數(shù)和除數(shù)都用帶符號位的補碼表示時，部分余數(shù)與除數(shù)是否夠除，不能用兩數(shù)直接相減的方法來判斷。部分余數(shù)[R]補除數(shù)[Y]補[R]補–[Y]補[R]補+[Y]補0

10

1000

11011夠減(商1)不夠減(商0)夠減(商0)夠減(商1)不夠減(商1)不夠減(商1)不夠減(商0)夠減(商0)表2.13兩補碼數(shù)是否夠減的判別方法表中的0或1表示相應(yīng)數(shù)的符號值；補碼除法的結(jié)果是連同符號位在內(nèi)的補碼形式的商。商為負數(shù)補碼在這里需做除法溢出判斷（定點小數(shù)）：若[X]

補與[Y]補同號且上商q0=1，則溢出。第1步：若[X]補與[Y]補同號：

R1=[X]補–[Y]補若[X]補與[Y]補異號：R1=[X]補+[Y]補若R1與[Y]補同號：上商q0=1若R1與[Y]補異號：上商q0=0若[X]

補與[Y]補異號且上商q0=0，則溢出?！舯怀龜?shù)為[X]補，除數(shù)為[Y]補，則[X/Y]

補的補碼除法運算規(guī)則：第2步：若已求出部分余數(shù)Ri，Ri與[Y]補同號：Ri+1=2Ri–[Y]補Ri與[Y]補異號：Ri+1=2Ri+[Y]補同樣，若Ri+1與[Y]補同號：上商qi=1第3步：重復(fù)執(zhí)行第2步，直到求得足夠位數(shù)的商為止。商為負數(shù)時，商的末位加1。若Ri+1與[Y]補異號：上商qi=0例3：已知[X]

補=1.0111,[Y]

補=0.1101

。▲[X/Y]

補的計算過程如下：部分余數(shù)商說明1101110000開始R0=[X]R1=[X]+[Y]00010000001R1與[Y]同號，則q0=100100000012R1（部分余數(shù)和商同時左移）+[-Y]11101100010R2與[Y]異號，則q1=011011000102R2+[Y]00001100101R3與[Y]同號，則q2=100001100101R3與[Y]同號，則q2=100011001012R3+[-Y]11100101010R4與[Y]異號，則q3=011001010102R4+[Y]11111110100R5與[Y]異號，則q4=0

+1商為負數(shù)，末位加1 10101[X/Y]補=1.0101；余數(shù)的補碼為1.1111×2-4。[X/Y]真=-0.1011；余數(shù)的真值為-0.0001×2-4。2.8.3陣列除法器▲圖2.32是一個組合邏輯單元；包含借位入和借位出的全減器?！粲媒M合邏輯線路來完成除法運算X：被減數(shù)二進制代碼Y：減數(shù)二進制代碼t：低位傳送來的借位入信號u:本單元送往高位的借位出信號；u=XY+Xt+Yta:控制信號；這個控制信號一方面決定本單元R的生成值，另一方面也傳送給低位。R:本單