算法與實(shí)現(xiàn)證明不第1頁，共156頁，2023年，2月20日，星期二1、定點(diǎn)數(shù)加減法運(yùn)算及電路實(shí)現(xiàn) 補(bǔ)碼的加減法運(yùn)算，全加器，溢出，快速加法運(yùn)算（進(jìn)位鏈），74181ALU2、定點(diǎn)數(shù)乘除運(yùn)算和電路實(shí)現(xiàn) 原碼、補(bǔ)碼，布斯算法，原碼恢復(fù)余數(shù)、不恢復(fù)余數(shù)3、快速乘除法運(yùn)算技術(shù)和電路實(shí)現(xiàn) 布斯高基乘法，陣列乘法器，陣列除法器4、浮點(diǎn)數(shù)四則運(yùn)算以及實(shí)現(xiàn) 加減乘除本講安排第2頁，共156頁，2023年，2月20日，星期二本講將解決的主要問題掌握計(jì)算機(jī)算法。加減乘除運(yùn)算方法和運(yùn)算器的構(gòu)成，原碼和補(bǔ)碼的加減乘除四則運(yùn)算，浮點(diǎn)數(shù)的四則運(yùn)算。

第3頁，共156頁，2023年，2月20日，星期二補(bǔ)碼加、減法溢出概念與檢測方法基本的二進(jìn)制加法/減法器十進(jìn)制加法器第4頁，共156頁，2023年，2月20日，星期二加法規(guī)則：先判符號(hào)位，若相同，絕對值相加，結(jié)果符號(hào)不變;若不同，則作減法，|大|-|小|，結(jié)果符號(hào)與|大|相同。減法規(guī)則：兩個(gè)原碼表示的數(shù)相減，首先將減數(shù)符號(hào)取反，然后將被減數(shù)與符號(hào)取反后的減數(shù)按原碼加法進(jìn)行運(yùn)算。補(bǔ)碼加法1.原碼加/減法運(yùn)算第5頁，共156頁，2023年，2月20日，星期二補(bǔ)碼加法的公式:[x]補(bǔ)＋[y]補(bǔ)＝[x＋y]補(bǔ)(mod2)

在模2意義下,任意兩數(shù)的補(bǔ)碼之和等于該兩數(shù)之和的補(bǔ)碼。這是補(bǔ)碼加法的理論基礎(chǔ)。2.補(bǔ)碼加法運(yùn)算特點(diǎn)：不需要事先判斷符號(hào)，符號(hào)位與碼值位一起參加運(yùn)算。符號(hào)位相加后若有進(jìn)位，則舍去該進(jìn)位數(shù)字。第6頁，共156頁，2023年，2月20日，星期二

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

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

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

[x]補(bǔ)＋[y]補(bǔ)＝x＋y＝[x＋y]補(bǔ)

(mod2)公式證明:第7頁，共156頁，2023年，2月20日，星期二(2)x﹥0,y﹤0,則x＋y>0或x＋y<0。相加的兩數(shù)一個(gè)為正,一個(gè)為負(fù),因此相加結(jié)果有正、負(fù)兩種可能。根據(jù)補(bǔ)碼定義，

∵[x]補(bǔ)＝x,

[y]補(bǔ)＝2＋y

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

當(dāng)x+y>0時(shí),2+(x+y)>2,進(jìn)位2必丟失,又因(x+y)>0，故[x]補(bǔ)＋[y]補(bǔ)＝x＋y＝[x＋y]補(bǔ)

(mod2)

當(dāng)x＋y<0時(shí),2＋(x＋y)<2,又因(x+y)<0，故

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

(mod2)第8頁，共156頁，2023年，2月20日，星期二(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ù)都是負(fù)數(shù),則其和也一定是負(fù)數(shù)?！遊x]補(bǔ)＝2＋x,

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

因?yàn)閨x＋y|<1,1<(2＋x＋y)<2,2＋(2＋x＋y)進(jìn)位2

必丟失，又因x+y<0

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

(mod2)第9頁，共156頁，2023年，2月20日，星期二

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

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

（1）符號(hào)位要作為數(shù)的一部分一起參加運(yùn)算；（2）在模2的意義下相加，即大于2的進(jìn)位要丟掉。結(jié)論：第10頁，共156頁，2023年，2月20日，星期二例:

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

