計算機算法和算法邏輯實現(xiàn)-課件

計算機組成原理第六-八講計算機算法和算法邏輯實現(xiàn)

計算機組成原理第六-八講計算機算法和算法邏輯實現(xiàn)1、定點數(shù)加減法運算及電路實現(xiàn) 補碼的加減法運算，全加器，溢出，快速加法運算（進位鏈），74181ALU2、定點數(shù)乘除運算和電路實現(xiàn) 原碼、補碼，布斯算法，原碼恢復(fù)余數(shù)、不恢復(fù)余數(shù)3、快速乘除法運算技術(shù)和電路實現(xiàn) 布斯高基乘法，陣列乘法器，陣列除法器4、浮點數(shù)四則運算以及實現(xiàn) 加減乘除本講安排1、定點數(shù)加減法運算及電路實現(xiàn)本講安排本講將解決的主要問題掌握計算機算法。加減乘除運算方法和運算器的構(gòu)成，原碼和補碼的加減乘除四則運算，浮點數(shù)的四則運算。

本講將解決的主要問題掌握計算機算法。補碼加、減法溢出概念與檢測方法基本的二進制加法/減法器十進制加法器補碼加、減法溢出概念與檢測方法基本的二進制加法/減法器十進制加法規(guī)則：先判符號位，若相同，絕對值相加，結(jié)果符號不變;若不同，則作減法，|大|-|小|，結(jié)果符號與|大|相同。減法規(guī)則：兩個原碼表示的數(shù)相減，首先將減數(shù)符號取反，然后將被減數(shù)與符號取反后的減數(shù)按原碼加法進行運算。補碼加法1.原碼加/減法運算加法規(guī)則：補碼加法1.原碼加/減法運算補碼加法的公式:[x]補＋[y]補＝[x＋y]補(mod2)

在模2意義下,任意兩數(shù)的補碼之和等于該兩數(shù)之和的補碼。這是補碼加法的理論基礎(chǔ)。2.補碼加法運算特點：不需要事先判斷符號，符號位與碼值位一起參加運算。符號位相加后若有進位，則舍去該進位數(shù)字。補碼加法的公式:[x]補＋[y]補＝[x＋y]補

假設(shè)采用定點小數(shù)表示,因此證明的先決條件是:

︱x︱﹤1,︱y︱﹤1,︱x＋y︱﹤1。(1)x﹥0,y﹥0,則x＋y﹥0。

相加兩數(shù)都是正數(shù),故其和也一定是正數(shù)。正數(shù)的補碼和原碼是一樣的,可得：

[x]補＋[y]補＝x＋y＝[x＋y]補

(mod2)公式證明:假設(shè)采用定點小數(shù)表示,因此證明的先決條件是:(1)(2)x﹥0,y﹤0,則x＋y>0或x＋y<0。相加的兩數(shù)一個為正,一個為負,因此相加結(jié)果有正、負兩種可能。根據(jù)補碼定義，

∵[x]補＝x,

[y]補＝2＋y

∴[x]補＋[y]補＝x＋2＋y＝2＋(x＋y)

當x+y>0時,2+(x+y)>2,進位2必丟失,又因(x+y)>0，故[x]補＋[y]補＝x＋y＝[x＋y]補

(mod2)

當x＋y<0時,2＋(x＋y)<2,又因(x+y)<0，故

[x]補＋[y]補＝2＋(x＋y)＝[x＋y]補

(mod2)(2)x﹥0,y﹤0,則x＋y>0(3)x<0,y>0,則x＋y>0或x＋y<0。同(2),把x和y的位置對調(diào)即可。(4)x<0,y<0,則x＋y<0。相加兩數(shù)都是負數(shù),則其和也一定是負數(shù)?！遊x]補＝2＋x,

[y]補＝2＋y∴[x]補＋[y]補＝2＋x＋2＋y＝2＋(2＋x＋y)

因為|x＋y|<1,1<(2＋x＋y)<2,2＋(2＋x＋y)進位2

必丟失，又因x+y<0

故[x]補＋[y]補＝2＋(x＋y)＝[x＋y]補

(mod2)(3)x<0,y>0,則x＋y>0或x＋

至此證明了在模2意義下，任意兩數(shù)的補碼之和等于該兩數(shù)之和的補碼。

其結(jié)論也適用于定點整數(shù)。補碼加法的特點：

（1）符號位要作為數(shù)的一部分一起參加運算；（2）在模2的意義下相加，即大于2的進位要丟掉。結(jié)論：至此證明了在模2意義下，任意兩數(shù)的補碼之和等于該兩數(shù)之例:

x＝0.1001,y＝0.0101,求x＋y。解:

[x]補＝0.1001,[y]補＝0.0101[x]補

0.1001

＋[y]補

0.0101

[x＋y]補

0.1110

所以x＋y＝＋0.1110例:

x＝＋0.1011,y＝－0.0101,求x＋y。所以x＋y＝0.0110解:

[x]補＝0.1011,

[y]補＝1.1011[x]補

0.1011＋[y]補

1.1011

[x＋y]補

10.0110

例:x＝0.1001,y＝0.0101,求x＋補碼減法減法運算要設(shè)法化為加法完成補碼減法運算的公式：

[x－y]補＝[x]補－[y]補＝[x]補＋[－y]補公式證明：只要證明[–y]補＝–[y]補,上式即得證?！遊x＋y]補＝[x]補＋[y]補

