組成原理課件 Computer Data Reprensation V12.8

1、,二、計(jì)算機(jī)數(shù)據(jù)表示,譚志虎,本章主要內(nèi)容,2.1 非數(shù)值數(shù)據(jù)表示法 2.2 數(shù)值數(shù)據(jù)表示法 2.3 數(shù)據(jù)信息的校驗(yàn),數(shù)據(jù)表示 Data Representation,非數(shù)值數(shù)據(jù) Qualitative C語(yǔ)言 char型 數(shù)值數(shù)據(jù) Quantitative 整數(shù) Integers Signed / Unsigned C語(yǔ)言 short int long 型 int8_t uint8_t int16_t uint16_t int32_t uint32_t int64_t uint64_t 非整數(shù) Non-integers (Real) Signed / Unsigned C語(yǔ)言 float d

2、ouble 型 匯編語(yǔ)言有無(wú)數(shù)據(jù)類型？,C99 stdint.h,typedef signed char int8_t; typedef unsigned char uint8_t; typedef short int16_t; typedef unsigned short uint16_t; typedef int int32_t; typedef unsigned uint32_t; typedef long long int64_t; typedef unsigned long long uint64_t;,2.1 非數(shù)值數(shù)據(jù)表示法,字符表示法 characters 漢字表示法 Chin

3、ese characters,2.1.1 Character representation ,如何使用數(shù)值表示字符數(shù)據(jù) Standards ASCII-American Standard Code for Information Interchange (ANSI 7bits) EBCDIC-Extended Binary-Coded Decimal Interchange Code (IBM 8bits) Unicode,128 Standard ASCII codes,52 Letters a-z, A-Z 10 Digits 0-9 34 Symbols ! # $ % 4 printf

4、(n%d ,a); 5 printf(n%d ,b); 6 printf(n%d ,c); 7 return(); ,127,-127,-128,？,機(jī)器數(shù)表示問(wèn)題,2.2 數(shù)值數(shù)據(jù)表示方法,計(jì)算機(jī)數(shù)值數(shù)據(jù)表示的特點(diǎn) 進(jìn)位制數(shù) 數(shù)的定點(diǎn)、浮點(diǎn)表示 機(jī)器數(shù),2.2.2 機(jī)器數(shù)/機(jī)器碼,真值 (書(shū)寫(xiě)用) 將用+ -表示正負(fù)的二進(jìn)制數(shù)稱為符號(hào)數(shù)的真值 機(jī)器不能識(shí)別書(shū)寫(xiě)格式，計(jì)算機(jī)如何表示負(fù)數(shù)？ 機(jī)器碼 (機(jī)器內(nèi)部使用) 將符號(hào)和數(shù)值一起編碼表示的二進(jìn)制數(shù)稱為機(jī)器碼 四種機(jī)器碼 原碼 Signed magnitude 反碼 Ones complement 補(bǔ)碼 Twos complement 移碼 B

5、iased notation,計(jì)算機(jī)內(nèi)存中的某個(gè)32位編碼到底是什么編碼？,原碼表示法（Signed magnitude）,增加符號(hào)位 Add a sign bit 最高位為符號(hào)位，0：正，1：負(fù)，數(shù)值位不變 符號(hào)位的權(quán)值是多少？,符號(hào)位權(quán)值是2n,符號(hào)位權(quán)值是1,原碼表示示例,+0原=0.0000 -0原=1.0000 -0.1111原 = 1.1111 0.1111原 = 0.1111 1110原 = 01110 -1110原 = 11110,原碼表示區(qū)間,定點(diǎn)小數(shù)x0.x1x2xn 0.111 +0.111 (12-n), 12-n 或 (1,1) 定點(diǎn)整數(shù)x0 x1x2xn 0111

6、+0111 (2n1), 2n1 或 (2n, 2n ) 對(duì)稱區(qū)間,原碼特性,直觀易懂 第一位為符號(hào)位 其他為數(shù)值位 正零負(fù)零兩個(gè)零 加、減運(yùn)算方式不統(tǒng)一 符號(hào)相異加法不能直接運(yùn)算 特別當(dāng) ab時(shí)，實(shí)現(xiàn) a-b比較困難 從50年代開(kāi)始，整數(shù)都采用補(bǔ)碼來(lái)表示 但浮點(diǎn)數(shù)的尾數(shù)用原碼定點(diǎn)小數(shù)表示,010110012 = 8910 + 110011012 = -7710 001001102 = 3810,反碼表示法,所謂反碼，就是二進(jìn)制的各位數(shù)碼取反 符號(hào)位表示方法與原碼相同 Example: 710 = 001112 710 = 110002 Called Ones Complement +0反=0

7、.0000 0反=1.1111 0.1111反=0.1111 0.1111反=1.0000 1110反=01110 1110反=10001,反碼表示法,反碼公式證明,定點(diǎn)小數(shù) -1x=0時(shí) 假設(shè) x=-0.x1x2xn 假x反= 1.x1x2xn x反+|x|=1.111 =1.111+0.001-0.001 =10.000-0.001 =2-2-n x反=2-2-n-|x|=2-2-n+x 定點(diǎn)整數(shù)證明方法相同,反碼表示區(qū)間,定點(diǎn)小數(shù) x0.x1x2xn 0.111 +0.111 (1-2-n),1-2-n 或 (-1,1) 定點(diǎn)整數(shù) x0 x1x2xn 0111 +0111 (2n1),