[x]補(bǔ)＝0.1001,[y]補(bǔ)＝0.0101[x]補(bǔ)

0.1001

＋[y]補(bǔ)

0.0101

[x＋y]補(bǔ)

0.1110

所以x＋y＝＋0.1110例:

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

[x]補(bǔ)＝0.1011,

[y]補(bǔ)＝1.1011[x]補(bǔ)

0.1011＋[y]補(bǔ)

1.1011

[x＋y]補(bǔ)

10.0110

第11頁，共156頁，2023年，2月20日，星期二補(bǔ)碼減法減法運(yùn)算要設(shè)法化為加法完成補(bǔ)碼減法運(yùn)算的公式：

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

(mod2)

令y=－x∴[0]補(bǔ)＝[x]補(bǔ)+[－

x]補(bǔ)

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

證明：第12頁，共156頁，2023年，2月20日，星期二例:

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

[x]補(bǔ)＝0.1101

[y]補(bǔ)＝0.0110,

[－y]補(bǔ)＝1.1010[x]補(bǔ)

0.1101

＋[－y]補(bǔ)

1.1010

[x－y]補(bǔ)

10.0111

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

[x]補(bǔ)

1.0011+[-y]補(bǔ)

0.0110[x-y]補(bǔ)

1.1001

例：x=-0.1101，y=-0.0110，求x-y=?∴x--y=-0.0111第13頁，共156頁，2023年，2月20日，星期二

溢出及與檢測方法

在定點(diǎn)小數(shù)機(jī)器中,數(shù)的表示范圍為|ｘ|<1。在運(yùn)算過程中如出現(xiàn)大于1的現(xiàn)象,稱為“溢出”。機(jī)器定點(diǎn)小數(shù)表示上溢下溢1.概念第14頁，共156頁，2023年，2月20日，星期二

解：

[x]補(bǔ)=0.1011

[y]補(bǔ)=0.1001

[x]補(bǔ)

0.1011

+

[y]補(bǔ)

0.1001

[x+y]補(bǔ)

1.0100

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

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

[x]補(bǔ)=1.0011

[y]補(bǔ)=1.0101

[x]補(bǔ)

1.0011

+

[y]補(bǔ)

1.0101

[x+y]補(bǔ)

0.1000

兩個(gè)負(fù)數(shù)相加的結(jié)果成為正數(shù)，這同樣是錯(cuò)誤的。第15頁，共156頁，2023年，2月20日，星期二

發(fā)生錯(cuò)誤的原因，是因?yàn)檫\(yùn)算結(jié)果產(chǎn)生了溢出。兩個(gè)正數(shù)相加:結(jié)果大于機(jī)器所能表示的最大正數(shù)，稱為上溢；兩個(gè)負(fù)數(shù)相加：結(jié)果小于機(jī)器所能表示的最小負(fù)數(shù)，稱為下溢。機(jī)器定點(diǎn)小數(shù)表示上溢下溢[分析]：第16頁，共156頁，2023年，2月20日，星期二2.溢出的檢測方法

[x]補(bǔ)

0.1011

+

[y]補(bǔ)

0.1001

[x+y]補(bǔ)

1.0100

[x]補(bǔ)

1.0011

+

[y]補(bǔ)

1.0101

[x+y]補(bǔ)

0.1000溢出邏輯表達(dá)式為：

V＝S1S2Sc+S1S2Sc(1)單符號(hào)位法FAVz0y0x0判斷電路判斷電路第17頁，共156頁，2023年，2月20日，星期二

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

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

x<24+x-2x<0

（mod4)第18頁，共156頁，2023年，2月20日，星期二

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

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

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

?兩個(gè)符號(hào)位都看做數(shù)碼一樣參加運(yùn)算；

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

[x]補(bǔ)+[y]補(bǔ)=[x+y]補(bǔ)

（mod4)采用變形補(bǔ)碼后數(shù)的表示：第19頁，共156頁，2023年，2月20日，星期二Sf1Sf2

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

01結(jié)果正溢

10結(jié)果負(fù)溢

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

兩個(gè)符號(hào)位的代碼一致時(shí)，表示沒有溢出。

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

V＝Sf1⊕Sf2

