数据编码和数据运算ppt课件.ppt

《数据编码和数据运算ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据编码和数据运算ppt课件.ppt（89页珍藏版）》请在三一办公上搜索。

1、第二章 数据编码和数据运算,两个基本要素,权 赋予每一数位的位值，也称位权。weight基数 相邻二位高位权与低位权的比值。radix,任意进制数的表示法：对于数N有,x= xi Ri,n-1,i=-m,（小数点前n位，小数点后m位）,R 基数xi 0-(R-1)任意一数i 位数；小数点前位正，后为负。 为n-1,n-2, , ,3,2,1,0. 1,-2,-3，-m,等式左边：任意进制数等式右边：同值十进制和式,进位计数制,例：十进制数：R=10， xi为0,1,2, 9各位权103 , 102 , 101 ,100 , 10-1 , 10-2 , 10-3二 进 制: R=2， xi为0,

2、1；各位权为23 , 22 , 21 , 20 , 2-1 , 2-2,常用进位制符号：,B（二进制），O或Q（八进制）H（十六进制），D（十进制）,例： 将二进制数1101011010分别用十进制，八进制和十六进制表示。,1101011010B = 129 + 1 28 + 1 26 + 1 24 + 1 23 + 1 21= 858D1 101 011 010B = 1532Q11 0101 1010B = 35AH,转换原理： 如有两个有理数相等，则两数的整数部分和小数部分一定分别相等。,不同进位制的转换,转换方法： 分为整数部分和小数部分，分别转换后合并。,整数部分：除基取余小数部分：

3、乘基取整, 十进制转换为其他进制,例：215.6875D?B,整数部分小数部分,215.6875D=110101111.1011B, 任意进制转换为十进制,转换方法：利用任意进制数定义式，将右边展开。,N= Ki Ri= Kn-1 Rn-1 + K3 R3+ K2 R2 + K1 R1 + K0 R0 + K-1 R-1 + K-2 R-2 + K-3 R-3 + K-4 R-4 +,n-1,i=-m,.,.,例：4FCH = 4162 + 15 R1 + 12 R0 = 1024 + 240 + 12 = 1276D, 二进制 十六进制,转换方法：以小数点为界，利用4位二进制数与1位 十六进

