1、第3章 運算方法和運算部件1、數據及其表示、數據及其表示 數制的一般概念，數制之間的相互轉換數制的一般概念，數制之間的相互轉換2、數據校驗碼、數據校驗碼 常用編碼（了解）常用編碼（了解）3、定點數加減法運算及電路實現、定點數加減法運算及電路實現補碼的加減法運算，溢出補碼的加減法運算，溢出4、定點數乘除運算和電路實現、定點數乘除運算和電路實現原碼、補碼，布斯算法，原碼恢復余數、不恢復余數原碼、補碼，布斯算法，原碼恢復余數、不恢復余數5、快速乘除法運算技術和電路實現、快速乘除法運算技術和電路實現布斯高基乘法，陣列乘法器，陣列除法器布斯高基乘法，陣列乘法器，陣列除法器6、浮點數四則運算以及實現、浮點

2、數四則運算以及實現加減乘除加減乘除計算機計算機中的數據中的數據1 1、進位計數制、進位計數制進位計數制進位計數制：用少量的數字符號，按先后次序把它們排成數位，：用少量的數字符號，按先后次序把它們排成數位，由低到高進行計數，計滿進位，這樣的方法稱為進位計數制由低到高進行計數，計滿進位，這樣的方法稱為進位計數制基數：基數：進位制基本特征數，即所用到的數字符號個數進位制基本特征數，即所用到的數字符號個數例如：例如：1010進制進制 ：09 09 十個數碼表示，基數為十個數碼表示，基數為1010再如：再如：1616進制有進制有0909，ABCDEFABCDEF，共，共1616個符號。個符號。權（位值）

3、：權（位值）：進位制中各位進位制中各位“1”1”所表示的值為該位的權所表示的值為該位的權常見的進位制：常見的進位制： 2 2，8 8，1010，1616進制，進制，M M進制進制十進制數的多項式表示十進制數的多項式表示: :N10=dn-1 10n-1 + dn-2 10n-2 + d1 101 + d0 100 + d-1 10-1 + d-2 10-2 + d-m 10-M m,nm,n為正整數為正整數, ,其中其中n n為整數位數；為整數位數；m m為小數位數。為小數位數。DiDi表示第表示第i i位的系數位的系數,10,10i i稱為該位的權稱為該位的權. .1、十進制(Decimal

4、)基數基數:10; 符號符號:0,1,2,3,4,5,6,7,8,9計算規律計算規律:“逢十進一逢十進一 ”或或“借一當十借一當十”例如例如:一個十進制數一個十進制數123.45的表示的表示123.45 =1102+ 2101+ 3 100 + 410-1+ 510-2注：等式左邊為并列表示法等式右邊為多項式表示法注：等式左邊為并列表示法等式右邊為多項式表示法2 2、二進制、二進制( (B Binary)inary)二進制的多項式表示二進制的多項式表示:N2=dn-1 2n-1 + dn-2 2n-2 + d1 21 + d0 20 + d-1 2-1 + d-2 2-2 + d-m 2-m其

5、中其中n為整數位數；為整數位數；m為小數位數。為小數位數。Di表示第表示第i位的系數位的系數,2i稱為該位的權稱為該位的權. 基數基數:2符號符號:0,1計算規律計算規律:逢二進一或借一當二逢二進一或借一當二3、十六進制(Hexadecimal)二進制的多項式表示二進制的多項式表示: :N16=dn-1 16n-1 + dn-2 16n-2 + d1 161 + d0 160 + d-1 16-1 + d-2 16-2 + d-m 16-m 其中其中n為整數位數；為整數位數；m為小數位數。為小數位數。Di表示第表示第i位的系數位的系數,16i稱稱為該位的權為該位的權.基數基數: :1616符號

6、符號: :0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F計算規律計算規律: :逢十六進一或借一當十六逢十六進一或借一當十六例如十六進制數例如十六進制數 (2C7.1F)16的表示的表示 (2C7.1F)16=2 162+ 12 161+ 7 160+ 1 16-1+ 15 16-24 、進位計數制之間的轉換1）R進制轉換成十進制的方法進制轉換成十進制的方法按權展開法按權展開法:先寫成多項式先寫成多項式,然后計算十進制結果然后計算十進制結果.N= dn-1dn-2 d1d0d-1d-2 d-m=dn-1 Rn-1 +

7、dn-2 Rn-2 + d1 R1 + d0 R0 + d-1 R-1 + d-2 R-2 + d-m R-m例例: :寫出寫出(1101.01)(1101.01)2 2,(237),(237)8 8,(10D),(10D)1616的十進制數的十進制數(10D)16=1162+13160=256+13=269(1101.01)2=123+122+021+120+02-1+12-2 =8+4+1+0.25=13.25(237)8=282+381+780 =128+24+7=1592）十進制轉換成二進制方法）十進制轉換成二進制方法一般分為兩個方法一般分為兩個方法：方法1、整數部分的轉換 除除2取余