(mod2)

令y=－x∴[0]補＝[x]補+[－

x]補

故[－x]補＝－[x]補(mod2)

證明：補碼減法減法運算要設(shè)法化為加法完成例:

x＝＋0.1101,y＝＋0.0110,求x－y。解:

[x]補＝0.1101

[y]補＝0.0110,

[－y]補＝1.1010[x]補

0.1101

＋[－y]補

1.1010

[x－y]補

10.0111

x－y＝＋0.0111解：[x]補=1.0011[y]補=1.1010[-y]補=0.0110

[x]補

1.0011+[-y]補

0.0110[x-y]補

1.1001

例：x=-0.1101，y=-0.0110，求x-y=?∴x--y=-0.0111例:x＝＋0.1101,y＝＋0.0110,求

溢出及與檢測方法

在定點小數(shù)機器中,數(shù)的表示范圍為|ｘ|<1。在運算過程中如出現(xiàn)大于1的現(xiàn)象,稱為“溢出”。機器定點小數(shù)表示上溢下溢1.概念溢出及與檢測方法在定點小數(shù)機器中,數(shù)的表示范圍為|ｘ

解：

[x]補=0.1011

[y]補=0.1001

[x]補

0.1011

+

[y]補

0.1001

[x+y]補

1.0100

兩個正數(shù)相加的結(jié)果成為負數(shù)，這顯然是錯誤的。例:x=+0.1011,y=+0.1001,求x+y。

例:x=-0.1101,y=-0.1011,求x+y。解：

[x]補=1.0011

[y]補=1.0101

[x]補

1.0011

+

[y]補

1.0101

[x+y]補

0.1000

兩個負數(shù)相加的結(jié)果成為正數(shù)，這同樣是錯誤的。

解：

[x]補=0.1011

發(fā)生錯誤的原因，是因為運算結(jié)果產(chǎn)生了溢出。兩個正數(shù)相加:結(jié)果大于機器所能表示的最大正數(shù)，稱為上溢；兩個負數(shù)相加：結(jié)果小于機器所能表示的最小負數(shù)，稱為下溢。機器定點小數(shù)表示上溢下溢[分析]：發(fā)生錯誤的原因，是因為運算結(jié)果產(chǎn)生了溢出。機器定2.溢出的檢測方法

[x]補

0.1011

+

[y]補

0.1001

[x+y]補

1.0100

[x]補

1.0011

+

[y]補

1.0101

[x+y]補

0.1000溢出邏輯表達式為：

V＝S1S2Sc+S1S2Sc(1)單符號位法FAVz0y0x0判斷電路判斷電路2.溢出的檢測方法

[x]補

0.1

一個符號位只能表示正、負兩種情況，當產(chǎn)生溢出時，符號位的含義就會發(fā)生混亂。如果將符號位擴充為兩位(Sf1、Sf2)，其所能表示的信息量將隨之擴大，既能判別是否溢出，又能指出結(jié)果的符號。

(2)雙符號位法雙符號位法也稱為“變形補碼”或“模4補碼”。變形補碼定義：[x]補=x0

x<24+x-2x<0

（mod4)一個符號位只能表示正、負兩種情況，當產(chǎn)生溢出時，

?

任何小于1的正數(shù)：兩個符號位都是“0”，即00.x1x2...xn;

?

任何大于-1的負數(shù)：兩個符號位都是“1”，即11.x1x2…xn

兩數(shù)變形補碼之和等于兩數(shù)和的變形補碼，要求：

?

兩個符號位都看做數(shù)碼一樣參加運算；

?

兩數(shù)進行以4為模的加法，即最高符號位上產(chǎn)生的進位要丟掉模4補碼加法公式：

[x]補+[y]補=[x+y]補

（mod4)采用變形補碼后數(shù)的表示：?任何小于1的正數(shù)：兩個符號位都是“0”，即00.Sf1Sf2

＝00結(jié)果為正數(shù)，無溢出

01結(jié)果正溢

10結(jié)果負溢

11結(jié)果為負數(shù)，無溢出即：結(jié)果的兩個符號位的代碼不一致時，表示溢出;

兩個符號位的代碼一致時，表示沒有溢出。

不管溢出與否，最高符號位永遠表示結(jié)果的正確符號。溢出邏輯表達式為：

V＝Sf1⊕Sf2

中Sf1和Sf2分別為最高符號位和第二符號位，此邏輯表達式可用異或門實現(xiàn)。雙符號位的含義如下：Sf1Sf2＝00結(jié)果為正

解：

[x]補=00.1100

[y]補=00.1000

[x]補

00.1100

+

[y]補

00.1000

01.0100

符號位出現(xiàn)“01”，表示已溢出，正溢。即結(jié)果大于+1例

x=+0.1100,y=+0.1000,求x+y。

解：

[x]補=11.0100

[y]補=11.1000

[x]補

11.0100

+

[y]補

11.1000

10.1100符號位出現(xiàn)“10”，表示已溢出，負溢出。即結(jié)果小于-1例

x=-0.1100,y=-0.1000,求x+y。

解：

[x]補=00.1100

