第3章運(yùn)算方法和運(yùn)算部件(2)-乘除及校驗

1、13.3 3.3 二進(jìn)制乘法運(yùn)算二進(jìn)制乘法運(yùn)算以加法器為核心，通過加法和移位實現(xiàn)乘法運(yùn)算。以加法器為核心，通過加法和移位實現(xiàn)乘法運(yùn)算。1.1.軟件編程方法實現(xiàn)軟件編程方法實現(xiàn)( (時序控制乘法器）時序控制乘法器） 原碼乘法是先取絕對值相乘，再根據(jù)同號相乘為正、異號原碼乘法是先取絕對值相乘，再根據(jù)同號相乘為正、異號相乘為負(fù)，單獨決定符號位。補(bǔ)碼乘法則讓符號位直接參相乘為負(fù)，單獨決定符號位。補(bǔ)碼乘法則讓符號位直接參加運(yùn)算，算法將會復(fù)雜一些。加運(yùn)算，算法將會復(fù)雜一些。2.2.硬件快速乘法器實現(xiàn)硬件快速乘法器實現(xiàn) 利用中大規(guī)模集成電路芯片，在一個節(jié)拍中實現(xiàn)多項部分利用中大規(guī)模集成電路芯片，在一個節(jié)拍中

2、實現(xiàn)多項部分積的相加，成為陣列乘法器。積的相加，成為陣列乘法器。23.3.1 3.3.1 定點數(shù)一位乘法定點數(shù)一位乘法1定點原碼一位乘法定點原碼一位乘法(1)乘法的運(yùn)算規(guī)則設(shè) x=xf.x1x2xn，y=yf.y1y2yn乘積為P，乘積的符號位為Pf，則Pf=xfyf，|P|=|x|y|例例A= 0.1101, B= 0.1011, A= 0.1101, B= 0.1011, 求求A A* *B B 0.1101 0.1101 0.1011 0.1011 0110101101 01101 01101 00000 00000 01101 01101 0.10001111 0.10001111筆算

3、法的特點：筆算法的特點：n n 位數(shù)相乘，需要將位數(shù)相乘，需要將n n個位積相加，需要個位積相加，需要2n2n位加位加法器，不能法器，不能有效有效利用全加器操作利用全加器操作 由手算到機(jī)器實現(xiàn)，要解決三個問題：符號問題、由手算到機(jī)器實現(xiàn)，要解決三個問題：符號問題、部分積相加進(jìn)位問題、移位問題。部分積相加進(jìn)位問題、移位問題。位積位積 ABiA*B= 0.10001111求求|P|P|的運(yùn)算規(guī)則：的運(yùn)算規(guī)則：位積=5原碼一位乘法的算法流程圖原碼一位乘法的算法流程圖: :i表示循環(huán)次數(shù)（相加移位的次數(shù)）yn表示乘數(shù)將要被判斷的那一位Pi為部分積6符號擴(kuò)展符號擴(kuò)展把一個數(shù)的位數(shù)進(jìn)行擴(kuò)充但其真值不變。把

4、一個數(shù)的位數(shù)進(jìn)行擴(kuò)充但其真值不變。正數(shù)的符號擴(kuò)展：最高符號位之前補(bǔ)正數(shù)的符號擴(kuò)展：最高符號位之前補(bǔ)0 0（“0”0”表表示正號）。示正號）。負(fù)數(shù)的符號擴(kuò)展：最高符號位之前補(bǔ)負(fù)數(shù)的符號擴(kuò)展：最高符號位之前補(bǔ)1 1（“1”1”表表示負(fù)號）。示負(fù)號）。例：例： XX補(bǔ)補(bǔ) =10010011=10010011，將其擴(kuò)展成，將其擴(kuò)展成1616位補(bǔ)碼，得位補(bǔ)碼，得 XX補(bǔ)補(bǔ) =1111111110010011=1111111110010011例：例： XX補(bǔ)補(bǔ) =00101100=00101100，將其擴(kuò)展成，將其擴(kuò)展成1616位補(bǔ)碼，得位補(bǔ)碼，得 XX補(bǔ)補(bǔ) =0000000000101100=00000

5、000001011007 A (部分積部分積累加和累加和) C（乘數(shù)乘數(shù)） 00.0000 1 0 1 1 +00.1101_ 00.1101 00.0110 1 1 0 1 1 +00.1101_ 01.0011 00.1001 1 1 1 0 1 +00.0000_ 00.1001 00.0100 1 1 1 1 0 +00.1101 _ 01.0001 00.1000 1 1 1 1 1丟棄項丟棄項10001111. 0YXYXPsss部分積右移部分積右移加加“被乘數(shù)被乘數(shù)”加加“0”寄存器：寄存器：A A：存放：存放部分積累加和、部分積累加和、 乘積高位乘積高位B B：存放：存放被乘數(shù)

6、被乘數(shù)C C：存放：存放乘數(shù)、乘積低位乘數(shù)、乘積低位 A = 00.0000A = 00.0000（初始值）（初始值）B = |X| = 00.1101 B = |X| = 00.1101 C = |Y| = 00.1011C = |Y| = 00.1011例例3.31 3.31 X=0.1101,Y=0.1011,求求XY. 計算過程如下計算過程如下:加加“被乘數(shù)被乘數(shù)”8 （2）邏輯實現(xiàn)9注意：注意：兩操作數(shù)的絕對值相乘， 符號位單獨處理。寄存器A.B均設(shè)置雙符號位，第1符號位始終是部分積符號，決定在右移時第1符號位補(bǔ)0操作步數(shù)由乘數(shù)的尾數(shù)位數(shù)決定，用計數(shù)器Cd來計數(shù)。即作n次累加和移位。

7、最后是加符號位，根據(jù)XsYs決定。10 補(bǔ)碼乘法不能簡單的套用原碼乘法的算法，因為補(bǔ)碼的符號位補(bǔ)碼乘法不能簡單的套用原碼乘法的算法，因為補(bǔ)碼的符號位是參加運(yùn)算的。是參加運(yùn)算的。(1)(1)校正法校正法所謂校正法，將所謂校正法，將XX補(bǔ)補(bǔ)和和YY補(bǔ)補(bǔ)按原碼運(yùn)算，所得結(jié)果根據(jù)情況加以校按原碼運(yùn)算，所得結(jié)果根據(jù)情況加以校正，從而得到正，從而得到XYXY補(bǔ)補(bǔ)。算法分析：算法分析：若被乘數(shù)若被乘數(shù)X X的符號任意的符號任意XX補(bǔ)補(bǔ) = X= X0 0.X.X1 1X X2 2XnXn 1 1）Y Y為正：為正：YY補(bǔ)補(bǔ) = 0.Y= 0.Y1 1Y Y2 2YnYn XYXY補(bǔ)補(bǔ) = X= X補(bǔ)補(bǔ)(0.

8、Y(0.Y1 1Y Y2 2Yn)Yn) 2 2）Y Y為負(fù)：為負(fù)：YY補(bǔ)補(bǔ) = 1.Y= 1.Y1 1Y Y2 2YnYn YY補(bǔ)補(bǔ)=2+Y=2+Y，真值，真值 Y=YY=Y補(bǔ)補(bǔ)-2=1.Y-2=1.Y1 1Y Y2 2Yn-2Yn-2 = 0.Y = 0.Y1 1Y Y2 2Yn-1Yn-1 XYXY補(bǔ)補(bǔ) = X= X補(bǔ)補(bǔ)(0.Y(0.Y1 1Y Y2 2Yn)+-XYn)+-X補(bǔ)補(bǔ) 3 3）Y Y符號任意：符號任意：XYXY補(bǔ)補(bǔ) = X= X補(bǔ)補(bǔ)0.Y0.Y1 1Y Y2 2Yn+-XYn+-X補(bǔ)補(bǔ)Y Y0 0符號位符號位Y0,Y0,除按除按 1 1）計算外，另加計算外，另加-XX補(bǔ)補(bǔ)校

9、正校正直接按原碼直接按原碼乘法運(yùn)算乘法運(yùn)算2 2、定點補(bǔ)碼一位乘法、定點補(bǔ)碼一位乘法11若例若例3.33中中Y=0.1011，求，求XY補(bǔ)補(bǔ)時，需在最后右移時，需在最后右移1位后，位后，X補(bǔ)補(bǔ)。校正南華大學(xué)計算機(jī)學(xué)院12(2) (2) 比較法比較法算法算法( (布斯公式布斯公式) )校正法在乘數(shù)為負(fù)數(shù)時，需要進(jìn)行校正，控制起校正法在乘數(shù)為負(fù)數(shù)時，需要進(jìn)行校正，控制起來要復(fù)雜一些，我們希望有一個對于正數(shù)和負(fù)數(shù)都一來要復(fù)雜一些，我們希望有一個對于正數(shù)和負(fù)數(shù)都一致的算法，這就是比較法。比較法是英國的致的算法，這就是比較法。比較法是英國的BoothBooth夫夫婦提出來的，因此又稱婦提出來的，因此又稱

10、BoothBooth法法。根據(jù)校正法的統(tǒng)一表達(dá)式：根據(jù)校正法的統(tǒng)一表達(dá)式： XYXY補(bǔ)補(bǔ) = = XX補(bǔ)補(bǔ)(0.(0.Y Y1 1Y Y2 2Y Yn n)+-X)+-X補(bǔ)補(bǔ)Y Y0 0 = = XX補(bǔ)補(bǔ)(0.(0.Y Y1 1Y Y2 2Y Yn n)-X)-X補(bǔ)補(bǔ)Y Y0 0 =XX補(bǔ)補(bǔ)(-(-Y Y0 0+ +2 2-1-1Y Y1 1+ + 2 2-2-2 Y Y2 2+ + +2 2-n-n Y Yn n) ) = X補(bǔ) -Y0+(Y1-2-1Y1)+(2-1 Y2-2-2 Y2)+(2-(n-1)Yn-2-n Yn) = X補(bǔ)( (Y Y1 1-Y-Y0 0)+2)+2-1-1(Y

11、(Y2 2-Y-Y1 1)+2)+2-2-2(Y(Y3 3-Y-Y2 2) )+ 2 2-n-n(Y(Yn+1n+1-Y-Yn n)201)(iniiiYYX補(bǔ)比較法：用相鄰兩位乘數(shù)比較的比較法：用相鄰兩位乘數(shù)比較的結(jié)果決定結(jié)果決定+XX補(bǔ)補(bǔ)、-XX補(bǔ)補(bǔ)或或+0+0。( (BoothBooth算法）的運(yùn)算規(guī)則算法）的運(yùn)算規(guī)則: :位積=（ - ） 14補(bǔ)碼一位乘法算法流程圖補(bǔ)碼一位乘法算法流程圖: :Pi為部分積00或11i表示循環(huán)次數(shù)（相加移位的次數(shù)）15例例3.33.34 4 x=-0.1101，y=-0.1011（書上y為正數(shù)），求xy補(bǔ)=?解：x補(bǔ)=11.0011， -x補(bǔ)=00.11

12、01 （雙符號）y補(bǔ)=1.0101 （單符號）16步數(shù)步數(shù) 條件條件 操作操作 P YP Y 00.0000 1.01010 0 1）0 1-X-X補(bǔ)補(bǔ)Yi Yi+1+ 00.110100.1101 00.01101 1.01012） 1 0X補(bǔ)+ 11.001111.100111.1100111.010 3） 0 1-X-X補(bǔ)補(bǔ)+ 00.110100.100100.01001111.01 4） 1 0X補(bǔ)+ 11.001111.011111.101111111.0Yi+1Yi 5） 0 1 -X-X補(bǔ)補(bǔ)+ 00.1101 00.1000 1111 XYXY補(bǔ)補(bǔ) = 0.10001111 =

13、0.10001111右移時左邊補(bǔ)0，因為是正數(shù)(根據(jù)符號擴(kuò)展原理)右移時左邊補(bǔ)1，因為是負(fù)數(shù)(根據(jù)符號擴(kuò)展原理)17P P、X X取雙符號位，取雙符號位，符號參加運(yùn)算符號參加運(yùn)算；Y Y取單符號位，符號參加移位，以決定最后是取單符號位，符號參加移位，以決定最后是否修正；否修正；Y Y末位設(shè)置附加位末位設(shè)置附加位Y Yi+1i+1，初值為，初值為0 0，Y Yi+1i+1Y Yi i組成判組成判斷位，決定運(yùn)算操作；斷位，決定運(yùn)算操作；需作需作n+1n+1次累加次累加, ,n n次移位次移位( (最后一次不移位最后一次不移位) )。 (4) (4)運(yùn)算規(guī)則運(yùn)算規(guī)則183.3.2.3.3.2.定點數(shù)

14、二位乘法定點數(shù)二位乘法 每次用兩位乘數(shù)去乘被乘數(shù)，乘法速度提高一倍每次用兩位乘數(shù)去乘被乘數(shù)，乘法速度提高一倍Y Yi-1i-1( (高位高位) ) Y Yi i ( (低位低位) ) 部分積累加、移位部分積累加、移位 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 1/41/4P P 1/4(P+X) 1/4(P+X) 1/4(P+2X) 1/4(P+2X) 1/4(P+3X) 1/4(P+3X)( 0 )( 0 )( 1 )( 1 )( 2 )( 2 )( 3 )( 3 ) 0 0 X X 2 2X X 3 3X XX X左移左移1 1位即得位即得2 2X X，如何實現(xiàn)，如何

15、實現(xiàn)+3+3X X操作？操作？ 原碼兩位乘法為例原碼兩位乘法為例 (1) (1) 算法分析算法分析( (P P4848) )19 1/4(P+3X)= 1/4(P+3X)= 1/4(P-X+4X)=1/4(P-X+4X)=1/4(P-X)1/4(P-X)+ +X X 設(shè)置設(shè)置欠帳觸發(fā)器欠帳觸發(fā)器C C=0 0 不欠帳不欠帳1 1 欠帳欠帳, ,下次補(bǔ)作下次補(bǔ)作+ +X X操作操作(2)算法算法( (P P4949表表3.3)3.3)0 0 00 0 00 0 10 0 10 1 00 1 00 1 10 1 1 0 0 0 01 0 11 0 11 1 01 1 01 1 11 1 1操操 作

16、作 Y Yi-1i-1 Y Yi i C C1/4(1/4(P+X) 0 P+X) 0 C C1/4(1/4(P+X) 0 P+X) 0 C C1/4(1/4(P+2X) 0 P+2X) 0 C C1/41/4P 0 P 0 C C1/4(1/4(P+2X) P+2X) 0 0 C C1/4(1/4(P-X) P-X) 1 1 C C1/4(1/4(P-X) P-X) 1 1 C C1/41/4P P 1 1 C C20 -X補(bǔ) = 11.011001 2X=01.001110部分積部分積乘數(shù)乘數(shù)欠位欠位C 00.000000 1 0 0 1 1 1 0+-X補(bǔ) 11.011001 11.01

17、1001 右移2位11.110110 0 1 1 0 0 1 1 2X 01.001110 01.000100 右移2位 00.010001 0 0 0 1 1 00 +2X 01.001110 01.011111 右移2位 00 010111 1 1 0 0 0 1 0 乘積高位 乘積低位 X * Y = 0.010111110001例例3.35 3.35 假定假定X=0.100111X=0.100111，Y= 0.100111 Y= 0.100111 求求XYXY？ 21注意注意： 若最后一次操作欠下若最后一次操作欠下4 4X X即即C=1C=1，則最后一，則最后一次右移次右移2 2位后，

18、還需補(bǔ)充位后，還需補(bǔ)充X X操作，操作，X X后不再后不再移位。移位。 乘數(shù)符號不參加運(yùn)算，參加運(yùn)算的操作數(shù)乘數(shù)符號不參加運(yùn)算，參加運(yùn)算的操作數(shù)取絕對值，取絕對值，x xX X，2x2x2 2X X，符號位，符號位單獨處理。單獨處理。南華大學(xué)計算機(jī)學(xué)院223.3.3陣列乘法器陣列乘法器為了進(jìn)一步提高乘法運(yùn)算的速度，可采用高速乘法模塊為了進(jìn)一步提高乘法運(yùn)算的速度，可采用高速乘法模塊組成的陣列乘法器，設(shè)有兩個帶符號的二進(jìn)制數(shù)。組成的陣列乘法器，設(shè)有兩個帶符號的二進(jìn)制數(shù)。 例：m=n=4時，有： x4 x3 x2 x1 * y4 y3 y2 y1 - x4y1 x3y1 x2y1 x1y1 x4y2

19、 x3y2 x2y2 x1y2 x4y3 x3y3 x2y3 x1y3 x4y4 x3y4 x2y4 x1y4 22221010101010)(knmkkjiminjjijnjiimiiPyxyxYXPYX P8 P7 P6 P5 P4 P3 P2 P1 其結(jié)構(gòu)圖其結(jié)構(gòu)圖見見P P5050圖圖3.73.7可同時得到可同時得到各項部分積，各項部分積，并一次將其相并一次將其相加就得到乘積加就得到乘積運(yùn)算速度快。運(yùn)算速度快。23圖3.7 陣列乘法器 243.4 3.4 二進(jìn)制除法運(yùn)算二進(jìn)制除法運(yùn)算二進(jìn)制除法可模仿十進(jìn)制除法運(yùn)算。二進(jìn)制除法可模仿十進(jìn)制除法運(yùn)算。除法，理論上是乘法的逆運(yùn)算，在算法除法，

20、理論上是乘法的逆運(yùn)算，在算法上本質(zhì)是一種上本質(zhì)是一種試探法：試探法：它試探被除數(shù)是大于它試探被除數(shù)是大于等于還是小于除數(shù)，大于等于時商為等于還是小于除數(shù)，大于等于時商為1 1，小小于時商為于時商為0 0。25筆算除法筆算除法 A=0.1001, B=0.1011, A=0.1001, B=0.1011, 求商求商C, C, 余余數(shù)數(shù)R.R. 0.11010.1101 0.1011 0.10010 0.1011 0.10010 R R0 0=A=A - 0.01011 - 0.01011 -2-2-1-1B B 0.001110 0.001110 R R1 1 - 0.001011 - 0.00

21、1011 -2-2-2-2B B 0.0000110 0.0000110 R R2 2 0.00001100 0.00001100 R R3 3 - 0.00001011 - 0.00001011 -2-2-4-4B B 0.00000001 0.00000001 R R4 426筆算過程在計算機(jī)上的實現(xiàn)，必須作些變動：筆算過程在計算機(jī)上的實現(xiàn)，必須作些變動：比較除數(shù)與被除數(shù)過程，用減法實現(xiàn)；比較除數(shù)與被除數(shù)過程，用減法實現(xiàn)； 除數(shù)乘以除數(shù)乘以1/21/2與余數(shù)比較，等效于除數(shù)不與余數(shù)比較，等效于除數(shù)不動，而使余數(shù)動，而使余數(shù)左左移一位；移一位； 上商可以通過在商寄存器末位置上商可以通過在商寄

22、存器末位置1 1（商（商1 1）或置或置0 0（商（商0 0）來實現(xiàn)。上商同時使商寄存）來實現(xiàn)。上商同時使商寄存器與余數(shù)寄存器一起器與余數(shù)寄存器一起左左移一位。移一位。( (商寄存器初始存放被除數(shù)的低位數(shù)值部分商寄存器初始存放被除數(shù)的低位數(shù)值部分) )273.4.1 3.4.1 定點除法運(yùn)算定點除法運(yùn)算定點原碼一位除法定點原碼一位除法 有有恢復(fù)余數(shù)法恢復(fù)余數(shù)法和和加減交替法加減交替法兩種方法，在兩種方法，在計算機(jī)中常用的是加減交替法，因為它的操作計算機(jī)中常用的是加減交替法，因為它的操作步驟少，而且也不復(fù)雜。步驟少，而且也不復(fù)雜。 兩個原碼數(shù)相除，其商的符號為兩數(shù)符號兩個原碼數(shù)相除，其商的符號為

23、兩數(shù)符號的異或值，數(shù)值則為兩數(shù)絕對值相除后的結(jié)果。的異或值，數(shù)值則為兩數(shù)絕對值相除后的結(jié)果。實現(xiàn)除法的關(guān)鍵：實現(xiàn)除法的關(guān)鍵：比較余數(shù)、除數(shù)絕對值大小，以決定上商。比較余數(shù)、除數(shù)絕對值大小，以決定上商。28運(yùn)算規(guī)則：運(yùn)算規(guī)則：符號位單獨處理，符號位單獨處理，C C0 0=A=A0 0 B B0 0數(shù)值部分變成兩正數(shù)相除，數(shù)值部分變成兩正數(shù)相除，即即:|A|/|B| :|A|/|B| (|A|B|(|A|B|，防止商溢出，防止商溢出) )第第1 1步除法通過步除法通過R R0 0 - |B|(R- |B|(R0 0=|A|)=|A|)實現(xiàn)；實現(xiàn)；其后每其后每1 1步除法通過步除法通過2R2Ri i

24、-|B|(i =1,2,n)-|B|(i =1,2,n)實現(xiàn)：實現(xiàn)：若若2R2Ri i-|B|=R-|B|=Ri+1i+1 0, 0, 即余數(shù)為即余數(shù)為正正，則商上，則商上1 1；若若2R2Ri i-|B|=R-|B|=Ri+1i+10, 0, 即余數(shù)為即余數(shù)為負(fù)負(fù)，則商上，則商上0 0。291. 1. 恢復(fù)余數(shù)法恢復(fù)余數(shù)法不管被除數(shù)（或余數(shù)）減除數(shù)是否夠減，都一律做減法。不管被除數(shù)（或余數(shù)）減除數(shù)是否夠減，都一律做減法。若余數(shù)為正或若余數(shù)為正或0 0，表示夠減，該位商上，表示夠減，該位商上“1”1”，余數(shù)左移，余數(shù)左移1 1位。位。若余數(shù)為負(fù)，表示不夠減，該位商上若余數(shù)為負(fù)，表示不夠減，該位

25、商上“0”0”，并要，并要恢復(fù)恢復(fù)原來的原來的被除數(shù)（或被除數(shù)（或余數(shù)余數(shù)），再將其左移），再將其左移1 1位。位。按上述規(guī)則實現(xiàn)的按上述規(guī)則實現(xiàn)的除法器，有什么問題？除法器，有什么問題？相同位數(shù)的除法，對于不同的值，由于可相同位數(shù)的除法，對于不同的值，由于可能有恢復(fù)余數(shù)過程，運(yùn)算步數(shù)不統(tǒng)一?？刂破鲗嵞苡谢謴?fù)余數(shù)過程，運(yùn)算步數(shù)不統(tǒng)一?？刂破鲗崿F(xiàn)困難！（回憶：乘法運(yùn)算器里的步數(shù)計數(shù)器）現(xiàn)困難?。ɑ貞洠撼朔ㄟ\(yùn)算器里的步數(shù)計數(shù)器）30設(shè)某步得到余數(shù)設(shè)某步得到余數(shù)R Ri i 0 0，得到下步除法的新余，得到下步除法的新余數(shù)數(shù)R Ri+1i+1： R Ri+1i+1 = 2 R = 2 Ri i -

26、|B| - |B|若若R Ri i是假余數(shù)，即是假余數(shù)，即R Ri i00，要得到下步除法的新，要得到下步除法的新余數(shù)余數(shù)R Ri+1i+1，要先恢復(fù)余數(shù)，而后左移一位再減，要先恢復(fù)余數(shù)，而后左移一位再減|B|B|才能得到新余數(shù)。即：才能得到新余數(shù)。即： R Ri+1i+1 = 2(R = 2(Ri i + |B|) - |B| + |B|) - |B|將上式變換一下，得：將上式變換一下，得： R Ri+1i+1 = 2 R = 2 Ri i + |B| + |B|去掉恢復(fù)步！去掉恢復(fù)步！加減交替法加減交替法31若某步除法若某步除法R Ri i00，要得到下步除法的新余數(shù)，要得到下步除法的新余

27、數(shù)R Ri+1i+1，不必恢復(fù)余數(shù)，只要將不必恢復(fù)余數(shù)，只要將R Ri i視為余數(shù)，左移一位，再加視為余數(shù)，左移一位，再加上上|B|B|就得到新余數(shù)就得到新余數(shù)R Ri+1i+1。即：。即：本次余數(shù)為本次余數(shù)為正正，下步除法作，下步除法作減減法；（夠減，商上法；（夠減，商上1 1）本次余數(shù)為本次余數(shù)為負(fù)負(fù)，下步除法作，下步除法作加加法。法。 （不夠減，商上（不夠減，商上0 0）2. 加減交替法加減交替法例例3.36 設(shè)被除數(shù)設(shè)被除數(shù)X=0.1011，除數(shù)，除數(shù)Y=0.1101，用加減交替法求，用加減交替法求X/Y。 -Y補(bǔ)補(bǔ)=11.0011,計算過程如下計算過程如下:0 0 1 0 1 1 0

28、 0 0 0 0 開始情形1 1 0 0 1 1 +-Y補(bǔ)1 1 1 1 1 0 0 0 0 0 0 不夠減,商上01 1 1 1 0 0 0 0 0 0 0 左移0 0 1 1 0 1 +Y0 0 1 0 0 1 0 0 0 0 1 夠減,商上10 1 0 0 1 0 0 0 0 1 0 左移1 1 0 0 1 1 +-Y補(bǔ)0 0 0 1 0 1 0 0 0 1 1 夠減,商上10 0 1 0 1 0 0 0 1 1 0 左移 1 1 0 0 1 1 +-Y補(bǔ)1 1 1 1 0 1 0 0 1 1 0 不夠減,商上01 1 1 0 1 0 0 1 1 0 0 左移0 0 1 1 0 1 +Y

29、0 0 0 1 1 1 0 1 1 0 1 夠減,商上1+)+)+)+)+)被除數(shù)(余數(shù)R) （被除數(shù))(商） 操作說明余數(shù) 商X/Y=0.1101, 余數(shù)=0.00000111余數(shù)寄存器余數(shù)寄存器(A)(A)中開始時存放被除數(shù)的絕對值，以中開始時存放被除數(shù)的絕對值，以后將存放各次余數(shù)，取雙符號位。后將存放各次余數(shù)，取雙符號位。除數(shù)寄存器除數(shù)寄存器(B)(B)存放除數(shù)的絕對值，取雙符號位。存放除數(shù)的絕對值，取雙符號位。商寄存器商寄存器(C)(C)同同來存放商及初始被除數(shù)低位數(shù)值（被除數(shù)位數(shù)可以來存放商及初始被除數(shù)低位數(shù)值（被除數(shù)位數(shù)可以是除數(shù)的兩倍），取單符號位。是除數(shù)的兩倍），取單符號位。將

30、被除數(shù)將被除數(shù)X X視為初始余數(shù)視為初始余數(shù)R R0 0，根據(jù)，根據(jù)R R0 0符號位正（絕對符號位正（絕對值），令商符為值），令商符為0 0，正式的商符以后再置入。，正式的商符以后再置入。第一第一步步為為-Y-Y。商值則根據(jù)余數(shù)商值則根據(jù)余數(shù)R Ri i的符號來決定，正則商上的符號來決定，正則商上1 1，求下，求下一位商的辦法是余數(shù)左移一位再減去除數(shù)；當(dāng)余數(shù)一位商的辦法是余數(shù)左移一位再減去除數(shù)；當(dāng)余數(shù)為負(fù)則商上為負(fù)則商上0 0，求下一位商的辦法是余數(shù)左移一位，求下一位商的辦法是余數(shù)左移一位再加上除數(shù)。左移位時末位補(bǔ)再加上除數(shù)。左移位時末位補(bǔ)0 0。最后一步最后一步操作：如果要求得操作：如果要

31、求得n n位商（不含符號位），位商（不含符號位），則需作則需作n n步步“左移左移- -加減加減”循環(huán)；若第循環(huán)；若第n n步步余數(shù)為負(fù)余數(shù)為負(fù)，則需增加一步恢復(fù)余數(shù)，增加的這一步不移位。則需增加一步恢復(fù)余數(shù)，增加的這一步不移位。343.4.2 3.4.2 提高除法運(yùn)算速度的方法舉例提高除法運(yùn)算速度的方法舉例 1. 跳0跳1除法 提高規(guī)格化小數(shù)絕對值相除速度的算法?？筛鶕?jù)余數(shù)前幾位代碼值再次求得幾位同為1或0的商。其規(guī)則是：(1) 如果余數(shù)R0，且R的高K個數(shù)位均數(shù)0，則本次直接得商1，后跟K-1個0。R左移K位后，減去除數(shù)Y，得新余數(shù)。(2) 如果余數(shù)R0，且R的高K個數(shù)位均為1，則本次商為