8、法（基數除法）取余法（基數除法） 小數部分的轉換 乘乘2取整法（基數乘法）取整法（基數乘法）方法2、減權定位法減權定位法除基取余法除基取余法：把給定的除以基數：把給定的除以基數,取余數作為最低位的系數取余數作為最低位的系數,然然后繼續將商部分除以后繼續將商部分除以 基數基數,余數作為次低位系數余數作為次低位系數,重復操作重復操作直至商為直至商為 0例如：用基數除法將例如：用基數除法將(327)10轉換成二進制數轉換成二進制數2 327 余數2 163 1 2 81 1 2 40 1 2 20 0 2 10 0 2 5 0 2 2 1 2 1 0 2 0 1 (327)(327)10 10 =(

9、101000111) =(101000111) 2 2 把給定的十進制小數乘以把給定的十進制小數乘以 2 ,2 ,取其整數作為二進制小數取其整數作為二進制小數的第一位的第一位, ,然后取小數部分繼續乘以然后取小數部分繼續乘以2,2,將所的整數部分作將所的整數部分作為第二位小數為第二位小數, ,重復操作直至得到所需要的二進制小數重復操作直至得到所需要的二進制小數例如例如: :將將(0.8125) (0.8125) 10 10 轉換成二進制小數轉換成二進制小數 整數部分整數部分 0.0.2 2 0.8125=1.625 10.8125=1.625 12 2 0.625 =1.25 10.625 =

10、1.25 12 2 0.25 =0.5 00.25 =0.5 02 2 0.5 =1 10.5 =1 1(0.8125) (0.8125) 10 10 =(0.1101) =(0.1101) 2 2乘基取整法乘基取整法(小數部分的轉換小數部分的轉換)例例:將將(0.2)10 10 轉換成二進制小數轉換成二進制小數整數部分整數部分 0 0.2 0.2 2 = 0.42 = 0.4 0 00.4 0.4 2 = 0.8 2 = 0.8 0 00.8 0.8 2 = 1.6 2 = 1.6 1 10.6 0.6 2 = 1.2 2 = 1.2 1 10.2 0.2 2 = 0.4 2 = 0.4 0

11、 00.4 0.4 2 = 0.8 2 = 0.8 0 00.8 0.8 2 = 1.6 2 = 1.6 1 10.6 0.6 2 = 1.2 2 = 1.2 1 1 (0.2)10 10 = 0.001100110011. 2 2 減權定位法減權定位法 將十進制數依次從二進制的最高位權值進行比較，若夠減則對應將十進制數依次從二進制的最高位權值進行比較，若夠減則對應位置位置1 1，減去該權值后再往下比較，若不夠減則對應位為，減去該權值后再往下比較，若不夠減則對應位為0 0，重復操作直，重復操作直至差數為至差數為0 0。 512 256 128 64 32 16 8 4 2 1512 256 1

12、28 64 32 16 8 4 2 1例如例如：將：將 (327)(327)10 10 轉換成二進制數轉換成二進制數 256327512256327512 327 - 256=71 1 256 327 - 256=71 1 256 71 128 0 128 71 128 0 128 71 - 64 =7 1 64 71 - 64 =7 1 64 7 32 0 32 7 32 0 32 7 16 0 16 7 16 0 16 7 8 0 8 7 8 0 8 7 - 4 =3 1 4 7 - 4 =3 1 4 3 2 =1 1 2 3 2 =1 1 2 1 1 =0 1 1 1 1 =0 1 1二

13、進制二進制( (B B) )轉換成八進制轉換成八進制( (Q Q) )例：例：(10110111 .01101) 2 2(10110111.01101) 2 2 =(267.32)8 8八進制八進制: 2 6 7 : 2 6 7 . . 3 2 3 2二進制二進制: 010 ,110 , 111 : 010 ,110 , 111 . 011 , 010 011 , 010二進制二進制: 10 ,: 10 ,110110 , , 111111 . . 011011 , 01 , 013）其它進制之間的直接轉換法）其它進制之間的直接轉換法八進制八進制( (Q Q) )轉換二進制轉換二進制( (B

14、B) )例如例如: (123.46 ) 8 8=(001,010,011 .100,110 ) 2 2 =(1010011.10011)2 2二進制二進制( (B B) )轉換成十六進制轉換成十六進制( (H H) )例例：(110110111 .01101) 2 2(10110111.01101) 2 2 =(1B7.68)1616十六進制十六進制: 1 B 7 : 1 B 7 . . 6 8 6 8二進制二進制: 0001 ,1011 , 0111 : 0001 ,1011 , 0111 . . 0110 ,10000110 ,1000二進制二進制: 1 ,1011 , 0111 : 1

15、,1011 , 0111 . . 0110 ,10110 ,110110111.01101B =1B7.68H十六進制十六進制( (H H) )轉換成二進制轉換成二進制( (B B) )例例: (7AC.DE ) 1616=(0111,1010,1100.1101,1110 ) 2 2 =(11110101100 .1101111 )2 2用四位二進制代碼的不同組合來表示一個十進制數碼的用四位二進制代碼的不同組合來表示一個十進制數碼的編碼方法，稱為二編碼方法，稱為二十進制編碼，也稱十進制編碼，也稱BCDBCD碼碼(Binary Coded (Binary Coded Decimal)Decim

16、al)。 1 1 二二十進制編碼原理十進制編碼原理1 1、二二十進制的編碼都采用壓縮的十進制串的方法，即四個二十進制的編碼都采用壓縮的十進制串的方法，即四個二進制位的值來表示一個十進制數碼。進制位的值來表示一個十進制數碼。2 2、各種編碼的區別在于選用哪十個狀態。選擇的原則是：要考各種編碼的區別在于選用哪十個狀態。選擇的原則是：要考慮輸入和輸出時轉換方便；內部運算時，加、減運算規則要慮輸入和輸出時轉換方便；內部運算時，加、減運算規則要盡量簡單；在特定場合，可能有其它一些要求。盡量簡單；在特定場合，可能有其它一些要求。3 3、從每個二進制位是否有確定的位權區分，可把二從每個二進制位是否有確定的位

