第二章、计算机数据表示方法.ppt

第二章、计算机数据表示方法,2,Outline,2.1非数值数据表示法2.2数值数据表示法2.3数据信息的校验,3,DataRepresentation,QualitativeQuantitativeIntegersSignedUnsignedNon-integers(Real)SignedUnsigned,4,2.1非数值数据表示法,字符表示法characters汉字表示法Chinesecharacters,5,2.1.1Characterrepresentation,如何使用数值表示字符数据StandardsASCII-AmericanStandardCodeforInformationInterchange(ANSI7bits)EBCDIC-ExtendedBinary-CodedDecimalInterchangeCode(IBM8bits)Unicode,6,128StandardASCIIcodes,52Lettersa-z,A-Z10Digits0-934Symbols!#$%intd;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,二进制存储,浮点数不是精确数,53,一个奇怪的程序,main()floata,b,c;intd;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,54,2.2数值数据表示方法,计算机数值数据表示的特点进位制数数的定点、浮点表示机器数,55,2.2.2机器数/机器码,真值(书写用)将用+-表示正负的二进制数称为符号数的真值机器不能识别书写格式，计算机如何表示负数？机器码(机器内部使用)将符号和数值一起编码表示的二进制数称为机器码原码Signedmagnitude反码Onescomplement补码Twoscomplement移码Biasednotation,56,原码表示法（Signedmagnitude）,计算机如何表示数的正负?增加符号位Addasignbit最高位为符号位，0为正，1为负，数值位不变,57,原码表示示例,+0原=0.0000-0原=1.0000-0.1111原=1.11110.1111原=0.11111110原=01110-1110原=11110,58,求值方法x=(-1)X0(x12n-1+xn-12+Xn),求值方法x=(-1)X0(x12-1+xn-12-(n-1)+Xn2-n),原码表示法,59,原码在数轴上的表示,-7+77个正数，7个负数，两个零-(2(n-1)-1)2(n-1)-1,60,SignedMagnitude,BothpositiveandnegativezeroEqualnumberofpositivesandnegativesEasytointerpretFirstbitisthesignRemainingbitsarenumberSoundsideal?But01011001+11001101=?,61,SignedMagnitude?,010110012=8910+110011012=-7710001001102=3210,Ifsignsaredifferentsignofresultwillbesignoflargeroperand,62,Shortcomingsofsignedmagnitude?,ArithmeticcircuitcomplicatedAlso,twozeros0 x00000000=+0ten0 x80000000=0tenWhatwouldtwo0smeanforprogramming?Thereforesignandmagnitudeabandoned,63,反码表示法,所谓反码,就是二进制的各位数码取反符号位表示方法与原码相同Example:710=001112；-710=110002CalledOnesComplement,64,反码0的表示,+0反=0.0000-0反=1.11110.1111反=0.1111-0.1111反=1.00001110反=01110-1110反=10001,65,反码公式证明,-1x=0时假设x=-0.x1x2xn假x反=1.x1x2xnx反+|x|=1.111=1.111+0.001-0.001=10.000-0.001=2-2-nx反=2-2-n-|x|=2-2-n+x,66,反码公式证明,-2nx=0时假设x=-x1x2xn假设x反=1x1x2xnx反+|x|=1111=1111+0001-0001=10000-0001=2n+1-1x反=2n+1-1-|x|=2n+1-1+x,67,求值方法(X反=x0 x1xn-1Xn)x=-x0（2n-1）+x12n-1+xn-12+Xn,反码表示法,68,反码在数轴上的表示,-7+7正数7个，负数7个，零两个-(2n-1)2n-1,69,原码&反码,70,ShortcomingsofOnescomplement?,Arithmeticstillasomewhatcomplicated.Stilltwozeros0 x00000000=+0ten0 xFFFFFFFF=-0tenAlthoughusedforawhileonsomecomputerproducts,onescomplementwaseventuallyabandonedbecauseanothersolutionwasbetter.,71,3与15、-9等效,有趣的时钟,12,3,6,9,72,同余的概念,假定有两个数a和b，若用某一个整数m去除，所得的余数相同，就称a,b两个数对m同余,记作：,ab(modm),假设X,Y,Z三个数，满足下列关系：Z=nX+Y(n为整数),则称Z和Y对模X是同余的，记作：,ZY(modX)YZ(modX),73,例子,Z=nX+YX为模数以12为模3=12+3=24+3=36+33，15，27，39都是相等的-9=12-9=3-9与3是相等的0=12,74,例子（减法变成加法）,7+(-4)=7+(12-4)=7+8=15=3,75,3.补码表示法,求值方法(X补=x0 x1xn-1Xn)x=-x02n+x12n-1+xn-12+Xn例如：10000100的真值为-128+4=-124,76,补码在数轴上的表示,-8+7正数7个，负数8个，零1个-2n2n-1,77,反码、补码数轴表示比较,78,补码编码的简便方法,正值直接取其原来的二进制码，对于负数是在对其逐位取反之后再在最低位LSB加1。-10101010补=101010101+1=101010110-0.010101补=1.101011,79,证明,定点小数时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反+1,80,例子,X=+0.11111111X补=?X补=0.11111111X=-0.11111111X补=?X补=1.00000000+0.00000001=1.00000001,X=-0.00000000X补=?X补=1.11111111+0.00000001=10.00000000=0.00000000,81,00000000000000000000000000000000two=0ten00000000000000000000000000000001two=+1ten00000000000000000000000000000010two=+2ten.01111111111111111111111111111110two=+2,147,483,646ten01111111111111111111111111111111two=+2,147,483,647ten10000000000000000000000000000000two=2,147,483,648ten10000000000000000000000000000001two=2,147,483,647ten10000000000000000000000000000010two=2,147,483,646ten.11111111111111111111111111111101two=3ten11111111111111111111111111111110two=2ten11111111111111111111111111111111two=1ten,32bitMIPSsignednumbers,82,模4补码,例：00.101011011.0101001又称双符号位补码，变形补码,83,补码的性质,零有唯一的表示方式,0.0000补=-0.0000补=0.0000,负一的补码,1.0000补=1.0000,84,补码加减法的实现,X+Y补=X补+Y补X-Y补=X补+-Y补,85,补码特点,唯一的零符号位可以直接参与运算减法可以变成加法负数比整数多一个,86,4.移码表示法Biased/ExcessNotation,保持数据原有大小顺序，便于进行比较操作。通常仅用于表示整数，表示浮点数的阶码。与补码的符号位相异，数据位相同,定义x移=2n+x-2nx1全部检错码为0表示数据正常不为零时检错码的值表示编码中出错数据位可检错，也可纠错每一数据位至少参加2个校验组，一位出错，可引起多个检错码的变化。,103,可检测一位错海明码,设海明码N位，其中数据位k位，校验位r位校验位r位表示共r个校验组N=k+r2r1(4,3)编码D4D3D2D1P3P2P1H7H6H5H4H3H2H1包含G3G2G1个校验组，P3P2P1分属其中一组,104,H7参与G3G2G1三校验组,H6参与G3G2两校验组,H5参与G3G1两校验组,H3参与G2G1两校验组,G2G1=0表示仅仅P3位出错,G3G1=0表示仅仅P2位出错,G3G2=0表示仅仅P1位出错,备注,H7出错,111,H6出错,110,H5出错,101,H3出错,011,P3存放在H4位置,H4出错,100,P2存放在H2位置,H2出错,010,P1存放在H1位置,H1出错,001,数据正常,000,出错位,G3G2G1,可检测一位错海明码,105,P1,P2,D1,P3,D2,D3,D4,G1(P1,H3,H5,H7)G2(P2,H3,H6,H7)G3(P3,H5,H6,H7),P1=D1D2D4P2=D1D3D4P3=D2D3D4,可检测一位错海明码,106,指错、纠错原理,G1=P1D1D2D4G2=P2D1D3D4G3=P3D2D3D4检错码G3G2G1!=000表示出错，具体值表示出错位置将对应位置上的数位取反即可纠错假设D1D2同时出错，则G3G2G1=110？引入总校验位P4=H1H2H3H4H5H6H7G4=P4H1H2H3H4H5H6H7判断一位错两位错,107,CRC循环冗余校验码,检错，纠错码数据位k位，校验位r位N=k+r2r1,108,模2运算规则,加法：按位加不考虑进位减法：按位减不考虑借位异或运算，不考虑进位乘法：部分积之和按模2加法计算除法：余数首位为1，商上1,否则上010000101=101*101+01,109,多项式,将待编码的k位有效信息位组表达为多项式M(x)M(x)=bk-1Xk-1+bk-2Xk-2+b1X1+b0将数据左移r位，以便空出r位校验位，多项式变成M(x)Xr将M(x)Xr除以生成多项式G(x)商为Q(x)余数R(x)M(x)Xr=Q(X)G(x)+R(X)将余数拼接在空出的校验位上M(x)Xr+R(X)=(Q(X)G(x)+R(X)+R(x)Q(X)G(x)CRC编码可被G(x)表示的编码整除,110,(7,4)循环码出错模式G(x)=1011,1,101,0100010,2,111,1000010,3,110,1110010,4,011,1101010,5,100,1100110,6,010,1100000,7,001,1100011,无,000,1100010,出错位,余数,A1A7,0,1,1,0,1,0,0,111,生成多项式,任何一位发生错误都应使余数不为0不同位发生错误应当使得余数不同对余数继续作模2除，应使余数循环(n,k)码，将Xn-1分解为若干质因子根据编码要求的码距选择其中的因式或若干因式的乘积为生成多项式,112,生成多项式,x7-1=(x+1)(x3+x+1)(x3+x2+1)G(x)=x+1=11(7,6)码，判一位错G(x)=x3+x+1G(x)(x3+x2+1)(7,4)码，判两位错或纠一位错G(x)=(x+1)(x3+x+1)=11101(7,3)码，判两位错并纠一位错,113,Example,现有一个(7,3)循环冗余校验码，其中3位为信息位，求信息位M(x)=110的CRC码，其中生成多项式为G(x)=11101。,114,(7,3)循环码出错模式G(x)=11101,6,0010,1101011,7,0001,1101000,无,0000,1101001,出错位,余数,A1A7,1+2+3,0100,0010001,5+6+7,0111,1101110,1+6,1100,0101011,2+3,1010,1011001,3+4,0101,1110001,4+5,1100,1100101,5+6,0110,1101111,6+7