32、0，后跟K-1個1，R左移K位后，加上除數(shù)Y，得新余數(shù)。(3) 不滿足(1)和(2)中條件時，按一位除法上商。 35例3.37 設(shè)X=0.1010000,Y=0.1100011,求X/Y。解 ：略 2. 除法運(yùn)算通過乘法操作來實現(xiàn)在計算機(jī)運(yùn)行時，執(zhí)行乘法指令的幾率比除法高。某些CPU中設(shè)置有專門的乘法器，一般沒有專用除法器，在這種情況下，利用乘法來完成除法運(yùn)算可提高速度。36設(shè)X為被除數(shù)，Y為除數(shù)，按下式完成X/Y。式中Fi(0ir)為迭代系數(shù)，如果迭代幾次后，可以使分母YF0F1Fr1，則分子即為商：XF0F1Fr 因此，問題是如何找到一組迭代系數(shù)，使分母很快趨近于1。若X和Y為規(guī)格化正小數(shù)

33、二進(jìn)制代碼，可寫成： Y=1- (01/2) rrFFFYFFFXYX 101037如果取 F0=1+，則第一次迭代結(jié)果：Y0=YF0=(1-)(1+)=1-2取F1=1+2，則第二次迭代結(jié)果：Y1=Y0F1=(1-2)(12)=1-4 取Fi=1+2i，則第i+1次迭代結(jié)果：Yi=Yi-1Fi=(1-2i)(1+2i)=1-2i+1當(dāng)i增加時，Y將很快趨近于1，其誤差為2i+1。實際上求得Fi的過程很簡單，即 Fi=1+2i=2-1+2i=2-(1-2i)=2-Yi-1Fi就是(-Yi-1)的補(bǔ)碼(0ir)。 38例3.38 設(shè)X=0.1000,Y=0.1011則=1-Y=0.0101，F(xiàn)0