從上面例中看到：當最高有效位有進位而符號位無進位時,產(chǎn)生上溢；當最高有效位無進位而符號位有進位時,產(chǎn)生下溢。（簡單地說是正數(shù)相加為負數(shù)或負數(shù)相加為正數(shù)則產(chǎn)生溢出）故溢出邏輯表達式為：V＝Cf⊕Co

其中Cf為符號位產(chǎn)生的進位,Co為最高有效位產(chǎn)生的進位。此邏輯表達式也可用異或門實現(xiàn)。(3)利用進位值的判別法[x]補

00.1100+[y]補

00.1000

01.1000[x]補

11.0100+[y]補

11.1000

10.1100從上面例中看到：(3)利用進位值的判別法[x]補

0FAFAz1z0Vc1c0y1x1y0x0FAFAVz1c0c1z0x1y1y0x0V＝C1⊕Co

V＝Sf1⊕Sf2判斷電路FAFAz1z0Vc1c0y1x1y0x0FAFAVz1c0基本的二進制加法/減法器加法運算：Ai+Bi+Ci=Si(Ci+1)加數(shù)進位輸入和進位輸出一位全加器真值表輸入輸出AiBiCiSiCi＋10000000110010100110110010101011100111111邏輯方程Si＝Ai⊕Bi⊕CiCi＋1＝AiBi＋BiCi＋CiAi1.一位全加器基本的二進制加法/減法器加法運算：Ai+Bi邏輯方程Si＝Ai⊕Bi⊕CiCi＋1=AiBi＋BiCi＋CiAiCi=AiBi+(AiBi)Ci-1邏輯電路（一位全加器）常用的全加器邏輯電路FACi+1CiSiAiBi邏輯符號邏輯方程Si＝Ai⊕Bi⊕CiCi＋1=AiBi＋BiCi2.n位的行波進位加減器n個1位的全加器(FA)可級聯(lián)成一個n位的行波進位加減器。2.n位的行波進位加減器n個1位的全加器(FA)T被定義為相應(yīng)于單級邏輯電路的單位門延遲。

T通常采用一個“與非”門或一個“或非”門的時間延遲來作為度量單位。3TXNOR異或非3TXOT異或2TOR或2TAND與TNOT非TNOR或非TNAND與非時間延遲邏輯符號（正邏輯）門的功能門的名稱典型門電路的邏輯符號和延遲時間接線邏輯(與或非)AOIT+TRC3.n位的行波進位加法器的問題時間延遲T被定義為相應(yīng)于單級邏輯電路的單位門延遲。3TXN(1)對一位全加器(FA)來說，Si的時間延遲為6T(每級異或門延遲3T)；Ci＋1的時間延遲為5T。3T3TTT(1)對一位全加器(FA)來說，Si的時間延遲為6T(每級3(2)n位行波進位加法器的延遲時間ta為:

?9T為最低位上的兩極“異或”門再加上溢出“異或”門的總時間；

?2T為每級進位鏈的延遲時間。ta＝n·2T＋9T＝(2n＋9)T考慮溢出檢測時，有：當不考慮溢出檢測時，有：ta＝(n-1)·2T＋9T

ta為在加法器的輸入端輸入加數(shù)和被加數(shù)后,在最壞的情況下加法器輸出端得到穩(wěn)定的求和輸出所需要的最長時間。

ta越小越好。(2)n位行波進位加法器的延遲時間ta為:?9T為最缺點：(1)串行進位,它的運算時間長；(2)只能完成加法和減法兩種操作而不能完成邏輯操作。多功能算術(shù)/邏輯運算單元(ALU):

不僅具有多種算術(shù)運算和邏輯運算的功能；而且具有先行進位邏輯。從而能實現(xiàn)高速運算。由一位全加器(FA)構(gòu)成的行波進位加法器:缺點：由一位全加器(FA)構(gòu)成的行波進位加法器:1.基本思想Si＝Ai⊕Bi⊕Ci一位全加器(FA)的邏輯表達式為:將Ai和Bi先組合成由控制參數(shù)S0,S1,S2,S3控制的組合函數(shù)Xi和Yi；(2)然后再將Xi,Yi和下一位進位數(shù)通過全加器進行全加。這樣,不同的控制參數(shù)可以得到不同的組合函數(shù),因而能夠?qū)崿F(xiàn)多種算術(shù)運算和邏輯運算。解決方案：

多功能算術(shù)/邏輯運算單元(ALU)將全加器的功能擴展以完成多種算術(shù)邏輯運算。Ci＋1=AiBi·(Ci·(Ai⊕Bi))=AiBi＋BiCi＋CiAi1.基本思想Si＝Ai⊕Bi⊕Ci一位全加器(FA)的邏輯表S0S1S2S3X0Y0

參數(shù)S0,S1,S2,S3

分別控制輸入Ai

和Bi

,產(chǎn)生Y和X的函數(shù)。其中：Yi是受S0,S1控制的Ai和Bi的組合函數(shù)；Xi是受S2

,S3控制的Ai和Bi組合函數(shù)。

函數(shù)關(guān)系如表所示。Xi＝S2S3＋S2S3(Ai＋Bi)＋S2S3(Ai＋Bi)＋S2S3Ai

Yi＝S0S1Ai＋S0S1AiBi＋S0S1AiBi?

核心部分是由兩個半加器組成的全加器。?

由M控制第二級半加器選擇邏輯運算或算術(shù)運算（所需的低位進位Cn