17、權區分，可把二十進制編十進制編碼分為碼分為有權碼有權碼和和無權碼無權碼。十進制數碼的編碼十進制數碼的編碼無權碼中，用的較多的是余無權碼中，用的較多的是余3 3碼碼(Excess-3 code)(Excess-3 code)和格雷和格雷碼碼(Gray code)(Gray code)，格雷碼又稱循環碼。，格雷碼又稱循環碼。1.1.余余3 3碼碼（1 1）余余3 3碼是在碼是在84218421碼的基礎上，把每個代碼都加上碼的基礎上，把每個代碼都加上00110011而形而形成的。成的。（2 2）普通普通84218421碼的加法器仍能為余碼的加法器仍能為余3 3碼加法器直接利用。碼加法器直接利用。（1

18、 1）格雷碼的編碼規則是使相鄰的兩個代碼，只有一個二進制格雷碼的編碼規則是使相鄰的兩個代碼，只有一個二進制位的狀態不同，其余三個二進制位必須有相同狀態。位的狀態不同，其余三個二進制位必須有相同狀態。（2 2）優點：從一個編碼變到下一個相鄰編碼時，只有一個位的優點：從一個編碼變到下一個相鄰編碼時，只有一個位的狀態發生變化，有利于保證代碼變換的連續性。在模擬狀態發生變化，有利于保證代碼變換的連續性。在模擬/ /數數字轉換和產生節拍電位等應用場合特別有用。字轉換和產生節拍電位等應用場合特別有用。有關二有關二十進制的部分編碼方案列于表中。十進制的部分編碼方案列于表中。2.2.格雷碼格雷碼字符的表示方法

19、字符的表示方法現代計算機處理：現代計算機處理： 數值領域的問題；數值領域的問題； 非數值領域的問題：需引入文字、字母以及某些非數值領域的問題：需引入文字、字母以及某些 專用符號，以便表示文字專用符號，以便表示文字 語言、邏輯語言等信息。語言、邏輯語言等信息。 目前國際上普遍采用的字符系統是七位的目前國際上普遍采用的字符系統是七位的ASCIIASCII碼碼( (美國國美國國家信息交換標準字符碼家信息交換標準字符碼) )： 包括包括128128個元素個元素, , 因此二進制編碼需因此二進制編碼需7 7位位, ,加一位偶校驗位加一位偶校驗位, ,共共8 8位一個字節。位一個字節。非數值數據非數值數據

20、ASCIIASCII碼碼“美國標準信息交換代碼美國標準信息交換代碼”( (A American merican S Standard tandard C Code for ode for I Information nformation I Interchange)nterchange)，簡稱，簡稱ASCIIASCII碼。碼。7 7位二進制編碼，可表示位二進制編碼，可表示2 27 7=128=128個字符。個字符。ASCIIASCII碼中，編碼值碼中，編碼值0 03131不對應任何可印刷（或不對應任何可印刷（或稱有字形）字符，通常稱它們為控制字符，用于通信稱有字形）字符，通常稱它們為控制字符，

21、用于通信中的通信控制或對計算機設備的功能控制。編碼值為中的通信控制或對計算機設備的功能控制。編碼值為3232的是空格（或間隔）字符的是空格（或間隔）字符SPSP。編碼值為。編碼值為127127的是刪的是刪除控制除控制DELDEL碼。其余的碼。其余的9494個字符稱為可印刷字符。個字符稱為可印刷字符。字符編碼字符編碼EBCDICEBCDIC碼碼(Extended Binary Coded Decimal (Extended Binary Coded Decimal Interchange CodeInterchange Code，擴展，擴展BCDBCD碼碼) )，它是，它是8 8位二進制編碼，可

22、位二進制編碼，可以表示以表示256256個編碼狀態，但只選用其中一部分。個編碼狀態，但只選用其中一部分。 主要用在主要用在IBMIBM公司生產的各種機器中。公司生產的各種機器中。EBCDICEBCDIC碼碼 ASCII 字符表0000010100111001011101110000NULDLESP0Pp0001SOHDC1!1AQaq0010STXDC22BRbr0011ETXDC3#3CScs0100EOTDC4$4DTdt0101ENGNAK%5EUeu0110ACKSYN&6FVfv0111BELETB7GWgw1000BSCAN(8HXhx1001HTEM)9IYiy1010L

23、FSUB*:JZjz1011VTESC+;Kk1100FFFS,Nn1111SIUS/?OoDEL注：H表示高3位，L表示低4位。HL 元件故障、噪聲干擾等各種因素常常導致計算機在處理信息元件故障、噪聲干擾等各種因素常常導致計算機在處理信息過程中出現錯誤。為了防止錯誤過程中出現錯誤。為了防止錯誤, , 可將信號采用專門的邏輯線可將信號采用專門的邏輯線路進行編碼以檢測錯誤路進行編碼以檢測錯誤, ,甚至校正錯誤。甚至校正錯誤。 通常的方法是：通常的方法是：在每個字上添加一些校驗位在每個字上添加一些校驗位, ,用來確定字中出用來確定字中出 現錯誤的位置。現錯誤的位置。 常用方法：常用方法： 奇偶校驗