34、=1+=1.0101分子分母分別進(jìn)行乘法運(yùn)算。F1=2-Y0=2-0.1110=1.0010 分母趨近于1所以1110. 01011. 00101. 11011. 00101. 11000. 00000FYFXYX1111. 01100. 00010. 11110. 00010. 11011. 0101011FYFXYX1100. 0111XYXYX393.5 浮點數(shù)的運(yùn)算方法浮點數(shù)的表示形式（以浮點數(shù)的表示形式（以2 2為底）：為底）： N = N = M M 2 2E E其中，其中，M M為浮點數(shù)的為浮點數(shù)的尾數(shù)尾數(shù)，一般為絕對值，一般為絕對值小于小于1 1的規(guī)格化二進(jìn)制小數(shù)用原碼或補(bǔ)碼形

35、的規(guī)格化二進(jìn)制小數(shù)用原碼或補(bǔ)碼形式表示；式表示；E E為浮點數(shù)的為浮點數(shù)的階碼階碼，一般是用移碼，一般是用移碼或補(bǔ)碼表示的整數(shù)?；蜓a(bǔ)碼表示的整數(shù)。 403.5.3.5.1 1 浮點數(shù)的加減法運(yùn)算兩數(shù)首先均為規(guī)格化數(shù)，在進(jìn)行規(guī)格化浮點數(shù)兩數(shù)首先均為規(guī)格化數(shù)，在進(jìn)行規(guī)格化浮點數(shù)的加減運(yùn)算需經(jīng)過五步完成：的加減運(yùn)算需經(jīng)過五步完成：（1 1）對階操作：低階向高階補(bǔ)齊，使階碼相等；）對階操作：低階向高階補(bǔ)齊，使階碼相等；（2 2）尾數(shù)運(yùn)算：階碼對齊后直接對尾數(shù)運(yùn)算；）尾數(shù)運(yùn)算：階碼對齊后直接對尾數(shù)運(yùn)算；（3 3）結(jié)果規(guī)格化：對運(yùn)算結(jié)果進(jìn)行規(guī)格化處理；）結(jié)果規(guī)格化：對運(yùn)算結(jié)果進(jìn)行規(guī)格化處理； ( (使補(bǔ)碼

36、尾數(shù)的最高位和尾數(shù)符號相反使補(bǔ)碼尾數(shù)的最高位和尾數(shù)符號相反) ) （4 4）舍入操作：丟失位進(jìn)行）舍入操作：丟失位進(jìn)行0 0舍舍1 1入或恒置入或恒置1 1處理；處理；（5 5）判斷溢出：判斷階碼是否溢出，下溢則將運(yùn)）判斷溢出：判斷階碼是否溢出，下溢則將運(yùn) 算結(jié)果置算結(jié)果置0 0（機(jī)器零）（機(jī)器零），上溢則溢出中斷。，上溢則溢出中斷。舉例說明如下：(1)對階運(yùn)算對階運(yùn)算( (小階向大階對齊小階向大階對齊) )尾數(shù)為原碼時尾數(shù)為原碼時, ,尾數(shù)右移尾數(shù)右移, ,符號位不動符號位不動, ,最高位補(bǔ)最高位補(bǔ)0 0尾數(shù)為補(bǔ)碼時尾數(shù)為補(bǔ)碼時, ,尾數(shù)右移尾數(shù)右移, ,符號也移位符號也移位, ,最高位補(bǔ)符

