計(jì)算機(jī)組成原理第4講_乘法

1、1計(jì)算機(jī)組成原理Principles of Computer Organization廣義雙語教學(xué)課程09/skyclass25/青島理工大學(xué) 校級精品課程http:/ 運(yùn)算方法和運(yùn)算部件運(yùn)算方法和運(yùn)算部件( 3 )A binary multiplier is an electronic circuit used in digital electronics, such as a computer, to multiply two binary numbers. It is built using binary adders.Until the late 1

2、970s, most minicomputers did not have a multiply instruction, and so programmers used a multiply routine” which repeatedly shifts and accumulates partial results, often written using loop unwinding. Early microprocessors also had no multiply instruction.原碼一位乘法原碼一位乘法補(bǔ)碼一位乘法補(bǔ)碼一位乘法補(bǔ)碼兩位乘法補(bǔ)碼兩位乘法原碼兩位乘法原碼兩位

3、乘法Unsigned Binary Multiplication 無符號數(shù)乘法無符號數(shù)乘法兩個尾數(shù)為兩個尾數(shù)為n位的數(shù)相乘，乘積的尾數(shù)為位的數(shù)相乘，乘積的尾數(shù)為2n位位。手算乘法的過程：1011 被乘數(shù) 1101 乘數(shù)101100001011101110001111位積乘積需要需要n個寄存器保存位積個寄存器保存位積對應(yīng)于乘數(shù)的位，將被乘數(shù)逐次左移一位加在左下方。最后將n個位積相加，得到乘積。計(jì)算機(jī)不能照搬手算的算法。運(yùn)算器一次只能完成兩數(shù)的求和操作。運(yùn)算器一次只能完成兩數(shù)的求和操作。需要需要2n位的加法器位的加法器3. 3 二進(jìn)制乘法運(yùn)算二進(jìn)制乘法運(yùn)算 Binary Multiplicatio

4、n Binary (Fixed-Point) Multiplication Arithmetic被乘數(shù)左移，根據(jù)乘數(shù)每個位做不同運(yùn)算，都不便于計(jì)算機(jī)實(shí)現(xiàn)計(jì)算機(jī)的算法： 只能把每一個新位積與部分積（部分積的初值為零）相加，只能把每一個新位積與部分積（部分積的初值為零）相加，總共做總共做n次加法（累加）。次加法（累加）。 部分積與位積相加時，只有n位與位積相加，其余部分并不參加運(yùn)算。因此用n位的加法器就可完成乘法了。被乘數(shù)左移一位的操作改為部分積右移一位后與被乘數(shù)相加。只需用1個n位的寄存器存放部分積的高位，部分積的低位與乘數(shù)共用一個n位的寄存器，在乘數(shù)右移一位（計(jì)算該位位積后自動丟失）的同時將部

5、分積最低一位移入。乘法完成后，原來存放乘數(shù)的寄存器中是乘積的低n位，乘數(shù)全部丟失，而硬件則節(jié)省了一個寄存器。被乘數(shù)10111101 乘數(shù)0000部分積+ 10111011+ 000001011+ 101101011 110 右移一位001011 11 右移一位設(shè)計(jì)乘法邏輯&計(jì)數(shù)器A 部分積 AFBFF/2ACdC 乘數(shù)B 被乘數(shù) F 加法器 移位電路 C/2C無符號數(shù)乘法無符號數(shù)乘法邏輯原理圖邏輯原理圖運(yùn)算前，先將被乘數(shù)送寄存器B，乘數(shù)送寄存器C，計(jì)數(shù)器的初值為N，部分積寄存器A清零。若乘數(shù)末位Yi1，部分積與被乘數(shù)在加法器相加。若乘數(shù)末位Yi0，則加法器輸出的是部分積與0的和。寄存器

6、A和C中的部分積和乘數(shù)都右移一位形成新的部分積，部分積的最低位移入C空出的最高位。如此重復(fù)N次，乘法計(jì)算完畢。乘積的高N位在A中，低N位在C中，原來在C中的乘數(shù)在移位中丟失。CPA例1 X+0.1011B，Y0.1101B，解：乘積的符號位110SSYX用原碼一位乘法計(jì)算XYX原 =|X|=Y原 =|Y|=0.10111.11010.10110.1101原碼運(yùn)算，必須把符號位與數(shù)值部分分開進(jìn)行。符號位做異或運(yùn)算，數(shù)值部分做無符號數(shù)相乘。Most computers use a shift and add algorithm for multiplying small integers.|X|=