24、碼奇偶校驗碼 ； 海明校驗與糾錯碼海明校驗與糾錯碼 ； 循環冗余校驗碼循環冗余校驗碼 。1.1.為什么設置校驗碼為什么設置校驗碼3.7 3.7 數據校驗碼數據校驗碼1、碼字：、碼字：由若干位代碼組成，滿足某種編碼規律的一個代碼字。由若干位代碼組成，滿足某種編碼規律的一個代碼字。例：例：編碼規則編碼規則“代碼中代碼中1的個數為奇數的個數為奇數”則則 “01001001”合法合法 “11001001”不合法不合法2、碼距、碼距：碼距指任何一種編碼的任兩組二進制代碼中，其對應：碼距指任何一種編碼的任兩組二進制代碼中，其對應位置的代碼最少有幾個二進制位不相同。位置的代碼最少有幾個二進制位不相同。例例：

25、若用：若用4位二進制數表示位二進制數表示16種狀態，種狀態，16種狀態都用，則碼距種狀態都用，則碼距L=1。若用。若用4位二進制數表示位二進制數表示8種狀態，而把另外種狀態，而把另外8種狀態作種狀態作為非法編碼，此時的碼距為非法編碼，此時的碼距L=2。3、最小碼距：、最小碼距：指一種編碼的任意兩個指一種編碼的任意兩個碼字中間，對應位置碼字中間，對應位置代碼代碼變化的最少個數。變化的最少個數。8421BCD碼碼01111001 L=3 而而01000101 L=14、數據校驗的實現原理、數據校驗的實現原理：數據校驗碼是在合法的數據編碼之間，：數據校驗碼是在合法的數據編碼之間，加進一些不允許出現的

26、加進一些不允許出現的(非法的非法的)編碼，使合法的數據編碼出編碼，使合法的數據編碼出現錯誤時成為非法編碼。這樣就可以通過檢測編碼的合法性現錯誤時成為非法編碼。這樣就可以通過檢測編碼的合法性達到發現錯誤的目的。達到發現錯誤的目的。數據校驗碼原理數據校驗碼原理2.2.奇偶校驗奇偶校驗 原理原理：在在 k 位數據碼之外增加位數據碼之外增加 1 位校驗位，位校驗位， 使使 k+1 位碼字中取值為位碼字中取值為 1 的位數的位數保持為保持為 偶數（偶校驗偶數（偶校驗）或）或 奇數奇數（奇校驗奇校驗）偶校驗偶校驗奇校驗奇校驗校驗位校驗位0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 1 0 1

27、 0 1 0 1 0 0 1 0 1 1原有數據位原有數據位 兩個新的碼字兩個新的碼字例如：例如： 同理同理, ,偶校驗位偶校驗位定義為定義為 C C x0 x1 xn-1 即即x中包含偶數個中包含偶數個1 1時時, ,才使才使C C0 0。 設設x( x0 x1xn-1 )是一個是一個n n位字位字, , 則則奇校驗位奇校驗位定義為定義為 C C x0 x1 xn-1 式中式中代表按位加代表按位加, , 只有當只有當x中包含有奇數個中包含有奇數個1 1時時, ,C C0 0。定義：定義：例例 已知下表中左面一欄有已知下表中左面一欄有5 5個字節的數據。請分別用奇校驗和個字節的數據。請分別用奇

28、校驗和偶校驗進行編碼。偶校驗進行編碼。數據數據偶校驗編碼偶校驗編碼奇校驗編碼奇校驗編碼1 0 1 0 1 0 1 00 1 0 1 0 1 0 00 0 0 0 0 0 0 00 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 01 10 01 10 01 10 01

29、 10 01 1特點：特點： 奇偶校驗可提供單（奇偶校驗可提供單（奇數奇數）個錯誤檢測，）個錯誤檢測， 但無法檢測多（但無法檢測多（偶偶數數）個錯誤個錯誤, 更無法識別錯誤信息的位置及糾正錯誤。更無法識別錯誤信息的位置及糾正錯誤。 發送：發送： x0 x1xn-1C （算出（算出C加到需發送字的后面）加到需發送字的后面） 接收：接收： x0 x1 xn-1 C 計算：計算：Fx0 x1 xn-1 C 結果：若結果：若F1，意味著收到的信息有錯；，意味著收到的信息有錯； 若若F0，表明，表明x字傳送正確。字傳送正確。校驗方法：校驗方法： (以偶校驗為例以偶校驗為例)奇偶校驗碼常用于存儲器讀寫檢查

30、，或奇偶校驗碼常用于存儲器讀寫檢查，或ASCII字符傳送過程字符傳送過程中的檢查。中的檢查。1原理原理海明校驗碼的實現原理是：在數據位中加入幾個校驗位，將海明校驗碼的實現原理是：在數據位中加入幾個校驗位，將數據代碼的碼距均勻地拉大，并把數據的每個二進制位分配數據代碼的碼距均勻地拉大，并把數據的每個二進制位分配在幾個奇偶校驗組中。當某一位出錯后，就會引起有關的幾在幾個奇偶校驗組中。當某一位出錯后，就會引起有關的幾個校驗位的值發生變化，這不但可以發現錯誤，還能指出是個校驗位的值發生變化，這不但可以發現錯誤，還能指出是哪一位出錯，為進一步自動糾錯提供了依據。哪一位出錯，為進一步自動糾錯提供了依據。2

