《二章计算机数据表示方法》由会员分享,可在线阅读,更多相关《二章计算机数据表示方法(119页珍藏版)》请在金锄头文库上搜索。
1、第二章、计算机数据表示方法版权所有,引用请注明出处原著谭志虎主讲(改编) 蒋文斌Outlineoo2.12.1非数值数据表示法oo2.22.2数值数据表示法oo2.32.3数据信息的校验2DataRepresentationoQualitativeoQuantitativenIntegersoSignedoUnsignednNon-integers(Real)oSignedoUnsigned32.1非数值数据表示法o字符表示法characterso汉字表示法Chinesecharacters42.1.1Characterrepresentationo如何使用数值表示字符数据oStandards
2、nASCII-American Standard Code for Information Interchange (ANSI 7bits)nEBCDIC-Extended Binary-Coded Decimal Interchange Code (IBM 8bits)nUnicode5128StandardASCIIcodeso52Lettersna-z,A-Zo10Digitsn0-9o34Symbolsn!#$%&*()o32Controlcharactersn6ASCIIo使用7bit表示128个字符nFrom0000000to111111127=128o注意:ASCII中的数字字符
3、和数字本身不相等o几乎所有计算机均支持该代码集o但不是所有语言都能用128个字符表示o8Bit?oMSF=071 11 10 01 11 10 00 01 17 76 65 54 43 32 21 10 0Terminologyo计算机利用寄存器存储数据o寄存器中每个位称bit(BinaryDigiT)o最高有效位(MSB)最低有效位(LSB) MSBMostsignificantbit LSBLeast significant bit82.1.2汉字表示法o8bit数据仅能表示256个字符,常用汉字6000多个,故其无法表示汉字oGB2312国家标准采用16位表示o与ASCII字符的区别,最
4、高有效位MSB=1o内码,外码(输入法),字模码(显示用)9GB2312-80国家标准o1981年,GB2312-80国家标准,包括6763个汉字/682个非汉字字符,称为国标码或国际交换码oGB2312字符集的构成:n一级常用汉字3755个,按汉语拼音排列n二级常用汉字3008个,按偏旁部首排列n非汉字字符682个10汉字标准oGB2312-1980(GB0)(简体)n6763个汉字oGB13000-1993n20902个汉字(Unicode1.1版本)o汉字扩展规范GBK1.0标准1995(非国家标准)n21003个字符(兼容GB2312)oGB18030-2000(1/2/4字节编码)n
5、27484汉字(向下兼容GB2312GBK,GB13000)11字模码介绍o字模码是用点阵表示的汉字字型代码,是汉字的输出形式。o字模点阵的信息量是很大的,所占存储空间也很大。以16*16为例,每个汉字要占用32个字节,o因此字模点阵只能用来构成汉字库,而不能用于机内存储。12Charsetoocharset=gb2312简体中文charset=big5繁体中文charset=EUC_KR韩语charset=Shift_JIS或EUC_JP日语charset=KOI8-R/Windows-1251俄语charset=iso-8859-2中欧语系charset=utf-8unicode多语言13
6、Unicodewww.unicode.orgo用于克服字符数字的限制o为所有语言中的字符分配唯一的代码o16bit字符集,65536Unicode字符o提供唯一的代码n不论任何平台n不论任何程序n不论任何语言14UniversalCharacterSetISOoUCSnISO10646nUCS-2UCS-4oUTF(UnicodeTransformformat)nUTF-7nUTF-8nUTF-1615TerminologyoUUEncode/UudecodeoMIMEn(MultipurposeInternetMailExtensions)162.2数值数据表示方法o计算机数值数据表示的特点
7、o进位制数o数的定点、浮点表示o机器数17计算机数据编码需要考虑的因素:o数的类型(小数、整数、实数和复数)o数值范围o数值精确度o数值存储和处理所需的硬件代价18计算机数据编码特点o少量简单的基本符号表示大量复杂的信息o状态简单o电路实现简单o运算方便o硬件成本19Humanvs.Computero人们日常生活采用10进制n天生10个手指o计算机采用二进制n计算机采用电子开关n开关仅仅包括两个状态ONOFF20十进制编码特点o0123456789共10种状态,状态过多o运算组合状态过多o加法组合数=C102+10=10*9/2!+10=55C82+8=8*7/2!+8=36C42+4=4*3
8、/2!+4=10C22+2=2*1/2!+2=3八进制:四进制:二进制:结论:二进制的组合状态最少21二进制编码特点o符号个数最少,“0、1” 物理上容易实现o用数字电路的两个状态表示(如电压高低)o与二值逻辑的 真假 两个值对应简单o二进制位可以表示任何对象(字符,数值,逻辑值)o用二进制码表示数值数据运算规则简单n0+1=1+0=1 1+1=0 0+0=0n仅仅三种运算规则(10进制有55种)n一个异或门即可完成该运算22一位全加器输入输入: : 加数加数A Ai i 、B Bi i 低位进位输入低位进位输入C Ci i输出输出: : 和数和数S Si i ,进位输出,进位输出C Ci+1
9、i+1111111001110101010011000进位Ci+10110和数Si110010100000加数Bi加数Ai低位进位Ci23二进制加法器基本电路24进制表示nN代表一个数值nr是这个数制的基(Radix)ni表示这些符号排列的位号nDi是位号为i的位上的一个符号nri是位号为i的位上的1代表的值nDi*ri是第i位的所代表的实际值n表示m+k+1位的值求累加和25例子o(10456)1011040103 410251016100o(0xF96)16F1629161 6100o(10010001)2127026 025 124 023 022 021 12026进制转换o二进制数转
10、八进制o二进制数转十六进制o二进制数转十进制o十进制数转二进制27二到八或十六进制转换o二进制转到八进制 从小数点向左右三位一分组(10011100.01)2=(234.2)8010o二进制转十六进制 从小数点向左右四位一分组(10011100.01)2=(9C.4)160100 说明:整数部分不足位数对转换无影响, 小数部分不足位数要补零凑足,则出错。28二进制转十进制从二进制数求其十进制的值,逐位码权累加求和o1001000112702602512402302202112029十进制转二进制整数部分除2取余小数部分乘2取整2 1 1222521011010.625 * 210.25 * 2
11、00.5 * 21 0.0 除尽为止 1011低高高低求得位数满足要求为止30进制转换的简单运算方法o17/128的二进制表示方法?o大数的转换方法,记住几个常用的2的幂2532 2664 27128 28256 29512 2101024(1Kilo) 2112048 21240962138182 21416364 2153272821665536 2201048576(1Mega)2301073741824(1Giga) 2401Tera更大的单位是多少?2501 Peta 2601 Exa 2701 Zetta 2801 YottaMEMORIZE!31Kilo,Mega,Giga,Te
12、ra,Peta,Exa,Zetta,Yottaphysics.nist.gov/cuu/Units/binary.htmlo30GB=?Byte 1Mbits=?o30 GB drive30 x 109 28 x 230 bytes 1 Mbit/s = 106 bpso硬盘厂商及通讯行业是计算机行业唯一使用SI因子的321999NewIECStandardPrefixeshttp:/en.wikipedia.org/wiki/Binary_prefixoSI (International System of Units )仅指10进制o234可以访问多少存储单元?o2.5TiB存储空间需要多
13、少地址线进行译码?MEMORIZE!33几个简化运算的例子-17/128=-0.001000165539=65536+3=1000000000000001165539=65536+3=10000000000000011 1111 1111111111111110=11111110=1111111111111111-11111-1=2=21212-1-1=4046-1-1=4046130=128+2=130=128+2=10001000001000101111111111111111011101112 21212-1-8-1-82003=2047-44=11112003=2047-44=1111
14、111111111111-32-8-41111-32-8-4MEMORIZE!342.2数值数据表示方法o计算机数值数据表示的特点o进位制数o数的定点、浮点表示o机器数352.2.1数的定点、浮点表示方法o定点表示(小数点位置固定的数)n定点小数n定点整数n仅能表示纯小数及纯整数o浮点表示oSigned&Unsigned36定点小数符号位小数点位置数值部分X X0 0X X1 1X X2 2X X3 3X Xn nX X0 01 11 11 11 1X X0 00 00 00 01 12-n|X|1-2-n下溢/上溢最低有效位最低有效位最高有效位最高有效位37o数值表示 X=X0.X1X 2X
15、 n X i=0,1,0in =X 12-1+X n-12-n+1+X n 2-no数值范围0|x| 1-2-n定点小数的编码38定点整数符号位小数点位置数值部分X X0 0X X1 1X X2 2X X3 3X Xn nX X0 01 11 11 11 1X X0 00 00 00 01 11|X|2n-1上溢最高有效位最高有效位最低有效位最低有效位39o数值表示X=X1X2Xn Xi=0,1,0in=X12n-1+Xn-121+Xno数值范围0|x|2n-1定点整数的编码40浮点数如何表示o?o参与运算的数据通常既包括整数也包括小数部分。o如何表示?如何运算?o将数据按照一定比例因子缩小成
16、定点小数或扩大成定点整数进行表示和运算o运算完毕后再根据比例因子还原成实际数值o计算机中浮点运算有专门的器件41浮点数如何表示o电子的质量910-28go太阳的质量21033g0.21034o科学记数法N=10EMoN=RemoM称为尾数,是一个纯小数,e是比例因子的阶数,称为浮点数的指数,是一个整数,R为基数42浮点数的表示o将比例因子以适当形式表示在数据中即可表示浮点数o可有效提高数字表示范围,也保持了数字有效精度oN=Rem=2EM=2e(m)E E0 0E E1 1E E2 2E EmmMM0 0M1M2Mn尾数值阶值阶符尾符43浮点数的表示范围- +负数正数0负上溢正上溢负下溢正下溢
17、oN=2EMo|N|产生正上溢或者负上溢o阶码正上溢E+o阶码负上溢E-o|N|0产生正下溢或者负下溢44o机器字长一定时,阶码越长,表示范围越大,精度越低o浮点数表示范围比定点数大,精度高E E0 0E E1 1E E2 2E EmmMM0 0MM1 1MM2 2MMn n尾数值阶值阶符尾符Range&precision45Exampleo8位定点小数可表示的范围n0.0000001-0.1111111n1/128-127/128o设阶码2位,尾数4位n可表示2-11*0.0001-211*0.1111n0.0000001-111.1o设阶码3位,尾数3位n可表示2-111*0.001-21
18、11*0.111n0.0000000001-111000046浮点数的规格化问题normalizationo0.05*101 50*10-2 5*10-1 o0.01*21 1*2-2 1*2-1 o尾数最高有效位为1的数称为规格化数。o为了在尾数中表示最多的有效数据位o为了数据表示的唯一性。o两种规格化数 1.XXXXX 0.1XXXXX o机器零:全部为0,特殊的数据编码47S(1bit)E(2330共8bit)M(022共23bit)o32/64位浮点数(Float/Double)S(1bit)E(5262共11bit)M(051共52bit)N = (-1)N = (-1)S SX M
19、X M X X 2 2E E 构成:阶码构成:阶码E E,尾数,尾数M M,符号位,符号位S S,浮点数标准IEEE75448o规格化数(Normal):(-1)s1.m2e-127o非规格化数(Subnormal)(e=0)(-1)s0.m2-126o尾数部分采用原码表示,故表示范围对称oemin=1,emax=254/2046o最高数字位总是1,该标准将这个1缺省存储(隐藏位implicit),使得尾数表示范围比实际存储多一位浮点数标准IEEE75449单精度浮点数编码格式+0/-0000/1(-1)S (0.f) 2(-126)f(非零)00/1(-1)S (1.f) 2(e-127)f
20、12540/1- 02551+02550sNaN Signaling NaN非零0xxxx2550/1NaN Not a Number非零1xxxx2550/1表示尾数阶码符号位50IEEE754 规格化浮点数表示范围Emax=2046,f=1.1111,1.111122046-1023=21023(2-2-52)Emin=1,M=0,1.021-1023=2-1022双精度双精度Emax=254,f=1.1111,1.11112254-127=2127(2-2-23)Emin=1,M=0,1.021-127=2-126单精度单精度最大值最小值格式51一个奇怪的程序main() double
21、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二进制存储浮点数不是精确数52一个奇怪的程序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,2532.2数值数据表示方法o计算机数值数据表示的特点o进位制数o数的定点、浮点表示o机器数5
22、42.2.2机器数/机器码o真值(书写用)n将用+-表示正负的二进制数称为符号数的真值o机器不能识别书写格式,计算机如何表示负数?o机器码(机器内部使用)n将符号和数值一起编码表示的二进制数称为机器码o原码Signedmagnitude反码Onescomplemento补码Twoscomplement移码Biasednotation55原码表示法(Signedmagnitude)o计算机如何表示数的正负?o增加符号位Addasignbito最高位为符号位,0为正,1为负,数值位不变56原码表示示例o+0原=0.0000o-0原=1.0000o-0.1111原=1.1111o0.1111原=0.
23、1111o1110原=01110o-1110原=1111057X X 原原原原=X 0X2X 0X2n n2 2n nX -2X -2n n X X 0 0X X 原原原原=X 0X1X 0X11- X -11- X -1 X X 0 0求值方法 x = (-1)X0( x12n-1 + + xn-12 +Xn)求值方法 x = (-1)X0( x12-1 + + xn-12-(n-1) +Xn2-n)原码表示法58原码在数轴上的表示p-7+77个正数,7个负数,两个零p-(2(n-1)-1)2(n-1)-159SignedMagnitudeoBothpositiveandnegativeze
24、rooEqualnumberofpositivesandnegativesoEasytointerpretnFirstbitisthesignnRemainingbitsarenumberoSoundsideal?Buto01011001+11001101=?60SignedMagnitude? 010110012 = 8910 + 110011012 = -7710 001001102 = 3210If signs are different sign of result will be sign of larger operandIf signs are different sign of
25、 result will be sign of larger operand61Shortcomingsofsignedmagnitude?oArithmeticcircuitcomplicatedoAlso,twozerosn0x00000000=+0tenn0x80000000=0tennWhatwouldtwo0smeanforprogramming?oThereforesignandmagnitudeabandoned62反码表示法o所谓反码,就是二进制的各位数码取反o符号位表示方法与原码相同oExample:710=001112;-710=110002oCalledOnesCompl
26、ement63反码0的表示o+0反=0.0000o-0反=1.1111o0.1111反=0.1111o-0.1111反=1.0000o1110反=01110o-1110反=1000164反码公式证明o-1x=0时n假设x=-0.x1x2xnn假x反=1.x1x2xnnx反+|x|=1.111=1.111+0.001-0.001=10.000-0.001=2-2-nox反=2-2-n-|x|=2-2-n+x65反码公式证明o-2nx=0时n假设x=-x1x2xnn假设x反=1x1x2xnnx反+|x|=1111=1111+0001-0001=10000-0001=2n+1-1ox反=2n+1-1
27、-|x|=2n+1-1+x66X X 反反反反=X 0X2X 0X2n n2 2n+1n+11+X -21+X -2n n X X 0 0X X 反反反反=X 0X1X 0X12 - 22 - 2n n+X+X -1 -1 X X 0 0求值方法(X反= x0x1 xn-1 Xn) x = -x0(2n -1)+ x12n-1 + + xn-12 +Xn 反码表示法67反码在数轴上的表示p-7+7正数7个,负数7个,零两个p-(2n-1)2n-168原码&反码69ShortcomingsofOnescomplement?oArithmeticstillasomewhatcomplicated.
28、oStilltwozerosn0x00000000=+0tenn0xFFFFFFFF=-0tenoAlthoughusedforawhileonsomecomputerproducts,onescomplementwaseventuallyabandonedbecauseanothersolutionwasbetter.70o3与15、-9等效有趣的时钟12369123691236971同余的概念o假定有两个数a和b,若用某一个整数m去除,所得的余数相同,就称a,b两个数对m同余,记作:ab(modm)o假设X,Y,Z三个数,满足下列关系:Z=nX+Y(n为整数),则称Z和Y对模X是同余的,记
29、作:ZY(modX)YZ(modX)72例子oZ=nX+YX为模数o以12为模o3=12+3=24+3=36+3o3,15,27,39都是相等的o-9=12-9=3o-9与3是相等的o0=1273例子(减法变成加法)o7+(-4)o=7+(12-4)o=7+8o=15=3743.补码表示法求值方法(X补= x0x1 xn-1 Xn)x = -x02n + x12n-1 + + xn-12 +Xn 例如:10000100的真值为-128+4=-124X X 补补补补=X 0X2X 0X2n n2 2n+1n+1+X -2+X -2n nX0X0X X 补补补补=X 0X1X 0X12+X -1X
30、02+X -1X075补码在数轴上的表示p-8+7正数7个,负数8个,零1个p-2n2n-176反码、补码数轴表示比较77补码编码的简便方法o正值直接取其原来的二进制码,对于负数是在对其逐位取反之后再在最低位LSB加1。o-10101010补=101010101+1=101010110o-0.010101补=1.10101178证明定点小数时x反=2-2-n+xx补=2+x=(2-2-n+x)+2-n=x反+2-n整数时x反=2n+1-1+xx补=2n+1+x=(2n+1-1+x)+1=x反+179例子oX=+0.11111111X补=?X补=0.11111111oX=-0.11111111X
31、补=?X补=1.00000000+0.00000001=1.00000001oX=-0.00000000X补=?X补=1.11111111+0.00000001=10.00000000=0.000000008000000000000000000000000000000000two=0ten00000000000000000000000000000001two=+1ten00000000000000000000000000000010two=+2ten.01111111111111111111111111111110two=+2,147,483,646ten0111111111111111111
32、1111111111111two=+2,147,483,647ten10000000000000000000000000000000two=2,147,483,648ten10000000000000000000000000000001two=2,147,483,647ten10000000000000000000000000000010two=2,147,483,646ten.11111111111111111111111111111101two=3ten11111111111111111111111111111110two=2ten11111111111111111111111111111
33、111two=1tenmaxintminint32bitMIPSsignednumbers81模4补码例: 00.1010110 11.0101001又称 双符号位补码,变形补码X X 补补补补=X 0X2X 0X2n n2 2n+2n+2+X -2+X -2n nX0X0X X 补补补补=X 0X1X 0X14+X -1X04+X -1X082补码的性质o零有唯一的表示方式0.0000补=-0.0000补=0.0000o负一的补码1.0000补=1.000083补码加减法的实现X+Y补=X补+Y补X-Y补=X补+-Y补84补码特点o唯一的零o符号位可以直接参与运算o减法可以变成加法o负数比整
34、数多一个854.移码表示法Biased/ExcessNotationp 保持数据原有大小顺序,便于进行比较操作。p 通常仅用于表示整数,表示浮点数的阶码。p 与补码的符号位相异,数据位相同定义x移 = 2n+x -2n x 1o全部检错码为0表示数据正常o不为零时检错码的值表示编码中出错数据位o可检错,也可纠错o每一数据位至少参加2个校验组,一位出错,可引起多个检错码的变化。102可检测一位错海明码o设海明码N位,其中数据位k位,校验位r位o校验位r位表示共r个校验组oN=k+r2r1o(4,3)编码nD4D3D2D1P3P2P1nH7H6H5H4H3H2H1n包含G3G2G1个校验组,P3P
35、2P1分属其中一组103H7参与G3G2G1三校验组H6参与G3G2两校验组H5参与G3G1两校验组H3参与G2G1两校验组G2G1=0表示仅仅P3位出错G3G1=0表示仅仅P2位出错G3G2=0表示仅仅P1位出错备注H7出错111H6出错110H5出错101H3出错011P3存放在H4位置H4出错100P2存放在H2位置H2出错010P1存放在H1位置H1出错001数据正常000出错位G3G2G1可检测一位错海明码104P1P2D1P3D2D3D4H1H2H3H4H5H6H7oG1(P1,H3,H5,H7)oG2(P2,H3,H6,H7)oG3(P3,H5,H6,H7)oP1=D1D2D4o
36、P2=D1D3D4oP3=D2D3D4可检测一位错海明码H7参与G3G2G1校验组H6参与G3G2校验组H5参与G3G1校验组H3参与G2G1校验组H7出错111H6出错110H5出错101H3出错011备注出错位G3G2G1105指错、纠错原理oG1=P1D1D2D4oG2=P2D1D3D4oG3=P3D2D3D4o检错码G3G2G1!=000表示出错,具体值表示出错位置o将对应位置上的数位取反即可纠错o假设D1D2同时出错,则G3G2G1=110?o引入总校验位P4=H1H2H3H4H5H6H7oG4=P4H1H2H3H4H5H6H7 判断一位错两位错106CRC循环冗余校验码o检错,纠错
37、码o数据位k位,校验位r位oN=k+r2r1107模2运算规则o加法:按位加不考虑进位o减法:按位减不考虑借位n异或运算,不考虑进位o乘法:部分积之和按模2加法计算o除法:余数首位为1,商上1,否则上0n10000101n=101*101+01108多项式o将待编码的k位有效信息位组表达为多项式M(x)oM(x)=bk-1Xk-1 + bk-2Xk-2 + b1X1 + b0o将数据左移r位,以便空出r位校验位,多项式变成M(x)X r o将M(x)X r除以生成多项式G(x)n商为Q(x)余数R(x)M(x)X r=Q(X)G(x)+R(X)o将余数拼接在空出的校验位上oM(x)X r+R(
38、X)=(Q(X)G(x)+R(X)+R(x)Q(X)G(x) CRC编码可被G(x)表示的编码整除109(7,4)循环码出错模式G(x)=101111010100010211110000103110111001040111101010510011001106010110000070011100011无0001100010出错位余数A1A71101-01011001101-01111101-001101101101-0001001000110100010110生成多项式o任何一位发生错误都应使余数不为0o不同位发生错误应当使得余数不同o对余数继续作模2除,应使余数循环o(n,k)码,将Xn-1分
39、解为若干质因子o根据编码要求的码距选择其中的因式或若干因式的乘积为生成多项式111生成多项式ox7-1=(x+1)(x3+x+1)(x3+x2+1)oG(x)=x+1=11n(7,6)码,判一位错oG(x)= x3+x+1 G(x)(x3+x2+1)n(7,4)码,判两位错或纠一位错oG(x)=(x+1)(x3+x+1)=11101n(7,3)码,判两位错并纠一位错112Exampleo现有一个(7,3)循环冗余校验码,其中3位为信息位,求信息位M(x)=110的CRC码,其中生成多项式为G(x)=11101。113(7,3)循环码出错模式G(x)=1110111110010100120111
40、1001001311011111001410001100001501001101101600101101011700011101000无00001101001出错位余数A1A71+2+3010000100015+6+7011111011101+6110001010112+3101010110013+4010111100014+5110011001015+6011011011116+700111101010出错位余数A7A1114CRC(CyclicRedundancyChecko可检测出所有的双错、奇数位错o可检测所有小于、等于校验位长度的突发错n突发错是指几乎连续发生的一串错,突发长度就是指
41、从出错的第一位到出错的最后一位的长度(但是,中间并不一定每一位都错)o广泛运用于通信传输领域,磁存储领域115本章重点内容o二进制表示以及进制转换运算o2X、X/2、X/64的求解方法o真值、原码、补码、移码、反码的编码方法。n熟练掌握o纠错码和检错码n奇偶校验熟练掌握n海明,CRC会计算oBCD码机器数有权码校验码概念116Example(清华大学1998年试题)o写出数据-11.4的规格化浮点数形式表示,阶码采用4位移码,尾数用12位原码,含符号位。o写出上述格式的规格化浮点数所能表示的最大正数和最小正数。o说明上述格式中浮点数的机器零o说明浮点数中隐藏位含义和用法117解答o-11.4=-1011.01100111o-11.4=-0.101101100111*24o-11.4=-1.01101100111*23o-11.4=-1.01101100111*23o-11.4=-01101100111*23o-11.4=1,01101100111*23oM=1,01101100111E=3=1,011118解答(-1)s1.m2eo最大整数1.1111111111127=(2-2-11)27o最小整数1.000000000002-8 = 2-8119