）。一位ALU基本邏輯電路S0S1S2S3X0Y0參數(shù)S0,S1,S2,S3S0S1

Yi

S2S3

Xi

0

0

0

1

1

0

1

1Ai

AiBi

AiBi

00

0

0

1

1

0

1

11

Ai＋Bi

Ai＋Bi

Ai

進一步化簡:Xi=S3AiBi+S2AiBiYi=Ai+S0Bi+S1BiAi+S0Bi+S1BiS3AiBi+S2AiBiXiYi==Yi

Fi＝Y(jié)i⊕Xi⊕Cn+iCn＋i＋1＝Y(jié)i＋XiCn＋iS0S1YiS2S3Xi00

01

10

綜上所述，ALU的一位邏輯表達式為：Xi=S3AiBi+S2AiBiYi=Ai+S0Bi+S1Bi

Fi＝Y(jié)i⊕Xi⊕Cn+iCn＋i＋1＝Y(jié)i＋XiCn＋i綜上所述，ALU的一位邏輯表達式為：Xi=S3AiBi4位之間采用先行進位（并行進位）公式。根據(jù)Cn＋i＋1＝Y(jié)i＋XiCn＋i，每一位的進位公式可遞推如下：

?

第0位向第1位的進位公式為:

Cn＋1＝Y(jié)0＋X0Cn

(其中Cn是向第0位（末位）的進位)

?

第1位向第2位的進位公式為:

Cn＋2＝Y(jié)1＋X1Cn＋1＝Y(jié)1＋Y0X1＋X0X1Cn

?

第2位向第3位的進位公式為:

Cn＋3＝Y(jié)2＋X2Cn＋2＝Y(jié)2＋Y1X1＋Y0X1X2＋X0X1X2Cn?

第3位的進位輸出（即整個4位運算進位輸出）公式為:

Cn＋4=Y3+X3Cn＋3=Y3+Y2X3+Y1X2X3+Y0X1X2X3+X0X1X2X3Cn4位ALU的進位關(guān)系及邏輯電路4位之間采用先行進位（并行進位）公式。4位ALU的進位關(guān)系Cn＋1＝Y(jié)0＋X0CnCn＋2＝Y(jié)1＋X1Cn＋1＝Y(jié)1＋Y0X1＋X0X1Cn

Cn＋3＝Y(jié)2＋X2Cn＋2＝Y(jié)2＋Y1X1＋Y0X1X2＋X0X1X2CnCn＋4=Y3+X3Cn＋3=Y3+Y2X3+Y1X2X3+Y0X1X2X3+X0X1X2X3Cn

Cn+4是最后進位輸出。邏輯表達式表明,這是一個先行進位邏輯。換句話說,第0位的進位輸入Cn可以直接傳送到最高位上去,因而可以實現(xiàn)高速運算。下圖為用上述原始推導(dǎo)公式實現(xiàn)的4位算術(shù)/邏輯運算單元(ALU)

——74181ALU從進位關(guān)系上看Cn＋1＝Y(jié)0＋X0Cn從進位關(guān)系上看X0Y0X1Y1X2Y2X3Y3

正邏輯表示的74181X0Y0X1Y1X2Y2X3

第3位的進位輸出（即整個4位運算進位輸出）公式為:

Cn＋4=Y3+X3Cn＋3=Y3+Y2X3+Y1X2X3+Y0X1X2X3+X0X1X2X3Cn設(shè)G＝Y(jié)3＋Y2X3＋Y1X2X3＋Y0X1X2X3

P＝X0X1X2X3

則

Cn＋4＝G＋PCn

其中G稱為進位發(fā)生輸出,P稱為進位傳送輸出。在電路中多加這兩個進位輸出的目的,是為了便于實現(xiàn)多片（組）ALU之間的先行進位。P和G的含義第3位的進位輸出（即整個4位運算進位輸出）公式為:P和G的負邏輯表示的74181X0Y0X1Y1X2Y2X3Y3負邏輯表示的74181X0Y0X1Y1X2

2.算術(shù)邏輯運算的實現(xiàn)上圖中控制端Ｍ用來控制ALU進行算術(shù)運算還是進行邏輯運算:Ｍ＝0時：

Ｍ對進位信號沒有任何影響。此時Fi

不僅與本位的被操作數(shù)Yi和操作數(shù)Xi

有關(guān),而且與向本位的進位值Cn+i

有關(guān),因此Ｍ＝0時,進行算術(shù)操作。

Ｍ＝1時：

封鎖了各位的進位輸出,即Cn+i

＝0,因此各位的運算結(jié)果Fi

僅與Yi

和Xi

有關(guān),故Ｍ＝1時,進行邏輯操作。2.算術(shù)邏輯運算的實現(xiàn)上圖中控制端Ｍ用來控制ALU進行算術(shù)下圖為工作于負邏輯和正邏輯操作方式的74181ALU方框圖。兩種操作是等效的。?

對正邏輯操作數(shù)來說：

算術(shù)運算稱高電平操作；邏輯運算稱正邏輯操作

(即高電平為“1”,低電平為“0”)。?

對于負邏輯操作數(shù)來說:

正好相反。下圖為工作于負邏輯和正邏輯操作方式的74181ALU方框圖。AA+BA+B減1A加AB（A+B）加ABA減B減1AB減1A加ABA加B（A+B）加ABAB減1A加A*（A+B）加A（A+B）加AA減1AA+BAB邏輯0ABBABABA+BABBAB邏輯1A+BA+BA