31、編碼規則編碼規則若海明碼的最高位號為若海明碼的最高位號為m，最低位號為，最低位號為1，即，即mm-121，則，則海明碼的編碼規則是：海明碼的編碼規則是：（1）校驗位與數據位之和為）校驗位與數據位之和為m，每個校驗位，每個校驗位Pi在海明碼中被分在海明碼中被分在位號在位號2i-1的位置上，其余各位為數據位，并按從低向高逐位的位置上，其余各位為數據位，并按從低向高逐位依次排列的關系分配各數據位。依次排列的關系分配各數據位。（2）海明碼的每一位位碼）海明碼的每一位位碼Hi（包括數據位和校驗位）由多個校（包括數據位和校驗位）由多個校驗位校驗，其關系是被校驗的每一位位號要等于校驗它的各驗位校驗，其關系是

32、被校驗的每一位位號要等于校驗它的各校驗位的位號之和。校驗位的位號之和。海明校驗碼海明校驗碼3增添校驗位增添校驗位 假設欲檢測的有效信息為假設欲檢測的有效信息為n位，需增加的校驗位為位，需增加的校驗位為k位，則校位，則校驗碼的長度為驗碼的長度為n+k位。校驗位的狀態組合，應當具有指出位。校驗位的狀態組合，應當具有指出n+k位中任一位有錯或無錯的能力，即需要區別出位中任一位有錯或無錯的能力，即需要區別出n+k+1種種狀態。應滿足以下關系式：狀態。應滿足以下關系式：2kn+k+1 這個關系式稱為這個關系式稱為海明不等式海明不等式，若信息位長度，若信息位長度n確定后，由此可確定后，由此可得到校驗位得到

33、校驗位k的最短長度。的最短長度。 確定校驗位后，就可以與信息位組成海明校驗位。假設數據確定校驗位后，就可以與信息位組成海明校驗位。假設數據位是位是7位二進制編碼，據上所述，位二進制編碼，據上所述，校驗位的位數校驗位的位數k為為4,故海明故海明碼的總位數為碼的總位數為11。它們的排列關系可表示為：。它們的排列關系可表示為： 海明碼位號：海明碼位號： H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1 海明碼：海明碼： D7 D6 D5 P4 D4 D3 D2 P3 D1 P2 P1 可知：可知： 每個校驗位由其本身校驗；每個校驗位由其本身校驗； 每個數據位由若干校驗位校驗每個數

34、據位由若干校驗位校驗。4校驗位校驗任務的分配校驗位校驗任務的分配根據海明碼的編碼規則，每一位海明碼都有多個校驗位根據海明碼的編碼規則，每一位海明碼都有多個校驗位校驗，且被校驗的每一位的位號等于參與校驗它的幾個校驗校驗，且被校驗的每一位的位號等于參與校驗它的幾個校驗位的位號之和。位的位號之和。 占據各權位上的校驗位按權組成的占據各權位上的校驗位按權組成的8421碼，正好等于碼，正好等于海明碼的位號，即海明碼的位號海明碼的位號，即海明碼的位號Hi正好等于要校驗它的校驗正好等于要校驗它的校驗位所占權位權值之和。位所占權位權值之和。例如：例如：H11P423P221P120這說明了這說明了H11位將由

35、位將由 P4、P2、P1進行校驗。進行校驗。校驗位校驗位P1可以校驗：可以校驗：H1 、H3、H5 、H7 、H9、H11、H13、H15校驗位校驗位P2可以校驗：可以校驗：H2 、H3、 H6、H7 、H10、H11、H14 、H15校驗位校驗位P3可以校驗：可以校驗：H4 、H5、 H6、 H7 、H12、H13、H14 、H15校驗位校驗位P4可以校驗：可以校驗：H8、H9、 H10、H11、H12、H13、H14 、H15根據校驗時根據校驗時偶校驗偶校驗，可以寫出相應的校驗方程。，可以寫出相應的校驗方程。例：例：設有一個設有一個7位信息碼位位信息碼位0110001，求它的海明碼。，求它

36、的海明碼。解：解： 此例中，信息位此例中，信息位n=7，根據海明不等式，可求得校驗位，根據海明不等式，可求得校驗位最短長度最短長度k=4。其海明碼先表示如下：其海明碼先表示如下：海明碼位號：海明碼位號：H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1海明碼：海明碼： 0 1 1 P4 0 0 0 P3 1 P2 P1按偶校驗寫出校驗方程為：按偶校驗寫出校驗方程為：H1 H3 H5 H7 H9 H110 （P1H1）H2 H3 H6 H7 H10 H110 （P2H2）H4 H5 H6 H70 （P3H4）H8 H9 H10 H110 （P4H8）由此可得：由此可得：P10、

37、P20、P30、P40，所以，所以0110001的的海明碼為海明碼為01100000100。 方法方法：將錯了的碼字重新代入校驗方程校驗一次即可。假設：將錯了的碼字重新代入校驗方程校驗一次即可。假設上面例子中的海明碼上面例子中的海明碼01100000100傳送后，若傳送后，若H6位發生了位發生了錯誤，變成了錯誤，變成了01100100100，這時把它們代入上面的偶校，這時把它們代入上面的偶校驗校驗方程，如下：驗校驗方程，如下： H1 H3 H5 H7 H9 H110 1 0 0 1 0 = 0 = E1 H2 H3 H6 H7 H10 H110 1 1 0 1 0= 1 = E2 H4 H5