8、2n1 或 (2n, 2n ) 對(duì)稱區(qū)間,反碼特性,兩個(gè)零 求反用邏輯門(mén)容易實(shí)現(xiàn) 運(yùn)算仍然很復(fù)雜 相加時(shí)需要將符號(hào)位的進(jìn)位位增加到LSB上,有趣的時(shí)鐘,9與-3、21等效,12,3,6,9,同余的概念,假定有兩個(gè)數(shù)a和b，若用某一個(gè)整數(shù)m去除，所得的余數(shù)相同，就稱a,b兩個(gè)數(shù)對(duì)m同余,記作： ab (mod m) 模為m 假設(shè)X,Y,Z三個(gè)數(shù)，滿足下列關(guān)系：Z=nX+Y (n為整數(shù)),則稱Z和Y對(duì)模X是同余的，記作： ZY (mod X) YZ (mod X) 以12為模 9 12+9 24+9 36+9 9 21 33 45 -3 12-3 9,例子,7+(-3) =7+(12-3) =7+

9、9 =16 =4 表示負(fù)數(shù)的時(shí)候如利用模的性質(zhì)轉(zhuǎn)換成正數(shù)， 即可將原碼運(yùn)算中的減法變成加法運(yùn)算,補(bǔ)碼公式,模：符號(hào)位進(jìn)位位的權(quán)值 真值為正數(shù)，補(bǔ)碼等于原數(shù)據(jù) 真值為負(fù)數(shù)，增加一個(gè)模,模是2n+1,模是2,補(bǔ)碼與反碼的關(guān)系,定點(diǎn)小數(shù) x反=2-2-n+x x補(bǔ)=2+x =(2-2-n+x)+2-n =x反+2-n,整數(shù) x反=2n+1-1+x x補(bǔ)=2n+1+x =(2n+1-1+x)+1 = x反+1,當(dāng)X為負(fù)數(shù)時(shí)，補(bǔ)碼等于反碼末位加1,補(bǔ)碼編碼的簡(jiǎn)便方法,正值直接取其原來(lái)的二進(jìn)制碼，符號(hào)位為0 負(fù)值則逐位取反，末位加1，符號(hào)位為1 -10101010補(bǔ) =1 01010101+1 =1 01

10、010110 -0.010101補(bǔ)=1.101011 掃描法 從最右側(cè)開(kāi)掃描找到第一個(gè)1，該數(shù)位左側(cè)所有數(shù)據(jù)位取反，其他數(shù)據(jù)位不變,例子,X=-0.11111111 X補(bǔ) =? X補(bǔ) =1.00000000 +0.00000001 =1.00000001 X=-0.00000001 X補(bǔ) =1.11111111 X=-000000001 X補(bǔ) =111111111,X=-0.00000000 X補(bǔ) =? X補(bǔ) =1.11111111 +0.00000001 =10.00000000 =0.00000000,補(bǔ)碼特性,零有唯一的表示方式 0.0000補(bǔ)= -0.0000補(bǔ)= 0.0000 -1.

11、0的補(bǔ)碼 1.0000補(bǔ)= 0.1111+0.0001=1.0000 2+X=2-1=1 補(bǔ)碼相對(duì)原碼少一個(gè)負(fù)零，多一個(gè)負(fù)一，,補(bǔ)碼表示區(qū)間,定點(diǎn)小數(shù)x0.x1x2xn -1.000 +0.111 -1,1-2-n 或 -1,1) 定點(diǎn)整數(shù)x0 x1x2xn -1000 +0111 -2n, 2n-1 或 -2n, 2n ) 非對(duì)稱區(qū)間，左側(cè)多一個(gè)數(shù),雙符號(hào)位補(bǔ)碼（變形補(bǔ)碼） 模=？,例：0001010110 1101010001,例：00.01010110 11.01010001,符號(hào)位01表示正溢出，10表示負(fù)溢出，最高位表示正確符號(hào)位,補(bǔ)碼加減法的實(shí)現(xiàn),X + Y補(bǔ)= X補(bǔ)+ Y補(bǔ) XY

12、補(bǔ)= X補(bǔ)+ Y補(bǔ) Y補(bǔ)= Y補(bǔ)補(bǔ) 對(duì) Y補(bǔ)逐位取反, 再在最低位加 1,補(bǔ)碼加減法運(yùn)算實(shí)例,x=0.1011 y= -0.0101 用模4補(bǔ)碼 求x+y x-y x補(bǔ) = 00 1011, y補(bǔ) = 11 1011 -y補(bǔ) = 00 0101,補(bǔ)碼表示中的符號(hào)位擴(kuò)展,由 X補(bǔ) 求 X / 2補(bǔ) 原符號(hào)位不變，符號(hào)位與數(shù)值位均右移一位， X補(bǔ) =10010 則 X/2補(bǔ) =11001 符號(hào)向右擴(kuò)展 2x補(bǔ)=? 左移，末位補(bǔ)零，符號(hào)變化溢出 不同位數(shù)的整數(shù)補(bǔ)碼相加減時(shí)，如何運(yùn)算,補(bǔ)碼表示中的符號(hào)位擴(kuò)展,不同位數(shù)的整數(shù)補(bǔ)碼相加減時(shí) 位數(shù)少的補(bǔ)碼符號(hào)位向左擴(kuò)展 一直擴(kuò)展到符號(hào)位對(duì)齊,補(bǔ)碼特性,唯一的