A減1AB減1

AB減1

減1A加（A+B）AB加（A+B）A減B減1A+BA加（A+B）A加BAB加（A+B）A+BA加A*AB加AAB加AA

AAB

A+B

邏輯1

A+BB

ABA+B

ABAB

BA+B

邏輯0AB

ABALLLLLLLHLLHLLLHHLHLLLHLHLHHLLHHHHLLLHLLHHLHLHLHHHHLLHHLHHHHLHHHH算術(shù)運算M=LCn=H邏輯M=H算術(shù)運算M=LCn=L邏輯M=H正邏輯輸入與輸出負邏輯輸入與輸出工作方式選擇輸入S3S2S1S0

AAA減1AL(1)H＝高電平,L＝低電平；(2)*表示每一位均移到下一個更高位,即A*＝2A。(3)

算術(shù)運算操作是用補碼表示法來表示的，其中：

“加”是指算術(shù)加，運算時要考慮進位；符號“＋”是指“邏輯加”。(4)

減法是用補碼方法進行的，其中數(shù)的反碼是內(nèi)部產(chǎn)生的,而結(jié)果輸出“A減B減1”，因此做減法時需在最末位產(chǎn)生一個強迫進位(加1),以便產(chǎn)生“A減B”的結(jié)果。(5)

“A＝B”輸出端可指示兩個數(shù)是否相等；(1)H＝高電平,L＝低電平；3.并行加法器的進位邏輯74181ALU為4位并行加法器，組成16位的并行加法器——怎么辦？

4片(組)74181連接——怎樣連？

?

組與組之間串行連接

?

組與組之間并行連接3.并行加法器的進位邏輯74181ALU為4位并行加法器組間串行進位C4＝G0＋P0C0C8＝G1＋P1C4C12＝G2＋P2C8C16＝G3＋P3C12進位關(guān)系Cn＋1＝Y(jié)0＋X0CnCn＋2＝Y(jié)1＋X1Cn＋1＝Y(jié)1＋Y0X1＋X0X1Cn

Cn＋3＝Y(jié)2＋X2Cn＋2＝Y(jié)2＋Y1X1＋Y0X1X2＋X0X1X2CnCn＋4=Y3+X3Cn＋3=Y3+Y2X3+Y1X2X3+Y0X1X2X3+X0X1X2X3Cn組內(nèi)組間X0Y0X1Y1X2Y2X3Y3X0Y0X1Y1X2Y2X3Y3C4C8C4C00011G＝Y(jié)3＋Y2X3＋Y1X2X3＋Y0X1X2X3

P＝X0X1X2X3組間串行進位C4＝G0＋P0C0C8＝G1＋P1C4C1第1組4-1位并行進位X3Y3X2Y1X1Y1X0Y0C4C3C2C1第2組8-5位并行進位X7Y7X6Y6X5Y5X4Y4C8C7C6C5第3組12-9位并行進位X11Y11X10Y10X9Y9X8Y8C12C11C10C9第4組16-13位并行進位X15Y15X14Y14X13Y13X12Y12C16C15C14C13進位傳遞時間C16C12C8C4C01.534.56tyC1CC16C12C8C4C01.534.57tyC1C5.589.5第1組X3Y3X2Y1X1Y1X0Y0C4C3C2C1第2組(2)組間并行進位——兩級先行進位的ALU由串行進位關(guān)系C8=G1＋P1C4=G1+P1(G0＋P0C0)=G1+G0P1+P0P1C0得：C4＝G0＋P0C0C8＝G1＋P1C4C12＝G2＋P2C8C16＝G3＋P3C12C4=G0＋P0C0C12=G2＋P2C8=G2+P2(G1+G0P1+P0P1Cn)=G2+G1P2+G0P1P2+P0P1P2C0C16=G3+P3C12=G3+G2P3+G1P1P2+G0P1P2P3+P0P1P2P3C0

=G*＋P*C0其中:P*＝P0P1P2P3G*＝G3＋G2P3＋G1P1P2＋G0P1P2P3根據(jù)上述公式實現(xiàn)邏輯電路:(2)組間并行進位——兩級先行進位的ALU由串行進位關(guān)系C8

X0Y0X1Y1X2Y2X3Y3

C12C8C4

X0Y0X1Y1X2Y2X3Y3

X0Y0X1Y1X2Y2X3Y3

0X0Y0X1Y1X2Y2X3Y3C12C進位的傳遞時間C16C12C8C4C01.534.56tyC1CC3第1小組X3~0Y3~0C3C2C1P0G0第2小組X7~4Y7~4C7C6C5P1G1第3小組X11~8Y11~8C11C10C9P2G2第4小組X15~12Y15~12C15C14C3P3G3第二級進位鏈C0C4C8C12C16進位的傳遞時間C16C12C8C4C01.534.56由上圖可見，?

當Xi和Yi形成以后，經(jīng)過1.5ty，產(chǎn)生第一小組的C1，C2，C3

和所有的Gi、Pi；?

經(jīng)過1.5ty，由第二級進位鏈產(chǎn)生C4，C8，C12，C16；?

再經(jīng)1.5ty后，產(chǎn)生第2，3，4小組內(nèi)的C5C6C7，

