版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、第3章 運(yùn)算方法和運(yùn)算部件1、數(shù)據(jù)及其表示、數(shù)據(jù)及其表示 數(shù)制的一般概念,數(shù)制之間的相互轉(zhuǎn)換數(shù)制的一般概念,數(shù)制之間的相互轉(zhuǎn)換2、數(shù)據(jù)校驗(yàn)碼、數(shù)據(jù)校驗(yàn)碼 常用編碼(了解)常用編碼(了解)3、定點(diǎn)數(shù)加減法運(yùn)算及電路實(shí)現(xiàn)、定點(diǎn)數(shù)加減法運(yùn)算及電路實(shí)現(xiàn)補(bǔ)碼的加減法運(yùn)算,溢出補(bǔ)碼的加減法運(yùn)算,溢出4、定點(diǎn)數(shù)乘除運(yùn)算和電路實(shí)現(xiàn)、定點(diǎn)數(shù)乘除運(yùn)算和電路實(shí)現(xiàn)原碼、補(bǔ)碼,布斯算法,原碼恢復(fù)余數(shù)、不恢復(fù)余數(shù)原碼、補(bǔ)碼,布斯算法,原碼恢復(fù)余數(shù)、不恢復(fù)余數(shù)5、快速乘除法運(yùn)算技術(shù)和電路實(shí)現(xiàn)、快速乘除法運(yùn)算技術(shù)和電路實(shí)現(xiàn)布斯高基乘法,陣列乘法器,陣列除法器布斯高基乘法,陣列乘法器,陣列除法器6、浮點(diǎn)數(shù)四則運(yùn)算以及實(shí)現(xiàn)、浮點(diǎn)
2、數(shù)四則運(yùn)算以及實(shí)現(xiàn)加減乘除加減乘除計(jì)算機(jī)計(jì)算機(jī)中的數(shù)據(jù)中的數(shù)據(jù)1 1、進(jìn)位計(jì)數(shù)制、進(jìn)位計(jì)數(shù)制進(jìn)位計(jì)數(shù)制進(jìn)位計(jì)數(shù)制:用少量的數(shù)字符號(hào),按先后次序把它們排成數(shù)位,:用少量的數(shù)字符號(hào),按先后次序把它們排成數(shù)位,由低到高進(jìn)行計(jì)數(shù),計(jì)滿進(jìn)位,這樣的方法稱為進(jìn)位計(jì)數(shù)制由低到高進(jìn)行計(jì)數(shù),計(jì)滿進(jìn)位,這樣的方法稱為進(jìn)位計(jì)數(shù)制基數(shù):基數(shù):進(jìn)位制基本特征數(shù),即所用到的數(shù)字符號(hào)個(gè)數(shù)進(jìn)位制基本特征數(shù),即所用到的數(shù)字符號(hào)個(gè)數(shù)例如:例如:1010進(jìn)制進(jìn)制 :09 09 十個(gè)數(shù)碼表示,基數(shù)為十個(gè)數(shù)碼表示,基數(shù)為1010再如:再如:1616進(jìn)制有進(jìn)制有0909,ABCDEFABCDEF,共,共1616個(gè)符號(hào)。個(gè)符號(hào)。權(quán)(位值)
3、:權(quán)(位值):進(jìn)位制中各位進(jìn)位制中各位“1”1”所表示的值為該位的權(quán)所表示的值為該位的權(quán)常見的進(jìn)位制:常見的進(jìn)位制: 2 2,8 8,1010,1616進(jìn)制,進(jìn)制,M M進(jìn)制進(jìn)制十進(jìn)制數(shù)的多項(xiàng)式表示十進(jìn)制數(shù)的多項(xiàng)式表示: :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為正整數(shù)為正整數(shù), ,其中其中n n為整數(shù)位數(shù);為整數(shù)位數(shù);m m為小數(shù)位數(shù)。為小數(shù)位數(shù)。DiDi表示第表示第i i位的系數(shù)位的系數(shù),10,10i i稱為該位的權(quán)稱為該位的權(quán). .1、十進(jìn)制(Decimal
4、)基數(shù)基數(shù):10; 符號(hào)符號(hào):0,1,2,3,4,5,6,7,8,9計(jì)算規(guī)律計(jì)算規(guī)律:“逢十進(jìn)一逢十進(jìn)一 ”或或“借一當(dāng)十借一當(dāng)十”例如例如:一個(gè)十進(jìn)制數(shù)一個(gè)十進(jìn)制數(shù)123.45的表示的表示123.45 =1102+ 2101+ 3 100 + 410-1+ 510-2注:等式左邊為并列表示法等式右邊為多項(xiàng)式表示法注:等式左邊為并列表示法等式右邊為多項(xiàng)式表示法2 2、二進(jìn)制、二進(jìn)制( (B Binary)inary)二進(jìn)制的多項(xiàng)式表示二進(jìn)制的多項(xiàng)式表示: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為整數(shù)位數(shù);為整數(shù)位數(shù);m為小數(shù)位數(shù)。為小數(shù)位數(shù)。Di表示第表示第i位的系數(shù)位的系數(shù),2i稱為該位的權(quán)稱為該位的權(quán). 基數(shù)基數(shù):2符號(hào)符號(hào):0,1計(jì)算規(guī)律計(jì)算規(guī)律:逢二進(jìn)一或借一當(dāng)二逢二進(jìn)一或借一當(dāng)二3、十六進(jìn)制(Hexadecimal)二進(jìn)制的多項(xiàng)式表示二進(jìn)制的多項(xiàng)式表示: :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為整數(shù)位數(shù);為整數(shù)位數(shù);m為小數(shù)位數(shù)。為小數(shù)位數(shù)。Di表示第表示第i位的系數(shù)位的系數(shù),16i稱稱為該位的權(quán)為該位的權(quán).基數(shù)基數(shù): :1616符號(hào)
6、符號(hào): :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計(jì)算規(guī)律計(jì)算規(guī)律: :逢十六進(jìn)一或借一當(dāng)十六逢十六進(jìn)一或借一當(dāng)十六例如十六進(jìn)制數(shù)例如十六進(jìn)制數(shù) (2C7.1F)16的表示的表示 (2C7.1F)16=2 162+ 12 161+ 7 160+ 1 16-1+ 15 16-24 、進(jìn)位計(jì)數(shù)制之間的轉(zhuǎn)換1)R進(jìn)制轉(zhuǎn)換成十進(jìn)制的方法進(jìn)制轉(zhuǎn)換成十進(jìn)制的方法按權(quán)展開法按權(quán)展開法:先寫成多項(xiàng)式先寫成多項(xiàng)式,然后計(jì)算十進(jìn)制結(jié)果然后計(jì)算十進(jìn)制結(jié)果.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的十進(jìn)制數(shù)的十進(jìn)制數(shù)(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)十進(jìn)制轉(zhuǎn)換成二進(jìn)制方法)十進(jìn)制轉(zhuǎn)換成二進(jìn)制方法一般分為兩個(gè)方法一般分為兩個(gè)方法:方法1、整數(shù)部分的轉(zhuǎn)換 除除2取余
8、法(基數(shù)除法)取余法(基數(shù)除法) 小數(shù)部分的轉(zhuǎn)換 乘乘2取整法(基數(shù)乘法)取整法(基數(shù)乘法)方法2、減權(quán)定位法減權(quán)定位法除基取余法除基取余法:把給定的除以基數(shù):把給定的除以基數(shù),取余數(shù)作為最低位的系數(shù)取余數(shù)作為最低位的系數(shù),然然后繼續(xù)將商部分除以后繼續(xù)將商部分除以 基數(shù)基數(shù),余數(shù)作為次低位系數(shù)余數(shù)作為次低位系數(shù),重復(fù)操作重復(fù)操作直至商為直至商為 0例如:用基數(shù)除法將例如:用基數(shù)除法將(327)10轉(zhuǎn)換成二進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)2 327 余數(shù)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 把給定的十進(jìn)制小數(shù)乘以把給定的十進(jìn)制小數(shù)乘以 2 ,2 ,取其整數(shù)作為二進(jìn)制小數(shù)取其整數(shù)作為二進(jìn)制小數(shù)的第一位的第一位, ,然后取小數(shù)部分繼續(xù)乘以然后取小數(shù)部分繼續(xù)乘以2,2,將所的整數(shù)部分作將所的整數(shù)部分作為第二位小數(shù)為第二位小數(shù), ,重復(fù)操作直至得到所需要的二進(jìn)制小數(shù)重復(fù)操作直至得到所需要的二進(jìn)制小數(shù)例如例如: :將將(0.8125) (0.8125) 10 10 轉(zhuǎn)換成二進(jìn)制小數(shù)轉(zhuǎn)換成二進(jìn)制小數(shù) 整數(shù)部分整數(shù)部分 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乘基取整法乘基取整法(小數(shù)部分的轉(zhuǎn)換小數(shù)部分的轉(zhuǎn)換)例例:將將(0.2)10 10 轉(zhuǎn)換成二進(jìn)制小數(shù)轉(zhuǎn)換成二進(jìn)制小數(shù)整數(shù)部分整數(shù)部分 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 減權(quán)定位法減權(quán)定位法 將十進(jìn)制數(shù)依次從二進(jìn)制的最高位權(quán)值進(jìn)行比較,若夠減則對(duì)應(yīng)將十進(jìn)制數(shù)依次從二進(jìn)制的最高位權(quán)值進(jìn)行比較,若夠減則對(duì)應(yīng)位置位置1 1,減去該權(quán)值后再往下比較,若不夠減則對(duì)應(yīng)位為,減去該權(quán)值后再往下比較,若不夠減則對(duì)應(yīng)位為0 0,重復(fù)操作直,重復(fù)操作直至差數(shù)為至差數(shù)為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 轉(zhuǎn)換成二進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù) 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、進(jìn)制二進(jìn)制( (B B) )轉(zhuǎn)換成八進(jìn)制轉(zhuǎn)換成八進(jìn)制( (Q Q) )例:例:(10110111 .01101) 2 2(10110111.01101) 2 2 =(267.32)8 8八進(jìn)制八進(jìn)制: 2 6 7 : 2 6 7 . . 3 2 3 2二進(jìn)制二進(jìn)制: 010 ,110 , 111 : 010 ,110 , 111 . 011 , 010 011 , 010二進(jìn)制二進(jìn)制: 10 ,: 10 ,110110 , , 111111 . . 011011 , 01 , 013)其它進(jìn)制之間的直接轉(zhuǎn)換法)其它進(jìn)制之間的直接轉(zhuǎn)換法八進(jìn)制八進(jìn)制( (Q Q) )轉(zhuǎn)換二進(jìn)制轉(zhuǎn)換二進(jìn)制( (B
14、B) )例如例如: (123.46 ) 8 8=(001,010,011 .100,110 ) 2 2 =(1010011.10011)2 2二進(jìn)制二進(jìn)制( (B B) )轉(zhuǎn)換成十六進(jìn)制轉(zhuǎn)換成十六進(jìn)制( (H H) )例例:(110110111 .01101) 2 2(10110111.01101) 2 2 =(1B7.68)1616十六進(jìn)制十六進(jìn)制: 1 B 7 : 1 B 7 . . 6 8 6 8二進(jìn)制二進(jìn)制: 0001 ,1011 , 0111 : 0001 ,1011 , 0111 . . 0110 ,10000110 ,1000二進(jìn)制二進(jìn)制: 1 ,1011 , 0111 : 1
15、,1011 , 0111 . . 0110 ,10110 ,110110111.01101B =1B7.68H十六進(jìn)制十六進(jìn)制( (H H) )轉(zhuǎn)換成二進(jìn)制轉(zhuǎn)換成二進(jìn)制( (B B) )例例: (7AC.DE ) 1616=(0111,1010,1100.1101,1110 ) 2 2 =(11110101100 .1101111 )2 2用四位二進(jìn)制代碼的不同組合來表示一個(gè)十進(jìn)制數(shù)碼的用四位二進(jìn)制代碼的不同組合來表示一個(gè)十進(jìn)制數(shù)碼的編碼方法,稱為二編碼方法,稱為二十進(jìn)制編碼,也稱十進(jìn)制編碼,也稱BCDBCD碼碼(Binary Coded (Binary Coded Decimal)Decim
16、al)。 1 1 二二十進(jìn)制編碼原理十進(jìn)制編碼原理1 1、二二十進(jìn)制的編碼都采用壓縮的十進(jìn)制串的方法,即四個(gè)二十進(jìn)制的編碼都采用壓縮的十進(jìn)制串的方法,即四個(gè)二進(jìn)制位的值來表示一個(gè)十進(jìn)制數(shù)碼。進(jìn)制位的值來表示一個(gè)十進(jìn)制數(shù)碼。2 2、各種編碼的區(qū)別在于選用哪十個(gè)狀態(tài)。選擇的原則是:要考各種編碼的區(qū)別在于選用哪十個(gè)狀態(tài)。選擇的原則是:要考慮輸入和輸出時(shí)轉(zhuǎn)換方便;內(nèi)部運(yùn)算時(shí),加、減運(yùn)算規(guī)則要慮輸入和輸出時(shí)轉(zhuǎn)換方便;內(nèi)部運(yùn)算時(shí),加、減運(yùn)算規(guī)則要盡量簡單;在特定場合,可能有其它一些要求。盡量簡單;在特定場合,可能有其它一些要求。3 3、從每個(gè)二進(jìn)制位是否有確定的位權(quán)區(qū)分,可把二從每個(gè)二進(jìn)制位是否有確定的位
17、權(quán)區(qū)分,可把二十進(jìn)制編十進(jìn)制編碼分為碼分為有權(quán)碼有權(quán)碼和和無權(quán)碼無權(quán)碼。十進(jìn)制數(shù)碼的編碼十進(jìn)制數(shù)碼的編碼無權(quán)碼中,用的較多的是余無權(quán)碼中,用的較多的是余3 3碼碼(Excess-3 code)(Excess-3 code)和格雷和格雷碼碼(Gray code)(Gray code),格雷碼又稱循環(huán)碼。,格雷碼又稱循環(huán)碼。1.1.余余3 3碼碼(1 1)余余3 3碼是在碼是在84218421碼的基礎(chǔ)上,把每個(gè)代碼都加上碼的基礎(chǔ)上,把每個(gè)代碼都加上00110011而形而形成的。成的。(2 2)普通普通84218421碼的加法器仍能為余碼的加法器仍能為余3 3碼加法器直接利用。碼加法器直接利用。(1
18、 1)格雷碼的編碼規(guī)則是使相鄰的兩個(gè)代碼,只有一個(gè)二進(jìn)制格雷碼的編碼規(guī)則是使相鄰的兩個(gè)代碼,只有一個(gè)二進(jìn)制位的狀態(tài)不同,其余三個(gè)二進(jìn)制位必須有相同狀態(tài)。位的狀態(tài)不同,其余三個(gè)二進(jìn)制位必須有相同狀態(tài)。(2 2)優(yōu)點(diǎn):從一個(gè)編碼變到下一個(gè)相鄰編碼時(shí),只有一個(gè)位的優(yōu)點(diǎn):從一個(gè)編碼變到下一個(gè)相鄰編碼時(shí),只有一個(gè)位的狀態(tài)發(fā)生變化,有利于保證代碼變換的連續(xù)性。在模擬狀態(tài)發(fā)生變化,有利于保證代碼變換的連續(xù)性。在模擬/ /數(shù)數(shù)字轉(zhuǎn)換和產(chǎn)生節(jié)拍電位等應(yīng)用場合特別有用。字轉(zhuǎn)換和產(chǎn)生節(jié)拍電位等應(yīng)用場合特別有用。有關(guān)二有關(guān)二十進(jìn)制的部分編碼方案列于表中。十進(jìn)制的部分編碼方案列于表中。2.2.格雷碼格雷碼字符的表示方法
19、字符的表示方法現(xiàn)代計(jì)算機(jī)處理:現(xiàn)代計(jì)算機(jī)處理: 數(shù)值領(lǐng)域的問題;數(shù)值領(lǐng)域的問題; 非數(shù)值領(lǐng)域的問題:需引入文字、字母以及某些非數(shù)值領(lǐng)域的問題:需引入文字、字母以及某些 專用符號(hào),以便表示文字專用符號(hào),以便表示文字 語言、邏輯語言等信息。語言、邏輯語言等信息。 目前國際上普遍采用的字符系統(tǒng)是七位的目前國際上普遍采用的字符系統(tǒng)是七位的ASCIIASCII碼碼( (美國國美國國家信息交換標(biāo)準(zhǔn)字符碼家信息交換標(biāo)準(zhǔn)字符碼) ): 包括包括128128個(gè)元素個(gè)元素, , 因此二進(jìn)制編碼需因此二進(jìn)制編碼需7 7位位, ,加一位偶校驗(yàn)位加一位偶校驗(yàn)位, ,共共8 8位一個(gè)字節(jié)。位一個(gè)字節(jié)。非數(shù)值數(shù)據(jù)非數(shù)值數(shù)據(jù)
20、ASCIIASCII碼碼“美國標(biāo)準(zhǔn)信息交換代碼美國標(biāo)準(zhǔn)信息交換代碼”( (A American merican S Standard tandard C Code for ode for I Information nformation I Interchange)nterchange),簡稱,簡稱ASCIIASCII碼。碼。7 7位二進(jìn)制編碼,可表示位二進(jìn)制編碼,可表示2 27 7=128=128個(gè)字符。個(gè)字符。ASCIIASCII碼中,編碼值碼中,編碼值0 03131不對(duì)應(yīng)任何可印刷(或不對(duì)應(yīng)任何可印刷(或稱有字形)字符,通常稱它們?yōu)榭刂谱址?,用于通信稱有字形)字符,通常稱它們?yōu)榭刂谱址?/p>
21、用于通信中的通信控制或?qū)τ?jì)算機(jī)設(shè)備的功能控制。編碼值為中的通信控制或?qū)τ?jì)算機(jī)設(shè)備的功能控制。編碼值為3232的是空格(或間隔)字符的是空格(或間隔)字符SPSP。編碼值為。編碼值為127127的是刪的是刪除控制除控制DELDEL碼。其余的碼。其余的9494個(gè)字符稱為可印刷字符。個(gè)字符稱為可印刷字符。字符編碼字符編碼EBCDICEBCDIC碼碼(Extended Binary Coded Decimal (Extended Binary Coded Decimal Interchange CodeInterchange Code,擴(kuò)展,擴(kuò)展BCDBCD碼碼) ),它是,它是8 8位二進(jìn)制編碼,可
22、位二進(jìn)制編碼,可以表示以表示256256個(gè)編碼狀態(tài),但只選用其中一部分。個(gè)編碼狀態(tài),但只選用其中一部分。 主要用在主要用在IBMIBM公司生產(chǎn)的各種機(jī)器中。公司生產(chǎn)的各種機(jī)器中。EBCDICEBCDIC碼碼 ASCII 字符表0000010100111001011101110000NULDLESP0Pp0001SOHDC1!1AQaq0010STXDC22BRbr0011ETXDC3#3CScs0100EOTDC4$4DTdt0101ENGNAK%5EUeu0110ACKSYN&6FVfv0111BELETB7GWgw1000BSCAN(8HXhx1001HTEM)9IYiy1010L
23、FSUB*:JZjz1011VTESC+;Kk1100FFFS,Nn1111SIUS/?OoDEL注:H表示高3位,L表示低4位。HL 元件故障、噪聲干擾等各種因素常常導(dǎo)致計(jì)算機(jī)在處理信息元件故障、噪聲干擾等各種因素常常導(dǎo)致計(jì)算機(jī)在處理信息過程中出現(xiàn)錯(cuò)誤。為了防止錯(cuò)誤過程中出現(xiàn)錯(cuò)誤。為了防止錯(cuò)誤, , 可將信號(hào)采用專門的邏輯線可將信號(hào)采用專門的邏輯線路進(jìn)行編碼以檢測錯(cuò)誤路進(jìn)行編碼以檢測錯(cuò)誤, ,甚至校正錯(cuò)誤。甚至校正錯(cuò)誤。 通常的方法是:通常的方法是:在每個(gè)字上添加一些校驗(yàn)位在每個(gè)字上添加一些校驗(yàn)位, ,用來確定字中出用來確定字中出 現(xiàn)錯(cuò)誤的位置?,F(xiàn)錯(cuò)誤的位置。 常用方法:常用方法: 奇偶校驗(yàn)
24、碼奇偶校驗(yàn)碼 ; 海明校驗(yàn)與糾錯(cuò)碼海明校驗(yàn)與糾錯(cuò)碼 ; 循環(huán)冗余校驗(yàn)碼循環(huán)冗余校驗(yàn)碼 。1.1.為什么設(shè)置校驗(yàn)碼為什么設(shè)置校驗(yàn)碼3.7 3.7 數(shù)據(jù)校驗(yàn)碼數(shù)據(jù)校驗(yàn)碼1、碼字:、碼字:由若干位代碼組成,滿足某種編碼規(guī)律的一個(gè)代碼字。由若干位代碼組成,滿足某種編碼規(guī)律的一個(gè)代碼字。例:例:編碼規(guī)則編碼規(guī)則“代碼中代碼中1的個(gè)數(shù)為奇數(shù)的個(gè)數(shù)為奇數(shù)”則則 “01001001”合法合法 “11001001”不合法不合法2、碼距、碼距:碼距指任何一種編碼的任兩組二進(jìn)制代碼中,其對(duì)應(yīng):碼距指任何一種編碼的任兩組二進(jìn)制代碼中,其對(duì)應(yīng)位置的代碼最少有幾個(gè)二進(jìn)制位不相同。位置的代碼最少有幾個(gè)二進(jìn)制位不相同。例例:
25、若用:若用4位二進(jìn)制數(shù)表示位二進(jìn)制數(shù)表示16種狀態(tài),種狀態(tài),16種狀態(tài)都用,則碼距種狀態(tài)都用,則碼距L=1。若用。若用4位二進(jìn)制數(shù)表示位二進(jìn)制數(shù)表示8種狀態(tài),而把另外種狀態(tài),而把另外8種狀態(tài)作種狀態(tài)作為非法編碼,此時(shí)的碼距為非法編碼,此時(shí)的碼距L=2。3、最小碼距:、最小碼距:指一種編碼的任意兩個(gè)指一種編碼的任意兩個(gè)碼字中間,對(duì)應(yīng)位置碼字中間,對(duì)應(yīng)位置代碼代碼變化的最少個(gè)數(shù)。變化的最少個(gè)數(shù)。8421BCD碼碼01111001 L=3 而而01000101 L=14、數(shù)據(jù)校驗(yàn)的實(shí)現(xiàn)原理、數(shù)據(jù)校驗(yàn)的實(shí)現(xiàn)原理:數(shù)據(jù)校驗(yàn)碼是在合法的數(shù)據(jù)編碼之間,:數(shù)據(jù)校驗(yàn)碼是在合法的數(shù)據(jù)編碼之間,加進(jìn)一些不允許出現(xiàn)的
26、加進(jìn)一些不允許出現(xiàn)的(非法的非法的)編碼,使合法的數(shù)據(jù)編碼出編碼,使合法的數(shù)據(jù)編碼出現(xiàn)錯(cuò)誤時(shí)成為非法編碼。這樣就可以通過檢測編碼的合法性現(xiàn)錯(cuò)誤時(shí)成為非法編碼。這樣就可以通過檢測編碼的合法性達(dá)到發(fā)現(xiàn)錯(cuò)誤的目的。達(dá)到發(fā)現(xiàn)錯(cuò)誤的目的。數(shù)據(jù)校驗(yàn)碼原理數(shù)據(jù)校驗(yàn)碼原理2.2.奇偶校驗(yàn)奇偶校驗(yàn) 原理原理:在在 k 位數(shù)據(jù)碼之外增加位數(shù)據(jù)碼之外增加 1 位校驗(yàn)位,位校驗(yàn)位, 使使 k+1 位碼字中取值為位碼字中取值為 1 的位數(shù)的位數(shù)保持為保持為 偶數(shù)(偶校驗(yàn)偶數(shù)(偶校驗(yàn))或)或 奇數(shù)奇數(shù)(奇校驗(yàn)奇校驗(yàn))偶校驗(yàn)偶校驗(yàn)奇校驗(yàn)奇校驗(yàn)校驗(yàn)位校驗(yàn)位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原有數(shù)據(jù)位原有數(shù)據(jù)位 兩個(gè)新的碼字兩個(gè)新的碼字例如:例如: 同理同理, ,偶校驗(yàn)位偶校驗(yàn)位定義為定義為 C C x0 x1 xn-1 即即x中包含偶數(shù)個(gè)中包含偶數(shù)個(gè)1 1時(shí)時(shí), ,才使才使C C0 0。 設(shè)設(shè)x( x0 x1xn-1 )是一個(gè)是一個(gè)n n位字位字, , 則則奇校驗(yàn)位奇校驗(yàn)位定義為定義為 C C x0 x1 xn-1 式中式中代表按位加代表按位加, , 只有當(dāng)只有當(dāng)x中包含有奇數(shù)個(gè)中包含有奇數(shù)個(gè)1 1時(shí)時(shí), ,C C0 0。定義:定義:例例 已知下表中左面一欄有已知下表中左面一欄有5 5個(gè)字節(jié)的數(shù)據(jù)。請(qǐng)分別用奇校驗(yàn)和個(gè)字節(jié)的數(shù)據(jù)。請(qǐng)分別用奇
28、校驗(yàn)和偶校驗(yàn)進(jìn)行編碼。偶校驗(yàn)進(jìn)行編碼。數(shù)據(jù)數(shù)據(jù)偶校驗(yàn)編碼偶校驗(yàn)編碼奇校驗(yàn)編碼奇校驗(yàn)編碼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特點(diǎn):特點(diǎn): 奇偶校驗(yàn)可提供單(奇偶校驗(yàn)可提供單(奇數(shù)奇數(shù))個(gè)錯(cuò)誤檢測,)個(gè)錯(cuò)誤檢測, 但無法檢測多(但無法檢測多(偶偶數(shù)數(shù))個(gè)錯(cuò)誤個(gè)錯(cuò)誤, 更無法識(shí)別錯(cuò)誤信息的位置及糾正錯(cuò)誤。更無法識(shí)別錯(cuò)誤信息的位置及糾正錯(cuò)誤。 發(fā)送:發(fā)送: x0 x1xn-1C (算出(算出C加到需發(fā)送字的后面)加到需發(fā)送字的后面) 接收:接收: x0 x1 xn-1 C 計(jì)算:計(jì)算:Fx0 x1 xn-1 C 結(jié)果:若結(jié)果:若F1,意味著收到的信息有錯(cuò);,意味著收到的信息有錯(cuò); 若若F0,表明,表明x字傳送正確。字傳送正確。校驗(yàn)方法:校驗(yàn)方法: (以偶校驗(yàn)為例以偶校驗(yàn)為例)奇偶校驗(yàn)碼常用于存儲(chǔ)器讀寫檢查
30、,或奇偶校驗(yàn)碼常用于存儲(chǔ)器讀寫檢查,或ASCII字符傳送過程字符傳送過程中的檢查。中的檢查。1原理原理海明校驗(yàn)碼的實(shí)現(xiàn)原理是:在數(shù)據(jù)位中加入幾個(gè)校驗(yàn)位,將海明校驗(yàn)碼的實(shí)現(xiàn)原理是:在數(shù)據(jù)位中加入幾個(gè)校驗(yàn)位,將數(shù)據(jù)代碼的碼距均勻地拉大,并把數(shù)據(jù)的每個(gè)二進(jìn)制位分配數(shù)據(jù)代碼的碼距均勻地拉大,并把數(shù)據(jù)的每個(gè)二進(jìn)制位分配在幾個(gè)奇偶校驗(yàn)組中。當(dāng)某一位出錯(cuò)后,就會(huì)引起有關(guān)的幾在幾個(gè)奇偶校驗(yàn)組中。當(dāng)某一位出錯(cuò)后,就會(huì)引起有關(guān)的幾個(gè)校驗(yàn)位的值發(fā)生變化,這不但可以發(fā)現(xiàn)錯(cuò)誤,還能指出是個(gè)校驗(yàn)位的值發(fā)生變化,這不但可以發(fā)現(xiàn)錯(cuò)誤,還能指出是哪一位出錯(cuò),為進(jìn)一步自動(dòng)糾錯(cuò)提供了依據(jù)。哪一位出錯(cuò),為進(jìn)一步自動(dòng)糾錯(cuò)提供了依據(jù)。2
31、編碼規(guī)則編碼規(guī)則若海明碼的最高位號(hào)為若海明碼的最高位號(hào)為m,最低位號(hào)為,最低位號(hào)為1,即,即mm-121,則,則海明碼的編碼規(guī)則是:海明碼的編碼規(guī)則是:(1)校驗(yàn)位與數(shù)據(jù)位之和為)校驗(yàn)位與數(shù)據(jù)位之和為m,每個(gè)校驗(yàn)位,每個(gè)校驗(yàn)位Pi在海明碼中被分在海明碼中被分在位號(hào)在位號(hào)2i-1的位置上,其余各位為數(shù)據(jù)位,并按從低向高逐位的位置上,其余各位為數(shù)據(jù)位,并按從低向高逐位依次排列的關(guān)系分配各數(shù)據(jù)位。依次排列的關(guān)系分配各數(shù)據(jù)位。(2)海明碼的每一位位碼)海明碼的每一位位碼Hi(包括數(shù)據(jù)位和校驗(yàn)位)由多個(gè)校(包括數(shù)據(jù)位和校驗(yàn)位)由多個(gè)校驗(yàn)位校驗(yàn),其關(guān)系是被校驗(yàn)的每一位位號(hào)要等于校驗(yàn)它的各驗(yàn)位校驗(yàn),其關(guān)系是
32、被校驗(yàn)的每一位位號(hào)要等于校驗(yàn)它的各校驗(yàn)位的位號(hào)之和。校驗(yàn)位的位號(hào)之和。海明校驗(yàn)碼海明校驗(yàn)碼3增添校驗(yàn)位增添校驗(yàn)位 假設(shè)欲檢測的有效信息為假設(shè)欲檢測的有效信息為n位,需增加的校驗(yàn)位為位,需增加的校驗(yàn)位為k位,則校位,則校驗(yàn)碼的長度為驗(yàn)碼的長度為n+k位。校驗(yàn)位的狀態(tài)組合,應(yīng)當(dāng)具有指出位。校驗(yàn)位的狀態(tài)組合,應(yīng)當(dāng)具有指出n+k位中任一位有錯(cuò)或無錯(cuò)的能力,即需要區(qū)別出位中任一位有錯(cuò)或無錯(cuò)的能力,即需要區(qū)別出n+k+1種種狀態(tài)。應(yīng)滿足以下關(guān)系式:狀態(tài)。應(yīng)滿足以下關(guān)系式:2kn+k+1 這個(gè)關(guān)系式稱為這個(gè)關(guān)系式稱為海明不等式海明不等式,若信息位長度,若信息位長度n確定后,由此可確定后,由此可得到校驗(yàn)位得到
33、校驗(yàn)位k的最短長度。的最短長度。 確定校驗(yàn)位后,就可以與信息位組成海明校驗(yàn)位。假設(shè)數(shù)據(jù)確定校驗(yàn)位后,就可以與信息位組成海明校驗(yàn)位。假設(shè)數(shù)據(jù)位是位是7位二進(jìn)制編碼,據(jù)上所述,位二進(jìn)制編碼,據(jù)上所述,校驗(yàn)位的位數(shù)校驗(yàn)位的位數(shù)k為為4,故海明故海明碼的總位數(shù)為碼的總位數(shù)為11。它們的排列關(guān)系可表示為:。它們的排列關(guān)系可表示為: 海明碼位號(hào):海明碼位號(hào): H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1 海明碼:海明碼: D7 D6 D5 P4 D4 D3 D2 P3 D1 P2 P1 可知:可知: 每個(gè)校驗(yàn)位由其本身校驗(yàn);每個(gè)校驗(yàn)位由其本身校驗(yàn); 每個(gè)數(shù)據(jù)位由若干校驗(yàn)位校驗(yàn)每個(gè)數(shù)
34、據(jù)位由若干校驗(yàn)位校驗(yàn)。4校驗(yàn)位校驗(yàn)任務(wù)的分配校驗(yàn)位校驗(yàn)任務(wù)的分配根據(jù)海明碼的編碼規(guī)則,每一位海明碼都有多個(gè)校驗(yàn)位根據(jù)海明碼的編碼規(guī)則,每一位海明碼都有多個(gè)校驗(yàn)位校驗(yàn),且被校驗(yàn)的每一位的位號(hào)等于參與校驗(yàn)它的幾個(gè)校驗(yàn)校驗(yàn),且被校驗(yàn)的每一位的位號(hào)等于參與校驗(yàn)它的幾個(gè)校驗(yàn)位的位號(hào)之和。位的位號(hào)之和。 占據(jù)各權(quán)位上的校驗(yàn)位按權(quán)組成的占據(jù)各權(quán)位上的校驗(yàn)位按權(quán)組成的8421碼,正好等于碼,正好等于海明碼的位號(hào),即海明碼的位號(hào)海明碼的位號(hào),即海明碼的位號(hào)Hi正好等于要校驗(yàn)它的校驗(yàn)正好等于要校驗(yàn)它的校驗(yàn)位所占權(quán)位權(quán)值之和。位所占權(quán)位權(quán)值之和。例如:例如:H11P423P221P120這說明了這說明了H11位將由
35、位將由 P4、P2、P1進(jìn)行校驗(yàn)。進(jìn)行校驗(yàn)。校驗(yàn)位校驗(yàn)位P1可以校驗(yàn):可以校驗(yàn):H1 、H3、H5 、H7 、H9、H11、H13、H15校驗(yàn)位校驗(yàn)位P2可以校驗(yàn):可以校驗(yàn):H2 、H3、 H6、H7 、H10、H11、H14 、H15校驗(yàn)位校驗(yàn)位P3可以校驗(yàn):可以校驗(yàn):H4 、H5、 H6、 H7 、H12、H13、H14 、H15校驗(yàn)位校驗(yàn)位P4可以校驗(yàn):可以校驗(yàn):H8、H9、 H10、H11、H12、H13、H14 、H15根據(jù)校驗(yàn)時(shí)根據(jù)校驗(yàn)時(shí)偶校驗(yàn)偶校驗(yàn),可以寫出相應(yīng)的校驗(yàn)方程。,可以寫出相應(yīng)的校驗(yàn)方程。例:例:設(shè)有一個(gè)設(shè)有一個(gè)7位信息碼位位信息碼位0110001,求它的海明碼。,求它
36、的海明碼。解:解: 此例中,信息位此例中,信息位n=7,根據(jù)海明不等式,可求得校驗(yàn)位,根據(jù)海明不等式,可求得校驗(yàn)位最短長度最短長度k=4。其海明碼先表示如下:其海明碼先表示如下:海明碼位號(hào):海明碼位號(hào):H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1海明碼:海明碼: 0 1 1 P4 0 0 0 P3 1 P2 P1按偶校驗(yàn)寫出校驗(yàn)方程為:按偶校驗(yàn)寫出校驗(yàn)方程為: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。 方法方法:將錯(cuò)了的碼字重新代入校驗(yàn)方程校驗(yàn)一次即可。假設(shè):將錯(cuò)了的碼字重新代入校驗(yàn)方程校驗(yàn)一次即可。假設(shè)上面例子中的海明碼上面例子中的海明碼01100000100傳送后,若傳送后,若H6位發(fā)生了位發(fā)生了錯(cuò)誤,變成了錯(cuò)誤,變成了01100100100,這時(shí)把它們代入上面的偶校,這時(shí)把它們代入上面的偶校驗(yàn)校驗(yàn)方程,如下:驗(yàn)校驗(yàn)方程,如下: 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看成一個(gè)看成一個(gè)“錯(cuò)誤字錯(cuò)誤字”,因?yàn)槠涠?,因?yàn)槠涠M(jìn)制碼為進(jìn)制碼為0110,說明,說明H6出了錯(cuò),是出了錯(cuò),是H6錯(cuò)成了錯(cuò)成了1,所以要糾錯(cuò),所以要糾錯(cuò),糾錯(cuò)時(shí)將糾錯(cuò)時(shí)將H6位取反值,即讓它恢復(fù)到正確值位取反值,即讓它恢復(fù)到正確值0。這樣糾錯(cuò)后。這樣糾錯(cuò)后即可得到正確的海明碼即可得到正確的海明碼01100000100。5檢錯(cuò)與糾錯(cuò)檢錯(cuò)與糾錯(cuò)1 1CRCCRC的編碼方法的編碼方法循環(huán)冗余校驗(yàn)碼循環(huán)冗余校驗(yàn)碼循環(huán)冗余校驗(yàn)碼(循環(huán)冗余校驗(yàn)碼(CRC)的基本原
39、理是:)的基本原理是:在在K位信息碼后再拼位信息碼后再拼接接R位的校驗(yàn)碼,整個(gè)編碼長度為位的校驗(yàn)碼,整個(gè)編碼長度為N位,因此,這種編碼又叫位,因此,這種編碼又叫(N,K)碼。對(duì)于一個(gè)給定的()碼。對(duì)于一個(gè)給定的(N,K)碼,可以證明存在一)碼,可以證明存在一個(gè)最高次冪為個(gè)最高次冪為N-K=R的多項(xiàng)式的多項(xiàng)式G(x)。根據(jù)。根據(jù)G(x)可以生成可以生成K位信位信息的校驗(yàn)碼,而息的校驗(yàn)碼,而G(x)叫做這個(gè)叫做這個(gè)CRC碼的生成多項(xiàng)式。碼的生成多項(xiàng)式。 校驗(yàn)碼的具體生成過程為:假設(shè)發(fā)送信息用信息多項(xiàng)式校驗(yàn)碼的具體生成過程為:假設(shè)發(fā)送信息用信息多項(xiàng)式C(X)表示,將表示,將C(x)左移左移R位,則可
40、表示成位,則可表示成C(x)*2R ,這樣,這樣C(x)的右邊的右邊就會(huì)空出就會(huì)空出R位,這就是校驗(yàn)碼的位置。通過位,這就是校驗(yàn)碼的位置。通過C(x)* 2R除以生成除以生成多項(xiàng)式多項(xiàng)式G(x)得到的余數(shù)就是校驗(yàn)碼。得到的余數(shù)就是校驗(yàn)碼。 幾個(gè)基本概念幾個(gè)基本概念1、多項(xiàng)式與二進(jìn)制數(shù)碼、多項(xiàng)式與二進(jìn)制數(shù)碼 n多項(xiàng)式包括生成多項(xiàng)式多項(xiàng)式包括生成多項(xiàng)式G(x)和信息多項(xiàng)式和信息多項(xiàng)式C(x)。 n如生成多項(xiàng)式為如生成多項(xiàng)式為G(x)=x4+x3+x+1, 可轉(zhuǎn)可轉(zhuǎn)換為二進(jìn)制數(shù)碼換為二進(jìn)制數(shù)碼11011。 n而發(fā)送信息位而發(fā)送信息位 1111,可轉(zhuǎn)換為數(shù)據(jù)多項(xiàng)式,可轉(zhuǎn)換為數(shù)據(jù)多項(xiàng)式為為C(x)=x3
41、+x2+x+1。 2 2模模2 2運(yùn)算:運(yùn)算:不考慮借位和進(jìn)位不考慮借位和進(jìn)位(1 1)模)模2 2加減:加減:可用異或門實(shí)現(xiàn),即:可用異或門實(shí)現(xiàn),即: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減求部分余數(shù),每上一位商,部分余減求部分余數(shù),每上一位商,部分余數(shù)要減少一位,數(shù)要減少一位
42、,上商規(guī)則是上商規(guī)則是:只要余數(shù)最高位為:只要余數(shù)最高位為1,則商,則商1,否則為否則為0。當(dāng)部分余數(shù)的位數(shù)小于除數(shù)時(shí),該余數(shù)為最后余數(shù)。當(dāng)部分余數(shù)的位數(shù)小于除數(shù)時(shí),該余數(shù)為最后余數(shù)。例如:例如: 111.商11(除數(shù)) 1000(被除數(shù)) 11 10 11 10 11 1CRC碼的生成(一)碼的生成(一)n多項(xiàng)式除法n1、將碼多項(xiàng)式C(x)乘以xrn2、用G(x)除C(x)*xr,得余式R(x)n3、 C(x)*xr+ R(x)及編碼后的多項(xiàng)式例: G(x)=x4+x3+x+1,C(x)=x3+x2+x+1,R=4nC(x)*x4/G(x) = x2+1n校驗(yàn)碼:校驗(yàn)碼:0101n完整編碼:
43、完整編碼:11110101CRC碼的生成(二)碼的生成(二)n1、將x的最高冪次為R的生成多項(xiàng)式G(x)轉(zhuǎn)換成對(duì)應(yīng)的R+1位二進(jìn)制數(shù)。 n2、將信息碼左移R位,相當(dāng)與對(duì)應(yīng)的信息多項(xiàng)式C(x)*2R n3、用生成多項(xiàng)式(二進(jìn)制數(shù))對(duì)信息碼做模2除,得到R位的余數(shù)。 n4、將余數(shù)拼到信息碼左移后空出的位置,得到完整的CRC碼。 例例 設(shè)四位有效信息位是設(shè)四位有效信息位是11001100,選用生成多項(xiàng)式,選用生成多項(xiàng)式 G(X)=G(X)=1 1011011,試求有效信息位試求有效信息位11001100的的CRCCRC編碼。編碼。 解:解: (1)(1)將有效信息位將有效信息位11001100表示為
44、多項(xiàng)式表示為多項(xiàng)式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位的生成多項(xiàng)式位的生成多項(xiàng)式 G(X)G(X),對(duì),對(duì)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位余數(shù)位余數(shù)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加加) ) 因?yàn)橐驗(yàn)閗=7k=7、n=4n=4,所以編好的,所以編好的CRCCRC碼又稱為碼又稱為(7(7,4)4)碼。碼。3 3CRCCRC的譯碼及糾錯(cuò)的譯碼及糾錯(cuò) CRC CRC碼傳送到目標(biāo)部件,用約定的多項(xiàng)式碼傳送到目標(biāo)部件,用約定的多項(xiàng)式G(x)
46、G(x)對(duì)收到的對(duì)收到的CRCCRC碼進(jìn)行碼進(jìn)行“模模2 2除除”,若余數(shù)為若余數(shù)為0 0,則表明該,則表明該CRCCRC校驗(yàn)碼正確;校驗(yàn)碼正確;否則表明有錯(cuò),不同的出錯(cuò)位,其余數(shù)是不同的。由余數(shù)否則表明有錯(cuò),不同的出錯(cuò)位,其余數(shù)是不同的。由余數(shù)具體指出是哪一位出了錯(cuò),然后加以糾正。具體指出是哪一位出了錯(cuò),然后加以糾正。 不同的出錯(cuò)位,其余數(shù)也是不同的。不同的出錯(cuò)位,其余數(shù)也是不同的。可以證明:更換不同的有效信息位,余數(shù)與出錯(cuò)位的可以證明:更換不同的有效信息位,余數(shù)與出錯(cuò)位的對(duì)應(yīng)關(guān)系不會(huì)發(fā)生變化,只與碼制和生成多項(xiàng)式對(duì)應(yīng)關(guān)系不會(huì)發(fā)生變化,只與碼制和生成多項(xiàng)式G(X)G(X)有關(guān)。有關(guān)。不是任何
47、一個(gè)不是任何一個(gè)(k+1)(k+1)位多項(xiàng)式都能作為生成多項(xiàng)式,從檢位多項(xiàng)式都能作為生成多項(xiàng)式,從檢錯(cuò)、糾錯(cuò)的要求來看,生成多項(xiàng)式應(yīng)滿足下列要求:錯(cuò)、糾錯(cuò)的要求來看,生成多項(xiàng)式應(yīng)滿足下列要求:(1)(1)任何一位發(fā)生錯(cuò)誤,都應(yīng)使余數(shù)不為零;任何一位發(fā)生錯(cuò)誤,都應(yīng)使余數(shù)不為零;(2)(2)不同位發(fā)生錯(cuò)誤,都應(yīng)使余數(shù)不同;不同位發(fā)生錯(cuò)誤,都應(yīng)使余數(shù)不同;(3)(3)用余數(shù)補(bǔ)零,繼續(xù)作用余數(shù)補(bǔ)零,繼續(xù)作“模模2 2除除”,應(yīng)使余數(shù)循環(huán)。,應(yīng)使余數(shù)循環(huán)。常用的常用的CRCCRC生成多項(xiàng)式:生成多項(xiàng)式: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產(chǎn)生電路產(chǎn)生電路 CRCCRC校驗(yàn)碼不僅檢錯(cuò)率高,而且硬件實(shí)現(xiàn)簡單,因而到校驗(yàn)碼不僅檢錯(cuò)率高,而且硬件實(shí)
49、現(xiàn)簡單,因而到底廣泛應(yīng)用。底廣泛應(yīng)用。4 4關(guān)于生成多項(xiàng)式關(guān)于生成多項(xiàng)式Questions and Answers計(jì)算機(jī)中常用的數(shù)據(jù)表示格式有兩種計(jì)算機(jī)中常用的數(shù)據(jù)表示格式有兩種: 定點(diǎn)格式定點(diǎn)格式容許的數(shù)值范圍有限,但要求的處理硬件比容許的數(shù)值范圍有限,但要求的處理硬件比 較簡單。較簡單。 浮點(diǎn)格式浮點(diǎn)格式容許的數(shù)值范圍很大,但要求的處理硬件比容許的數(shù)值范圍很大,但要求的處理硬件比 較復(fù)雜。較復(fù)雜。1.1.定點(diǎn)數(shù)的表示方法定點(diǎn)數(shù)的表示方法定點(diǎn)表示定點(diǎn)表示:約定機(jī)器中所有數(shù)據(jù)的小數(shù)點(diǎn)位置是固定不變的。:約定機(jī)器中所有數(shù)據(jù)的小數(shù)點(diǎn)位置是固定不變的。 ( (由于約定在固定的位置,小數(shù)點(diǎn)就不再使用記
50、號(hào)由于約定在固定的位置,小數(shù)點(diǎn)就不再使用記號(hào)“.”.” 來表示。來表示。) ) 通常將數(shù)據(jù)表示成通常將數(shù)據(jù)表示成純小數(shù)純小數(shù)或或純整數(shù)。純整數(shù)。數(shù)據(jù)表示數(shù)據(jù)表示定點(diǎn)數(shù)定點(diǎn)數(shù):小數(shù)點(diǎn)位置固定不變的數(shù)小數(shù)點(diǎn)位置固定不變的數(shù)定點(diǎn)整數(shù)定點(diǎn)整數(shù):小數(shù)點(diǎn)固定在小數(shù)點(diǎn)固定在最低位最低位數(shù)的數(shù)的右面右面(b) 定點(diǎn)小數(shù)x7x6x5x4x3x2x1x0(a) 定點(diǎn)整數(shù)x6x7x5x4x3x2x1x0數(shù)值范圍:數(shù)值范圍: 純小數(shù)純小數(shù) 0 |x| 1 2-n 純整數(shù)純整數(shù) 0 |x| 2n 1 目前計(jì)算機(jī)中多采用定點(diǎn)純整數(shù)表示,因此將定點(diǎn)數(shù)表示目前計(jì)算機(jī)中多采用定點(diǎn)純整數(shù)表示,因此將定點(diǎn)數(shù)表示的運(yùn)算簡稱為的運(yùn)算簡
51、稱為整數(shù)運(yùn)算整數(shù)運(yùn)算。定點(diǎn)小數(shù)定點(diǎn)小數(shù):小數(shù)點(diǎn)固定在小數(shù)點(diǎn)固定在最高位最高位數(shù)的數(shù)的后面后面,即純小數(shù)表示,即純小數(shù)表示真值真值:正、負(fù)號(hào)加某進(jìn)制數(shù)絕對(duì)值的形式稱為真值。如+3,-5等,即實(shí)際值。機(jī)器數(shù)機(jī)器數(shù):符號(hào)以及數(shù)值都數(shù)碼化的數(shù)稱為機(jī)器數(shù)如 :X=01011 Y=11011 即真值在機(jī)器中的表示,稱為機(jī)器數(shù)名詞解釋:真值和機(jī)器數(shù)名詞解釋:真值和機(jī)器數(shù)計(jì)算機(jī)中計(jì)算機(jī)中定點(diǎn)數(shù)定點(diǎn)數(shù)表示方法表示方法 原碼、補(bǔ)碼、反碼、移碼原碼、補(bǔ)碼、反碼、移碼。 若若定點(diǎn)小數(shù)定點(diǎn)小數(shù)的原碼形式為的原碼形式為 x0. x1 x2 xn, ,(共(共n+1n+1位)則原位)則原碼表示的定義是:碼表示的定義是:式中
52、式中x原原是機(jī)器數(shù),是機(jī)器數(shù),x是真值。是真值。1 1、原碼表示法、原碼表示法 (1)(1)定點(diǎn)小數(shù)定點(diǎn)小數(shù) x 1 x = 1+ |x| -1 x 00 x 1x原原 = 數(shù)的機(jī)器碼表示數(shù)的機(jī)器碼表示 若若定點(diǎn)整數(shù)定點(diǎn)整數(shù)的原碼形式為的原碼形式為 x0 x1 x2 xn, ,則原碼表示的定則原碼表示的定義是:義是:(2)(2)定點(diǎn)整數(shù)定點(diǎn)整數(shù) x 2n x = 2n + |x| -2n x 00 x 0X0時(shí)時(shí) X + M M 自動(dòng)丟失,自動(dòng)丟失, x補(bǔ)補(bǔ)= X (Mod M)當(dāng)當(dāng)X0X0時(shí)時(shí) X + M = M - | X | M, x補(bǔ)補(bǔ)= X + M (Mod M) 若若定點(diǎn)小數(shù)定點(diǎn)小
53、數(shù)的補(bǔ)碼形式為的補(bǔ)碼形式為 x0. x1 x2 xn, ,則補(bǔ)碼表示的定則補(bǔ)碼表示的定義是:義是:(2)定點(diǎn)小數(shù)定點(diǎn)小數(shù) x0 x 1 2 + x = 2 |x| -1 x 0 x補(bǔ)補(bǔ) = (mod 2)例例: x = +0.1011, 則則 x補(bǔ)補(bǔ)=0.1011x = -0.1011, 則則 x補(bǔ)補(bǔ)=10+x = 10.0000-0.1011= 1.0101 對(duì)于對(duì)于0,+0補(bǔ)補(bǔ)-0補(bǔ)補(bǔ)0.0000 (mod 2) 注意:注意:0的補(bǔ)碼表示只有一種形式。的補(bǔ)碼表示只有一種形式。 若若定點(diǎn)整數(shù)定點(diǎn)整數(shù)的補(bǔ)碼形式為的補(bǔ)碼形式為 x0 x1 x2 xn, ,則補(bǔ)碼表示的定則補(bǔ)碼表示的定義是:義是:
54、(3)(3)定點(diǎn)整數(shù)定點(diǎn)整數(shù) x 2n+1 + x = 2n+1 |x| -2n x 00 x 2nx補(bǔ)補(bǔ) =(mod 2n+1)例例: x = +0111, 則則 x補(bǔ)補(bǔ)=00111 x = -0111, 則則 x補(bǔ)補(bǔ)=24+1 |-0111|=100000 0111=11001補(bǔ)碼補(bǔ)碼最高一位為符號(hào)位,最高一位為符號(hào)位,0正正1負(fù)負(fù);補(bǔ)碼補(bǔ)碼零有唯一編碼;零有唯一編碼;補(bǔ)碼補(bǔ)碼能很好用于加減運(yùn)算。能很好用于加減運(yùn)算。(4)(4)特點(diǎn)特點(diǎn)補(bǔ)碼補(bǔ)碼滿足滿足 -x補(bǔ)補(bǔ)+ x補(bǔ)補(bǔ)=0 +7補(bǔ)補(bǔ)=00111最高位參與演算,與其它位一樣對(duì)待。最高位參與演算,與其它位一樣對(duì)待。 -7補(bǔ)補(bǔ)=11001擴(kuò)展
55、方便。擴(kuò)展方便。5位的位的補(bǔ)碼補(bǔ)碼擴(kuò)展為擴(kuò)展為8位位 00111 0000011111001 11111001算術(shù)移位。假設(shè)算術(shù)移位。假設(shè) x補(bǔ)補(bǔ)= x0. x1 x2 xn, , x/2補(bǔ)補(bǔ)= x0. x0 x1 x2 xn-1最大的優(yōu)點(diǎn)就是將減法運(yùn)算轉(zhuǎn)換成加法運(yùn)算。最大的優(yōu)點(diǎn)就是將減法運(yùn)算轉(zhuǎn)換成加法運(yùn)算。X+YX+Y補(bǔ)補(bǔ)= X= X補(bǔ)補(bǔ)+Y+Y補(bǔ)補(bǔ)X - YX - Y補(bǔ)補(bǔ) = X= X補(bǔ)補(bǔ)+ -Y+ -Y補(bǔ)補(bǔ)例如例如: X=(11)X=(11)1010=(1011)=(1011)2 2 Y=(5) Y=(5)1010=(0101)=(0101)2 2已知字長已知字長n=5n=5位位XX補(bǔ)補(bǔ)
56、+ -Y+ -Y補(bǔ)補(bǔ)=01011+11011=01011+11011=1 100110=00110=(6)00110=00110=(6)10 10 注:注: 最高最高1 1位已經(jīng)超過字長故應(yīng)丟掉位已經(jīng)超過字長故應(yīng)丟掉X - Y補(bǔ)= 0110補(bǔ)=00110原碼與補(bǔ)碼之間的轉(zhuǎn)換已知原碼求補(bǔ)碼已知原碼求補(bǔ)碼正數(shù)正數(shù) X X補(bǔ)補(bǔ)=X=X原原負(fù)數(shù)負(fù)數(shù) 符號(hào)除外,各位取反,末位加符號(hào)除外,各位取反,末位加1 1例例:X= -1001001X= -1001001 X X原原= =1 110010011001001 X X補(bǔ)補(bǔ)= =1 10110110+1=0110110+1=1 10110111011011
57、1 X X補(bǔ)補(bǔ)= 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補(bǔ)碼與真值之間的轉(zhuǎn)換補(bǔ)碼與真值之間的轉(zhuǎn)換補(bǔ)碼
58、補(bǔ)碼符號(hào)位為符號(hào)位為“1”1”-負(fù),余下求補(bǔ)為數(shù)值部分負(fù),余下求補(bǔ)為數(shù)值部分符號(hào)位為符號(hào)位為“0”0”-正,余下為數(shù)值部分正,余下為數(shù)值部分例例:XX補(bǔ)補(bǔ) = = 0 0100 1001 X= 0100 1001 100 1001 X= 0100 1001 例:例:XX補(bǔ)補(bǔ) = =1 1000 0000 X=000 0000 X=- 1000 0000B = 80H =-128- 1000 0000B = 80H =-128(1)(1)定點(diǎn)小數(shù)定義定點(diǎn)小數(shù)定義 x x (2 2 (2 2-n-n) + ) + x x -1 -1 x x 0 00 0 x x 1 1 x x 反反 = =一般情
59、況下一般情況下, , 對(duì)于正數(shù)對(duì)于正數(shù) x x = +0.= +0.x x1 1x x2 2 x xn, n, 則有:則有: x x 反反= 0.= 0.x x1 1x x2 2 x xn n 對(duì)于負(fù)數(shù)對(duì)于負(fù)數(shù) 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、反碼表示法、反碼表示法 所謂反碼所謂反碼, , 就是二進(jìn)制的各位數(shù)碼就是二進(jìn)制的各位數(shù)碼0 0變?yōu)樽優(yōu)? 1,1 1變?yōu)樽優(yōu)? 0。例:例: x x = 0.10110 -0.10110 0.0000 = 0.10110 -0.1011
60、0 0.0000 x x 反反= =(2)(2)由反碼求補(bǔ)碼的公式由反碼求補(bǔ)碼的公式 (2-2 (2-2-n-n) + ) + x x x x 反反 = = 2 + 2 + x x x x 補(bǔ)補(bǔ) = =由反碼與補(bǔ)碼的定義由反碼與補(bǔ)碼的定義得:得: x x 反反 + 2+ 2-n-n x x 補(bǔ)補(bǔ) = = 即:若要一個(gè)即:若要一個(gè)負(fù)數(shù)變補(bǔ)碼,其方負(fù)數(shù)變補(bǔ)碼,其方法是符號(hào)位置法是符號(hào)位置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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年保密協(xié)議文檔
- 2025年產(chǎn)假補(bǔ)償協(xié)議
- 2025年醫(yī)療服務(wù)營養(yǎng)配餐協(xié)議
- 2025年代理商代理傭金費(fèi)協(xié)議
- 2025年大型露天演出場地租用協(xié)議
- 2025年生存保險(xiǎn)受益人變更申請(qǐng)
- 《用友業(yè)務(wù)流程》課件
- 二零二五版增值稅發(fā)票委托第三方服務(wù)框架協(xié)議3篇
- 事業(yè)單位2024年度勞動(dòng)合同定制版
- 二零二五年度知識(shí)產(chǎn)權(quán)侵權(quán)賠償合同補(bǔ)充協(xié)議3篇
- 2024-2030年中國連續(xù)性腎臟替代治療(CRRT)行業(yè)市場發(fā)展趨勢與前景展望戰(zhàn)略分析報(bào)告
- 跨學(xué)科主題學(xué)習(xí):實(shí)施策略、設(shè)計(jì)要素與評(píng)價(jià)方式(附案例)
- 場地委托授權(quán)
- 2024年四川省成都市龍泉驛區(qū)中考數(shù)學(xué)二診試卷(含答案)
- 項(xiàng)目工地春節(jié)放假安排及安全措施
- 印染廠安全培訓(xùn)課件
- 紅色主題研學(xué)課程設(shè)計(jì)
- 胸外科手術(shù)圍手術(shù)期處理
- 裝置自動(dòng)控制的先進(jìn)性說明
- 《企業(yè)管理課件:團(tuán)隊(duì)管理知識(shí)點(diǎn)詳解PPT》
- 移動(dòng)商務(wù)內(nèi)容運(yùn)營(吳洪貴)任務(wù)二 軟文的寫作
評(píng)論
0/150
提交評(píng)論