13、零 符號(hào)位可以直接參與運(yùn)算 減法可以變成加法，運(yùn)算電路統(tǒng)一 負(fù)數(shù)比整數(shù)多一個(gè) Twos complement is the standard for integer !,移碼表示法 Biased/Excess Notation,定義 x移 = 2n+x -2n x 2n 保持?jǐn)?shù)據(jù)原有大小順序，便于進(jìn)行比較操作。 與補(bǔ)碼的符號(hào)位相異，數(shù)據(jù)位相同 X=+10101 X移 =25+10101=110101 X=-10101 X移 =25-10101001011 僅用于表示整數(shù)，通常表示浮點(diǎn)數(shù)的階碼,不同機(jī)器碼公式對(duì)比,定點(diǎn)數(shù)機(jī)器碼表示范圍,n+1位定點(diǎn)數(shù)，數(shù)據(jù)位n位,原碼反碼,補(bǔ)碼,12n, 2n1

14、,2n1, 12n,2n, 2n1,1, 12n,移碼,2n, 2n1,小數(shù)無(wú)移碼,(2n, 2n),(1, 1),2n, 2n),1, 1),2n, 2n),機(jī)器碼小結(jié),MSB表示數(shù)符 4種定點(diǎn)編碼方式 原碼 用來(lái)表示浮點(diǎn)（實(shí)）數(shù)的尾數(shù) 反碼 已不用于表示數(shù)值數(shù)據(jù) 補(bǔ)碼 50年代開(kāi)始成為整數(shù)標(biāo)準(zhǔn) 移碼 用于浮點(diǎn)數(shù)階碼 補(bǔ)碼優(yōu)勢(shì) 模運(yùn)算，加、減運(yùn)算統(tǒng)一 唯一0，方便使用,C語(yǔ)言中的機(jī)器碼？,main() char a=127,b=128,c=129;d=257 printf(n%d ,a); printf(n%d ,b); printf(n%d ,c); printf(n%d ,d); ret

15、urn(0); ,127,-127,-128,？,機(jī)器碼賦值,真值輸出,變量a，b，c 機(jī)器碼實(shí)際存儲(chǔ)值是多少？,1,變量?jī)?nèi)存值？,char 127 = 127 = 7F,char 128 = -128 = FFFFFF80,char 129 = -127 = FFFFFF81,8081-FF7F,機(jī)器碼賦值,真值輸出,機(jī)器碼輸出,內(nèi)存輸出,反匯編,a=127;,b=128;,c=129;,d=-1;,aedx,aeax,edx形參,eax形參,打印格式地址形參,調(diào)用printf,變量a，b,c,d內(nèi)存地址為啥不連續(xù)？,C語(yǔ)言中的定點(diǎn)數(shù),無(wú)符號(hào)整數(shù) unsigned char unsigned

16、 short unsigned int 一般用于地址運(yùn)算，編號(hào)表示 有符號(hào)整數(shù) char short int long 采用補(bǔ)碼表示 無(wú)符號(hào)整數(shù)的最大值大于位數(shù)相同的帶符號(hào)整數(shù)的最大值 8位無(wú)符號(hào)整數(shù)最大是255（1111 1111） 8位帶符號(hào)整數(shù)最大為127（0111 1111）,32 位補(bǔ)碼表示范圍,-231，231-1,0000 0000 0000 0000 0000 0000 0000 0000two = 0ten0000 0000 0000 0000 0000 0000 0000 0001two = + 1ten0000 0000 0000 0000 0000 0000 0000

17、0010two = + 2ten.0111 1111 1111 1111 1111 1111 1111 1110two = + 2,147,483,646ten0111 1111 1111 1111 1111 1111 1111 1111two = + 2,147,483,647ten1000 0000 0000 0000 0000 0000 0000 0000two = 2,147,483,648ten1000 0000 0000 0000 0000 0000 0000 0001two = 2,147,483,647ten1000 0000 0000 0000 0000 0000 0000

18、0010two = 2,147,483,646ten.1111 1111 1111 1111 1111 1111 1111 1101two = 3ten1111 1111 1111 1111 1111 1111 1111 1110two = 2ten1111 1111 1111 1111 1111 1111 1111 1111two = 1ten,Limits of exact-width integer types,/ c99 stdint.h #define INT8_MIN (-128) #define INT16_MIN (-32768) #define INT32_MIN (-214

19、7483647 - 1) #define INT64_MIN (-9223372036854775807LL - 1) #define INT8_MAX 127 #define INT16_MAX 32767 #define INT32_MAX 2147483647 #define INT64_MAX 9223372036854775807LL #define UINT8_MAX 0 xff /* 255U */ #define UINT16_MAX 0 xffff /* 65535U */ #define UINT32_MAX 0 xffffffff /* 4294967295U */ #d

20、efine UINT64_MAX 0 xffffffffffffffffULL,why not -2147483648?,32位機(jī)器上的程序,main() int x=-1; unsigned u = 2147483648; printf ( x = %u = %X = %dn,x,x,x); printf ( u = %u = %X = %dn,u,u,u); return; ,機(jī)器碼輸出,真值賦值,x = 4294967295 = FFFFFFFF = -1,u = 2147483648 = 80000000 = -2147483648,C語(yǔ)言程序中的整數(shù),常數(shù)后面加u”或“U”表示無(wú)符號(hào)