C9C10C11，C13C14C15。整個進位傳遞時間為4.5ty。由上圖可見，?經(jīng)過1.5ty，由第二級進位鏈產(chǎn)生C4，C84.先行進位部件（CLA）——7418274182是一個并行進位部件，其內(nèi)部結(jié)構(gòu)圖如下：其中G*稱為成組進位發(fā)生輸出，P*稱為成組進位傳送輸出。4.先行進位部件（CLA）——7418274182是一Cn+ｘ=G0+P0CnCn+ｙ=G1+P1Cn+ｘ=G1+G0P1+P0P1CnCn+ｚ=G2+P2Cn+ｙ=G2+G1P2+G0P1P2+P0P1P2CnCn＋4=G3+P3Cn+ｚ=G3+G2P3+G1P1P2+G0P1P2P3+P0P1P2P3Cn

=G*＋P*Cn其中:P*＝P0P1P2P3

G*＝G3＋G2P3＋G1P1P2＋G0P1P2P3先行進位部件74182CLA所提供的進位邏輯關(guān)系如下：Cn+ｘ=G0+P0Cn先行進位部件74182CLA所提供74181ALU設(shè)置了P和G兩個本組先行進位輸出端。如果將四片74181的P,G輸出端送入到74182先行進位部件（CLA）,又可實現(xiàn)第二級的先行進位,即組與組之間的先行進位。例：16位字長ALU的構(gòu)成G*P*74181ALU設(shè)置了P和G兩個本組先行進位輸出端。例：?C3、C7、C11是由74182同時形成的；?

其不同點是74182還提供大組間的進位函數(shù)G*

和大組傳遞條件P*，以便在位數(shù)更長時組成下一級先行進位鏈。由圖可知：?C3、C7、C11是由74182同時形成的；由圖可知：

用若干個74181ALU位片,與配套的74182先行進位部件CLA在一起,可構(gòu)成一個全字長的ALU。例：全字長的ALU的構(gòu)成用兩個16位全先行進位部件級聯(lián)組成的32位ALU邏輯方框圖。用若干個74181ALU位片,與配套的74182十進制加法器

十進制加法器可由BCD碼(二－十進制碼)來設(shè)計,它可以在二進制加法器的基礎(chǔ)上加上適當?shù)摹靶Ｕ边壿媮韺崿F(xiàn)。70111+6+0110131101

（=D）

+011010011（=13）30011+5+010181000（=8）X+Y+C<10不調(diào)整X+Y+C>10調(diào)整十進制加法器十進制加法器可由BCD碼(二－十進制碼)故：

1.和為10～15時，加6校正；

2.和數(shù)有進位時，加6校正。和數(shù)(4位)有進位調(diào)整2800101000+9＋000010013700110001（=31）

＋0000011000110111(=37)故：和數(shù)(4位)2800101001.一位BCD碼行波式進位加法器一般結(jié)構(gòu)：0111010101111001101111011111.一位BCD碼行波式進位加法器一般結(jié)構(gòu)：01110102.n位BCD碼行波式進位加法器一般結(jié)構(gòu)：2.n位BCD碼行波式進位加法器一般結(jié)構(gòu)：原碼乘法補碼乘法定點乘法運算原碼乘法補碼乘法定點乘法運算

設(shè)n位被乘數(shù)和乘數(shù)用定點小數(shù)表示

被乘數(shù)

[x]原＝xf.xn－1…x1x0

乘數(shù)

[y]原＝y(tǒng)f.yn－1…y1y0

則乘積

[z]原＝(xf⊕yf)＋(0.xn－1…x1x0)(0.yn－1…y1y0)

式中，xf為被乘數(shù)符號，

yf為乘數(shù)符號。原碼一位乘法1.乘法的手工算法設(shè)n位被乘數(shù)和乘數(shù)用定點小數(shù)表示原碼一位乘法1.(2)手工運算過程：設(shè)ｘ＝0.1101,ｙ＝0.10110.1101(x)0.1011(y)110111010000+11010.10001111(z)(1)乘積符號的運算規(guī)則：同號相乘為正，異號相乘為負。(2)手工運算過程：設(shè)ｘ＝0.1101,ｙ＝0.1011(1)機器通常只有n位長,兩個n位數(shù)相乘,乘積可能為2n位。(2)只有兩個操作數(shù)相加的加法器難以勝任將n位積一次相加起來的運算。機器與人們習慣的算法不同之處：0.1101x×0.1011y0.00001101x共4次右移

0.0001101x共3次右移

0.000000x共2次右移

+0.01101x共1次右移

0.10001111

2.適合定點機的形式(1)機器通常只有n位長,兩個n位數(shù)相乘,乘積可能

為了適合兩個操作數(shù)相加的加法器，將xy改寫成下面形式：xy=x(0.1011)=0.1x+0.00x+0.001x+0.0001x=0.1{x+0.1[0+0.1(x+0.1x)]}=2-1{x+2-1[0+2-1(x+2-1x)]}

根據(jù)此式，按式中括號可表達的層次，從內(nèi)向外逐次進行移位累加。為了適合兩個操作數(shù)相加的加法器，將xy改寫成下面形式一般而言，設(shè)被乘數(shù)x,乘數(shù)y都是小于1的n位定點正數(shù)：