7、 0.1011， |Y|= 0.1101高位部分積 0 0 0 0 0低位部分積 / 乘數(shù) 1 1 0 1初始狀態(tài)|XY|=0.10001111右移 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1右移 0 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 1 1+) 0 1 0 1 1右移 0 0 0 1 0 1 1 1 1 0 0 1 0 1 1 1 1 0+) 0 0 0 0 0右移 0 0 1 0 1 1 1 1 0 0 1 0 1 1 1 1 0 1+) 0 1 0 1 1+) 0 1 0 1 1XY0.10001111BXY原=1.10001111乘

8、數(shù)最低位為1，加|X|乘數(shù)最低位為0，加0乘數(shù)最低位為1，加|X|乘數(shù)最低位為1，加|X|原碼一位乘法流程圖YY開始結(jié)束A0，CdnBX，CYCn=1?A(A)+(B)(A),(C)右移一位Cd(Cd)1Cd=0?SSSYXPNNFlowchart如果乘數(shù)的數(shù)值部分是N位，則共需做N次加法，N次右移。乘積的數(shù)值部分是2N位。原碼乘法做的是絕對值相乘，相當(dāng)于無符號數(shù)相乘。右移按邏輯右移進(jìn)行。缺點(diǎn)：需做N次加法，N次右移，時間太長。計(jì)數(shù)器乘數(shù)被乘數(shù)部分積乘積的符號位乘積的符號位SSYX 原碼運(yùn)算，必須把符號位與數(shù)值部分分開進(jìn)行。原碼運(yùn)算，必須把符號位與數(shù)值部分分開進(jìn)行。符號位做異或運(yùn)算，數(shù)值部分做

9、無符號數(shù)相乘。符號位做異或運(yùn)算，數(shù)值部分做無符號數(shù)相乘。 兩個原碼表示的數(shù)（無論小數(shù)或整數(shù)）相乘，乘積的值是兩數(shù)絕對值之積，符號是相乘兩數(shù)符號位的異或值。兩個尾數(shù)為n位的數(shù)相乘，乘積的尾數(shù)為2n位。The second problem is that the basic school method handles the sign with a separate rule (+ with + yields +, + with - yields -, etc.). This method is mathematically correct, but it has two serious engi

10、neering problems. The first is that it involves 32 intermediate additions in a 32-bit computer, or 64 intermediate additions in a 64-bit computer. These additions take a lot of time.原碼兩位乘法原碼兩位乘法按照乘數(shù)每兩位的情況，一次求出對應(yīng)于該2位的部分積。增加少量邏輯電路，可使乘法的速度提高一倍。乘數(shù)的相鄰兩位Yi-1Yi有4種狀態(tài)組合，分別對應(yīng)一種操作：Yi-1Yi 操 作0 00 11 01 1相當(dāng)于0X相當(dāng)

11、于1X相當(dāng)于2X相當(dāng)于3X部分積Pi +0后右移2位部分積Pi +X后右移2位部分積Pi +2X后右移2位部分積Pi +3X后右移2位加2X很容易實(shí)現(xiàn)。把X左移一位，或者把X向左斜傳送一位。加3X一般不能一次完成。分兩次（3X=X+2X）又降低了速度。如果令 3X=4XX， 形式上看好象需要2次。實(shí)際上可以這樣： 本次運(yùn)算只做減減X，用一個欠帳觸發(fā)器欠帳觸發(fā)器C記下欠加4X，下一步操作時補(bǔ)上。 由于本次累加后，部分積要右移2位，相當(dāng)于乘數(shù)相對左移2位。此時做+X相當(dāng)于前一步+4X。所以，3X=4XX只需要做一次。欠帳觸發(fā)器欠帳觸發(fā)器C的初值為的初值為0。Yi-1Yi 操 作0 00 11 01

12、 1相當(dāng)于0X相當(dāng)于1X相當(dāng)于2X相當(dāng)于3X部分積Pi +0后右移2位部分積Pi +X后右移2位部分積Pi +2X后右移2位部分積Pi +3X后右移2位原碼二位乘法的運(yùn)算規(guī)則：當(dāng)欠帳觸發(fā)器當(dāng)欠帳觸發(fā)器C=0時，時，Yi-1 Yi C 0 0 0 0 1 0 1 0 0 1 1 0操 作部分積Pi +0后右移2位部分積Pi +X后右移2位部分積Pi +2X后右移2位部分積Pi X后右移2位0C0C0C1C當(dāng)欠帳觸發(fā)器當(dāng)欠帳觸發(fā)器C=1時，時，Yi-1 Yi C 0 0 1 0 1 1 1 0 1 1 1 1操 作部分積Pi +X后右移2位部分積Pi +2X后右移2位部分積Pi +-X補(bǔ)后右移2位

