計算機組成原理第講乘法

第一頁，共二十四頁，編輯于2023年，星期一第3章運算方法和運算部件(3)Abinarymultiplierisanelectroniccircuitusedindigitalelectronics,suchasacomputer,tomultiplytwobinarynumbers.Itisbuiltusingbinaryadders.Untilthelate1970s,mostminicomputersdidnothaveamultiplyinstruction,andsoprogrammersuseda"multiplyroutine”whichrepeatedlyshiftsandaccumulatespartialresults,oftenwrittenusingloopunwinding.Earlymicroprocessorsalsohadnomultiplyinstruction.原碼一位乘法補碼一位乘法補碼兩位乘法原碼兩位乘法第二頁，共二十四頁，編輯于2023年，星期一UnsignedBinaryMultiplication

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

Binary(Fixed-Point)MultiplicationArithmetic被乘數(shù)左移，根據(jù)乘數(shù)每個位做不同運算，都不便于計算機實現(xiàn)第三頁，共二十四頁，編輯于2023年，星期一計算機的算法：

只能把每一個新位積與部分積（部分積的初值為零）相加，總共做n次加法（累加）。

部分積與位積相加時，只有n位與位積相加，其余部分并不參加運算。因此用n位的加法器就可完成乘法了。被乘數(shù)左移一位的操作改為部分積右移一位后與被乘數(shù)相加。只需用1個n位的寄存器存放部分積的高位，部分積的低位與乘數(shù)共用一個n位的寄存器，在乘數(shù)右移一位（計算該位位積后自動丟失）的同時將部分積最低一位移入。乘法完成后，原來存放乘數(shù)的寄存器中是乘積的低n位，乘數(shù)全部丟失，而硬件則節(jié)省了一個寄存器。被乘數(shù)10111101乘數(shù)0000部分積+10111011+000001011+101101011110右移一位00101111右移一位設計乘法邏輯第四頁，共二十四頁，編輯于2023年，星期一&&計數(shù)器A部分積A→FB→FF/2→ACd…C乘數(shù)B被乘數(shù)F加法器

移位電路C/2→C無符號數(shù)乘法邏輯原理圖運算前，先將被乘數(shù)送寄存器B，乘數(shù)送寄存器C，計數(shù)器的初值為N，部分積寄存器A清零。若乘數(shù)末位Yi＝1，部分積與被乘數(shù)在加法器相加。若乘數(shù)末位Yi＝0，則加法器輸出的是部分積與0的和。寄存器A和C中的部分積和乘數(shù)都右移一位形成新的部分積，部分積的最低位移入C空出的最高位。如此重復N次，乘法計算完畢。乘積的高N位在A中，低N位在C中，原來在C中的乘數(shù)在移位中丟失。CPA第五頁，共二十四頁，編輯于2023年，星期一[例1]X＝+0.1011B，Y＝－0.1101B，解：乘積的符號位用原碼一位乘法計算X·Y[X]原=|X|=[Y]原=|Y|=0.10111.11010.10110.1101原碼運算，必須把符號位與數(shù)值部分分開進行。符號位做異或運算，數(shù)值部分做無符號數(shù)相乘。Mostcomputersusea"shiftandadd"algorithmformultiplyingsmallintegers.第六頁，共二十四頁，編輯于2023年，星期一|X|=0.1011，|Y|=0.1101高位部分積

00000低位部分積/乘數(shù)

1101

初始狀態(tài)|X·Y|=0.10001111右移010001111100011111右移00110111

1011011111+)01011右移000101111001011110+)00000右移001011110010111101+)01011+)01011X·Y＝－0.10001111B[X·Y]原=1.10001111乘數(shù)最低位為1，加|X|乘數(shù)最低位為0，加0乘數(shù)最低位為1，加|X|乘數(shù)最低位為1，加|X|第七頁，共二十四頁，編輯于2023年，星期一原碼一位乘法流程圖YY開始結束A←0，Cd←nB←X，C←YCn=1?A←(A)+(B)(A),(C)右移一位Cd←(Cd)—1Cd=0?NNFlowchart如果乘數(shù)的數(shù)值部分是N位，則共需做N次加法，N次右移。乘積的數(shù)值部分是2N位。原碼乘法做的是絕對值相乘，相當于無符號數(shù)相乘。右移按邏輯右移進行。缺點：需做N次加法，N次右移，時間太長。計數(shù)器乘數(shù)被乘數(shù)部分積第八頁，共二十四頁，編輯于2023年，星期一乘積的符號位原碼運算，必須把符號位與數(shù)值部分分開進行。符號位做異或運算，數(shù)值部分做無符號數(shù)相乘。