x=0.x1x2......xn<1y=0.y1y2......yn<1其乘積為：x·y=x(0.y1y2......yn)=x(y12-1+y22-2+…+yn2-n)=2-1(y1x+2-1(y2x+2-1(…+2-1(yn-1x+2-1(ynx+0))…)))一般而言，設(shè)被乘數(shù)x,乘數(shù)y都是小于1的n位定點正數(shù)：其乘積形成遞推公式

令zi表示第i次部分積，則根據(jù)從內(nèi)到外的原則有：

z0=0,z1=2-1(ynx+z0)z2=2-1(yn-1x+z1)┊zi=2-1(yn-i+1x+zi-1)┊zn=xy=2-1(y1x+zn-1)特點：每次只需要相加兩個數(shù)，然后右移一位。且相加的兩個數(shù)（部分積和位積）都只有n位，因而不需要2n位的加法器。形成遞推公式令zi表示第i次部分積，則根據(jù)從內(nèi)到外的原則3.原碼一位乘法流程圖

開始zi=0,i=0yn=1?zi+0zi+xzi,y右移一位，i=i+1i=n?

結(jié)束yynn3.原碼一位乘法流程圖開始zi=0,部分積乘數(shù)說明最后結(jié)果：xy=0.10001111

00.0000yf1011

z0=0+00.1101y4=1,+x00.1101

00.01101yf101右移，得z1+00.1101y3=1,+x

01.001100.100111yf

10右移，得z2+00.0000y2=0,+0

00.100100.0100111yf

1右移，得z3+00.1101y1=1,+x01.000100.10001111yf右移，得z4=xy例：x=0.1101,y=0.1011,求x·y

。部分積乘數(shù)說明最后結(jié)果：xy=0.1000114.原碼一位乘硬件邏輯原理圖

R0→

R1→ynR2

計數(shù)器i

部分積z

被乘數(shù)x

乘數(shù)y

LDR0LDR1

T1,T2,…

Ti

QQ加法器RS啟動ynCx計數(shù)器：對移位的次數(shù)進行計數(shù)，以便判斷乘法運算是否結(jié)束。當計數(shù)器i=n時，計數(shù)器i的溢出信號使控制觸發(fā)器Cx

置0，關(guān)閉時序脈沖T，乘法操作結(jié)束。4.原碼一位乘硬件邏輯原理圖R0→R1→ynR2計數(shù)

原碼一位乘法的主要問題是：符號位不能參與運算，而補碼乘法可以實現(xiàn)符號位直接參與運算。2補碼一位乘法1.原碼一位乘的缺點2.補碼一位乘法的規(guī)律推導(dǎo)

采用比較法。比較法是Booth夫婦首先提出來的，又稱Booth算法。原碼一位乘法的主要問題是：符號位不能參與運算，2

設(shè)[x]補

=x0.x1x2…xn

當x0時,x0=0，Booth算法[x]補=0.x1x2…xn==x=-1+0.x1x2…xn=-1+x=-x0+真值與補碼的關(guān)系：