37、最高位補(bǔ)符號位號位例如：例如： 求求 =? =?小階對大階小階對大階舍掉的是舍掉的是如大階對小階如大階對小階則舍掉的是則舍掉的是21001. 021101. 0333321111. 020010. 021101. 021101. 021001. 020100. 020001.0321100. 03332101110. 02001010. 021001. 0(2)(2)尾數(shù)的加減運(yùn)算尾數(shù)的加減運(yùn)算(3)(3)規(guī)格化：原碼尾數(shù)值高位為規(guī)格化：原碼尾數(shù)值高位為1 1，補(bǔ)碼尾數(shù)值高位與符號相反，補(bǔ)碼尾數(shù)值高位與符號相反 (4)(4)舍入操作：舍入操作：0 0舍舍1 1入入 或或 恒置恒置1 1例1：求

38、=?0舍1入后為恒置1例2：求 =?0舍1入后為恒置1(5)判斷結(jié)果的正確性判斷結(jié)果的正確性( (即結(jié)果的階碼是否溢出即結(jié)果的階碼是否溢出) )21001.021001.033332101101.02001001.021001.021010.021001.03321100.0321011.0321011.0321011.0南華大學(xué)計算機(jī)學(xué)院43規(guī)格化浮點數(shù)加減運(yùn)算流程。（規(guī)格化浮點數(shù)加減運(yùn)算流程。（P P9191）44例例3.39 3.39 兩浮點數(shù)相加，求兩浮點數(shù)相加，求X+YX+Y。 已知：已知：X X2 2010 010 0.11011011 0.11011011， y y2 2100