38、H6 H70 0 1 0 = 1 = E3 H8 H9 H10 H110 1 1 0 = 0 = E4可以把可以把E4E3E2E1= 0110看成一個看成一個“錯誤字錯誤字”，因為其二，因為其二進制碼為進制碼為0110，說明，說明H6出了錯，是出了錯，是H6錯成了錯成了1，所以要糾錯，所以要糾錯，糾錯時將糾錯時將H6位取反值，即讓它恢復到正確值位取反值，即讓它恢復到正確值0。這樣糾錯后。這樣糾錯后即可得到正確的海明碼即可得到正確的海明碼01100000100。5檢錯與糾錯檢錯與糾錯1 1CRCCRC的編碼方法的編碼方法循環冗余校驗碼循環冗余校驗碼循環冗余校驗碼（循環冗余校驗碼（CRC）的基本原

39、理是：）的基本原理是：在在K位信息碼后再拼位信息碼后再拼接接R位的校驗碼，整個編碼長度為位的校驗碼，整個編碼長度為N位，因此，這種編碼又叫位，因此，這種編碼又叫（N，K）碼。對于一個給定的（）碼。對于一個給定的（N，K）碼，可以證明存在一）碼，可以證明存在一個最高次冪為個最高次冪為N-K=R的多項式的多項式G(x)。根據。根據G(x)可以生成可以生成K位信位信息的校驗碼，而息的校驗碼，而G(x)叫做這個叫做這個CRC碼的生成多項式。碼的生成多項式。 校驗碼的具體生成過程為：假設發送信息用信息多項式校驗碼的具體生成過程為：假設發送信息用信息多項式C(X)表示，將表示，將C(x)左移左移R位，則可

40、表示成位，則可表示成C(x)*2R ，這樣，這樣C(x)的右邊的右邊就會空出就會空出R位，這就是校驗碼的位置。通過位，這就是校驗碼的位置。通過C(x)* 2R除以生成除以生成多項式多項式G(x)得到的余數就是校驗碼。得到的余數就是校驗碼。 幾個基本概念幾個基本概念1、多項式與二進制數碼、多項式與二進制數碼 n多項式包括生成多項式多項式包括生成多項式G(x)和信息多項式和信息多項式C(x)。 n如生成多項式為如生成多項式為G(x)=x4+x3+x+1， 可轉可轉換為二進制數碼換為二進制數碼11011。 n而發送信息位而發送信息位 1111，可轉換為數據多項式，可轉換為數據多項式為為C(x)=x3

41、+x2+x+1。 2 2模模2 2運算：運算：不考慮借位和進位不考慮借位和進位（1 1）模）模2 2加減：加減：可用異或門實現，即：可用異或門實現，即：0+0=00+0=0；0+1=10+1=1；1+0=11+0=1；1+1=01+1=0；0-0=00-0=0；0-1=10-1=1；1-0=11-0=1；1-1=01-1=0；（2 2）模）模2 2乘法：乘法：用模用模2 2加求部分積之和加求部分積之和例如：例如： 1011 x 11 1011 + 1011 11101 （3） 模模2除法：除法：按模按模2減求部分余數，每上一位商，部分余減求部分余數，每上一位商，部分余數要減少一位，數要減少一位

42、，上商規則是上商規則是：只要余數最高位為：只要余數最高位為1，則商，則商1，否則為否則為0。當部分余數的位數小于除數時，該余數為最后余數。當部分余數的位數小于除數時，該余數為最后余數。例如：例如： 111.商11（除數） 1000（被除數） 11 10 11 10 11 1CRC碼的生成（一）碼的生成（一）n多項式除法n1、將碼多項式C(x)乘以xrn2、用G(x)除C(x)*xr，得余式R(x)n3、 C(x)*xr+ R(x)及編碼后的多項式例: G(x)=x4+x3+x+1，C(x)=x3+x2+x+1，R=4nC(x)*x4/G(x) = x2+1n校驗碼：校驗碼：0101n完整編碼：

43、完整編碼：11110101CRC碼的生成（二）碼的生成（二）n1、將x的最高冪次為R的生成多項式G(x)轉換成對應的R+1位二進制數。 n2、將信息碼左移R位，相當與對應的信息多項式C(x)*2R n3、用生成多項式（二進制數）對信息碼做模2除，得到R位的余數。 n4、將余數拼到信息碼左移后空出的位置，得到完整的CRC碼。 例例 設四位有效信息位是設四位有效信息位是11001100，選用生成多項式，選用生成多項式 G(X)=G(X)=1 1011011，試求有效信息位試求有效信息位11001100的的CRCCRC編碼。編碼。 解：解： (1)(1)將有效信息位將有效信息位11001100表示為

44、多項式表示為多項式M(x)M(x) M(X) = X M(X) = X3 3 + X+ X2 2 = 1100= 1100 (2) (2)M(X)M(X)左移左移r=3r=3位，得位，得M(x)M(x)* *X X3 3 M(x)M(x)* *X X3 3 = X= X6 6 + X+ X5 5 = 1100000= 1100000 (3) (3)用用r+1r+1位的生成多項式位的生成多項式 G(X)G(X)，對，對M(x)M(x)* *X Xr r作作“模模2 2除除” 1100000/1011 = 1110 + 010/10111100000/1011 = 1110 + 010/1011