13、部分積Pi +0后右移2位0C0C1C1C減X用加-X補(bǔ)實(shí)現(xiàn)。右移按補(bǔ)碼右移規(guī)則進(jìn)行。右移按補(bǔ)碼右移規(guī)則進(jìn)行。 當(dāng)乘數(shù)的數(shù)值部分是當(dāng)乘數(shù)的數(shù)值部分是N位（位（N必須是偶數(shù)必須是偶數(shù)），則共需做），則共需做N/2次次加法和加法和N/2次右移。最后如果還有次右移。最后如果還有欠帳，再做一次欠帳，再做一次+X。欠帳觸發(fā)器C的初值為0。 由于在運(yùn)算中有由于在運(yùn)算中有+2|X|，產(chǎn)生的進(jìn)位可能侵占符號位，所以被，產(chǎn)生的進(jìn)位可能侵占符號位，所以被乘數(shù)和部分積應(yīng)該取乘數(shù)和部分積應(yīng)該取3符號位。符號位。例2：X= -0.111111，Y= +0.111001，用原碼二位乘法計(jì)算X*Y符號位單獨(dú)處理符號位單獨(dú)處

14、理，000YXP乘數(shù)乘數(shù)的數(shù)值部分的數(shù)值部分必須是偶數(shù)位必須是偶數(shù)位。相乘的是兩數(shù)的絕對值。原碼二位乘法的運(yùn)算規(guī)則：解：X 原=1.111111乘積的符號位101000YXP| X |=0.111111| 2X |=001.111110例2：X= -0.111111，Y= +0.111001，用原碼二位乘法計(jì)算X*YY 原=0.111001| Y |=0.111001-|X |補(bǔ)補(bǔ)=1.000001|X|= 0.111111, |Y|= 0.111001, | 2X |=001.111110, -|X |補(bǔ)=1.000001高位部分積 000. 0 0 0 0 0 0乘數(shù) 欠帳觸發(fā)器C 1 1

15、 1 0 0 1 0 初始狀態(tài) 000. 1 1 1 0 0 0 0 0 0 1 1 1 111. 1 1 1 0 0 1 0 0 0 1 1 1 1 右移2位 111. 1 0 0 1 0 0+ 111. 0 0 0 0 0 1000. 1 0 0 0 1 1 0 1 1 1 1 1 0 右移2位 010. 0 0 1 1 0 1+ 001. 1 1 1 1 1 0000. 0 0 1 1 1 1 1 1 1 1 1 0 0 右移2位 000. 1 1 1 1 1 1+ 000. 1 1 1 1 1 1+ 000. 1 1 1 1 1 1Yi-1Yi C010，加|X|,0CYi-1Yi C

16、100，加|2X| ,0CYi-1Yi C110，加-|X|補(bǔ),1CC1，加|X|X*Y原原 =1. 111000000111X*Y= -0.111000000111|X*Y| = 0. 111000000111 在計(jì)算機(jī)系統(tǒng)內(nèi)，由于電路故障或電磁干擾等原因，數(shù)據(jù)在存取或傳送過程中可能產(chǎn)生錯誤。為了能發(fā)現(xiàn)或糾正這類錯誤，常采用具有能發(fā)現(xiàn)某些錯誤，或具有能確定錯誤的性質(zhì)和準(zhǔn)確的出錯位置乃至能自動糾正錯誤的能力的編碼方法，即數(shù)據(jù)校驗(yàn)碼。Most codes are systematic: the transmitter sends a fixed number of original data b

17、its, followed by fixed number of check bits (usually referred to as redundancy in the literature) which are derived from the data bits by some deterministic algorithm. 其實(shí)現(xiàn)原理是在合法的數(shù)據(jù)編碼之間加進(jìn)一些不允許出現(xiàn)的非法編碼，使合法編碼的碼距增大。當(dāng)合法的數(shù)據(jù)編碼出現(xiàn)錯誤時，就變成非法編碼。這就可以用檢測編碼的合法性來發(fā)現(xiàn)錯誤。The receiver applies the same algorithm to the re

18、ceived data bits and compares its output to the received check bits; if the values do not match, an error has occurred at some point during the transmission.3.7 數(shù)據(jù)校驗(yàn)碼數(shù)據(jù)校驗(yàn)碼 由若干位代碼組成的一個字叫“碼字”，一種碼制是若干種碼字的組合。將兩個碼字逐位比較兩個碼字逐位比較，有幾個二進(jìn)制位不同有幾個二進(jìn)制位不同稱為這兩個碼字間的距離兩個碼字間的距離。 只有一位不同只有一位不同的，稱其碼距為碼距為1。例如，3位二進(jìn)制代碼有8種狀態(tài)

