《【教学课件】第二章数据的表示.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第二章数据的表示.ppt（93页珍藏版）》请在三一办公上搜索。
1、第二章 数据的表示,主讲：关桂霞,http:/,计算机最基本的功能是什么?,数据运算,操作对象？,数制转换（二进制）,文字、图表、图形图像、声音、视频等各种媒体信息,任意R计数制的数可以按其位权方式展开,D=Dn-1Dn-2D2D1D0.D-1 D-m,基数,进位记数法,常用的进制,十进制、二进制、八进制、十六进制,(123.55)8=182+281+380+58-1+58-2,(123.55)10=1102+2101+3100+510-1+510-2,(101.01)2=122+021+120+02-1+12-2,数制转换,二进制数转换为十进制数,累加二进制数中全部数值为1的那些位的位权,(
2、1101.1100)2=(123+122+021+120+12-1+12-2+02-3+02-4)10=(123+122+120+12-1+12-2)10=(13.75)10,十进制数转换为二进制数,将十进制数转化成2的米次方之和的形式,(12.25)10=(123+122+12-2)10=(1100.01)2,计算机中数据的表示方法,计算机中的数据通常可以分为以下三种类型：,逻辑数据 符号数据 数值数据,与、或、非,一、逻辑型数据,逻辑型数据,True、真False、假,数据表示,10,数据运算,二、字符数据的表示方法,为每个符号进行编码以字符串的形式在计算机存储器中存放,重要的人机界面,字
3、符集编码标准,ASCIIUNICODE,1.ASCII码(American Standard Code for Information Interchange),包括：26个英文字母的大小写、10个数字、各种常用符号、控制符号等，共计需要128个编码。,采用7位二进制编码，占用一个字节。,高3位011,低4位0100,=(0110100)2,16位表示一个字符，可以表示65536个字符。将整个编码空间划分为块，每块为16的整数 倍，按块进行分配。保留6400个码点供本地化使用。依然无法覆盖所有字符。,2.UNICODE编码,计算机中有符号数的表示方法 机器数的定点表示与浮点表示 浮点数阶码的移
4、码表示 实用浮点数格式,三、数值数据的表示方法,1.基本概念,真 值:用“+”、“-”号表示的实际数值。机器数:符号和数值一起编码表示的二进制数。常用的机器数有原码、反码、补码三种表示。,1)原码表示,用原码表示带符号的二进制数时，符号位用0表示正，1表示负；数值位保持不变。原码表示法又称为符号数值表示法。,2.计算机中有符号数的表示方法,X1=+1011X2=-1011,X1原=0,1011,X2原=1,1011,原码特点：简单直观，与数据真值的转换方便，进行乘除运算比较容易。但是用原码进行加减运算不方便，既要考虑数的符号又要考虑其数值，比如说两个异号数相加，或两个同号数相减，就要做减法，机
5、器中需要增加减法器。为了使机器的结构简单，有可能将减法运算转换为加法运算吗？,10-4=6(点)倒拔10+8=6(点)顺拔,10+8=12+6,模,8与-4对模12互为补数,可见，只要确定了“模”，就可找到一个与负数等价的正数（该正数即为负数的补数）来代替此负数，而这个正数可以用模加上负数本身求得，这样就可把减法运算用加法实现了。,10-4=10+(-4)=10+(12-4)=10+8=6(mod 12),将补数的概念用到计算机中，便出现了补码这种机器数。,符号位与原码相同；数值位与符号位相关:正数补码的数值位与原码相同；负数补码的数值位是原码的数值位按位取反，并在最低位加1。,2)补码表示,
6、X1=+1011X2=-1011,X1补=0,1011,X2补=1,0101,就是符号位与数值位一起参加运算，并且可以将减法运算用加法实现，从而有利于运算器结构的简化，所以目前大多数计算机均采用补码这种机器数形式表示有符号数。,采用补码的最大优点:,设机器字长4位（含1位符号位），以纯整数为例：,原码可表示的数:,补码可表示的数:,7个正数,8个负数,1000,0,+1,+2,+3,+4,+5,+6,+7,-1,-2,-3,-4,-5,-6,-7,0111,1111,1001,0001,0010,1010,0000,多表示一个负数!,练习：已知下列两数的补码，求它们的真值。x补1,101100
7、 y补0,101011,1)定点数表示法 约定小数点在固定的位置。有二种情况：,3.机器数的定点、浮点表示,当Xs=0，X1Xn=1时，X为最大正数，即：,最大正数,0,设数值位的位数为n，分析定点小数的范围：,X最大正数=(1-2-n)。,当Xs=0，X1Xn-1=0且Xn=1时，X为最小正数，即：,最小正数,0,X最小正数=2-n。,原码表示的绝对值最大负数,1,X绝对值最大负数(原码表示时）=-(1-2-n),补码表示的绝对值最大负数,1,X绝对值最大负数（补码表示时）=-1,注意,定点整数,最大正数,0,X最大正数=(2n-1),设数值位的位数为n，分析定点整数的范围：,X最小正数=1
8、,最小正数,0,X绝对值最大负数（原码表示时）=-(2n-1),X绝对值最大负数（补码表示时）=-2n,1,1,注意,原码表示的绝对值最大负数,补码表示的绝对值最大负数,定点小数的表示范围：-(1-2-n)X+(1-2-n),定点整数的表示范围：-(2n-1)X+(2n-1),设数值位为 n 位，用原码表示时:,采用补码表示时，定点数的表示范围:,在字长8位时定点整数的范围,+127,-128,0,-1 X 1-2-n，-2n X 2n-1,定点数表示简单直观；但数值表示范围太小（字长），运算时易产生溢出。,设某机字长16位，问:在下列几种情况下所能表示数值的范围。(1)无符号整数(2)用原码
9、表示的定点小数(3)用补码表示的定点小数(4)用原码表示的定点整数(5)用补码表示的定点整数,练习题:,相当于数学上的指数表示法。可以将一个任意的二进制数 N 表示为：,其中：M 称为尾数，为定点小数（精度）E 称为阶码，为定点整数（范围）J 基数，通常为2，在机内隐含,2)浮点数表示法,举例:(-1101.00101)2 在机内的浮点表示。,设机器字长为16位，尾数占10位.,若其它条件不变,尾数与阶码均为8位,会发生什么情况呢?,即：尾数为-0.110100101，,解：(-1101.00101)2=-0.11010010124,阶码为+4(0100),若都采用原码表示时，则该数在机内的表
10、示形式为：,3）浮点数的规格化处理,规格化：要求浮点数尾数值的最高位为。,【例】把非规格化的浮点数N2110.0110规格化。解：把浮点数N的尾数向左移一位，变成0.1100，同时，阶码递减1，得到N0.1100210，这就是规格化的浮点数。,(-1101.00101)2=-0.11010010124=-0.011010010125=-0.0011010010126,在尾数用补码表示时，规格化浮点数应满足尾数最高数位与符号位不同（msm1=1），即当1/2M1时，应有0.1xxx形式，当-1M-1/2时，应有1.0 xxx形式。注意-1/2的补码形式，它不算规格化的数。,2.如何判断机内机器数
11、的规格化形式?,提高精度、机内格式唯一。,1.机内为什么要采用规格化浮点数格式?,1/2|M|1,【例 将 58 表示成二进制定点数和浮点数。具体要求是：写出它在定点机中的原码和补码的机器数（11位）；浮点机中的阶码为原码,尾数为补码的形式。其中数值部分均取 10 位，数符取 1 位，浮点数阶码取 5 位（含1位阶符）。,x=0000111010,解：,x=58,二进制形式:,定点数机外表示:,0,0110;1.0001100000,浮点数,x=111010,练习：设十进制数 x=(-128.75)2-10,(1)用16 位定点数表示 x 的值（补码）,(2)用21 位表示浮点数，其中阶码用5
12、位补码，尾数用16位补码。请确定出浮点数的机内表示。,十进制,解：,(1)X=(-128.75)2-10=-10000000.112-10=-0.001000000011000,其16 位定点数表示为：1，补码),阶码用补码，尾数用补码表示的浮点机器数为：1，1110 1，,(2)X=(-128.75)2-10=-10000000.112-10=-0.10000000112-2=-0.1000000011000002-10,阶码部分E,尾数部分M,es,ms,X最大正数=(1-2-n)22k-1,(1)最大正数:,设阶码数值位是k位，尾数的数值位是n位，分析用补码表示的浮点数的范围。,浮点数的
13、表示范围：,阶码部分E,尾数部分M,es,ms,X最小正数=2-n2-2k,注意,(2)最小正数:,阶码部分E,尾数部分M,es,ms,X绝对值最大负数=-122k-1,(3)绝对值最大负数:,X规格化的最小正数=2-12-2k,下面格式中表示的数是什么呢?,综合以上两种情况：（1）采用原码表示阶码和尾数时,浮点正数的表示范围为：+2-m2-(2p-1)=+X=+(1-2-m)2+(2p-1)浮点负数的表示范围为：-(1-2-m)2+(2p-1)=-X=-2-m2-(2p-1),（2）用补码表示阶码和尾数时,浮点正数的表示范围为：+2-m2-2p=+X=+(1-2-m)2+(2p-1)浮点负数
14、的表示范围为：-12+(2p-1)=-X=-2-m2-2p,最大正数,(1 210)215,0,1111;0.1111111111,综合举例:设 n=10，k=4，阶符、数符各取 1位,分析用补码所表示的浮点数范围.,负数区,正数区,下溢,负上溢,正上溢,2(2m1),(1 2n)2(2m1),2n 2(2m),绝对值最大负数：,最大正数：,最小正数：,2n 2(2m),最大负数：,真值,最小正数,最大负数,绝对值最大负数,210 216,210 216,-215,1,0000;0.0000000001,1,0000;1.1111111111,0,1111;1.0000000000,补码,浮点
15、数绝对值太大的溢出称上溢；浮点数绝对值太小的溢出称下溢。发生上溢时,要中止运算,进行溢出处理,而发生下溢时不报错可作为机器零处理.,练习：某浮点数字长64位。其中：阶码16位，含位阶符，补码表示；尾数48位，含位数符，原码表示，问其所能表示的正数范围是多少？,如,十进制,x+25,+10101+100000,+11111+100000,错,错,正确,正确,0,10101,1,01011,0,11111,1,00001,+10101,10101,+11111,11111,=110101,=001011,=111111,=000001,二进制,补码,问题：补码能真实地反映真值的大小吗？,答案：补码
16、表示很难直接判断其真值大小！,定义：X移=2n+X 其中 为真值 2n 为偏置值，n为的位数,例：+1011移=-1011移=,四、浮点数阶码的移码表示,10000+1011=11011,10000-1011=00101,移码与其它机器数相比有以下特点：,用“”表示负号、用“”表示正号。同一个真值其移码的表示与补码的表示只是符号位相反，数值位完全相同。,补码与移码只差一个符号位！,移码可以直接反映出其所代表的真值的大小。,为什么要用移码来表示浮点数的阶码呢?,便于浮点数加减运算时的对阶操作。例：1.012-1+1.112 3=?补码 1111(-1)0011(+3)移码 0111(-1)101
17、1(+3)可以用移码表示的阶码直接比较阶码的大小!简化机器中的判零电路。当阶码全为0，尾数也全为0时，表示机器零。,为什么要引入移码?,移码是用来表示浮点数的阶码，方便浮点数的运算！,?,进一步讨论移码的作用,一位符号位和 7 位数值位组成的移码,其定义为；E移=27+E-2n=E2n 表示范围：00000000 11111111,8 位移码表示的机器数为数的真值在数轴上向右平移了 128 个位置,机器数,正数,负数,移码序列实际上是其真值在数轴上平移的结果，实际上是将有符号数转换成无符号数表示。,其中：阶码用移码表示 尾数用原码表示,五、实用浮点数格式,IEEE 754 标准的浮点数格式,实
18、用短浮点格式(32位),注意以下二点：1)阶码采用移码表示，偏置值为7FH(127)2)尾数规格化且采用隐蔽位技术（尾数实际上是24位）,为什么实用短浮点格式的偏置值为127？,例题1：求(15.75)10的实用短浮点格式。,解：将(15.75)10 转换为二进制；,表示成规格化二进制格式,并注意隐蔽位，以确定尾数部分值；,计算阶码的移码值。,得到该数的短浮点数格式如下:,4 1 7 C 0 0 0 0 H,(15.75)10=417C0000 H,例题2 求出短浮点数 C2308000H 所表示的真值。,e移=10000100 e=e移 7FH=101 M=1.011 0000 1000 0
19、000 0000 0000,1100 0010 0011 0000 1000 0000 0000 0000,1100 0010 0,X=-1.011000012+101,注意：为了表示和一些特殊的数值，阶码E全0和全1将留作它用。当E和m均为零时，表示机器零；当E全为1，m全为0时，表示。,文字、图表、图形图像、声音、视频等各种媒体信息,数值型数据（符号）,非数值型数据,逻辑数据,字符型数据,定点数,浮点数,定点整数,定点小数,西文字符,汉字编码,二进制编码表示的各种数据,本章内容 数据表示,机器数字长8位（含1位符号位），若机器数为81H（十六进制），当它分别表示原码、补码、反码和移码时，等
20、价的十进制数分别是多少？确定（0.000111)2在机内的实用短浮点格式。,测试题,本节内容小结：,机器数的定点数表示方法、表示范围。机器数的浮点数表示方法、表示范围。IEEE 754的实用短浮点数格式的转换。,如何提高系统可靠性？,在硬件上选用更高可靠性的器件 精心选择更合理的电路结构 改进生产工艺和测试手段采用检错和纠错的编码技术,2.1.2 数据校验码,在原有数据位之外再增加一到几位校验位，使新得到的代码带上某种特征，之后则通过检查该代码是否仍保持有这一特性，来发现是否出现了错误，甚至于定位错误并纠正错误，这就是检错纠错的编码技术。,一、与检验码的相关基本概念,何为错误检测码？,检错纠错
21、的过程,形成校验位的值，加进特征,检查接收的码字，发现/改正错误,检错纠错的必要条件,码字：表示一个数（或字符）的若干位二进制代码。码元：码字中的一位。码组：满足一定规则的所有码字的集合。最小码距(码距)：一个码组中任何两个码字之间的不同码元的最小个数。,n位码有2n个编码状态，全用于表示合法码，其最小码距为1。则任何一位出错,均会变成另一个合法码，不具有检错能力。n+1位码，只使用其2n个状态，可使码距 为2，如果一个合法码中的一位错了，就成为非法码，通过检查码字的合法性，就可以得到检错能力，这就是奇偶校验码。,最小码距与检错纠错的能力,1.功能：用于并行码检错。2.原理：在 n 位数据码之
22、外增加 1 位校验位，使 n+1 位码字中取值为 1 的位数总保持为偶数个（称为偶校验）或 奇数个（称为奇校验）。,二、奇偶校验码,奇偶校验码编码举例：四位数据代码,1010,01010,11010,偶数个1,奇数个1,0111,10111,00111,偶数个1,奇数个1,8位,8位,9位,9位,01010101,01010101,101010101,1,101010101,01010101,101010101,101010111,101010111,有4个1,有5个1,正确,出错,有6个1,中断处理,下面是奇校验的例子:,奇偶校验码的实现电路,产生校验位D7 D6 D5 D4 D3 D2 D
23、1 D0,奇校验位,偶校验位,偶校验码的检测电路,D7D6D5D4D3D2D1D0C,计算机在进行大量字节（数据块）传送时，不仅每一个字节有一个奇偶校验位做横向校验，而且全部字节的同一位也设置一个奇偶校验位做纵向校验，这种横向、纵向同时校验的方法称为交叉校验。A7 A6 A5 A4 A3 A2 A1 A0 横向校验位 第1字节 1 1 0 0 1 0 1 1 1 第2字节 0 1 0 1 1 1 0 0 0 第3字节 1 0 0 1 1 0 1 0 0 第4字节 1 0 0 1 0 1 0 1 0 纵向校验位1 0 0 1 1 0 0 0,交叉奇偶校验,交叉校验可以发现两位同时出错的情况，假设
24、第2字节的A6、A4两位均出错，横向校验位无法检出错误，但是第A6、A4位所在列的纵向校验位会显示出错，这与前述的简单奇偶校验相比要保险多了。,1,0,三、海明校验码,概述功能：用于多位并行数据检错、纠错处理。实现：为个数据位设立个校验位，使 位组成的码字具有以下特性：能发现并改正位中任何一位出错；能发现位中任何二位同时出错，但无法改正。,海明码的最低目标是纠正一位错，因此要求最小码距。,.海明码的编码,就是对给定的信息码，以纠正一位错为最低目标，确定校验位的位数及校验位的值，最终形成海明码的过程。,下面以海明码为例，说明海明码的编码过程。依据信息位,确定校验位:n=4,k=3,位数据位,位校
25、验位,按次序排列数据位和校验位，,位序：7 6 5 4 3 2 1,P3=D4 D3 D2P2=D4 D3 D1P1=D4 D2 D1,三个校验位的值按下式确定：,注：校验位安排在2i的位置上（i=0、1、）,P1,P2,P3,D1,D2,D3,D4,对给定的信息编码确定相应的海明码,设当 D4、D3、D2、D1=0100 时说明海明码的形成和检测。,则 P3=D4 D3 D2=1 P2=D4 D3 D1=1 P1=D4 D2 D1=0,与之对应海明码就是：0 1 0 1 0 1 0,8421海明码,对应的三个偶检测方程：S2=D4 D3 D2 P3S1=D4 D3 D1 P2S0=D4 D2
26、 D1 P1 若（S2 S1 S0）000 无错误发生，若（S2 S1 S0）000 说明错误发生，且其值可说明出错的位置。,.海明码的译码（检测和纠错）,例：若D2发生错误，则S2S1S0的值为:101由此可知错误发生在位序5。,根据结果可确定是否出错以及出错码元的位置！,校验位会发生错误吗？应如何处理？能否判别是校验位出错还是信息位出错呢？如何纠正信息位错误呢？如果发生了二位出错的情况又会怎样呢？,不具有发现二位的能力!,为什么？,4.N位信息的海明码,主要解决：对n位信息需要增加多少校验位，才能组成海明纠错码呢？,对 n 位信息位，当给出 k位校验位时，要发现并改正一位错，须 满 足 如
27、 下 关 系：2k=n+k+1,其中（n+k)种状态用于给定（n+k)位代码中某一位出错，另一种状态用来表示无出错的情况。,要发现并改正一位错，也能发现两位错，则：2k-1n+k,四、循环冗余码(Cyclic Redundancy Check）,1.功能 用于多位串行数据传送中的检错纠错处理。假若信息位为N位，校验位为K位，就构成(N+K,N)位的CRC码。例（7，3）码、（7，4）码,注意:N代表的是什么?K代表的是什么?,2.与CRC有关的几个概念,模2除类似于正常二进制除法，区别有3点：1）上商只看每次得到的余数的最高位，其值为 1 则上商 1，其值为 0 则上商 0。,2）求余数用模2
28、减。,3）一直做到余数的位数小于除数时，该余数就是最终的余数。,模2的加、减运算:实际为异或运算 模2的乘、除:,模2运算,任意一个由二进制串组成的代码都可以与一个系数取值仅为0、1的多项式对应。例：代码1010111对应的多项式为 X6+X4+X2+X+1 所以就有了信息多项式以及生成多项式。,是接受方和发送方的一个约定，也就是一个二进制数，在整个传输过程中，这个数始终不变。在发送方利用生成多项式做模2除进行CRC编码。例:G(X)=X3+X+1 1011,多项式与二进制数码,关于生成多项式,3.循环冗余码的编码,对给定的信息确定生成多项式G(x);将生成多项式G(x)转换成对应的R位二进制
29、数。将信息码左移R-1位（低位补R-1个0）。用生成多项式（二进制数）对信息码做模2除，得到R-1位的余数。将余数拼到信息码的低位，得到完整的CRC码。,与信息码1100拼接得到CRC码为1100010。,【例】对4位二进制数据1100生成CRC码 解：信息多项式M(x)=1100=x3+x2 生成多项式 G(x)=1011=x3+x+1 M(x)左移3位:M(x)*x3=x6+x5=1100 000 做模2除，求得余数R(x)：M(x)x3G(x)=1100 0001011=1110+0101011,例:信息多项式 M(x)=x3+x2=1100 生成多项式 G(x)=x3+x+1=1011
30、 将信息 M(x)x3=x6+x5=1100000 M(x)x3 1100000 010 G(x)1011 1011 M(x)x3+R(x)=1100000+010=1100010 编好的循环校验码称为(7,4)码,即n=4,k=3而这个码就应该能够被G（X）整除。,=,=1110+,4、循环冗余校验(CRC)码原理分析,发送 m(x),m(x).xr,R(x)=mod(m(x)xr)/g(x),CRC码:m(x).xr+R(x),接收方,将接收到的CRC码与g(x)作模2除(m(x).xr+R(x)/g(x),余数=0?,CRC校验正确,所以其过程可表示为:,N,Y,5.循环冗余码的纠错 将
31、接收到的CRC码，用同一个约定的生成多项式G（X）去除，有二种情况：余数为0，表明无错。余数不为0，某一位出错！而且不同的出错位置，余数的值不同，有固定的对应关系,所以用余数的值作为判断出错位置的依据而纠错。请看下列出错模式表.,（7，4）CRC码的出错模式（G(x)1011）,注：请比较教材表2-11的出错模式表,结论：余数与出错位的对应关系仅与码制及生成多项式有关，而与待测码字无关！如果循环码有一位出错，用G(x)作模2除将得到一个不为0的余数。如果对余数补0继续除下去，我们将发现一个有趣的结果；各次余数将按顺序循环。例如第一位出错，余数将为001，补0后再除（补0后若最高位为1，则用除数
32、做模2减取余；若最高位为0，则其最低3位就是余数），得到第二次余数为010。以后继续补0作模2除，依次得到余数为100，0ll，反复循环，这就是“循环码”名称的由来。,对G(x)1011，M(x)1010，若接收端收到的码字为1010111,如何作校验处理？,解：用G(x)1011做模2除得到一个不为0的余数100，说明传输有错。将此余数继续补0用G(x)1011作模2除，同时让码字循环左移1010111。做了4次后，得到余数为101，这时码字也循环左移4位，变成1111010。说明出错位已移到最高位A7，将最高位1取反后变成0111010。再将它循环左移3位，补足7次，出错位回到A3位，就成
33、为一个正确的码字1010011。,这样做有什么好处呢?,在发送方利用生成多项式做模2除进行CRC编码，在接受方利用生成多项式对收到的编码做模2除检测和确定出错的码元。目前已经有多种生成多项式被列入国际标准中，如：CRC-4、CRC-12、CRC-16等。局域网络应用中采用的生成多项式为g(x)=x4+x3+1。它的检错能力很强，误判率极低，校验效率较高，成为提高数据传输质量的有效差错控制手段。,6.对生成多项式的进一步说明,生成多项式的最高位和最低位必须为1。当被传送信息（CRC码）任何一位发生错误时，被生成多项式做模2除后应该使余数不为0。不同位发生错误时，应该使余数不同。对余数继续做模2除
34、，应使余数循环。将这些要求反映为数学关系是比较复杂的。但可以从有关资料查到常用的对应于不同码制的生成多项式如图所示：,生成多项式必须满足以下条件,生成多项式举例：,N K 码距 生成多项式 G（X）的码7 4 3 G(X)=X3+X+1 1011 或G(X)=X3+X2+1 11017 3 4 G(X)=(X3+X+1)(X+1)11101 G(X)=(X3+X2+1)(X+1)1011115 11 3 G(X)=X4+X3+1 1100131 26 3 G(X)=X5+X2+1 100101,1、求出信息码1101110的海明校验码。2、有一个（7，3）码，生成多项式为 G(X)=X4+X3+X2+1，写出代码001的CRC码和循环余数。,思考题,机器数字长8位（含1位符号位），若机器数为81H（十六进制），当它分别表示原码、补码、反码和移码时，等价的十进制数分别是多少？确定（0.000111)2在机内的实用短浮点格式。3.海明校验码最基本的功能是什么？为实现对5位数据的海明校验，最少应安排几个校验位？,测试题,