21、數(shù) 若同時(shí)有無(wú)符號(hào)和帶符號(hào)整數(shù)，將帶符號(hào)整數(shù)強(qiáng)制轉(zhuǎn)換為無(wú)符號(hào)數(shù) 以下表達(dá)式在32位補(bǔ)碼機(jī)器上執(zhí)行，結(jié)果是什么？ -1 000B(0) 2147483647 (int) 2147483648U 1 True B (231-1) 1000B (-231) 2147483647U -2147483647 1 False 2147483647 -2147483647 1 True 2147483647 -2147483648 False1B (231-1) 1000B(231),C編譯器對(duì)常量的處理,2147483647 -2147483648 執(zhí)行結(jié)果為false。Why ISO C90 21474

22、83648為unsigned int型， 求負(fù)后還是原值，按無(wú)符號(hào)數(shù)比較， 0 x7FFFFFFF 小于0 x80000000，結(jié)果為false。 ISO C99 2147483648為long long型， 表達(dá)式按帶符號(hào)整數(shù)比較， 執(zhí)行結(jié)果為T(mén)rue,C語(yǔ)言程序中的整數(shù),2147483647 -2147483648 （false/True） “int i=-2147483648;” “2147483647i”的執(zhí)行結(jié)果為true。 按int型比較，結(jié)果為true。 “ 2147483647 -2147483647-1”？ 按int型比較，結(jié)果為true #define INT32_MIN

23、(-2147483647 - 1),C語(yǔ)言中的整數(shù)小結(jié),整數(shù)補(bǔ)碼存儲(chǔ)，表示，運(yùn)算 C編譯器根據(jù)常量值的大小自動(dòng)匹配數(shù)據(jù)類型 -2147483648被當(dāng)成無(wú)符號(hào)數(shù) (C90) #define INT32_MIN (-2147483647 - 1) 有符號(hào)和無(wú)符號(hào)共存時(shí)無(wú)符號(hào)優(yōu)先 -1 0U 整數(shù)變量初始化 先按約定處理常量 轉(zhuǎn)換成機(jī)器碼 C90/99 有區(qū)別 然后根據(jù)變量長(zhǎng)度進(jìn)行強(qiáng)制轉(zhuǎn)換，位數(shù)超出的直接截去,一個(gè)奇怪的浮點(diǎn)運(yùn)算程序,main() double a,b,c; int d; b=3.3; c=1.1; a=b/c; d=b/c; printf(%f,%d,a,d); if (3.0!

24、=a) printf(nReally? 3.0!=a); ,3.000000,2,?,Really?3.0!=a,浮點(diǎn)數(shù)如何表示?,參與運(yùn)算的數(shù)據(jù)通常既包括整數(shù)也包括小數(shù)部分。 如何表示？ 最直接的辦法-整數(shù)部分，小數(shù)部分分別表示？ #define INT32_MAX 2147483647 電子的質(zhì)量 910-28g 太陽(yáng)的質(zhì)量21033g0.21034 浪費(fèi)存儲(chǔ)空間，數(shù)據(jù)表示范圍和精度均有限 有否更好的方法？,浮點(diǎn)數(shù)如何表示,電子的質(zhì)量 910-28g 太陽(yáng)的質(zhì)量 21033g 0.21034 科學(xué)記數(shù)法 讓數(shù)據(jù)表示唯一，規(guī)格化 N=10EM 1|M|10 N=2EM 1|M|2 科學(xué)記數(shù)法

25、利用冪和尾數(shù)表示浮點(diǎn)數(shù) 數(shù)據(jù)范圍更大，精度更高 數(shù)據(jù)表示唯一,浮點(diǎn)數(shù)的規(guī)格化問(wèn)題 normalization,0.05*101 50*10-2 5*10-1 0.01*21 1*2-2 0.1*2-1 尾數(shù)最高有效位為1的數(shù)稱為規(guī)格化數(shù)。 保障數(shù)據(jù)表示的唯一性，方便交換數(shù)據(jù) 簡(jiǎn)化浮點(diǎn)運(yùn)算算法 提升表示精度，尾數(shù)去掉了左側(cè)多余的零 兩種規(guī)格化數(shù) 1.XXXXX 0.1XXXXX 機(jī)器零：全部為0，特殊的數(shù)據(jù)編碼,浮點(diǎn)數(shù)的表示,N=Rem=2EM =2e (m) m的取值區(qū)間？,E0,M0,浮點(diǎn)數(shù)的表示范圍,N=2EM E+ 產(chǎn)生正上溢或者負(fù)上溢 E - 產(chǎn)生正下溢或者負(fù)下溢,- ,+,負(fù)數(shù),正數(shù)

26、,0,負(fù)上溢,正上溢,Range a=a/0; printf(a=%d,a); return; 程序出錯(cuò) Why？,main() float a=1.0,b=-1.0; a=a/0; b=b/0; printf(a=%f b=%f,a,b); return; ,a=1.#INF00 b=-1.#INF00,a = 正無(wú)窮 b=負(fù)無(wú)窮,浮點(diǎn)程序 例2,main() float a=0.0, b; a=a/0; b=-sqrt(-1); printf (a=%f b=%f,a,b); return; ,a=1.#IND00 b=1.#QNAN0,a = FFC0-0000 b=7FC0-0000,