中Sf1和Sf2分別為最高符號(hào)位和第二符號(hào)位，此邏輯表達(dá)式可用異或門實(shí)現(xiàn)。雙符號(hào)位的含義如下：第20頁，共156頁，2023年，2月20日，星期二

解：

[x]補(bǔ)=00.1100

[y]補(bǔ)=00.1000

[x]補(bǔ)

00.1100

+

[y]補(bǔ)

00.1000

01.0100

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

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

解：

[x]補(bǔ)=11.0100

[y]補(bǔ)=11.1000

[x]補(bǔ)

11.0100

+

[y]補(bǔ)

11.1000

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

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

第21頁，共156頁，2023年，2月20日，星期二從上面例中看到：當(dāng)最高有效位有進(jìn)位而符號(hào)位無進(jìn)位時(shí),產(chǎn)生上溢；當(dāng)最高有效位無進(jìn)位而符號(hào)位有進(jìn)位時(shí),產(chǎn)生下溢。（簡單地說是正數(shù)相加為負(fù)數(shù)或負(fù)數(shù)相加為正數(shù)則產(chǎn)生溢出）故溢出邏輯表達(dá)式為：V＝Cf⊕Co

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

00.1100+[y]補(bǔ)

00.1000

01.1000[x]補(bǔ)

11.0100+[y]補(bǔ)

11.1000

10.1100第22頁，共156頁，2023年，2月20日，星期二FAFAz1z0Vc1c0y1x1y0x0FAFAVz1c0c1z0x1y1y0x0V＝C1⊕Co

V＝Sf1⊕Sf2判斷電路第23頁，共156頁，2023年，2月20日，星期二基本的二進(jìn)制加法/減法器加法運(yùn)算：Ai+Bi+Ci=Si(Ci+1)加數(shù)進(jìn)位輸入和進(jìn)位輸出一位全加器真值表輸入輸出AiBiCiSiCi＋10000000110010100110110010101011100111111邏輯方程Si＝Ai⊕Bi⊕CiCi＋1＝AiBi＋BiCi＋CiAi1.一位全加器第24頁，共156頁，2023年，2月20日，星期二邏輯方程Si＝Ai⊕Bi⊕CiCi＋1=AiBi＋BiCi＋CiAi邏輯電路（一位全加器）常用的全加器邏輯電路FACi+1CiSiAiBi邏輯符號(hào)第25頁，共156頁，2023年，2月20日，星期二2.n位的行波進(jìn)位加減器n個(gè)1位的全加器(FA)可級聯(lián)成一個(gè)n位的行波進(jìn)位加減器。第26頁，共156頁，2023年，2月20日，星期二T被定義為相應(yīng)于單級邏輯電路的單位門延遲。

T通常采用一個(gè)“與非”門或一個(gè)“或非”門的時(shí)間延遲來作為度量單位。3TXNOR異或非3TXOT異或2TOR或2TAND與TNOT非TNOR或非TNAND與非時(shí)間延遲邏輯符號(hào)（正邏輯）門的功能門的名稱典型門電路的邏輯符號(hào)和延遲時(shí)間接線邏輯(與或非)AOIT+TRC3.n位的行波進(jìn)位加法器的問題時(shí)間延遲第27頁，共156頁，2023年，2月20日，星期二(1)對一位全加器(FA)來說，Si的時(shí)間延遲為6T(每級異或門延遲3T)；Ci＋1的時(shí)間延遲為5T。3T3TTT第28頁，共156頁，2023年，2月20日，星期二(2)n位行波進(jìn)位加法器的延遲時(shí)間ta為:?9T為最低位上的兩極“異或”門再加上溢出“異或”門的總時(shí)間；

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

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

ta越小越好。第29頁，共156頁，2023年，2月20日，星期二缺點(diǎn)：(1)串行進(jìn)位,它的運(yùn)算時(shí)間長；(2)只能完成加法和減法兩種操作而不能完成邏輯操作。多功能算術(shù)/邏輯運(yùn)算單元(ALU):

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

多功能算術(shù)/邏輯運(yùn)算單元(ALU)將全加器的功能擴(kuò)展以完成多種算術(shù)邏輯運(yùn)算。Ci＋1=AiBi·(Ci·(Ai⊕Bi))=AiBi＋BiCi＋CiAi第31頁，共156頁，2023年，2月20日，星期二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?

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

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