39、100 (-0.10101100) (-0.10101100)計算過程：計算過程：解：解：X X和和Y Y在機(jī)器中的浮點補(bǔ)碼表示形式為在機(jī)器中的浮點補(bǔ)碼表示形式為( (雙符號位雙符號位) )： 階符階符 階碼階碼 數(shù)符數(shù)符 尾數(shù)尾數(shù) X X： 0 0 0 1 0 0 0 1 1 0 1 1 0 1 10 0 0 1 0 0 0 1 1 0 1 1 0 1 1 Y Y： 0 0 1 0 0 1 1 0 1 0 1 0 1 0 00 0 1 0 0 1 1 0 1 0 1 0 1 0 0（1 1）對階操作對階操作 階差階差EEExEx補(bǔ)補(bǔ)+-+-E EY Y 補(bǔ)補(bǔ)=00010+11100=1111

40、0=00010+11100=11110 X X階碼小，階碼小，MxMx右移右移2 2位，保留階碼位，保留階碼E E0010000100。 MxMx補(bǔ)補(bǔ)=00 00 110 110 =00 00 110 110 1111 下劃線上的數(shù)是右移出去而保留的附加位。下劃線上的數(shù)是右移出去而保留的附加位。（2 2）尾數(shù)相加尾數(shù)相加 MxMx補(bǔ)補(bǔ)+M MY Y 補(bǔ)補(bǔ)=0000110110=00001101101111+1101010100=1110001010+1101010100=11100010101111。（3 3）規(guī)格化操作規(guī)格化操作 左規(guī)，移左規(guī)，移1 1位，結(jié)果：位，結(jié)果：1100010101