27、浮點(diǎn)程序 例3,union char c4; float f; int i; t1,t2; void main() t1.i = 0X00000000; t2.i = 0X80000000; if (t1.f=t2.f) printf(“float data is equal!n); if (t1.i=t2.i) printf(int data is equal!n); Output32BitHex( ,float data is equal! 0000-0000 8000-0000,float型與真值之間的變換流程,浮點(diǎn)數(shù)真值 十進(jìn)制數(shù)N,單精度 float 32位二進(jìn)制,浮點(diǎn)數(shù)轉(zhuǎn)換實(shí)例,3

28、.310 IEEE 754 float 十進(jìn)制轉(zhuǎn)換二進(jìn)制 3.310 =11.01001100110011001100110011.2 規(guī)格化 =1.10100110011001100110011001121 取23位尾數(shù)，舍入后會(huì)變小 8位階碼 = 1 + 127 = 100000002,浮點(diǎn)數(shù)轉(zhuǎn)換實(shí)例,1.110 IEEE 754 float 十進(jìn)制轉(zhuǎn)換二進(jìn)制 3.310 = 1.0001100110011001100110011.2 規(guī)格化 = 1.000110011001100110011001120 取23位尾數(shù)，舍入后會(huì)變大 8位階碼 = 0 + 127 = 011111112,一

29、個(gè)奇怪的浮點(diǎn)運(yùn)算程序,main() double a,b,c; int d; b=3.3; c=1.1; a=b/c; d=b/c; printf(%f,%d,a,d); if (3.0!=a) printf(nReally? 3.0!=a); ,3.000000,2,?,Really?3.0!=a,二進(jìn)制存儲(chǔ),浮點(diǎn)數(shù)不能精確表示一些十進(jìn)制數(shù),一個(gè)更奇怪的浮點(diǎn)運(yùn)算程序,main() float a,b,c; int d; b=3.3; c=1.1; a=b/c; d=b/c; printf(%f,%d,a,d); if (3.0!=a) printf(nYeah!); ,3.000000,2,

30、?,3.3/1.1,void double_currency_test() double a,b,c; a=3.3; b=1.1; c=a/b; Output64BitHex( ,一個(gè)奇怪的浮點(diǎn)運(yùn)算程序,浮點(diǎn)數(shù)的表示范圍與精度,階碼越長(zhǎng)，表示范圍越大，精度越高 (規(guī)格化) 階碼相同，尾數(shù)越長(zhǎng)，數(shù)據(jù)精度越高 浮點(diǎn)數(shù)擴(kuò)大了數(shù)值表示的范圍， 未增加表示數(shù)值的個(gè)數(shù) 絕對(duì)值越大，浮點(diǎn)數(shù)分布越稀疏，浮點(diǎn)數(shù)是離散空間 浮點(diǎn)運(yùn)算不滿足結(jié)合律 （2-126+1020）-1020 = ? 2-126 + (1020 - 1020) =?,非規(guī)格化數(shù),判斷表達(dá)式,int i; float f; double d;

31、i=(int)(float)i f=(float)(int)f i=(int)double(i) f=(float)(double)f d=(float)d f=-(-f) (d+f)-d=f,C語(yǔ)言浮點(diǎn)數(shù)總結(jié),float，double型對(duì)應(yīng)IEEE754 單精度和雙精度 浮點(diǎn)數(shù)在數(shù)軸上分布不均勻，數(shù)軸右側(cè)分布更稀疏 浮點(diǎn)數(shù)運(yùn)算不滿足結(jié)合律 (d+f)-d != f Int 32位 float 32位在整數(shù)區(qū)域僅部分重疊 i=(int) (float) i 不成立 Int 32位 double 64位在整數(shù)區(qū)域完全重疊 i=(int) (double) i 成立,非規(guī)格化數(shù),C語(yǔ)言浮點(diǎn)數(shù)總結(jié),

32、float數(shù)據(jù)集是double的子集 f=(float) (double) f 成立 浮點(diǎn)數(shù)尾數(shù)原碼表示 f=( f) 成立 浮點(diǎn)數(shù)存在兩個(gè)零 C語(yǔ)言不關(guān)注 浮點(diǎn)運(yùn)算指令實(shí)現(xiàn)必須考慮這個(gè)因素,2.2.3 十進(jìn)制數(shù)的表示 BCD碼,Binary coded decimal 二進(jìn)制編碼的十進(jìn)制 幾種BCD碼 8421碼 (8*X3+4*X2+2*X1+1*X0) 有權(quán)碼 2421碼 (2*X3+4*X2+2*X1+1*X0) 有權(quán)碼 余三碼 (8*X3+4*X2+2*X1+1*X0) + 0011 BCD碼運(yùn)算的問(wèn)題(編碼校正) 用途？,BCD碼運(yùn)算問(wèn)題,8421碼的校正 871000011111

33、11 非法編碼 余三碼的校正 00001100110110 3 非法編碼 44011101111110 ？非法編碼 相對(duì)而言運(yùn)算比較復(fù)雜,程序中數(shù)據(jù)類型的寬度,高級(jí)語(yǔ)言支持多類型、多長(zhǎng)度的數(shù)據(jù) C語(yǔ)言中char型的寬度為1字節(jié) 可表示一個(gè)字符（非數(shù)值數(shù)據(jù)） 也可表示一個(gè)8位的整數(shù)（數(shù)值數(shù)據(jù)） 同類型數(shù)據(jù)在不同機(jī)器上寬度可能不同 分配的字節(jié)數(shù)隨機(jī)器字長(zhǎng)和編譯器的不同而不同。,Compaq Alpha是64位機(jī)器,本章主要內(nèi)容,2.1 非數(shù)值數(shù)據(jù)表示法 2.2 數(shù)值數(shù)據(jù)表示法 2.3 數(shù)據(jù)信息的校驗(yàn),2.3 數(shù)據(jù)信息的校驗(yàn),奇偶校驗(yàn) 海明校驗(yàn) CRC循環(huán)冗余校驗(yàn),身份證的秘密,身份證編碼格式 各位

34、權(quán)值：Wi=2(i-1)(mod11) 校驗(yàn)位 = (AiWi)mod 11,銀行卡編碼規(guī)則,信用卡編碼格式 卡號(hào)最后一位數(shù)字開(kāi)始，逆向?qū)⑵鏀?shù)位數(shù)字相加求和 卡號(hào)最后一位數(shù)字開(kāi)始，逆向?qū)⑴紨?shù)位數(shù)字先乘以2，如果乘積為兩位數(shù)，則減去9，再求和 將奇數(shù)位總和加偶數(shù)位總和，結(jié)果可以被10整除,2.3 數(shù)據(jù)信息的校驗(yàn),解決編碼在時(shí)間、空間上傳輸可靠性問(wèn)題 編碼中引入一定冗余，增加最小碼距，使編碼符合某種規(guī)則，當(dāng)編碼出現(xiàn)一個(gè)或多個(gè)錯(cuò)誤時(shí)變成非法代碼（不符合規(guī)則） 奇偶信息的校驗(yàn) 編碼中1的個(gè)數(shù)的奇偶性 海明校驗(yàn) 多校驗(yàn)組的奇偶性，檢錯(cuò)碼為出錯(cuò)位 CRC 循環(huán)冗余校驗(yàn) 編碼能被生成多項(xiàng)式整除，余數(shù)循環(huán),碼

