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

第3章運(yùn)算方法和運(yùn)算部件(3)Abinarymultiplierisanelectroniccircuitusedindigitalelectronics,suchasacomputer,tomultiplytwobinarynumbers.Itisbuiltusingbinaryadders.Untilthelate1970s,mostminicomputersdidnothaveamultiplyinstruction,andsoprogrammersuseda"multiplyroutine”whichrepeatedlyshiftsandaccumulatespartialresults,oftenwrittenusingloopunwinding.Earlymicroprocessorsalsohadnomultiplyinstruction.原碼一位乘法補(bǔ)碼一位乘法補(bǔ)碼兩位乘法原碼兩位乘法第2頁,共24頁，2024年2月25日，星期天UnsignedBinaryMultiplication

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

Binary(Fixed-Point)MultiplicationArithmetic被乘數(shù)左移，根據(jù)乘數(shù)每個(gè)位做不同運(yùn)算，都不便于計(jì)算機(jī)實(shí)現(xiàn)第3頁,共24頁，2024年2月25日，星期天計(jì)算機(jī)的算法：

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

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

移位電路C/2→C無符號(hào)數(shù)乘法邏輯原理圖運(yùn)算前，先將被乘數(shù)送寄存器B，乘數(shù)送寄存器C，計(jì)數(shù)器的初值為N，部分積寄存器A清零。若乘數(shù)末位Yi＝1，部分積與被乘數(shù)在加法器相加。若乘數(shù)末位Yi＝0，則加法器輸出的是部分積與0的和。寄存器A和C中的部分積和乘數(shù)都右移一位形成新的部分積，部分積的最低位移入C空出的最高位。如此重復(fù)N次，乘法計(jì)算完畢。乘積的高N位在A中，低N位在C中，原來在C中的乘數(shù)在移位中丟失。CPA第5頁,共24頁，2024年2月25日，星期天[例1]X＝+0.1011B，Y＝－0.1101B，解：乘積的符號(hào)位用原碼一位乘法計(jì)算X·Y[X]原=|X|=[Y]原=|Y|=0.10111.11010.10110.1101原碼運(yùn)算，必須把符號(hào)位與數(shù)值部分分開進(jìn)行。符號(hào)位做異或運(yùn)算，數(shù)值部分做無符號(hào)數(shù)相乘。Mostcomputersusea"shiftandadd"algorithmformultiplyingsmallintegers.第6頁,共24頁，2024年2月25日，星期天|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|第7頁,共24頁，2024年2月25日，星期天原碼一位乘法流程圖YY開始結(jié)束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位。原碼乘法做的是絕對(duì)值相乘，相當(dāng)于無符號(hào)數(shù)相乘。右移按邏輯右移進(jìn)行。缺點(diǎn)：需做N次加法，N次右移，時(shí)間太長(zhǎng)。計(jì)數(shù)器乘數(shù)被乘數(shù)部分積第8頁,共24頁，2024年2月25日，星期天乘積的符號(hào)位原碼運(yùn)算，必須把符號(hào)位與數(shù)值部分分開進(jìn)行。符號(hào)位做異或運(yùn)算，數(shù)值部分做無符號(hào)數(shù)相乘。

兩個(gè)原碼表示的數(shù)（無論小數(shù)或整數(shù)）相乘，乘積的值是兩數(shù)絕對(duì)值之積，符號(hào)是相乘兩數(shù)符號(hào)位的異或值。兩個(gè)尾數(shù)為n位的數(shù)相乘，乘積的尾數(shù)為2n位。Thesecondproblemisthatthebasicschoolmethodhandlesthesignwithaseparaterule("+with+yields+","+with-yields-",etc.).Thismethodismathematicallycorrect,butithastwoseriousengineeringproblems.Thefirstisthatitinvolves32intermediateadditionsina32-bitcomputer,or64intermediateadditionsina64-bitcomputer.Theseadditionstakealotoftime.第9頁,共24頁，2024年2月25日，星期天原碼兩位乘法按照乘數(shù)每?jī)晌坏那闆r，一次求出對(duì)應(yīng)于該2位的部分積。增加少量邏輯電路，可使乘法的速度提高一倍。乘數(shù)的相鄰兩位Yi-1Yi有4種狀態(tài)組合，分別對(duì)應(yīng)一種操作：Yi-1Yi

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