41、 1100010101 1010；階碼；階碼-1-1，E E0001100011。 45（4 4）舍入）舍入附加位最高位為附加位最高位為1 1，在所得結(jié)果的最低，在所得結(jié)果的最低位位+1+1。得新結(jié)果：得新結(jié)果： MM補(bǔ)補(bǔ)=1100010110=1100010110， M M： - 0- 01110101011101010。（5 5）判溢出）判溢出 階碼符號位為階碼符號位為0000，故不溢出。，故不溢出。最終結(jié)果為：最終結(jié)果為： X+Y=2X+Y=2011 011 (-0 (-011101010)11101010)浮點數(shù)的乘除浮點數(shù)的乘除: :階碼為兩數(shù)階碼之和、差，其尾數(shù)應(yīng)為兩數(shù)的尾數(shù)之積、

42、商。結(jié)果的處理：結(jié)果的處理：結(jié)果必須進(jìn)行規(guī)格化、舍入和判溢出等操作。 3.5.2 浮點數(shù)浮點數(shù)的乘除法運(yùn)算的乘除法運(yùn)算1. 浮點數(shù)的階碼運(yùn)算階碼運(yùn)算：+1，-1，兩階碼求和以及兩階碼求差四種。移碼的運(yùn)算規(guī)則：移碼的定義為：X移=2n+X -2nX2n X移+Y移=2n+X+2n+Y=2n+(2n+(X+Y) =2n+X+Y移 結(jié)果的最高位多加了個1，要得到移碼形式的結(jié)果，需對結(jié)果的符號取反。根據(jù)補(bǔ)碼定義：Y補(bǔ)=2n+1+Y mod 2n+1 因此求階碼和(移碼表示)可用如下方式完成：X移+Y補(bǔ)=2n+X+2n+1+Y=2n+1+(2n+(X+Y) =X+Y移 mod 2n+1同理有 X移+-Y

43、補(bǔ)=X-Y移。執(zhí)行移碼加或減時，取加數(shù)或減數(shù)符號位的反碼（補(bǔ)碼）進(jìn)行運(yùn)算。即被加(減)數(shù)為移碼，加(減)數(shù)為補(bǔ)碼。直接用移碼實現(xiàn)求階碼之和 使用雙符號位的階碼相加減，并規(guī)定移碼（被加數(shù)或被減數(shù)）的第二個符號位，即最高符號位恒用0參加加減運(yùn)算。當(dāng)結(jié)果的最高符號位為0時，表明沒有溢出。低位符號位為1，表明結(jié)果為正；為0時，表明結(jié)果為負(fù)。溢出條件是結(jié)果的最高符號位為1。 溢出時，當(dāng)?shù)臀环栁粸?時結(jié)果上溢，為1時結(jié)果下溢。判定溢出的方法例：階碼用4位表示，其范圍為-8到+7 。 （1）當(dāng)X=+011，Y=+110時，則有X移=01011，Y補(bǔ)=00110， -Y補(bǔ)=11010階碼加 X+Y移= X移

44、+Y補(bǔ) =01011+ 00110=10001，結(jié)果上溢階碼減 X-Y移= X移+-Y補(bǔ) =01011+ 11010=00101，結(jié)果正確，為-3（2）當(dāng)X=-011，Y=-110時，則有X移=00101，Y補(bǔ)=11010， -Y補(bǔ)=00110階碼加 X+Y移= X移+Y補(bǔ) =00101+ 11010=11111，結(jié)果下溢階碼減 X-Y移= X移+-Y補(bǔ) =00101+ 00110=01011，結(jié)果正確，為+32. 浮點數(shù)的舍入處理計算機(jī)中，浮點數(shù)的尾數(shù)有確定的位數(shù)，若浮點數(shù)的運(yùn)算結(jié)果超過給定的位數(shù)，要進(jìn)行去除多余位數(shù)的處理。處理的原則是使本次處理所造成的誤差以及按此原則產(chǎn)生的累計誤差都比較小

45、。 無條件地丟掉正常尾數(shù)最低位之后的全部數(shù)值。這種辦法被稱為截斷處理，其好處是處理簡單，缺點是影響結(jié)果的精度。 保留右移中移出的若干高位的值，然后再按某種規(guī)則用這些位上的值修正尾數(shù)。這種處理方法被稱為舍入處理。舍入方法： 只要尾數(shù)最低位為1，或移出去的幾位中有1，就把尾數(shù)的最低位置1，否則仍保持原有的0值?；蛘卟捎酶啽愕姆椒ǎ醋畹臀缓阒?的方法。 0舍1入法(相當(dāng)于十進(jìn)制中的四舍五入法)，即當(dāng)丟失的最高位的值為1時，把這個1加到最低數(shù)值位上進(jìn)行修正，否則舍去丟失的各位的值，其缺點是要多進(jìn)行一次加法運(yùn)算。例3.40 設(shè)有5位數(shù)(其中有一附加位)，用原碼或補(bǔ)碼表示，舍入后保留4位結(jié)果。（0舍1

46、入法）設(shè)： X原=0.11011 舍入后X原=0.1110X原=0.11100 舍入后X原=0.1110X補(bǔ)=1.00101 舍入后X補(bǔ)=1.0011X補(bǔ)=1.00100 舍入后X補(bǔ)=1.0010舍入后產(chǎn)生了誤差，但誤差值小于末位的權(quán)值。3. 浮點乘法運(yùn)算步驟舉例說明浮點乘法的運(yùn)算步驟：例3.41 階碼4位(移碼)，尾數(shù)8位(補(bǔ)碼，含1符號位)，階碼以2為底。運(yùn)算結(jié)果仍取8位尾數(shù)。 設(shè)：X=2-50.1110011, Y=23(-0.1110010)運(yùn)算過程中階碼取雙符號位。(1) 求乘積的階碼。乘積的階碼為兩數(shù)階碼之和。 EX+EY移=EX移+EY補(bǔ)=00011+00011=00110(2)

47、 尾數(shù)相乘。用定點數(shù)相乘的辦法， XY補(bǔ)=1.0011001 1001010 (尾數(shù)部分) 高位部分高位部分低位部分低位部分(3) 規(guī)格化處理。本例尾數(shù)已規(guī)格化，不需要再處理。如未規(guī)格化，需左規(guī)。(4) 舍入。尾數(shù)(乘積)低位部分的最高為1，需要舍入，在乘積高位部分的最低位加1，因此 XY補(bǔ)=1.0011010 (尾數(shù)部分)(5) 判溢出。階碼未溢出，故結(jié)果為正確。XY=2-2(-0.1100110) 在求乘積的階碼(即兩階碼相加)時，有可能產(chǎn)生上溢或下溢的情況；在進(jìn)行規(guī)格化處理時，有可能產(chǎn)生下溢。 4. 浮點數(shù)乘法運(yùn)算(階碼的底為8或16)N=8EM 或 N=16EM階碼E和尾數(shù)M還都是用二

48、進(jìn)制表示的，其運(yùn)算規(guī)則與階碼以2為底基本相同，但關(guān)于對階和規(guī)格化操作有新的相應(yīng)規(guī)定。l當(dāng)階碼以8為底時，只要尾數(shù)滿足1/8M1或 -1M-1/8就是規(guī)格化數(shù)。執(zhí)行對階和規(guī)格化操作時，每當(dāng)階碼的值增或減1，尾數(shù)要相應(yīng)右移或左移三位。 l當(dāng)階碼以16為底時，只要尾數(shù)滿足1/16M1或 -1M-1/16就是規(guī)格化數(shù)。執(zhí)行對階和規(guī)格化操作時，階碼的值增或減1，尾數(shù)必須移四位。5. 浮點數(shù)除法運(yùn)算步驟（1 1）求商的階碼尾數(shù)調(diào)整：保證尾數(shù)調(diào)整：保證M MX XM MY Y階碼相加減階碼相加減（2 2）尾數(shù)相除）尾數(shù)相除（3 3）規(guī)格化（4 4）舍入（5 5）判溢出583.6 3.6 運(yùn)算部件運(yùn)算部件 1

49、. 1. 定點運(yùn)算部件定點運(yùn)算部件 定點運(yùn)算部件由定點運(yùn)算部件由算術(shù)邏輯運(yùn)算部件算術(shù)邏輯運(yùn)算部件ALUALU、若、若干個干個寄存器寄存器、移位電路移位電路、計數(shù)器計數(shù)器、門電路門電路等組等組成。成。 ALUALU部件主要完成加減法部件主要完成加減法算術(shù)運(yùn)算算術(shù)運(yùn)算及及邏輯邏輯運(yùn)算運(yùn)算。59602 2浮點運(yùn)算部件浮點運(yùn)算部件 通常通常由由階碼運(yùn)算部件階碼運(yùn)算部件和和尾數(shù)運(yùn)算部件尾數(shù)運(yùn)算部件組成組成，其各自的結(jié)構(gòu)與定點運(yùn)算部件相似。其各自的結(jié)構(gòu)與定點運(yùn)算部件相似。但但階碼部階碼部分僅執(zhí)行加減法運(yùn)算分僅執(zhí)行加減法運(yùn)算。其尾數(shù)部分則執(zhí)行加減其尾數(shù)部分則執(zhí)行加減乘除運(yùn)算乘除運(yùn)算，左規(guī)時有時需要左移多位。

50、為加速，左規(guī)時有時需要左移多位。為加速移位過程，有的機(jī)器設(shè)置了可移動多位的電路移位過程，有的機(jī)器設(shè)置了可移動多位的電路。3.7 3.7 數(shù)據(jù)校驗碼數(shù)據(jù)校驗碼 計算機(jī)系統(tǒng)中的數(shù)據(jù)，在讀寫、存取和傳送的過程中可計算機(jī)系統(tǒng)中的數(shù)據(jù)，在讀寫、存取和傳送的過程中可能產(chǎn)生錯誤。能產(chǎn)生錯誤。為減少和避免這類錯誤，一方面是精心設(shè)計為減少和避免這類錯誤，一方面是精心設(shè)計各種電路，提高計算機(jī)硬件的可靠性；另一方面是在數(shù)據(jù)各種電路，提高計算機(jī)硬件的可靠性；另一方面是在數(shù)據(jù)編碼上找出路，編碼上找出路，即采用某種編碼法，通過少量的附加電路，即采用某種編碼法，通過少量的附加電路，使之能發(fā)現(xiàn)某些錯誤，甚至能確定出錯位置，進(jìn)

51、而實現(xiàn)自使之能發(fā)現(xiàn)某些錯誤，甚至能確定出錯位置，進(jìn)而實現(xiàn)自動改錯的能力。動改錯的能力。 數(shù)據(jù)校驗碼數(shù)據(jù)校驗碼: :是一種常用的帶有發(fā)現(xiàn)某些錯誤或自動改是一種常用的帶有發(fā)現(xiàn)某些錯誤或自動改錯能力的數(shù)據(jù)編碼方法。錯能力的數(shù)據(jù)編碼方法。( (查錯與糾錯查錯與糾錯) ) 實現(xiàn)原理：是加進(jìn)一些實現(xiàn)原理：是加進(jìn)一些冗余碼冗余碼，使合法數(shù)據(jù)編碼出錯變，使合法數(shù)據(jù)編碼出錯變成非法數(shù)據(jù)來發(fā)現(xiàn)或改正數(shù)據(jù)。成非法數(shù)據(jù)來發(fā)現(xiàn)或改正數(shù)據(jù)。常用的數(shù)據(jù)校驗碼：常用的數(shù)據(jù)校驗碼：奇偶校驗碼、海明校驗碼和循環(huán)冗余校驗奇偶校驗碼、海明校驗碼和循環(huán)冗余校驗碼。碼。 采用采用冗余校驗冗余校驗方法：方法： 即在基本的有效數(shù)據(jù)外，再擴(kuò)即

52、在基本的有效數(shù)據(jù)外，再擴(kuò)充部分位，增加部分（冗余部分）被稱為充部分位，增加部分（冗余部分）被稱為校校驗位驗位。將校驗位與數(shù)據(jù)位一起按某種規(guī)則編。將校驗位與數(shù)據(jù)位一起按某種規(guī)則編碼，寫入存儲器或向外發(fā)送。當(dāng)從存儲器讀碼，寫入存儲器或向外發(fā)送。當(dāng)從存儲器讀出或接收到外部傳入的代碼時，再按相應(yīng)的出或接收到外部傳入的代碼時，再按相應(yīng)的規(guī)則進(jìn)行判讀。若不符合約定的規(guī)則，則表規(guī)則進(jìn)行判讀。若不符合約定的規(guī)則，則表示出現(xiàn)錯誤。根據(jù)錯誤的特征進(jìn)行修正恢復(fù)。示出現(xiàn)錯誤。根據(jù)錯誤的特征進(jìn)行修正恢復(fù)。幾個名詞概念幾個名詞概念碼字：由若干代碼組成的一個字。碼字：由若干代碼組成的一個字。如如84218421碼中碼中 0

53、110 0110（ 6 6 ），），01110111（ 7 7 ）距離：兩個碼字之間不同的代碼個數(shù)。距離：兩個碼字之間不同的代碼個數(shù)。 8421 8421碼中，最小的距離為碼中，最小的距離為1 1，如，如00000000和和 0001 0001、00100010和和00110011等；最大距離為等；最大距離為4 4， 如如01110111和和10001000。碼距碼距( (最小碼距最小碼距) )：一種碼制中任意兩個碼字間的最?。阂环N碼制中任意兩個碼字間的最小距離。距離。（合法碼到合法碼變動的最小位數(shù)合法碼到合法碼變動的最小位數(shù)）84218421碼的碼距為碼的碼距為1 1。碼距為。碼距為1 1，

54、即不能查錯也不，即不能查錯也不能糾錯。碼距越大，查錯、糾錯能力越強(qiáng)。能糾錯。碼距越大，查錯、糾錯能力越強(qiáng)。碼距與檢糾錯的關(guān)系為了檢測e個誤碼，要求最小碼距d0應(yīng)滿足： d0 e+1 為了糾正t個誤碼，要求最小碼d0距應(yīng)滿足： d0 2t+1 為了糾正t個誤碼，同時能檢測e個誤碼(et)，要求最小碼距d0應(yīng)滿足： d0 e+t+12/20/2022643.7.1 奇偶校驗碼 奇偶校驗碼是計算機(jī)中廣泛采用的檢查傳輸數(shù)奇偶校驗碼是計算機(jī)中廣泛采用的檢查傳輸數(shù)據(jù)準(zhǔn)確性的方法。據(jù)準(zhǔn)確性的方法。奇偶校驗的原理奇偶校驗的原理是：是：在每組數(shù)據(jù)信息上附加一個校驗位，使碼距由在每組數(shù)據(jù)信息上附加一個校驗位，使碼

55、距由1 1增增加到加到2 2（合法碼到合法碼變動的最小位數(shù)為合法碼到合法碼變動的最小位數(shù)為2 2）。）。若編碼若編碼中有奇數(shù)個二進(jìn)制位出錯了，這個碼將變成非法編碼。中有奇數(shù)個二進(jìn)制位出錯了，這個碼將變成非法編碼。 如果采用奇校驗，則這組數(shù)據(jù)加上校驗碼位后如果采用奇校驗，則這組數(shù)據(jù)加上校驗碼位后數(shù)據(jù)中數(shù)據(jù)中1 1的個數(shù)應(yīng)為奇數(shù)個。奇校驗位形成公式的個數(shù)應(yīng)為奇數(shù)個。奇校驗位形成公式: : C =XC =X0 0 X X1 1 X Xn-1n-1 如果采用偶校驗，則這組數(shù)據(jù)加上校驗碼位后如果采用偶校驗，則這組數(shù)據(jù)加上校驗碼位后數(shù)據(jù)中數(shù)據(jù)中1 1的個數(shù)應(yīng)為偶數(shù)個。偶校驗位形成公式的個數(shù)應(yīng)為偶數(shù)個。偶校

56、驗位形成公式: : C =XC =X0 0 X X1 1 X Xn-1n-1下面給出對幾個字節(jié)值的奇偶校驗的編碼結(jié)果：下面給出對幾個字節(jié)值的奇偶校驗的編碼結(jié)果： 數(shù)據(jù)數(shù)據(jù) 奇校驗的編碼奇校驗的編碼 偶校碼的編碼偶校碼的編碼 00000000 00000000 l l00000000 00000000 0 00000000000000000 010l0l00 010l0l00 0 0010l0100 010l0100 l l01010l0001010l00 01ll1lll 01ll1lll 0 0011l1111 011l1111 1 10l111l1l0l111l1l其中，最高一位為校驗位，

57、其余低八位為數(shù)據(jù)其中，最高一位為校驗位，其余低八位為數(shù)據(jù)位。從中可以看到，校驗位的值取位。從中可以看到，校驗位的值取O O還是還是1 1，是由，是由數(shù)據(jù)位中數(shù)據(jù)位中1 1的個數(shù)決定的。的個數(shù)決定的。缺點缺點: :這種方案只能發(fā)現(xiàn)一這種方案只能發(fā)現(xiàn)一位錯或奇數(shù)個位錯，但不能位錯或奇數(shù)個位錯，但不能確定是哪一位錯，也不能發(fā)確定是哪一位錯，也不能發(fā)現(xiàn)偶數(shù)個位錯?，F(xiàn)偶數(shù)個位錯。優(yōu)點優(yōu)點: :該方案還是有很好的該方案還是有很好的實用價值。實用價值。12345678DDDDDDDDEV偶校驗偶校驗位形成位形成奇偶校驗的特點：奇偶校驗的特點：1、奇偶校驗碼使數(shù)據(jù)的碼距為、奇偶校驗碼使數(shù)據(jù)的碼距為2，因而可檢

58、出數(shù)，因而可檢出數(shù)據(jù)傳送過程中奇數(shù)個數(shù)位出錯的情況（一位變動據(jù)傳送過程中奇數(shù)個數(shù)位出錯的情況（一位變動會使校驗位改變，會使校驗位改變， d0 e+1 =2）；）；2、實際中兩位同時出錯的概率極低，奇偶校驗法、實際中兩位同時出錯的概率極低，奇偶校驗法簡便可靠易行，但它只能發(fā)現(xiàn)錯誤，卻不知錯在簡便可靠易行，但它只能發(fā)現(xiàn)錯誤，卻不知錯在何處，因而不能自動糾正。何處，因而不能自動糾正。3、 奇偶校驗碼是一種開銷最小，能發(fā)現(xiàn)數(shù)據(jù)代碼奇偶校驗碼是一種開銷最小，能發(fā)現(xiàn)數(shù)據(jù)代碼中一位出錯情況的編碼。中一位出錯情況的編碼。常用于存儲器讀寫檢查，或常用于存儲器讀寫檢查，或ASCII字符傳送字符傳送過程中的檢查。過

59、程中的檢查。3.7.2 海明校驗碼海明校驗碼 海明校驗碼是海明校驗碼是Richard HammingRichard Hamming于于19501950年提出的，目前仍年提出的，目前仍廣泛使用的一種編碼方法。廣泛使用的一種編碼方法。1 1、原理、原理（1 1）特點：能檢測出）特點：能檢測出兩位同時出錯兩位同時出錯、亦能檢測出一位出錯并能自亦能檢測出一位出錯并能自動糾錯。動糾錯。( (碼距碼距d d0 0 e+t+1=2+1+1=4 e+t+1=2+1+1=4) )（2 2）實現(xiàn)原理：）實現(xiàn)原理： 在在k k個數(shù)據(jù)位個數(shù)據(jù)位之外加上之外加上r r個校驗位個校驗位，從而形成一個，從而形成一個k+rk

60、+r位位的的新碼字新碼字，當(dāng)，當(dāng)某一位出錯某一位出錯后，就會后，就會引起相關(guān)的幾個（引起相關(guān)的幾個（ d d0 0 個）校驗位的值發(fā)生變化個）校驗位的值發(fā)生變化，從而達(dá)到檢錯、糾錯的目的。，從而達(dá)到檢錯、糾錯的目的。 能檢測與自動糾正一位錯，并發(fā)現(xiàn)兩位錯，校驗位能檢測與自動糾正一位錯，并發(fā)現(xiàn)兩位錯，校驗位r r與數(shù)與數(shù)據(jù)位據(jù)位k k應(yīng)滿足下述關(guān)系：應(yīng)滿足下述關(guān)系：2r-1k+r r ( (一位出錯并糾錯且發(fā)現(xiàn)兩位錯一位出錯并糾錯且發(fā)現(xiàn)兩位錯 d0 e+t+1=2+1+1=4) )數(shù)據(jù)位數(shù)據(jù)位k k與校驗位與校驗位r r的對應(yīng)關(guān)系：的對應(yīng)關(guān)系： 2 2、編碼規(guī)則、編碼規(guī)則 若海明碼的最高位號為若