35、距概念,碼距：任意兩個(gè)合法編碼間不同的二進(jìn)制位數(shù) 最小碼距 碼距越大，抗干擾能力、糾錯(cuò)能力越強(qiáng)，數(shù)據(jù)冗余越大，編碼效率越低 選擇碼距應(yīng)考慮信息出錯(cuò)概率和系統(tǒng)容錯(cuò)率 奇偶校驗(yàn) 最小碼距為2 海明碼 最小碼距為3,碼距實(shí)例,一代穿孔卡 磁卡 NFC感應(yīng)卡 穿孔卡的安全隱患？,碼距與糾錯(cuò)性能,最小碼距e+1 可檢測(cè)e個(gè)錯(cuò)誤 最小碼距2t+1 可糾正t個(gè)錯(cuò)誤 最小碼距e+t+1 et 可糾正t個(gè)錯(cuò)誤，同時(shí)檢測(cè)e個(gè)錯(cuò)誤,且表示假設(shè)無(wú)更多位錯(cuò)誤發(fā)生時(shí)，可以區(qū)分這兩種出錯(cuò)模式，或表示無(wú)法區(qū)分，需要進(jìn)一步假設(shè),2.3.1 奇偶校驗(yàn),奇校驗(yàn) 冗余位：1位 校驗(yàn)位 P 編碼規(guī)則：校驗(yàn)碼（數(shù)據(jù)校驗(yàn)位）中1的個(gè)數(shù)為奇

36、數(shù) 最小碼距：2 0000 00001 (奇校驗(yàn)) 0001 00011 (偶校驗(yàn)),偶校驗(yàn):,奇校驗(yàn):,檢錯(cuò)碼:,G=1： 數(shù)據(jù)一定出錯(cuò)，否則較大概率正常,奇偶校驗(yàn)過(guò)程,發(fā)送方生成 校驗(yàn)碼 = 原始數(shù)據(jù) + 校驗(yàn)位p 接收方生成利用校驗(yàn)碼生成 檢錯(cuò)碼g 檢測(cè)碼不為零表示錯(cuò)誤發(fā)生！ 檢測(cè)碼為零時(shí)是否表示數(shù)據(jù)正確？ 能否糾錯(cuò)？,奇偶校驗(yàn)性能,00011,00011,00011,00010,01101,11101,00011,識(shí)別奇數(shù)錯(cuò)，不能糾錯(cuò)，不保證正確，實(shí)現(xiàn)簡(jiǎn)單，編碼效率高,正確傳輸,正常檢錯(cuò),正確檢錯(cuò),不能檢錯(cuò),奇偶校驗(yàn)應(yīng)用場(chǎng)合,能糾錯(cuò)？,ECC（Error Checking and Co

37、rrecting）,校驗(yàn)和 CheckSum,Sender: add all words of a packet and append the result (checksum) to the packet Receiver: add all words of a received packet and compare the result with the checksum Internet checksum,二維奇偶校驗(yàn),若干數(shù)據(jù)一個(gè)校驗(yàn)位 整個(gè)數(shù)據(jù)包增加一個(gè)校驗(yàn)字節(jié),校驗(yàn)性能？,All 1-bit errors,可檢錯(cuò)行，奇數(shù)個(gè)1,可檢錯(cuò)列，奇數(shù)個(gè)1,校驗(yàn)性能？,All 2-bit er