本次運(yùn)算只做減X，用一個(gè)欠帳觸發(fā)器C記下欠加4X，下一步操作時(shí)補(bǔ)上。

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

操作00011011相當(dāng)于0·X相當(dāng)于1·X相當(dāng)于2·X相當(dāng)于3·X部分積Pi+0后右移2位部分積Pi+X后右移2位部分積Pi+2X后右移2位部分積Pi+3X后右移2位第11頁,共24頁，2024年2月25日，星期天原碼二位乘法的運(yùn)算規(guī)則：當(dāng)欠帳觸發(fā)器C=0時(shí)，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

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

001 011 101 111 操作

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

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

第12頁,共24頁，2024年2月25日，星期天減X用加[-X]補(bǔ)實(shí)現(xiàn)。右移按補(bǔ)碼右移規(guī)則進(jìn)行。

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

由于在運(yùn)算中有+2|X|，產(chǎn)生的進(jìn)位可能侵占符號(hào)位，所以被乘數(shù)和部分積應(yīng)該取3符號(hào)位。例2：X=-0.111111，Y=+0.111001，用原碼二位乘法計(jì)算X*Y符號(hào)位單獨(dú)處理，乘數(shù)的數(shù)值部分必須是偶數(shù)位。相乘的是兩數(shù)的絕對(duì)值。原碼二位乘法的運(yùn)算規(guī)則：第13頁,共24頁，2024年2月25日，星期天解：[X]

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

原=0.111001|Y|=0.111001[-|X|]補(bǔ)=1.000001第14頁,共24頁，2024年2月25日，星期天|X|=0.111111,|Y|=0.111001,

|2X|=001.111110,[-|X|]補(bǔ)=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.001111

1111100

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

=0.111000000111第15頁,共24頁，2024年2月25日，星期天

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

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

只有一位不同的，稱其碼距為1。例如，3位二進(jìn)制代碼有8種狀態(tài)，若一種碼制用到全部8種碼字，其碼距為1。就是說，任何一個(gè)合法碼字的一位或幾位出錯(cuò)時(shí)，就變成另一個(gè)合法碼字。一種碼制中各碼字間的最小距離稱為該碼制的“碼距”。000111101001110010011100第17頁,共24頁，2024年2月25日，星期天一種碼制中各碼字間的最小距離稱為該碼制的“碼距”。

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

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

根據(jù)糾錯(cuò)理論，編碼的最小距離與編碼的檢測(cè)、糾錯(cuò)能力的關(guān)系為：L—1=C+D其中：L是編碼的最小距離，D是可以檢測(cè)錯(cuò)誤代碼的位數(shù)，C是可以糾正錯(cuò)誤代碼的位數(shù)，D≥C。當(dāng)L=3時(shí)，可檢測(cè)出2個(gè)錯(cuò)誤，或者可檢測(cè)并糾正1位錯(cuò)誤。當(dāng)L=4時(shí)，可檢測(cè)出3個(gè)錯(cuò)誤，或者可檢測(cè)出2位并糾正1位錯(cuò)誤。第19頁,共24頁，2024年2月25日，星期天奇偶校驗(yàn)碼

ParityCheckCode

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

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

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

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

奇校驗(yàn)碼

偶校驗(yàn)碼1010101010100101010101101101101110110110Aparitybitisanerrordetectionmechanismthatcanonlydetectanoddnumberoferrors.設(shè)校驗(yàn)位在最右邊第20頁,共24頁，2024年2月25日，星期天交叉奇偶校驗(yàn)

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

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

↓↓↓↓↓↓↓↓縱向校驗(yàn)位10111000交叉奇偶校驗(yàn)?zāi)軌虬l(fā)現(xiàn)兩個(gè)位同時(shí)出錯(cuò)。

奇偶校驗(yàn)?zāi)馨l(fā)現(xiàn)1位或者奇數(shù)個(gè)位同時(shí)出錯(cuò)，但不能發(fā)現(xiàn)偶數(shù)個(gè)位同時(shí)出錯(cuò)，也