45、(4) (4)M(x)M(x)* *X X3 3 與與r r位余數位余數R(X) R(X) 作作“模模2 2加加”，即可求得它，即可求得它的的CRCCRC編碼編碼 M(x)M(x)* *X X3 3 + R(X) = 1100000 + + R(X) = 1100000 + 010010 = 1100010 = 1100010 ( (模模2 2加加) ) 因為因為k=7k=7、n=4n=4，所以編好的，所以編好的CRCCRC碼又稱為碼又稱為(7(7，4)4)碼。碼。3 3CRCCRC的譯碼及糾錯的譯碼及糾錯 CRC CRC碼傳送到目標部件，用約定的多項式碼傳送到目標部件，用約定的多項式G(x)

46、G(x)對收到的對收到的CRCCRC碼進行碼進行“模模2 2除除”，若余數為若余數為0 0，則表明該，則表明該CRCCRC校驗碼正確；校驗碼正確；否則表明有錯，不同的出錯位，其余數是不同的。由余數否則表明有錯，不同的出錯位，其余數是不同的。由余數具體指出是哪一位出了錯，然后加以糾正。具體指出是哪一位出了錯，然后加以糾正。 不同的出錯位，其余數也是不同的。不同的出錯位，其余數也是不同的。可以證明：更換不同的有效信息位，余數與出錯位的可以證明：更換不同的有效信息位，余數與出錯位的對應關系不會發生變化，只與碼制和生成多項式對應關系不會發生變化，只與碼制和生成多項式G(X)G(X)有關。有關。不是任何

47、一個不是任何一個(k+1)(k+1)位多項式都能作為生成多項式，從檢位多項式都能作為生成多項式，從檢錯、糾錯的要求來看，生成多項式應滿足下列要求：錯、糾錯的要求來看，生成多項式應滿足下列要求：(1)(1)任何一位發生錯誤，都應使余數不為零；任何一位發生錯誤，都應使余數不為零；(2)(2)不同位發生錯誤，都應使余數不同；不同位發生錯誤，都應使余數不同；(3)(3)用余數補零，繼續作用余數補零，繼續作“模模2 2除除”，應使余數循環。，應使余數循環。常用的常用的CRCCRC生成多項式：生成多項式：CRC-12 12CRC-12 12位位 x x1212+x+x1111+x+x3 3+x+x2 2+

48、1 +1 CRC-16 16CRC-16 16位位 x x1616+x+x1515+x+x2 2+1 +1 （IBM)IBM)CRC-16 16CRC-16 16位位 x x1616+x+x1212+x+x5 5+1 +1 （CCITT)CCITT)CRC-32 32CRC-32 32位位 x x3232+x+x2626+x+x2323+x+x1616+x+x1111+x+x1010+x+x8 8+x+x7 7+x+x5 5+x+x4 4+x+x2 2+x+1 +x+1 5 5、CRCCRC產生電路產生電路 CRCCRC校驗碼不僅檢錯率高，而且硬件實現簡單，因而到校驗碼不僅檢錯率高，而且硬件實

49、現簡單，因而到底廣泛應用。底廣泛應用。4 4關于生成多項式關于生成多項式Questions and Answers計算機中常用的數據表示格式有兩種計算機中常用的數據表示格式有兩種: 定點格式定點格式容許的數值范圍有限，但要求的處理硬件比容許的數值范圍有限，但要求的處理硬件比 較簡單。較簡單。 浮點格式浮點格式容許的數值范圍很大，但要求的處理硬件比容許的數值范圍很大，但要求的處理硬件比 較復雜。較復雜。1.1.定點數的表示方法定點數的表示方法定點表示定點表示：約定機器中所有數據的小數點位置是固定不變的。：約定機器中所有數據的小數點位置是固定不變的。 ( (由于約定在固定的位置，小數點就不再使用記

50、號由于約定在固定的位置，小數點就不再使用記號“.”.” 來表示。來表示。) ) 通常將數據表示成通常將數據表示成純小數純小數或或純整數。純整數。數據表示數據表示定點數定點數：小數點位置固定不變的數小數點位置固定不變的數定點整數定點整數：小數點固定在小數點固定在最低位最低位數的數的右面右面(b) 定點小數x7x6x5x4x3x2x1x0(a) 定點整數x6x7x5x4x3x2x1x0數值范圍：數值范圍： 純小數純小數 0 |x| 1 2-n 純整數純整數 0 |x| 2n 1 目前計算機中多采用定點純整數表示，因此將定點數表示目前計算機中多采用定點純整數表示，因此將定點數表示的運算簡稱為的運算簡

51、稱為整數運算整數運算。定點小數定點小數：小數點固定在小數點固定在最高位最高位數的數的后面后面，即純小數表示，即純小數表示真值真值:正、負號加某進制數絕對值的形式稱為真值。如+3,-5等，即實際值。機器數機器數：符號以及數值都數碼化的數稱為機器數如 ：X=01011 Y=11011 即真值在機器中的表示，稱為機器數名詞解釋：真值和機器數名詞解釋：真值和機器數計算機中計算機中定點數定點數表示方法表示方法 原碼、補碼、反碼、移碼原碼、補碼、反碼、移碼。 若若定點小數定點小數的原碼形式為的原碼形式為 x0. x1 x2 xn, ,（共（共n+1n+1位）則原位）則原碼表示的定義是：碼表示的定義是：式中

52、式中x原原是機器數，是機器數，x是真值。是真值。1 1、原碼表示法、原碼表示法 (1)(1)定點小數定點小數 x 1 x = 1+ |x| -1 x 00 x 1x原原 = 數的機器碼表示數的機器碼表示 若若定點整數定點整數的原碼形式為的原碼形式為 x0 x1 x2 xn, ,則原碼表示的定則原碼表示的定義是：義是：(2)(2)定點整數定點整數 x 2n x = 2n + |x| -2n x 00 x 0X0時時 X + M M 自動丟失，自動丟失， x補補= X （Mod M）當當X0X0時時 X + M = M - | X | M， x補補= X + M （Mod M） 若若定點小數定點小