19、，若一種碼制用到全部8種碼字，其碼距為1。就是說，任何一個合法碼字的一位或幾位出錯時，就變成另一個合法碼字。一種碼制中各碼字間的最小距離稱為該碼制的一種碼制中各碼字間的最小距離稱為該碼制的“碼距碼距”。000111101001110010011100一種碼制中各碼字間的最小距離稱為該碼制的“碼距”。 若增大編碼的冗余度冗余度，設(shè)計(jì)該碼制時用4個二進(jìn)制位來表示8個合法碼字。由于只利用了全部16種狀態(tài)中的8種來表示合法碼，就可以把其余8種狀態(tài)作為非法碼，則碼距可能增大到2。當(dāng)一個合法碼的一位出錯時，將變成一個非法碼而被發(fā)現(xiàn)。所增加的一位稱為所增加的一位稱為校驗(yàn)位校驗(yàn)位。數(shù)據(jù)000001010011

20、100101110111編碼00000011010101101001101011001111非法碼00100001011101001011100011101101出錯 合理的安排非法編碼的數(shù)量和編碼規(guī)則，增大合法碼的碼距就可以提高發(fā)現(xiàn)錯誤的能力，甚至能自動糾正錯誤；但表示一定數(shù)量的合法碼所使用的二進(jìn)制位數(shù)也增多，使數(shù)據(jù)存儲和傳送的數(shù)量增大，硬件開銷也相應(yīng)增大。常用的數(shù)據(jù)校驗(yàn)碼有：奇偶校驗(yàn)碼奇偶校驗(yàn)碼、海明校驗(yàn)碼海明校驗(yàn)碼 和 循環(huán)冗余校驗(yàn)碼循環(huán)冗余校驗(yàn)碼等。 根據(jù)糾錯理論，編碼的最小距離與編碼的檢測、糾錯能力的關(guān)系為：L1 = C+D其中：L是編碼編碼的最小距最小距離，D是可以檢測錯誤代碼可以

21、檢測錯誤代碼的位數(shù)位數(shù)，C是可以糾正錯誤代碼可以糾正錯誤代碼的位數(shù)位數(shù)，DC。當(dāng)L=3時，可檢測出檢測出2個錯誤個錯誤，或者可檢測并糾正可檢測并糾正1位錯誤位錯誤。當(dāng)L=4時，可檢測檢測出3個錯誤個錯誤，或者可檢測檢測出2位并糾正位并糾正1位錯誤位錯誤。奇偶校驗(yàn)碼奇偶校驗(yàn)碼 Parity Check Code 奇偶校驗(yàn)碼的編碼方法是給n位的合法編碼增加一個奇偶校奇偶校驗(yàn)位驗(yàn)位，使其碼距增加到碼距增加到2。任何一位出錯一位出錯（包括校驗(yàn)校驗(yàn)位）都會使代碼代碼的奇偶性奇偶性改變改變，從而被發(fā)現(xiàn)。校驗(yàn)位可以放在最高數(shù)據(jù)位的左邊，或最低數(shù)據(jù)位的右邊。 若若n+1位的奇偶校驗(yàn)碼中位的奇偶校驗(yàn)碼中“1”的

22、個數(shù)為奇數(shù)的個數(shù)為奇數(shù)稱為奇校驗(yàn)奇校驗(yàn)，“1”的個數(shù)為偶數(shù)的個數(shù)為偶數(shù)稱為偶校驗(yàn)。偶校驗(yàn)。 當(dāng)n位信息代碼中有偶數(shù)個位信息代碼中有偶數(shù)個1，則偶校驗(yàn)附加的校驗(yàn)位為偶校驗(yàn)附加的校驗(yàn)位為0，而奇校驗(yàn)的校驗(yàn)位為奇校驗(yàn)的校驗(yàn)位為1 。例如：數(shù)據(jù)代碼奇校驗(yàn)碼偶校驗(yàn)碼1010101010100101010101101101101110110110A parity bit is an error detection mechanism that can only detect an odd number of errors.設(shè)校驗(yàn)位在最右邊交叉奇偶校驗(yàn)交叉奇偶校驗(yàn) 奇偶校驗(yàn)碼廣泛應(yīng)用于存儲器讀寫檢查，數(shù)據(jù)傳