當x0時,x0=1，[x]補=1.x1x2…xn=2+xx=1.x1x2…xn-2(1)真值和補碼之間的關(guān)系設(shè)[x]補=x0.x1x2…xnBooth算法[x

在補碼機器中，一個數(shù)不論其正負，連同符號位向右移一位，符號位保持不變，就等于乘1/2。

設(shè)[x]補

=x0.x1x2…xn

∵x=-x0+∴x=-x0+121212=-x0+x0+1212=-x0+寫成補碼的形式，即得：要得到[2-ix]補,連同符號位右移i位即可(2)補碼的右移12[

x]補

=

x0.x0x1x2…xn在補碼機器中，一個數(shù)不論其正負，連同符號位向右移一位，

設(shè)被乘數(shù)

[x]補

=x0.x1x2…xn

乘數(shù)[y]補

=y0.y1y2…yn

均為任意符號，則有補碼乘法算式：[x·y]補=[x]補·y或：[x·y]補=[x]補·

(3)補碼乘法規(guī)則設(shè)被乘數(shù)[x]補=x0.x1x2…xn[x·y1）、當被乘數(shù)x符號任意，乘數(shù)y符號為正時：

根據(jù)補碼定義：==yyyy.]y[nL210補)(modxxxxx.x]x[nn+=+==+L1210222補∴

由于（y1y2…yn)是大于或等于1的正整數(shù)，根據(jù)模運算性質(zhì)（大于2的部分全部丟掉）有：2(y1y2…yn)=2∴(mod2)即：公式證明1）、當被乘數(shù)x符號任意，乘數(shù)y符號為正時：==yyyy.]2）、當被乘數(shù)x符號任意，乘數(shù)y符號為負時：)(modyyyy.]y[n22121+==L補xxx.x]x[n210=L補∵∴又因(0.y1y2…yn)>0所以：2）、當被乘數(shù)x符號任意，乘數(shù)y符號為負時：)(modyy(mod2)=[x]補·=[x]補·y(mod2)=[x]補·=[x]補·y

為推導(dǎo)出邏輯實現(xiàn)的分步算法，將上式展開得到各項部分積累加的形式。(yn+1是增加的附加位，初值為0)公式展開為推導(dǎo)出邏輯實現(xiàn)的分步算法，將上式展開得到各項部分積累加

將上式改為接近于分步運算邏輯實現(xiàn)的遞推關(guān)系。補]z[00=補補補}]x)[yy(]z{[]z[nn12112-+=--補補補}]x)[yy(]z{[]z[ininii12112-+=+-+---補補補}]x)[yy(]z{[]z[nn11112-+=--補補補}]x)[yy(]z{[]z[nn10112-+=+-MM遞推公式補補補補]x)[yy(]z[]z[]yx[nn011-+==+·最后一步不移位將上式改為接近于分步運算邏輯實現(xiàn)的遞推關(guān)系。補]z[00=由此可見：每次都是在前次部分積的基礎(chǔ)上，由（yi+1-yi)

決定對[x]補的操作，然后再右移一位，得到新的部分積；重復(fù)進行。yn+1，yn的作用：開始操作時，補充一位yn+1,使其初始為0。由yn+1yn

判斷進行什么操作；然后再由ynyn-1

判斷第二步進行什么操作…。

若

ynyn＋1=０1則

yi＋1-yi=1做加[x]補運算；ynyn＋1=１０

則

yi＋1-yi=-１做加[-x]補運算；ynyn＋1=１1ynyn＋1=0０則yi＋1-yi=0

[zi]加0，即保持不變；

由此可見：yn+1，yn的作用：若ynyn＋1=０1補碼一位乘的運算規(guī)則(1)如果yn=yn+1

，則部分積[zi]加0，再右移一位；(2)如果ynyn+1=01

，則部分積[zi]加[x]補，再右移一位；(2)如果ynyn+1=10

，則部分積[zi]加[-x]補,再右移一位；

如此重復(fù)n+1步，但最后一步不移位。包括一位符號位，所得乘積為2n+1位，其中n為尾數(shù)位數(shù)。補碼一位乘的運算規(guī)則(1)如果yn=yn+1，則部分積算法流程圖

開始結(jié)束[zi]補+[x]補→[zi]補[zi]補+[-x]補→[zi]補[z]補=0,i=0ynyn+1=?[zi]補不變i=n+1？[zi]補,y右移一位，i=i+1011001或11YN算法流程圖開始結(jié)束[zi]補+[x]補→[zi]補[zi00.00001.00110yn+1=0+00.1011ynyn+1=10,加[-x]補

00.101100.0101110011右移一位+00.0000ynyn+1=11,加000.010100.00101

11001右移一位+11.0101ynyn+1=01,加[x]補

11.011111.1011111100右移一位+00.0000ynyn+1=00,加011.101111.11011111

10右移一位+00.1011ynyn+1=10,加[-x]補

00.10001111

10最后一位不移位例：[x]補=1.0101，[y]補=1.0011,求[x·y]補=？[-x]補=0.1011[x·y]補=0.10001111算法步驟存在錯誤!!!部分積乘數(shù)

ynyn+1說明00.00001000000101100yn+1=0+000000ynyn+1=00,加0000000000000010110右移一位+110011ynyn+1=10,加[-x]補

1100111110011

01011右移一位+000000ynyn+1=11,加011.100111.1100110101右移一位+001101ynyn+1=01,加[x]補

0010010001001110

10右移一位+110011ynyn+1=10,加[-x]補

1101111110

10最后一位不移位[x]補=001101，[y]補=10110,[-x]補=110011[x·y]補=101111110部分積乘數(shù)

ynyn+1說明例：x=13,y=-10求x·y=？x·y=-010000010=-82H=補碼一位乘邏輯原理圖

R0→

R1→ynyn+1R2

計數(shù)器i

部分積z

被乘數(shù)x乘數(shù)y

+1LDR0LDR1

T1,T2,…+1

Ti

QQ加法器RS啟動Cxf

+-yn+1ynyn+1yn多開關(guān)路原反1001QQ4.補碼一位乘邏輯原理圖R0→R1→ynyn+1R2[注]被乘數(shù)寄存器R2的每一位用原碼（觸發(fā)器Q端）或反碼（觸發(fā)器Q端）經(jīng)多路開關(guān)送出；送[-x]補時，即送R2反碼且在加法器最末為加1；(2)R0保存部分積，其符號與加法器符號位f始終一致。(3)當計數(shù)器i=n+1時，封鎖LDR1、LDR0信號，使最后一步不移位。[注]高基乘法以上討論的乘法都只是檢查一位二進制位。能否同時檢查K位二進制位？以K=2，C=A×B為例如果這兩位二進制位為00，則加0如果這兩位二進制位為01，則加A如果這兩位二進制位為10，則加2A如果這兩位二進制位為11，則加3A2A=4A—2A3A=4A—A如果這兩位二進制位為11，則減A，4A待下一次補上，由于部分積已右移兩位，原來加4A變成加A如何知道有4A的操作哪？兩位二進制位為10或11，則加4A高基乘法以上討論的乘法都只是檢查一位二進制位。如果這兩位二進B的低兩位前次移出的位

運算

注釋2i+12i2i-10000+0+0001+A+0+A010+A+A+0011+2A+A+A100-2A+4A-2A+0101-A+4A-2A+A110-A+4A-A+01110+4A-A+ABooth4基乘法算法B的低兩位前次移出的位

2i+12i2i-10000例：A=011011，B=011001，計算C=A×B。0000000101001

0010，加[A]補+1110010111001011111001

010100算術(shù)右移兩位+0011100100,加[-2A]補

001100000001100

010

101算術(shù)右移兩位+00