53、數的補碼形式為的補碼形式為 x0. x1 x2 xn, ,則補碼表示的定則補碼表示的定義是：義是：(2)定點小數定點小數 x0 x 1 2 + x = 2 |x| -1 x 0 x補補 = （mod 2）例例: x = +0.1011, 則則 x補補=0.1011x = -0.1011, 則則 x補補=10+x = 10.0000-0.1011= 1.0101 對于對于0，+0補補-0補補0.0000 (mod 2) 注意：注意：0的補碼表示只有一種形式。的補碼表示只有一種形式。 若若定點整數定點整數的補碼形式為的補碼形式為 x0 x1 x2 xn, ,則補碼表示的定則補碼表示的定義是：義是：

54、(3)(3)定點整數定點整數 x 2n+1 + x = 2n+1 |x| -2n x 00 x 2nx補補 =（mod 2n+1）例例: x = +0111, 則則 x補補=00111 x = -0111, 則則 x補補=24+1 |-0111|=100000 0111=11001補碼補碼最高一位為符號位，最高一位為符號位，0正正1負負；補碼補碼零有唯一編碼；零有唯一編碼；補碼補碼能很好用于加減運算。能很好用于加減運算。(4)(4)特點特點補碼補碼滿足滿足 -x補補+ x補補=0 +7補補=00111最高位參與演算，與其它位一樣對待。最高位參與演算，與其它位一樣對待。 -7補補=11001擴展

55、方便。擴展方便。5位的位的補碼補碼擴展為擴展為8位位 00111 0000011111001 11111001算術移位。假設算術移位。假設 x補補= x0. x1 x2 xn, , x/2補補= x0. x0 x1 x2 xn-1最大的優點就是將減法運算轉換成加法運算。最大的優點就是將減法運算轉換成加法運算。X+YX+Y補補= X= X補補+Y+Y補補X - YX - Y補補 = X= X補補+ -Y+ -Y補補例如例如： X=(11)X=(11)1010=(1011)=(1011)2 2 Y=(5) Y=(5)1010=(0101)=(0101)2 2已知字長已知字長n=5n=5位位XX補補

56、+ -Y+ -Y補補=01011+11011=01011+11011=1 100110=00110=(6)00110=00110=(6)10 10 注：注： 最高最高1 1位已經超過字長故應丟掉位已經超過字長故應丟掉X - Y補= 0110補=00110原碼與補碼之間的轉換已知原碼求補碼已知原碼求補碼正數正數 X X補補=X=X原原負數負數 符號除外，各位取反，末位加符號除外，各位取反，末位加1 1例例：X= -1001001X= -1001001 X X原原= =1 110010011001001 X X補補= =1 10110110+1=0110110+1=1 10110111011011

57、1 X X補補= 2= 27+1 7+1 +X=100000000-1001001= +X=100000000-1001001= 1 101101110110111 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 - 1 0 0 1 0 0 1 - 1 0 0 1 0 0 1 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 求值方法求值方法x = -x02n + x12n-1 + + xn-12 + xn例如：例如： 1000010010000100的真值為的真值為 -128+4=-124-128+4=-124補碼與真值之間的轉換補碼與真值之間的轉換補碼

58、補碼符號位為符號位為“1”1”-負，余下求補為數值部分負，余下求補為數值部分符號位為符號位為“0”0”-正，余下為數值部分正，余下為數值部分例例：XX補補 = = 0 0100 1001 X= 0100 1001 100 1001 X= 0100 1001 例：例：XX補補 = =1 1000 0000 X=000 0000 X=- 1000 0000B = 80H =-128- 1000 0000B = 80H =-128(1)(1)定點小數定義定點小數定義 x x (2 2 (2 2-n-n) + ) + x x -1 -1 x x 0 00 0 x x 1 1 x x 反反 = =一般情

59、況下一般情況下, , 對于正數對于正數 x x = +0.= +0.x x1 1x x2 2 x xn, n, 則有：則有： x x 反反= 0.= 0.x x1 1x x2 2 x xn n 對于負數對于負數 x x = -0.= -0.x x1 1x x2 2 x xn,n,則有則有 x x 反反= 1.= 1.x x1 1x x2 2 x xn n3 3、反碼表示法、反碼表示法 所謂反碼所謂反碼, , 就是二進制的各位數碼就是二進制的各位數碼0 0變為變為1 1，1 1變為變為0 0。例：例： x x = 0.10110 -0.10110 0.0000 = 0.10110 -0.1011

60、0 0.0000 x x 反反= =(2)(2)由反碼求補碼的公式由反碼求補碼的公式 (2-2 (2-2-n-n) + ) + x x x x 反反 = = 2 + 2 + x x x x 補補 = =由反碼與補碼的定義由反碼與補碼的定義得：得： x x 反反 + 2+ 2-n-n x x 補補 = = 即：若要一個即：若要一個負數變補碼，其方負數變補碼，其方法是符號位置法是符號位置1 1，其余各位其余各位0 0變變1 1，1 1變變0 0，然后在最末，然后在最末位位(2(2-n-n) )上加上加1 1。0.101100.101101.010011.010010.0000 0.0000 1.11111