23、輸過程中的檢查等。對數(shù)據(jù)塊的橫向和縱向都有奇偶校驗(yàn)位。例如： A7 A6 A5 A4 A3 A2 A1 A0 橫向校驗(yàn)位橫向校驗(yàn)位 第第1字節(jié)字節(jié) 1 1 0 0 1 0 1 1 1第第2字節(jié)字節(jié) 0 1 1 1 1 1 0 0 1第第3字節(jié)字節(jié) 1 0 0 1 1 0 1 0 0第第4字節(jié)字節(jié) 1 0 0 1 0 1 0 1 0 縱向校驗(yàn)位縱向校驗(yàn)位 1 0 1 1 1 0 0 0交叉奇偶校驗(yàn)?zāi)軌虬l(fā)現(xiàn)兩個位同時出錯。交叉奇偶校驗(yàn)?zāi)軌虬l(fā)現(xiàn)兩個位同時出錯。 奇偶校驗(yàn)?zāi)馨l(fā)現(xiàn)奇偶校驗(yàn)?zāi)馨l(fā)現(xiàn)1位或者奇數(shù)個位同時出錯，但不能發(fā)現(xiàn)位或者奇數(shù)個位同時出錯，但不能發(fā)現(xiàn)偶數(shù)個位同時出錯，也沒有糾錯能力。偶數(shù)個位

24、同時出錯，也沒有糾錯能力。計(jì)算機(jī)組成原理設(shè)計(jì)性作業(yè)課題課題1 定點(diǎn)運(yùn)算器設(shè)計(jì)定點(diǎn)運(yùn)算器設(shè)計(jì) 設(shè)計(jì)一個簡單的設(shè)計(jì)一個簡單的16位定點(diǎn)運(yùn)算器邏輯結(jié)構(gòu)。位定點(diǎn)運(yùn)算器邏輯結(jié)構(gòu)。 畫出邏輯圖，說明所設(shè)計(jì)的定點(diǎn)運(yùn)算器是怎樣進(jìn)行定點(diǎn)畫出邏輯圖，說明所設(shè)計(jì)的定點(diǎn)運(yùn)算器是怎樣進(jìn)行定點(diǎn)補(bǔ)碼加法運(yùn)算、減法運(yùn)算和邏輯運(yùn)算的。補(bǔ)碼加法運(yùn)算、減法運(yùn)算和邏輯運(yùn)算的。 列出運(yùn)算器做不同運(yùn)算時的控制信號。列出運(yùn)算器做不同運(yùn)算時的控制信號。 在基本的定點(diǎn)運(yùn)算器基礎(chǔ)上，如果要求計(jì)算機(jī)還能做定點(diǎn)在基本的定點(diǎn)運(yùn)算器基礎(chǔ)上，如果要求計(jì)算機(jī)還能做定點(diǎn)乘法、除法運(yùn)算，可以怎樣設(shè)計(jì)？乘法、除法運(yùn)算，可以怎樣設(shè)計(jì)？實(shí)驗(yàn)課題實(shí)驗(yàn)課題1 ALU設(shè)計(jì)

25、設(shè)計(jì)實(shí)驗(yàn)內(nèi)容：實(shí)驗(yàn)內(nèi)容： 按照題目要求設(shè)計(jì)一個16位ALU的邏輯，決定外部的端口（名稱、有效電平）和內(nèi)部各元件的連接，畫出系統(tǒng)框圖和邏輯圖，設(shè)計(jì)仿真數(shù)據(jù)，用VHDL編程和仿真。 一、主要元件設(shè)計(jì)一、主要元件設(shè)計(jì) 14位并行進(jìn)位加法器 功能要求：能完成兩個4位二進(jìn)制數(shù)（補(bǔ)碼和無符號數(shù)）的加法和邏輯加運(yùn)算。內(nèi)部有并行進(jìn)位鏈?？梢詳U(kuò)展成多位組。 2組間并行進(jìn)位鏈邏輯 功能要求：4個4位小組的組間并行進(jìn)位鏈邏輯。 將組間并行進(jìn)位鏈邏輯與4個4位超前進(jìn)位加法器連接可以構(gòu)成16位超前進(jìn)位加法器?？蓞⒖?4182的邏輯函數(shù)。（4學(xué)時）實(shí)驗(yàn)課題實(shí)驗(yàn)課題1 ALU設(shè)計(jì)設(shè)計(jì)實(shí)驗(yàn)內(nèi)容：實(shí)驗(yàn)內(nèi)容： 按照題目要求設(shè)計(jì)一個16位ALU的邏輯，決定外部的端口（名稱、有效電平）和內(nèi)部各元件的連接，畫出