）。一位ALU基本邏輯電路第32頁，共156頁，2023年，2月20日，星期二S0S1

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

進(jìn)一步化簡:Xi=S3AiBi+S2AiBiYi=Ai+S0Bi+S1BiAi+S0Bi+S1BiS3AiBi+S2AiBiXiYi==Yi

Fi＝Y(jié)i⊕Xi⊕Cn+iCn＋i＋1＝Y(jié)i＋XiCn＋i第33頁，共156頁，2023年，2月20日，星期二綜上所述，ALU的一位邏輯表達(dá)式為：Xi=S3AiBi+S2AiBiYi=Ai+S0Bi+S1Bi

Fi＝Y(jié)i⊕Xi⊕Cn+iCn＋i＋1＝Y(jié)i＋XiCn＋i第34頁，共156頁，2023年，2月20日，星期二4位之間采用先行進(jìn)位（并行進(jìn)位）公式。根據(jù)Cn＋i＋1＝Y(jié)i＋XiCn＋i，每一位的進(jìn)位公式可遞推如下：

?

第0位向第1位的進(jìn)位公式為:

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

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

?

第1位向第2位的進(jìn)位公式為:

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

?

第2位向第3位的進(jìn)位公式為:

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

第3位的進(jìn)位輸出（即整個(gè)4位運(yùn)算進(jìn)位輸出）公式為:

Cn＋4=Y3+X3Cn＋3=Y3+Y2X3+Y1X2X3+Y0X1X2X3+X0X1X2X3Cn4位ALU的進(jìn)位關(guān)系及邏輯電路第35頁，共156頁，2023年，2月20日，星期二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是最后進(jìn)位輸出。邏輯表達(dá)式表明,這是一個(gè)先行進(jìn)位邏輯。換句話說,第0位的進(jìn)位輸入Cn可以直接傳送到最高位上去,因而可以實(shí)現(xiàn)高速運(yùn)算。下圖為用上述原始推導(dǎo)公式實(shí)現(xiàn)的4位算術(shù)/邏輯運(yùn)算單元(ALU)

——74181ALU從進(jìn)位關(guān)系上看第36頁，共156頁，2023年，2月20日，星期二X0Y0X1Y1X2Y2X3Y3

正邏輯表示的74181第37頁，共156頁，2023年，2月20日，星期二

第3位的進(jìn)位輸出（即整個(gè)4位運(yùn)算進(jìn)位輸出）公式為:

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稱為進(jìn)位發(fā)生輸出,P稱為進(jìn)位傳送輸出。在電路中多加這兩個(gè)進(jìn)位輸出的目的,是為了便于實(shí)現(xiàn)多片（組）ALU之間的先行進(jìn)位。P和G的含義第38頁，共156頁，2023年，2月20日，星期二負(fù)邏輯表示的74181X0Y0X1Y1X2Y2X3Y3第39頁，共156頁，2023年，2月20日，星期二

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

Ｍ對進(jìn)位信號(hào)沒有任何影響。此時(shí)Fi

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

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

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

Ｍ＝1時(shí)：

封鎖了各位的進(jìn)位輸出,即Cn+i

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

僅與Yi

和Xi

有關(guān),故Ｍ＝1時(shí),進(jìn)行邏輯操作。第40頁，共156頁，2023年，2月20日，星期二下圖為工作于負(fù)邏輯和正邏輯操作方式的74181ALU方框圖。兩種操作是等效的。?對正邏輯操作數(shù)來說：

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

(即高電平為“1”,低電平為“0”)。?對于負(fù)邏輯操作數(shù)來說:

正好相反。第41頁，共156頁，2023年，2月20日，星期二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ù)運(yùn)算M=LCn=H邏輯M=H算術(shù)運(yùn)算M=LCn=L邏輯M=H正邏輯輸入與輸出負(fù)邏輯輸入與輸出工作方式選擇輸入S3S2S1S0

第42頁，共156頁，2023年，2月20日，星期二(1)H＝高電平,L＝低電平；(2)*表示每一位均移到下一個(gè)更高位,即A*＝2A。(3)

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

“加”是指算術(shù)加，運(yùn)算時(shí)要考慮進(jìn)位；符號(hào)“＋”是指“邏輯加”。(4)

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