4、制数的对应关系转换。,例：1011011.100111B ?H,0101 1011.1001 1100B 5B9CH (逆转换成立, 二进制 八进制,转换方法：以小数点为界，利用3位二进制数与1位 八进制数的对应关系转换。,例： 1011011.100111B ?Q,001 011 011.100 111B133.87Q, BCD码（二进制编码的十进制数）,00000000110010200113010040101501106011171000810019,BCD码二进制方法类似于十进制二进制, 二进制数的运算法则, 算术运算法则,加法减法乘法除法0+0=00-0=00 0=00+1=10-1

5、=1(借位)0 1=01+0=11-0=11 0=01+1=1(进位)1-1=01 1=1,类似于十进制除法,由减法上商等逐步完成(够减上1,不够减上0), 逻辑运算法则,逻辑与逻辑或逻辑异或逻辑非00=00+0=000=00=101=00+1=1 01=11=010=01+0=110=1 11=1 1+1=011=0,应用：,1011 10111011and 0000 or 0000 xor0000 0000 10111011,1011 10111011and 1111 or 1111 xor1111 1011 11110100,全0屏蔽，全1屏蔽， 遇0保留，全1保留。全0保留。 遇1求反

6、。,对于二进制 x可写成x = xn x2 x1x0. x-1x-2x-mxi=0,1, -min,n+1位二进制整数 x的两种排序x = xn x2 x1x0 x = x0 x1x2 xn (本课程采用）,计算机中数据格式,定点格式 浮点格式,2.1 定点数的编码和运算,定点数：小数点位置固定不变的数定点整数：小数点定在最低位数的右面定点小数：小数点固定在最高位数的后面，即纯小数表示,2.1.1 无符号数的编码,定点整数数值表示：x = x0 x1x2xnxi=0,1, 0inx02n + x12n-1 + + xn-121 + xn数值范围0 x2n+1-1例如:x=010101其数值=2

7、4+22+20=21,定点小数,数值表示x = x0 . x1x2xnx0=0,xi=0,1, 0in x12-1 + + xn-12-n+1 + xn2-n数值范围0 x1-2-n 例如： x=0.10101其数值=2-1+2-3+2-5=21/32,2.1.2 有符号定点数的编码,机器数：二进制数最高位表示符号，1为-， 0 为+。 后面各位为数值（绝对值）。真值： 带符号机器数对应的数值。例： 真 值 机器数 N1 - 1001100 11001100 N2 +101001101010011, 原码 n+1 位二进制数原码定义,x原码 =,x0 x 2n2n -x -2n x 0, 反码

8、,N+1 位二进制数反码定义,x反码 =,x 0 x 2n（2n+1 1）+x -2n x 0, 补码,n 位二进制数补码定义,x补码 =,x0 x 2n2n+1 + x -2n x 0,原码，反码，补码 n +1位中最高位为符号位，后 n 位为X数值。原码形式与机器数相同。 对于定点小数的原码、补码、反码，只要把上述定义式中的2n用1代替，1用2-n即代替即可可。, 2n+1 - 1=11 111 （n+1个1） 2n+1 - 1+x 正好为 x （x为负）,例： -1101101反码 = 10010010,111111110110110110010010,x反码与 x补码的关系,0 x 2

9、n-1 x补码= x反码-2n-1 x 0 x补码= 2n + x =x反码+1,4 移码对于n+1位定点整数 xx移=2n+x 2nx2-nx：真值，x移：机器数,常用于表示浮点数的阶码，便于比较大小 移码中符号位与原码、补码和反码相反 计算机中移码只执行加减运算,原码，反码，补码二进制数表示数值范围,真值 十进制原码 反码 补码 移码+1111111 +127 01111111 01111111 01111111 11111111+0000001 +1 00000001 00000001 00000001 10000001+0000000 +0 00000000 00000000 0000

10、0000 10000000- 0000000 - 0 10000000 11111111 00000000 10000000 - 0000001 -1 10000001 11111110 11111111 01111111- 1111111 -127 11111111 10000000 10000001 00000001-10000000 -128 10000000 00000000,对于+0和-0，原码和反码都有两种形式，而补码的表示形式相同，所以补码表示的数比原码和反码要多1个数。对于 n+1 位二进制，该数为- 2n ，故补码表示范围为： 2n - 1 - 2n 。, 补码运算,计算机中

11、带符号数运算一律用补码运算，其运算结果也用补码表示。,对于带符号数 x，y下列公式成立： x补 + y补 = x +y 补 (1) x补 + -y补 = x -y 补 (2),-y补 求法： 用补码定义式求 -y补 = y 补 变补 即先求出y补， 后将y补 连同符号位求反加1即可。,例2-1 设x=1010，y=-1010，求x补和y补。,解：根据补码的编码方法，正数的补码与它的二进制表示相同，所以加上符号位0后得 x补=01010根据补码的编码方法，负数的补码的数值部分等于它的二进制位按位取反后在最低位上加1，符号位取反后为1，所以y补=10110,定点小数的补码编码,x= x0.x1xn

12、方法与定点整数的编码方式类似最高位x0作为符号位数值范围：-1 x 1 - 2-n例 设x=0.1010，y=-0.1010，则x补=0.1010，y补=1.0110,移码与补码的关系,编码与数值的关系,2.1.3 数据的存储与访问,数据类型整型数、单精度和双精度浮点数、字符型数据长度单字节、双字节、字、双字、四倍字字节存储顺序大数端(big Endian)和小数端(little Endian)。,数据的存储方式,对齐的方式非对齐的方式。,定点数的加减运算例子,例2-4 x=0.1010，y= -0.0011，用补码的加法求x+y。解：x补=0.1010，y补=1.1101x补 + y补 =

13、0.1010 + 1.1101 = 0.0111x+y = 0.0111例2-5 x = 0.1001，y = -0.0011，用补码的减法求x-y。解：x补=0.1001，y补=1.1101，-y补=0.0011x补 - y补 = x补 + -y补 = 0.1001 + 0.0011 = 0.1100 x-y = 0.1100,加减运算电路,cfb,cf,cf,数据溢出及其检测方法一符号位判断,0 1 1 0 1 0 0 1+ 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1,X0 =0， Y0 = 0， Z0 = 1，第二项为1，V = 1,有溢出。,方法二双符号位判断（变形

14、码）,Z0 Z1 = 01 =1，有溢出。,00 1 1 0 1 0 0 1+ 00 0 1 1 0 0 1 0 01 0 0 1 1 0 1 1,方法三判断符号位与最高数值位,0 1 1 0 1 0 0 1+ 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1,C0 C1 = 1 有溢出,避免数据的溢出的方法,增加数据的表示位数例如数据6在8位的计算机中表示为00000110，在16位计算机中表示为0000000000000110。例如用补码表示-2时在8位计算机中是1111 1110，在16位计算机中是1111 1111 1111 1110。符号扩展,数据溢出的概念与数据取模时

15、的丢弃,数据运算中最高位的进位被丢弃并不一定是溢出例如，两个负数的补码相加，设x= -0110，即-610；y= -0101，即-510。则x补=11010，y补=11011。x+y补=10101 (mod 25)，即-1110运算结果正确，没有发生溢出,习题,教材第66页第7题,2.1.5 定点数的乘除运算,二进制乘法,采用原码乘法,将符号位与数值位分开进行运算运算结果的数值部分是乘数和被乘数数值位的乘积运算结果的符号位是乘数和被乘数符号位的异或,44无符号阵列乘法电路,X4 Y4,Z8,进位保留乘法器,二进制除法,恢复余数法通过减法实现，不够减时再用加法恢复原来的部分余数。加减交替法除数每

16、一步运算所得的余数ri = 2ri-1 - y。当ri 0时，ri+1 = 2ri - y，上商1。如果ri0，上商0，并加y，然后左移一位，再做减y运算，得到ri+1，即ri+1 = 2(ri+y)-y = 2ri + y。,比较被除数（或部分余数）和除数大小的方法,实现加减交替法的电路,1001 101011111,1001 011001111,- 补码 +,1001 0110 0011,1001 101011111,- 补码 +,不够减：,够减：,2.2 浮点数的编码和运算,任意进制浮点数：,二进制浮点数的编码,规格化：为了在尾数中表示最多的有效数据位 为了数据表示的唯一性。机器零：全部

17、为0，特殊的数据编码,N = (-1)S 2E M,M 为数N的尾数E为数据N 的阶,二进制浮点数的规格化, M 1,12,要满足上式，必须使小数点后的第一位为1。,规格化的编码,原码数据位的最高位为1补码小数点前后两位互不相同。例如，尾数0.1010和1.0101是规格化的，而尾数0.0101和1.1010是非规格化的。基数为2的浮点数规格化后，其尾数的绝对值在1/2到1之间基数为R的浮点数规格化后，其尾数的绝对值在1/R到1之间。,1xxxxxx,特点,浮点数的表示范围,浮点数的溢出表现为阶码的溢出浮点数的上溢(overflow)数据太大，以至于大于阶码所能表示的数据浮点数的下溢(unde

18、rflow)数据太小，以至于小于阶码所能表示的数值时，,浮点数标准(IEEE754),三种格式：短实数、长实数、临时实数 （表2.1）规格化数：(-1)s1.f2e-127非规格化数：(-1)s0.f2e-126,IEEE754浮点数单精度格式,31 30 23 22 0,规格化数：0e255， V=(-1)S(2)e-127 1.f +0，-0：e=0且f=0，则V=(-1)S 0 DMRM(非规格化数）： e=0且f 0，则V= DMRM +，-正负无穷大： e=255且f=0，则V=(-1)S NaN（无定义数）： e=255且f 0，则V= NaN,IEEE754浮点数双精度格式,63

19、 62 52 51 0,规格化数：0e2047， V=(-1)S(2)e-1023 1.f +0，-0：e=0且f=0，则V=(-1)S 0 DMRM(非规格化数）： e=0且f 0，则V= DMRM +，-正负无穷大： e=2047且f=0，则V=(-1)S NaN（无定义数）： e=2047且f 0，则V= NaN,IEEE754浮点数的范围,例2-11 对数据12310作规格化浮点数的编码，假定1位符号位，基数为2，阶码5位，采用移码，尾数10位，采用补码。,解：先将数据表示成MRE的形式12310 = 1111011 = 0.111101100027分别对M和E按照题目要求进行编码，阶

20、码采用5位移码，尾数采用10位补码。7移=10000+00111 = 101110.1111011000补=0.1111011000将编码的结果按浮点数格式表示出来。因为符号位为0，所以浮点格式为：0 10111 1111011000,2.2.2 浮点数的运算浮点数加减法,五个基本步骤对阶尾数加减规格化（左规，右规）舍入（截去、0舍1入、冯诺依曼舍入）检查溢出,例2-9 两浮点数如下：x = 2010.1101，y = 211(-0.1010)。假设尾数在计算机中以补码表示，可存储4位尾数，2位保护位，阶码以原码表示，求x+y。,解：将x,y转换成浮点数据格式x浮 = 00 01, 00.11

21、01 y浮 = 00 11, 11.0110步骤1：对阶，阶差为11-01=10，即2，因此将x的尾数右移两位，得x浮 = 00 11, 00.001101步骤2：对尾数求和，得:x+y浮 = 00 11, 11.100101步骤3：由于符号位和第一位数相等，不是规格化数，向左规格化，得x+y浮 = 00 10, 11.001010步骤4：截去。x+y浮 = 00 10, 11.0010步骤5: 数据无溢出，因此结果为x+y = 210(-0.1110),浮点运算电路,浮点数乘除法,五个基本步骤阶码加减尾数乘除规格化舍入检查溢出,习题,教材第67页第12题第13题第14题,2.3 逻辑运算,按

22、位运算分别考虑每一位信息基本的逻辑运算逻辑与、逻辑或、逻辑非移位操作,逻辑运算的例子,x=10100001，y=10011011，则x OR y=10111011x AND y=10000001,移位运算,算术移位逻辑移位左移右移循环移位小循环大循环,例2-15 已知一个8位寄存器中的数据为11001011，求以下移位运算后寄存器的结果及标志位C的值。(1) 算术左移，(2) 算术右移，(3) 循环右移。,解：(1) 10010110，C=1。(2) 11100101，C=1。(3) 11100101，C=1。,算术逻辑运算单元,移位电路,定点运算器的例子,2.4 检错码和纠错码,错误(err

23、or)-导致系统故障的因素故障(fault)-系统紊乱现场失效(failure)-丧失了规定的功能,数据、生成、处理、存储和传送中出错原因：,提高系统可靠性： 出错检测-检错码（发现错） 出错纠正-纠错码（发现并纠正错）,2.4.1 检错码,奇偶校验码在数据信息中增加1位冗余位使信息码中1的个数为奇或偶的编码方法。奇校验：信息码中1的个数为奇偶校验：信息码中1的个数为偶特点：简单，能发现错但不能发现错次数，能 改 善一个数量级的误码率。,奇偶校验位的产生,奇校验位：P = a0a1 an偶校验位：P = a0a1 an,例：求10011010的奇校验码10011010P=100110101,码

24、距：两个合法代码对应位上编码不同的位数例：偶校验000 0000 100 1001001 0011 101 1010010 0101 110 1100 011 0110 111 1111,000100001 101010 110011 111,奇偶校验码的原理,在编码中引入一定的冗余，增加代码的最小码距，使得编码中出现一个错误时就成为非法代码。,2.4.2 纠错码,海明码(Hamming Code) 多重奇偶检错 k位奇偶校验位，n位数据位，n+k位新数据位满足关系式： 2k-1n+k,n：最大信息位数,海明码产生（插入法）,海明码位h: 二进制码 h=h3h2h1h0 表示1-15，即000

25、1-1111。校验位P插入2的幂次位置 令所有h0=1的码字位奇偶校验得P1，所有h1、h2、h3为1的码字位奇偶校验得P2、P4、P8。,例:用插入法产生01110011010的确海明码,用偶校验.,P1= d15 d13 d11 d9 d7 d5 d3 P2= d15 d14 d11 d10 d7 d6 d3 P4= d15 d14 d13 d12 d7 d6 d5 P8= d15 d14 d13 d12 d11 d10 d9海明码为:011100101011000,海明码纠错,对海明码复合码字运算得到检查码,由检查码检验结果,如出错指出位置。,检查码C=C3C2C1C0C0=d15d13

26、d11d9d7d5d3P1 C1=d15d14d11d10d7d6d3P2 C2=d15d14d13d12d7d6d5P4 C3=d15d14d13d12d11d10d9P8若C=0000,则未出错;若出错指出出错位置。例:d6出错,C1=0,C2=0;C=0110,指出了d6位置;对D6位求反纠错该位。,传统海明码能检测并纠正一位错,发现两位错;扩展海明码能监测多位错纠正一位错。,线性码：任意两个合法码字求和可得到另一个合法码字。海明码：（n, k）码长n=2m - 1信息位数k=2m - m - 1校验位数m= n - k最小码距d = 3,海明码产生其他方法）,(7,4)海明码的例子,c

27、1 = x1 + x2 + x3c2 = x2 + x3 + x4c3 = x1 + x2 + x4将这些信息位和校验位构成码字w，即w = x1,x2,x3,x4,c1,c2,c3=w1,w2,w3,w4,w5,w6,w7。校验方程：w1 + w2 + w3 + w5 = 0 w2 + w3 + w4 +w6 = 0w1 + w2 + w4 + w7 = 0,(7,4)海明码的例子(续),(7,4)海明码的例子(续),理论证明： 可检测出所有奇数个错可检测出单bit、双bit错可检测出小于、等于检测检测位长度的突发错,循环冗余校验码(CRC),模2运算模2加减：00=0，11=0， 10=1

28、，01=1,模2乘： 模2 除：,1 0 1 0 1 0 1 1 0 1 0 0 0 0 01 0 1 01 0 0 0 1 0,1 0 1 1 0 0 0 01 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1,1 0 1,X=2 的信息多项式 M(x),M(x) = x6+x3+x2+1 = 1001101,原理：,M(x)xr = Q(x)G(x) + R(x),M(x)：x=2的m-1次多项式 G(x)：r+1位生成多项式R(x)： r位余数,CRC校验位,CRC编码:M(x)xr + R(x),M(x)xr + R(x)= Q(x)G(x) + R(x)+R(x) =Q

29、(x)R(x),R0,+,+,CRC编码电路：移位寄存器中插进异或门,M(x),R(x),g1,G(x)=xr+ gr-1xr-1+ + g2x2+g1x1+1,1 （多项式系数）,R1,+,+,+,g2,gr-1,Rr-1,信息输入：由高位到低位串行输入。,Kr,Km,K,R,T(x),R0,R1,R2,+,+,CRC编码电路：移位寄存器中插进异或门,M(x),R(x),1,1,0,G(x)=x3+x+1的CRC编码电路,1 （多项式系数）,信息输入：由高位到低位串行输入。,R2 R1 R0 M(X)0 0 0 0 1 1 11 1 0 01 0 0 10 0 0 1,M(x) =x3+x+

30、1时R(x)=0,R0,+,+,CRC的译码与纠错(CRC译码电路),R(x),g1,G(x)=xr+ gr-1xr-1+ + g2x2+g1x1+1,1 （多项式系数）,R1,+,+,+,g2,gr-1,Rr-1,R,T (x),1, ,E,E=0 正确E=1 不正确,利用出错模式进行纠错：每一种生成多项式都有其出错模式。,R0,+,+,CRC的译码与纠错,R(x),g1,G(x)=xr+ gr-1xr-1+ + g2x2+g1x1+1,1 （多项式系数）,R1,+,+,+,g2,gr-1,Rr-1,R,T (x),3：8译码器, ,+ + + +,000 101 111 110 011,D

31、1 D2 D3 D4,0 正确1 出错,习题,教材第67页第21题,2.5 数据类型实例Intel奔腾处理器,1. 通用数据类型(general)。8位、16位、32位和64位。2. 整型(integer)。带符号的一个字节、字、或者双字数据，补码编码。3. 序数类型(ordinals)。字节、字和双字三种长度。4. 二十进制型。BCD型：用一个字节表示一个0到9之间的数据位，数据的高4位为0000紧缩BCD型：4位的无符号数，其有效值在0到9之间。5. 指针(pointer)。表示存储器位置的地址。近指针：32位的地址远指针：48位的地址。6. 位段(bit field)。最长32位。7. 串(string)。一连串的位、字节、字或者双字。8. 浮点数。采用IEEE754标准格式。,多媒体数据类型,1. 包装字节。八个字节数据包装成一个64位数据。2. 包装字。四个16位的数据包装成一个64位数据。3. 包装双字。两个32位数据包装成一个64位数据。4. 四倍字。一个64位的数据。,