38、rors,可檢錯(cuò)列，奇數(shù)個(gè)1,校驗(yàn)性能？,All 3-bit errors,可檢錯(cuò)列，奇數(shù)個(gè)1,校驗(yàn)性能？,Most 4-bit errors,可檢錯(cuò)行,二維奇偶校驗(yàn)的啟示,多個(gè)奇偶校驗(yàn)組 一個(gè)數(shù)據(jù)位參加多個(gè)校驗(yàn)組 一個(gè)數(shù)據(jù)位發(fā)生錯(cuò)誤可在多個(gè)檢測(cè)碼中反應(yīng) 可有效提高檢錯(cuò)能力,出錯(cuò)位,可檢錯(cuò)列，奇數(shù)個(gè)1,可檢錯(cuò)行，奇數(shù)個(gè)1,2.3 數(shù)據(jù)信息的校驗(yàn),奇偶校驗(yàn) 海明校驗(yàn) CRC循環(huán)冗余校驗(yàn),2.3.2 海明校驗(yàn) Hamming Codes,奇偶校驗(yàn) 一個(gè)校驗(yàn)位 只能檢錯(cuò)，無(wú)法糾錯(cuò) 海明碼 多個(gè)奇偶校驗(yàn)組 既能檢錯(cuò)，也能糾錯(cuò) 最小碼距為3,Richard Wesley Hamming 1950,可檢一

39、位錯(cuò)海明碼,編碼規(guī)則：分組交叉奇偶校驗(yàn)法 待編碼數(shù)據(jù)分成 r 個(gè)奇偶校驗(yàn)組，r1 r 位校驗(yàn)位（冗余），生成r位檢錯(cuò)碼 各數(shù)據(jù)位至少參加2個(gè)校驗(yàn)組 一個(gè)數(shù)據(jù)位出錯(cuò)，可導(dǎo)致多個(gè)檢錯(cuò)碼為1 檢錯(cuò)糾錯(cuò)：檢錯(cuò)碼值表示出錯(cuò)位置 （假設(shè)1位錯(cuò)） 檢錯(cuò)碼全零， 數(shù)據(jù)大概率正常 可檢錯(cuò)，也可糾錯(cuò)，將出錯(cuò)位取反即可,可檢一位錯(cuò)海明碼,設(shè)海明碼 N 位，其中數(shù)據(jù)位 k 位，校驗(yàn)位 r 位 （冗余位） N = k + r 2r 1 （r位可以表示2r狀態(tài)，0值去掉） 例：4位數(shù)據(jù)位，r=？ (4,3)海明碼 D4D3D2D1P3P2P1 3個(gè)校驗(yàn)組G3G2G1， P3P2P1分屬其中一組 H7H6H5H4H3H2H

40、1 最低位為什么從1開(kāi)始？ 校驗(yàn)組如何分組， Di , Pj Hk 如何映射,(4,3)碼分組依據(jù),H3參與G2 G1兩校驗(yàn)組,G3G2=0 表示僅僅P1位出錯(cuò),備注 (假設(shè)只有1位錯(cuò)),D1存放H3,P1存放在H1位置,數(shù)據(jù)正常,000,出錯(cuò)位,G3G2G1,(4,3)碼數(shù)據(jù)位映射,G1(P1,H3,H5,H7) G2(P2,H3,H6,H7) G3(P3,H5,H6,H7),P1,P2,D1,P3,D2,D3,D4,G1=P1D1D2D4 G2=P2D1D3D4 G3=P3D2D3D4,(4,3)碼編碼表,最小碼距為3，判兩位錯(cuò)或糾1位錯(cuò),(4,3)碼檢錯(cuò)、糾錯(cuò)性能 最小碼距3,可檢一位錯(cuò)

41、 檢錯(cuò)碼G3G2G1 !=000，具體值為出錯(cuò)位置，取反即可糾錯(cuò) 可檢兩位錯(cuò) 假設(shè)D1 ，D2同時(shí)出錯(cuò)， G3G2G1=110 ？ 大多數(shù)三位錯(cuò) D1，D2，D3同時(shí)出錯(cuò)？G3G2G1=000 ？ 能否區(qū)分區(qū)分一位錯(cuò)，兩位錯(cuò)？ 假設(shè)沒(méi)有3位錯(cuò) 引入總偶校驗(yàn)位 P4=H1H2H3H4H5H6H7 G4=P4H1H2H3H4H5H6H7 區(qū)分一位兩位錯(cuò),檢錯(cuò)必須有假設(shè)前提,（k，r）碼校驗(yàn)分組方法,(k, r) 海明碼的校驗(yàn)如何分組，設(shè)檢錯(cuò)碼為Gr.G4G3G2G1 根據(jù)編碼規(guī)則填寫(xiě)海明校驗(yàn)組分布表,ECC（Error Checking and Correcting）,海明碼特點(diǎn),編碼效率高：數(shù)據(jù)

42、增加一倍，校驗(yàn)位只增加一位 可糾正一位錯(cuò) 50年代發(fā)明時(shí)用于自動(dòng)處理穿孔卡片的故障 現(xiàn)在普遍用于ECC DRAM芯片 RAID2，衛(wèi)星通訊,海明編解碼過(guò)程,編碼 （按規(guī)則增加冗余信息） 傳輸 （時(shí)空、不可靠） 解碼 （規(guī)則判斷，檢錯(cuò)、盡力糾錯(cuò)）,原始數(shù)據(jù),校驗(yàn)碼,加擾后校驗(yàn)碼,盡力糾錯(cuò)的數(shù)據(jù),海明編碼傳輸實(shí)驗(yàn),2.3 數(shù)據(jù)信息的校驗(yàn),奇偶校驗(yàn) 海明校驗(yàn) CRC循環(huán)冗余校驗(yàn),CRC循環(huán)冗余校驗(yàn)碼 Cyclic redundancy check,編碼規(guī)則：編碼可被生成多項(xiàng)式整除 模2除法，余數(shù)為0（高概率正確），否則出錯(cuò) 設(shè)CRC碼 N 位，其中數(shù)據(jù)位 k 位，校驗(yàn)位 r 位（冗余位） N = k