“A＝B”輸出端可指示兩個(gè)數(shù)是否相等；第43頁，共156頁，2023年，2月20日，星期二3.并行加法器的進(jìn)位邏輯74181ALU為4位并行加法器，組成16位的并行加法器——怎么辦？

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

?組與組之間串行連接

?組與組之間并行連接第44頁，共156頁，2023年，2月20日，星期二組間串行進(jìn)位C4＝G0＋P0C0C8＝G1＋P1C4C12＝G2＋P2C8C16＝G3＋P3C12進(jìn)位關(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第45頁，共156頁，2023年，2月20日，星期二第1組4-1位并行進(jìn)位X3Y3X2Y1X1Y1X0Y0C4C3C2C1第2組8-5位并行進(jìn)位X7Y7X6Y6X5Y5X4Y4C8C7C6C5第3組12-9位并行進(jìn)位X11Y11X10Y10X9Y9X8Y8C12C11C10C9第4組16-13位并行進(jìn)位X15Y15X14Y14X13Y13X12Y12C16C15C14C13進(jìn)位傳遞時(shí)間C16C12C8C4C01.534.56tyC1CC16C12C8C4C01.534.57tyC1C5.589.5第46頁，共156頁，2023年，2月20日，星期二(2)組間并行進(jìn)位——兩級先行進(jìn)位的ALU由串行進(jìn)位關(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ù)上述公式實(shí)現(xiàn)邏輯電路:第47頁，共156頁，2023年，2月20日，星期二

X0Y0X1Y1X2Y2X3Y3

C12C8C4

X0Y0X1Y1X2Y2X3Y3

X0Y0X1Y1X2Y2X3Y3

0第48頁，共156頁，2023年，2月20日，星期二進(jìn)位的傳遞時(shí)間C16C12C8C4C01.534.56tyC1CC3第1小組X3~0Y3~0C3C2C1P0G0第2小組X7~4Y7~4C7C6C5P1G1第3小組X11~8Y11~8C11C10C9P2G2第4小組X15~12Y15~12C15C14C3P3G3第二級進(jìn)位鏈C0C4C8C12C16第49頁，共156頁，2023年，2月20日，星期二由上圖可見，?

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

和所有的Gi、Pi；?

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

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

C9C10C11，C13C14C15。整個(gè)進(jìn)位傳遞時(shí)間為4.5ty。第50頁，共156頁，2023年，2月20日，星期二4.先行進(jìn)位部件（CLA）——7418274182是一個(gè)并行進(jìn)位部件，其內(nèi)部結(jié)構(gòu)圖如下：其中G*稱為成組進(jìn)位發(fā)生輸出，P*稱為成組進(jìn)位傳送輸出。第51頁，共156頁，2023年，2月20日，星期二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先行進(jìn)位部件74182CLA所提供的進(jìn)位邏輯關(guān)系如下：第52頁，共156頁，2023年，2月20日，星期二74181ALU設(shè)置了P和G兩個(gè)本組先行進(jìn)位輸出端。如果將四片74181的P,G輸出端送入到74182先行進(jìn)位部件（CLA）,又可實(shí)現(xiàn)第二級的先行進(jìn)位,即組與組之間的先行進(jìn)位。例：16位字長ALU的構(gòu)成G*P*第53頁，共156頁，2023年，2月20日，星期二?C3、C7、C11是由74182同時(shí)形成的；?其不同點(diǎn)是74182還提供大組間的進(jìn)位函數(shù)G*

和大組傳遞條件P*，以便在位數(shù)更長時(shí)組成下一級先行進(jìn)位鏈。由圖可知：第54頁，共156頁，2023年，2月20日，星期二

用若干個(gè)74181ALU位片,與配套的74182先行進(jìn)位部件CLA在一起,可構(gòu)成一個(gè)全字長的ALU。例：全字長的ALU的構(gòu)成用兩個(gè)16位全先行進(jìn)位部件級聯(lián)組成的32位ALU邏輯方框圖。第55頁，共156頁，2023年，2月20日，星期二十進(jìn)制加法器

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

（=D）

+011010011（=13）30011+5+010181000（=8）X+Y+C<10不調(diào)整X+Y+C>10調(diào)整第56頁，共156頁，2023年，2月20日，星期二故：

1.和為10～15時(shí)，加6校正；

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

＋0000011000110111(=37)第57頁，共156頁，2023年，2月20日，星期二1.一位BCD碼行波式進(jìn)位加法器一般結(jié)構(gòu)：011101010111100110111101111第58頁，共156頁，2023年，2月20日，星期二2.n位BCD碼行波式進(jìn)位加法器一般結(jié)構(gòu)：第59頁，共156頁，2023年，2月20日，星期二原碼乘法補(bǔ)碼乘法定點(diǎn)乘法運(yùn)算第60頁，共156頁，2023年，2月20日，星期二

設(shè)n位被乘數(shù)和乘數(shù)用定點(diǎn)小數(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ù)符號(hào)，

yf為乘數(shù)符號(hào)。原碼一位乘法1.乘法的手工算法第61頁，共156頁，2023年，2月20日，星期二(2)手工運(yùn)算過程：設(shè)ｘ＝0.1101,ｙ＝0.10110.1101(x)0.1011(y)110111010000+11010.10001111(z)(1)乘積符號(hào)的運(yùn)算規(guī)則：同號(hào)相乘為正，異號(hào)相乘為負(fù)。第62頁，共156頁，2023年，2月20日，星期二(1)機(jī)器通常只有n位長,兩個(gè)n位數(shù)相乘,乘積可能為2n位。(2)只有兩個(gè)操作數(shù)相加的加法器難以勝任將n位積一次相加起來的運(yùn)算。機(jī)器與人們習(xí)慣的算法不同之處：0.1101x×0.1011y0.00001101x共4次右移

0.0001101x共3次右移

0.000000x共2次右移

+0.01101x共1次右移

0.10001111

2.適合定點(diǎn)機(jī)的形式第63頁，共156頁，2023年，2月20日，星期二

為了適合兩個(gè)操作數(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ù)此式，按式中括號(hào)可表達(dá)的層次，從內(nèi)向外逐次進(jìn)行移位累加。第64頁，共156頁，2023年，2月20日，星期二一般而言，設(shè)被乘數(shù)x,乘數(shù)y都是小于1的n位定點(diǎ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))…)))第65頁，共156頁，2023年，2月20日，星期二形成遞推公式