兩個原碼表示的數(shù)（無論小數(shù)或整數(shù)）相乘，乘積的值是兩數(shù)絕對值之積，符號是相乘兩數(shù)符號位的異或值。兩個尾數(shù)為n位的數(shù)相乘，乘積的尾數(shù)為2n位。Thesecondproblemisthatthebasicschoolmethodhandlesthesignwithaseparaterule("+with+yields+","+with-yields-",etc.).Thismethodismathematicallycorrect,butithastwoseriousengineeringproblems.Thefirstisthatitinvolves32intermediateadditionsina32-bitcomputer,or64intermediateadditionsina64-bitcomputer.Theseadditionstakealotoftime.第九頁，共二十四頁，編輯于2023年，星期一原碼兩位乘法按照乘數(shù)每兩位的情況，一次求出對應于該2位的部分積。增加少量邏輯電路，可使乘法的速度提高一倍。乘數(shù)的相鄰兩位Yi-1Yi有4種狀態(tài)組合，分別對應一種操作：Yi-1Yi

操作00011011相當于0·X相當于1·X相當于2·X相當于3·X部分積Pi+0后右移2位部分積Pi+X后右移2位部分積Pi+2X后右移2位部分積Pi+3X后右移2位第十頁，共二十四頁，編輯于2023年，星期一加2X很容易實現(xiàn)。把X左移一位，或者把X向左斜傳送一位。加3X一般不能一次完成。分兩次（3X=X+2X）又降低了速度。如果令3X=4X—X，形式上看好象需要2次。實際上可以這樣：

本次運算只做減X，用一個欠帳觸發(fā)器C記下欠加4X，下一步操作時補上。

由于本次累加后，部分積要右移2位，相當于乘數(shù)相對左移2位。此時做+X相當于前一步+4X。所以，3X=4X—X只需要做一次。欠帳觸發(fā)器C的初值為0。Yi-1Yi

操作00011011相當于0·X相當于1·X相當于2·X相當于3·X部分積Pi+0后右移2位部分積Pi+X后右移2位部分積Pi+2X后右移2位部分積Pi+3X后右移2位第十一頁，共二十四頁，編輯于2023年，星期一原碼二位乘法的運算規(guī)則：當欠帳觸發(fā)器C=0時，Yi-1YiC

000 010 100 110 操作

部分積Pi+0后右移2位 部分積Pi+X后右移2位 部分積Pi+2X后右移2位 部分積Pi—X后右移2位

0→C 0→C 0→C 1→C

當欠帳觸發(fā)器C=1時，Yi-1YiC

001 011 101 111 操作

部分積Pi+X后右移2位 部分積Pi+2X后右移2位 部分積Pi+[-X]補后右移2位 部分積Pi+0后右移2位

0→C 0→C 1→C 1→C

第十二頁，共二十四頁，編輯于2023年，星期一減X用加[-X]補實現(xiàn)。右移按補碼右移規(guī)則進行。

當乘數(shù)的數(shù)值部分是N位（N必須是偶數(shù)），則共需做N/2次加法和N/2次右移。最后如果還有欠帳，再做一次+X。欠帳觸發(fā)器C的初值為0。

由于在運算中有+2|X|，產(chǎn)生的進位可能侵占符號位，所以被乘數(shù)和部分積應該取3符號位。例2：X=-0.111111，Y=+0.111001，用原碼二位乘法計算X*Y符號位單獨處理，乘數(shù)的數(shù)值部分必須是偶數(shù)位。相乘的是兩數(shù)的絕對值。原碼二位乘法的運算規(guī)則：第十三頁，共二十四頁，編輯于2023年，星期一解：[X]

原=1.111111乘積的符號位|X|=0.111111|2X|=001.111110例2：X=-0.111111，Y=+0.111001，用原碼二位乘法計算X*Y[Y]

原=0.111001|Y|=0.111001[-|X|]補=1.000001第十四頁，共二十四頁，編輯于2023年，星期一|X|=0.111111,|Y|=0.111001,

|2X|=001.111110,[-|X|]補=1.000001高位部分積

000.000000乘數(shù)欠帳觸發(fā)器C

1110010

初始狀態(tài)

000.111000000111111.111001

0001111

右移2位

111.100100+111.000001000.1000110111110

右移2位010.001101+001.111110000.0011111111100

右移2位000.111111+000.111111+000.111111Yi-1YiC＝010，加|X|,0→CYi-1YiC＝100，加|2X|,0→CYi-1YiC＝110，加[-|X|]補,1→CC＝1，加|X|[X*Y]原=1.111000000111X*Y=-0.111000000111|X*Y|

=0.111000000111第十五頁，共二十四頁，編輯于2023年，星期一