43、 + r 2r 1 （2r個(gè)余數(shù)，0表示正確，N位中的每一位出錯(cuò)余數(shù)皆不同） 可檢錯(cuò)，可糾錯(cuò),W. Wesley Peterson 1961,模2運(yùn)算規(guī)則,1,1110,1011,0010,010,1010,1011,1011,0000,1011,商,1,1,0,加法：按位加不考慮進(jìn)位 減法：按位減不考慮借位 異或運(yùn)算，不考慮進(jìn)位 乘法：部分積之和按模2加法計(jì)算 除法：余數(shù)首位為1，商上1 ,否則為0 11000001011 1100000=1011*1110+010,CRC編碼規(guī)則,將待編碼的k位有效信息位組表達(dá)為多項(xiàng)式M(x) M(x)=bk-1xk-1 + bk-2xk-2 + b1x1

44、 + b0 x=2 將數(shù)據(jù)左移 r 位，空出r位校驗(yàn)位（冗余位），變成 M(x) x r 將M(x) xr 除以生成多項(xiàng)式 G(x)，商為Q(x)， 余數(shù)R(x) M(x) x r = Q(x) G(x) + R(x) 將余數(shù)填充在校驗(yàn)位 M(x) x r + R(x) = Q(x) G(x) + R(x) + R(x) = Q(x) G(x) 編碼規(guī)則： CRC編碼可被G(x)表示的編碼整除,CRC編碼規(guī)則,r位,k位,r+1位,r位余數(shù),余數(shù)為0正確，否則拒絕,不可靠傳輸,CRC 編解碼過(guò)程,生成多項(xiàng)式 Generator polynomial,生成多項(xiàng)式特征 任意位發(fā)生錯(cuò)誤都應(yīng)使余數(shù)不為

45、0 不同位發(fā)生錯(cuò)誤余數(shù)不同 余數(shù)左移一位繼續(xù)作模2除，應(yīng)使余數(shù)循環(huán)，循環(huán)周期 N=k+r ？ 如何產(chǎn)生生成多項(xiàng)式 (n,k)碼，將Xn+1分解為若干質(zhì)因子 （模2的運(yùn)算） 根據(jù)碼距要求選擇其中的因式或多個(gè)因式的乘積為生成多項(xiàng)式,生成多項(xiàng)式,X7+1 = (x+1) (x3+x+1) (x3+x2+1) 模2運(yùn)算 G(x) = x+1 = 11 (7,6)碼，判一位錯(cuò) G(x)= x3+x+1 G(x) (x3+x2+1) (7,4)碼，判兩位錯(cuò) 或 糾一位錯(cuò) 兩位錯(cuò)，一位錯(cuò)余數(shù)均不為零，但余數(shù)有重疊 G(x) = (x+1) (x3+x+1) = 11101 (7,3)碼，判兩位錯(cuò) 并 糾一位

46、錯(cuò) 兩位錯(cuò)，一位錯(cuò)余數(shù)均不為零，余數(shù)無(wú)重疊,編碼過(guò)程 (7,4)循環(huán)碼G(x)=1011,1,1110,1011,0010,010,1010,1011,1011,0000,被除數(shù)補(bǔ)零,商,1,1,0,(7,4)循環(huán)碼出錯(cuò)模式 G(x)=1011,最小碼距為3，判兩位錯(cuò)或糾1位錯(cuò),檢錯(cuò)過(guò)程 1位錯(cuò) (0001000） 2位錯(cuò) (1010000）,0,0010,0000,1000,011,0100,0000,0000,1011,商,0,0,1,1,0010,1011,1000,011,0100,0000,0000,1011,商,0,0,1,一位錯(cuò)、兩位錯(cuò)余數(shù)均不為零，但余數(shù)有重疊，判兩位錯(cuò)，或糾1

47、位錯(cuò),(7,4)循環(huán)碼 余數(shù)循環(huán)模式 G(x)=1011,1,101,1000000,2,111,0100000,3,110,0010000,4,011,0001000,5,100,0000100,6,010,0000010,7,001,0000001,無(wú),000,0000000,出錯(cuò)位,余數(shù),A1A7,0,1,1,0,1,0,0,CRC如何糾錯(cuò)？,全零永遠(yuǎn) 是合法編碼,(7,3)碼多位錯(cuò)余數(shù)情況,兩位數(shù)出錯(cuò)余數(shù)與一位錯(cuò)有重疊（見(jiàn)表） 三位錯(cuò)余數(shù)有可能為零 如 C1，C2，C4 （無(wú)法全部檢錯(cuò)）,兩位數(shù)出錯(cuò)組合,模2除法滿足結(jié)合律,(7,4）CRC編碼，生成多項(xiàng)式G(x)=1011，原始數(shù)據(jù)M(x)=1101，求CRC編碼, % % = % ,1101 000 1000 000 0100 000 0001 000,1101 011 1000 000 0100 000 0001 000 0000 011,先算26、25、24、23四個(gè)常量的余數(shù), 再用余數(shù)的組合求解任意編碼的余數(shù),兩數(shù)的余數(shù)異或等于兩數(shù)異或后的余數(shù),(7,3)碼編碼情況 G(x)=11101,最小碼距為4，可檢測(cè)3