令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)特點(diǎn)：每次只需要相加兩個(gè)數(shù)，然后右移一位。且相加的兩個(gè)數(shù)（部分積和位積）都只有n位，因而不需要2n位的加法器。第66頁，共156頁，2023年，2月20日，星期二3.原碼一位乘法流程圖

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

結(jié)束yynn第67頁，共156頁，2023年，2月20日，星期二部分積乘數(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

。第68頁，共156頁，2023年，2月20日，星期二4.原碼一位乘硬件邏輯原理圖

R0→

R1→ynR2

計(jì)數(shù)器i

部分積z

被乘數(shù)x

乘數(shù)y

LDR0LDR1

T1,T2,…

Ti

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

置0，關(guān)閉時(shí)序脈沖T，乘法操作結(jié)束。第69頁，共156頁，2023年，2月20日，星期二

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

采用比較法。比較法是Booth夫婦首先提出來的，又稱Booth算法。第70頁，共156頁，2023年，2月20日，星期二

設(shè)[x]補(bǔ)

=x0.x1x2…xn

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

當(dāng)x0時(shí),x0=1，[x]補(bǔ)=1.x1x2…xn=2+xx=1.x1x2…xn-2(1)真值和補(bǔ)碼之間的關(guān)系第71頁，共156頁，2023年，2月20日，星期二

在補(bǔ)碼機(jī)器中，一個(gè)數(shù)不論其正負(fù)，連同符號(hào)位向右移一位，符號(hào)位保持不變，就等于乘1/2。

設(shè)[x]補(bǔ)

=x0.x1x2…xn

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

x]補(bǔ)

=

x0.x0x1x2…xn第72頁，共156頁，2023年，2月20日，星期二

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

[x]補(bǔ)

=x0.x1x2…xn

乘數(shù)[y]補(bǔ)

=y0.y1y2…yn

均為任意符號(hào)，則有補(bǔ)碼乘法算式：[x·y]補(bǔ)=[x]補(bǔ)·y或：[x·y]補(bǔ)=[x]補(bǔ)·(3)補(bǔ)碼乘法規(guī)則第73頁，共156頁，2023年，2月20日，星期二1）、當(dāng)被乘數(shù)x符號(hào)任意，乘數(shù)y符號(hào)為正時(shí)：

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

