版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
計算機組成原理第六-八講計算機算法和算法邏輯實現(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ù)的表示范圍為|x|<1。在運算過程中如出現(xiàn)大于1的現(xiàn)象,稱為“溢出”。機器定點小數(shù)表示上溢下溢1.概念溢出及與檢測方法在定點小數(shù)機器中,數(shù)的表示范圍為|x
解:
[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)上圖中控制端M用來控制ALU進行算術(shù)運算還是進行邏輯運算:M=0時:
M對進位信號沒有任何影響。此時Fi
不僅與本位的被操作數(shù)Yi和操作數(shù)Xi
有關(guān),而且與向本位的進位值Cn+i
有關(guān),因此M=0時,進行算術(shù)操作。
M=1時:
封鎖了各位的進位輸出,即Cn+i
=0,因此各位的運算結(jié)果Fi
僅與Yi
和Xi
有關(guān),故M=1時,進行邏輯操作。2.算術(shù)邏輯運算的實現(xiàn)上圖中控制端M用來控制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+x=G0+P0CnCn+y=G1+P1Cn+x=G1+G0P1+P0P1CnCn+z=G2+P2Cn+y=G2+G1P2+G0P1P2+P0P1P2CnCn+4=G3+P3Cn+z=G3+G2P3+G1P1P2+G0P1P2P3+P0P1P2P3Cn
=G*+P*Cn其中:P*=P0P1P2P3
G*=G3+G2P3+G1P1P2+G0P1P2P3先行進位部件74182CLA所提供的進位邏輯關(guān)系如下:Cn+x=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ù)摹靶U边壿媮韺崿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è)x=0.1101,y=0.10110.1101(x)0.1011(y)110111010000+11010.10001111(z)(1)乘積符號的運算規(guī)則:同號相乘為正,異號相乘為負。(2)手工運算過程:設(shè)x=0.1101,y=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=01則
yi+1-yi=1做加[x]補運算;ynyn+1=10
則
yi+1-yi=-1做加[-x]補運算;ynyn+1=11ynyn+1=00則yi+1-yi=0
[zi]加0,即保持不變;
由此可見:yn+1,yn的作用:若ynyn+1=01補碼一位乘的運算規(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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024年云南客運員題庫軟件
- 2024年數(shù)據(jù)采集傳輸系統(tǒng)項目發(fā)展計劃
- 虛擬現(xiàn)實體驗館裝修合作
- 花藝工作室吊頂改造協(xié)議
- 電商倉庫搬遷裝修協(xié)議樣本
- 食品原料國內(nèi)配送合同范本
- 服裝設(shè)計采購物流合約
- 水庫淤泥清理運輸服務(wù)合同
- 超市排水系統(tǒng)裝修合同
- 礦山車輛駕駛員合同
- 統(tǒng)編版八年級道德與法治上冊第三單元教案教學設(shè)計
- Unit 3 Lesson 13 At School(教學設(shè)計)-2024-2025學年冀教版(三起)英語四年級上冊
- 人教版(2024新版)英語七年級上冊Unit 2 We're Family!大單元整體教學設(shè)計
- 石河子事業(yè)單位統(tǒng)一招聘考試真題
- 2024-2030年中國智慧公安行業(yè)發(fā)展動態(tài)及戰(zhàn)略規(guī)劃分析研究報告
- DB3305-T 178-2020液化石油氣氣瓶充裝單位鋼瓶管理規(guī)范
- 期中階段測試卷-2024-2025學年統(tǒng)編版語文六年級上冊
- Unit 2 Healthy Lifestyle 單詞講解教學設(shè)計-2024-2025學年高中英語人教版(2019)選擇性必修第三冊
- 2024市北京市西城區(qū)九年級中考二模英語試題(含答案)
- 2024新教科版一年級上冊第二單元我們自己第1課我們的身體教學課件含微課視頻
- 2022年中級注冊安全工程師考試《安全生產(chǎn)專業(yè)實務(wù)(建筑施工安全)》真題及詳解【完整版】
評論
0/150
提交評論