在計算機系統(tǒng)內，由于電路故障或電磁干擾等原因，數(shù)據(jù)在存取或傳送過程中可能產(chǎn)生錯誤。為了能發(fā)現(xiàn)或糾正這類錯誤，常采用具有能發(fā)現(xiàn)某些錯誤，或具有能確定錯誤的性質和準確的出錯位置乃至能自動糾正錯誤的能力的編碼方法，即數(shù)據(jù)校驗碼。Mostcodesare"systematic":thetransmittersendsafixednumberoforiginaldatabits,followedbyfixednumberofcheckbits(usuallyreferredtoasredundancyintheliterature)whicharederivedfromthedatabitsbysomedeterministicalgorithm.其實現(xiàn)原理是在合法的數(shù)據(jù)編碼之間加進一些不允許出現(xiàn)的非法編碼，使合法編碼的碼距增大。當合法的數(shù)據(jù)編碼出現(xiàn)錯誤時，就變成非法編碼。這就可以用檢測編碼的合法性來發(fā)現(xiàn)錯誤。Thereceiverappliesthesamealgorithmtothereceiveddatabitsandcomparesitsoutputtothereceivedcheckbits;ifthevaluesdonotmatch,anerrorhasoccurredatsomepointduringthetransmission.§3.7數(shù)據(jù)校驗碼第十六頁，共二十四頁，編輯于2023年，星期一

由若干位代碼組成的一個字叫“碼字”，一種碼制是若干種碼字的組合。將兩個碼字逐位比較，有幾個二進制位不同稱為這兩個碼字間的距離。

只有一位不同的，稱其碼距為1。例如，3位二進制代碼有8種狀態(tài)，若一種碼制用到全部8種碼字，其碼距為1。就是說，任何一個合法碼字的一位或幾位出錯時，就變成另一個合法碼字。一種碼制中各碼字間的最小距離稱為該碼制的“碼距”。000111101001110010011100第十七頁，共二十四頁，編輯于2023年，星期一一種碼制中各碼字間的最小距離稱為該碼制的“碼距”。

若增大編碼的冗余度，設計該碼制時用4個二進制位來表示8個合法碼字。由于只利用了全部16種狀態(tài)中的8種來表示合法碼，就可以把其余8種狀態(tài)作為非法碼，則碼距可能增大到2。當一個合法碼的一位出錯時，將變成一個非法碼而被發(fā)現(xiàn)。所增加的一位稱為校驗位。數(shù)據(jù)000001010011100101110111編碼00000011010101101001101011001111非法碼00100001011101001011100011101101出錯第十八頁，共二十四頁，編輯于2023年，星期一

合理的安排非法編碼的數(shù)量和編碼規(guī)則，增大合法碼的碼距就可以提高發(fā)現(xiàn)錯誤的能力，甚至能自動糾正錯誤；但表示一定數(shù)量的合法碼所使用的二進制位數(shù)也增多，使數(shù)據(jù)存儲和傳送的數(shù)量增大，硬件開銷也相應增大。常用的數(shù)據(jù)校驗碼有：奇偶校驗碼、海明校驗碼和循環(huán)冗余校驗碼等。

根據(jù)糾錯理論，編碼的最小距離與編碼的檢測、糾錯能力的關系為：L—1=C+D其中：L是編碼的最小距離，D是可以檢測錯誤代碼的位數(shù)，C是可以糾正錯誤代碼的位數(shù)，D≥C。當L=3時，可檢測出2個錯誤，或者可檢測并糾正1位錯誤。當L=4時，可檢測出3個錯誤，或者可檢測出2位并糾正1位錯誤。第十九頁，共二十四頁，編輯于2023年，星期一奇偶校驗碼

ParityCheckCode

奇偶校驗碼的編碼方法是給n位的合法編碼增加一個奇偶校驗位，使其碼距增加到2。任何一位出錯（包括校驗位）都會使代碼的奇偶性改變，從而被發(fā)現(xiàn)。校驗位可以放在最高數(shù)據(jù)位的左邊，或最低數(shù)據(jù)位的右邊。

若n+1位的奇偶校驗碼中“1”的個數(shù)為奇數(shù)稱為奇校驗，“1”的個數(shù)為偶數(shù)稱為偶校驗。

當n位信息代碼中有偶數(shù)個1，則偶校驗附加的校驗位為0，而奇校驗的校驗位為1

。例如：數(shù)據(jù)代碼

奇校驗碼

偶校驗碼1010101010100101010101101101101110110110Aparitybitisanerrordetectionmechanismthatcanonlydetectanoddnumberoferrors.設校驗位在最右邊第二十頁，共二十四頁，編輯于2023年，星期一交叉奇偶校驗

奇偶校驗碼廣泛應用于存儲器讀寫檢查，數(shù)據(jù)傳輸過程中的檢查等。對數(shù)據(jù)塊的橫向和縱向都有奇偶校驗位。例如：A7A6A5A4A3A2A1A0

橫向校驗位第1字節(jié)11001011→1第2字節(jié)01111100→1第3字節(jié)10011010→0第4字節(jié)10010101→0

↓↓↓↓↓↓↓↓縱向校驗位10111000交叉奇偶校驗能夠發(fā)現(xiàn)兩個位同時出錯。

奇偶校驗能發(fā)現(xiàn)1位或者奇數(shù)個