由于（y1y2…yn)是大于或等于1的正整數(shù)，根據(jù)模運(yùn)算性質(zhì)（大于2的部分全部丟掉）有：2(y1y2…yn)=2∴(mod2)即：公式證明第74頁，共156頁，2023年，2月20日，星期二2）、

當(dāng)被乘數(shù)x符號(hào)任意，乘數(shù)y符號(hào)為負(fù)時(shí)：)(modyyyy.]y[n22121+==L補(bǔ)xxx.x]x[n210=L補(bǔ)∵∴又因(0.y1y2…yn)>0所以：第75頁，共156頁，2023年，2月20日，星期二(mod2)=[x]補(bǔ)·=[x]補(bǔ)·y第76頁，共156頁，2023年，2月20日，星期二

為推導(dǎo)出邏輯實(shí)現(xiàn)的分步算法，將上式展開得到各項(xiàng)部分積累加的形式。(yn+1是增加的附加位，初值為0)公式展開第77頁，共156頁，2023年，2月20日，星期二

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

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

判斷進(jìn)行什么操作；然后再由ynyn-1

判斷第二步進(jìn)行什么操作…。

若

ynyn＋1=０1則

yi＋1-yi=1做加[x]補(bǔ)運(yùn)算；ynyn＋1=１０

則

yi＋1-yi=-１做加[-x]補(bǔ)運(yùn)算；ynyn＋1=１1ynyn＋1=0０則yi＋1-yi=0

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

第79頁，共156頁，2023年，2月20日，星期二補(bǔ)碼一位乘的運(yùn)算規(guī)則(1)如果yn=yn+1

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

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

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

如此重復(fù)n+1步，但最后一步不移位。包括一位符號(hào)位，所得乘積為2n+1位，其中n為尾數(shù)位數(shù)。第80頁，共156頁，2023年，2月20日，星期二算法流程圖

開始結(jié)束[zi]補(bǔ)+[x]補(bǔ)→[zi]補(bǔ)[zi]補(bǔ)+[-x]補(bǔ)→[zi]補(bǔ)[z]補(bǔ)=0,i=0ynyn+1=?[zi]補(bǔ)不變i=n+1？[zi]補(bǔ),y右移一位，i=i+1011001或11YN第81頁，共156頁，2023年，2月20日，星期二00.00001.00110yn+1=0+00.1011ynyn+1=10,加[-x]補(bǔ)

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

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

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

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

00.10001111

10最后一位不移位例：[x]補(bǔ)=1.0101，[y]補(bǔ)=1.0011,求[x·y]補(bǔ)=？[-x]補(bǔ)=0.1011[x·y]補(bǔ)=0.10001111部分積乘數(shù)

ynyn+1說明第82頁，共156頁，2023年，2月20日，星期二000000101100yn+1=0+000000ynyn+1=00,加0000000000000010110右移一位+110011ynyn+1=10,加[-x]補(bǔ)

1100111110011

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

0010010001001110

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

1101111110

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

ynyn+1說明例：x=13,y=-10求x·y=？x·y=-010000010=-82H=-130第83頁，共156頁，2023年，2月20日，星期二4.補(bǔ)碼一位乘邏輯原理圖

R0→

R1→ynyn+1R2

計(jì)數(shù)器i

部分積z

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

+1LDR0LDR1

T1,T2,…+1

Ti

QQ加法器RS啟動(dòng)Cxf

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

運(yùn)算

注釋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基乘法算法第87頁，共156頁，2023年，2月20日，星期二例：A=011011，B=011001，計(jì)算C=A×B。0000000101001

0010，加[A]補(bǔ)+1110010111001011111001

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

001100000001100

010

101算術(shù)右移兩位+0001110101，加[-A]補(bǔ)

00101000000101000010

1算術(shù)右移兩位解：[A]補(bǔ)=110010，[B]補(bǔ)=101001,[-A]補(bǔ)=0001110[-2A]補(bǔ)=0011100[A·B]補(bǔ)=0000101000010部分積乘數(shù)

yn-1ynyn+1說明A·B=000010100001