数据表示与数据运算算法和逻辑电路实现解析ppt课件

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,cai,第三章 数据表示、数据运算算法和逻辑电路实现,计算机组成与结构,3-1,数字化信息编码,3-2,数据表示,3-3,二进制数值数据的编码与运算算法,主要内容,2,一、数字化信息编码的概念,3-1,数字化信息编码,数值、文字、符号、语音、图形、图像等统称数据，在计算机内部，都必须用,数字化编码,的形式被,存储,、,加工,和,传送,数字化编码二要素,:,少量、简单的,基本符号,一定的,组合规则,用以表示大量复杂多样的信息,3,在计算机中，编码广泛使用的是,二进制码,特点：,只使用两个基本符号：,、,符号个数最少，物理上容易实现,与二值逻辑的,真、假,两个值对应简单，易于逻辑,操作与逻辑判断,用二进制码表示数值数据运算规则简单，容易用数,字电路实现，提高运行速度,3-1,数字化信息编码,4,3-1,数字化信息编码,二、二进制编码和码制转换,1.,进位计数制,数制的两大要素：,基数,R,：,指在这种进位制中允许使用的基本数码个数。,基数为,R,的数制称为,R,进制数,。,R,进制数的主要特点就是,逢,R,进,1,。,权,Wi,：,权也称位权，指某一位,i,上的数码的权重值，即权与数码所处的位置,i,有关。,W,i,R,i,。,假设任意数值,N,用,R,进制数来表示，形式为：,N=,（,D,m,1,D,m-2,D,0,D,-1,D,-2,D,-k,）,R,其中，,D,i,为该进制的基本符号，,D,i,0,，,R-1,，,i = -k,，,-k+1,，,，,m-1,，,m,；,小数点在,D,0,和,D,-1,之间。,5,3-1,数字化信息编码,则数值,N,的实际值为：,【,例,】 R,10,，,即十进制数。它的每一位上的数码,D,i,只能取,0,，,1,，,2,，,9,；各个数码的,权为,10,i,，,i,指示数码所处的位置，个位,i,0,，,十位,i,1,，,百位,i,2,，,依此类推。,思考：二进制、八进制、十六进制？,6,3-1,数字化信息编码,【,例,】,（,2345.459,）,10,210,3,310,2,410,1,510,0,410,-1,510,-2,910,-3,【,例,】,（,11011.011,）,2,12,4,12,3,02,2,12,1,12,-0,02,-1,12,-2,12,-3,=,（,27.375,）,10,【,例,】,（,123.67,）,8,18,2,28,1,38,0,68,-1,78,-2,=,（,83.859375,）,10,7,3-1,数字化信息编码,2.,数制转换,常用的几种数制的对应关系,十进制,二进制,八进制,十六进制,十进制,二进制,八进制,十六,进制,0,0000,0,0,8,1000,10,8,1,0001,1,1,9,1001,11,9,2,0010,2,2,10,1010,12,A,3,0011,3,3,11,1011,13,B,4,0100,4,4,12,1100,14,C,5,0101,5,5,13,1101,15,D,6,0110,6,6,14,1110,16,E,7,0111,7,7,15,1111,17,F,16,10000,20,10,8,二、八、十六进制转换为十进制,3-1,数字化信息编码,转换方法：加权求和。,【,例,】,（,5AC.E6,）,16,= 516,2,1016,1,1216,0,1416,1,616,2,（,1452.8984375,）,10,十进制（,Decimal,）、,二进制（,Binary,）、,八进制（,Octal,）、,十六进制（,Hexdecimal,）,数分别用,D,、,B,、,Q,、,H,来标志。,【,例,】,（,1011,）,2,（,1011,）,B,1011B1011b,【,例,】,（,123.45,）,2,（,123.45,）,D, 123.45D 123.45,【,例,】,（,2B.D,）,16,=,（,2B.D,）,H,=,（,43.8125,）,10,=(53.64),Q,9,十进制转换为二、八、十六进制,直接转换：十进制二、八、十六进制,整数部分：,除以,R,取余，先得低位,，直到商为,0,。,小数部分：,乘,R,取整，先得高位,，直到积为,0,或者达到精度要求为止。,间接转换：十进制二进制 八、十六进制,3-1,数字化信息编码,10,3-1,数字化信息编码,【,例,】,十进制转二进制,2,1 1,2,2,2,5,2,1,0,1,1,0,1,0.625 * 2,1,0.25 * 2,0,0.5 * 2,1,0.0,除尽为止,求得位数满足要求为止,低,高,高,低,11,3-1,数字化信息编码,当小数部分不能整除为二进制时，则乘以,2,取整的过程中，积不会为,0,；或者当小数部分转化为二进制位数很长，这时由精度来决定二进制位数。,【,例,】,（,0.35,）,10,（ ？ ）,2,（,0.671875,）,10,（ ？ ）,2,位数太长,若要求精度小于,10,，则表示“”左右两边的十进制值的差的绝对值,10,。,则我们只需取,4,位二进制小数即可满足要求，因为,2,4,2,时，校验码才具有检错能力，当码距,d,3,时，校验码才具有纠错能力。,3-1,数字化信息编码,19,3-1,数字化信息编码,常用的检错纠错码：,奇偶校验码：,码距,d=2,，检错码，,能检验奇数位错误,；通常用于磁带或者串行通信中。,海明校验码：,码距,d=3,，纠错码，,能纠正,1,位或多位错误,；通常用于磁盘冗余阵列中。,循环冗余（,CRC,）校验码：,码距,d=3,，纠错码，,能纠正,1,位错误,；通常用于磁盘或数据块的校验。,20,3-1,数字化信息编码,奇偶校验码,原理：在,k,位有效信息位之外增加,1,位校验，使,K+1,位码字中,1,的个数,总保持为 偶数（偶校验）或 奇数（奇校验）。,【,例,】,数据 奇校验编码 偶校验编码,00000000,1,00000000,0,00000000,01010100,0,01010100,1,01010100,01111111,0,01111111,1,01111111,奇（偶）校验码的编码和译码在硬件上通常采用异或非门（异或门）实现。,21,3-1,数字化信息编码,【,例,】,假设在发送端，要发送七位,ASCII,码（,D6 D5 D4 D3 D2 D1 D0,），在,ASCII,码前面添加一位奇偶校验位,P,变为一个奇偶校验的编码。,+,+,+,+,+,+,+,编码电路,0 D6 D5 D4 D3 D2 D1 D0,p,偶校验,奇校验,1,编码生成表达式和电路（发送方）,22,3-1,数字化信息编码,译码电路（接收方）,+,+,+,+,+,+,+,0 D6 D5 D4 D3 D2 D1 D0,+,P (,校验位,),出错指示：,0,正确,1,错误,23,3-1,数字化信息编码,海明校验码,1.,计算校验位的位数,假设有效信息位为,k,位，增加,r,位校验位，构成,n=,k+r,位海明码字。若要求海明码能纠正一位错误，用,r,位校验位产生的,2,r,个状态表明有无出错及错误位置，则要求,r,满足：,2,r, k + r + 1,如果要求能纠正一位错误，并能同时发现两位错误，则应满足,2,r, k + r + 2,（,2,r-1, k + r,）,24,3-1,数字化信息编码,2.,编码,以,8,位有效数据（,D7D6D5D4D3D2D1D0,）为例，需要校验位,4,位（,P4P3P2P1,），形成,12,位海明码：,H12 H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1,（,1,）确定,D,与,P,在海明码中的位置,H12,H11,H10,H9,H8,H7,H6,H5,H4,H3,H2,H1,D7,D6,D5,D4,P4,D3,D2,D1,P3,D0,P2,P1,其中：,Pi=,Hj,j=2,i-1,25,3-1,数字化信息编码,（,2,）确定校验关系,海明码,海明码下标,检验位组,表达式（偶校验）,H1,（,P1,）,1=0001B,P1,P1=,D6D4D3D1,D0,P2=D6D5D3D2D0,P3=D7D3D2D1,P4=D7D6D5D4,H2,（,P2,）,2=0010B,P2,H3,（,D0,）,3=2+1=0011B,P2,、,P1,H4,（,P3,）,4=0100B,P3,H5,（,D1,）,5=4+1=0101B,P3,、,P1,H6,（,D2,）,6=4+2=0110B,P3,、,P2,H7,（,D3,）,7=4+2+1=0111B,P3,、,P2,、,P1,H8,（,P4,）,8=1000B,P4,H9,（,D4,）,9=8+1=1001B,P4,、,P1,H10,（,D5,）,10=8+2=1010B,P4,、,P2,H11,（,D6,）,11=8+2+1=1011B,P4,、,P2,、,P1,H12,（,D7,）,12=8+4=1100B,P4,、,P3,26,3-1,数字化信息编码,海明码,分组,H12,H11,H10,H9,H8,H7,H6,H5,H4,H3,H2,H1,D7,D6,D5,D4,P4,D3,D2,D1,P3,D0,P2,P1,P4 (8),P3 (4),P2 (2),P1 (1),说明：若,D i=,Hj,，则,Di,参加那些位号之和等于,j,的校验位的分组校验。,P4=D7D6D5D4,P3=D7D3D2D1,P2=D6D5D3D2D0,P1=,D6D4D3D1,D0,27,3-1,数字化信息编码,【,例,】,有效信息为：,1101 0110 B,，则海明码是,？,P4=D7D6D5D4=1,P3=D7D3D2D1=1,P2=D6D5D3D2D0=0,P1=,D6D4D3D1,D0=1,海明码是：,1 1 0 1,1,0 1 1,1,0,0 1,B,28,3-1,数字化信息编码,3.,检错,监督表达式,:,S4=P4D7D6D5D4,S3=P3D7D3D2D1,S2=P2D6D5D3D2D0,S1=P1,D6D4D3D1,D0,若,S4S3S2S1=0000,，则信息正确。否则，表示,Hi,位出错,i=S4S3S2S1,的十进制数值。,【,例,】,上例的海明码是：,1 1 0 1,1,0 1 1,1,0,0 1,B,，若收到,1 1 0 0,1,0 1 1,1,0,0 1,B,，代入监督表达式得,S4S3S2S1=1001,，表示,H9,出错，将其取反即可。,29,3-2,数据表示,常用的信息编码,一、逻辑类型数据的表示,逻辑型数据只有两个值：,真,和,假,，,正好可以用二进制码的两个符号分别表示，,例如,1,表示 真,则,0,表示 假,不必使用另外的编码规则。,对逻辑型数据可以执行逻辑的 与、或、非等基本逻辑运算。,30,3-2,数据表示,常用的信息编码,二、字符类型数据的表示,低位,LSB,高位,MSB,0,000,1,001,2,010,3,011,4,100,5,101,6,110,7,111,0,1,2,3,4,5,0000,0001,0010,0011,0100,0101,NUL,SOH,STX,ETX,EOT,ENQ,DLE,DC1,DC2,DC3,DC4,NAK,SP,！,#,$,%,0,1,2,3,4,5,A,B,C,D,E,P,Q,R,S,T,U,、,a,b,c,d,e,p,q,r,s,t,u,6,7,8,9,A,0110,0111,1000,1001,1010,ACK,BEL,BS,HT,LF,SYN,ETB,CAN,EM,SUB,&,(,),*,6,7,8,9,：,F,G,H,I,J,V,W,X,Y,Z,f,g,h,i,j,v,w,x,y,z,B,C,D,E,F,1011,1100,1101,1110,1111,VT,FF,CR,SO,SI,ESC,FS,GS,RS,US,+,-,/,;,?,K,L,M,N,O,k,l,m,n,o,|,DEL,1. ASCII,码,31,3-2,数据表示,常用的信息编码,2.,字符串,由字符的,ASCII,码或者文字的,Unicode,编码组成，按顺序存放在内存或寄存器中。每个,ASCII,码字符占,1,个字节，每个,Unicode,编码占用,2,个字节。,32,3-2,数据表示,常用的信息编码,二、数值类型数据的表示,定点小数,:,N = N,s,N,-1,N,-2,N,-m,整 数,:,N = N,s,N,n,N,n-1,.N,1,N,0,浮 点 数,: N = M,s,E,s,E,m-1,.E,1,E,0,M,n,M,n-1,.M,0,符号位 阶码位 尾数数码位 总位数,短浮点数,: 1 8 23 32,长浮点数,: 1 11 52 64,临时浮点数,: 1 15 64 80,IEEE,标准： 阶码用移码，尾数用原码,基为,2,33,3-2,数据表示,常用的信息编码,十进制数编码,用四位二进制编码一位十进制数，,16,个编码状态选用其中的,10,个编码,有多种方案，例如：,8421,码，余,3,码，循环码,又可区分为：,有权码：每位上的,1,代表确定的值,无权码：无法确定每位上的,1,代表的值,34,3-2,数据表示,常用的信息编码,0,0000,0000,0011 0000,1,0001,0111,0100 0001,2,0010 0110,0101 0011,3,0011,0101,0110 0010,4,0100,0100,0111 0110,5,0101,1011,1000 1110,6,0110 1010,1001 1010,7,0111 1001,1010 1000,8,1000,1000,1011 1100,9,1001 1111,1100 0100,有权码,无权码,8421,余3码,格雷码,84-2-1,35,8421BCD,码的修正,调整规则：,当相加的两数之和,S9,时，加,6,修正；当,S9,时，且无进位时，结果正确，不需修正。,3-2,数据表示,常用的信息编码,电路,当,S,8,S,4,S,2,S,1,=1010-1111,时，两个与门至少有一个输出,1,；,有进位时，,C=1,；,以上两种情况都会加,6,修正,36,3-3,二进制数值数据的编码与运算算法,一、原码、反码、补码的定义,1.,定点小数,（,N,s,N,1,N,2,N,n,）,定义：, X ,原,=,X,1 - X,-1 X 0,0 X 1,【,例,】 X = 0.1011 -0.1011 +0.0000 -0.0000, X ,原,= 01011 11011 00000 10000,结论：原码为符号位加数的绝对值，,0,正,1,负,原码零有两个编码，,+0,和,-0,编码不同,原码难以用于加减运算，但乘除方便,原码,37,3-3,二进制数值数据的编码与运算算法,反码,定义：, X ,反,=,X,(2-2,-n,),+ X,-1 X 0 MOD,(2-2,-n,),0 X 1,【,例,】 X = 0.1011 -0.1011 +0.0000 -0.0000, X ,反,= 01011 10100 00000 11111,结论：反码负数为符号位跟每位的反, 0,正,1,负,反码零有二个编码，分,+0,和,-0,反码难以用于加减运算，有循环进位问题,反码实现算术运算不方便，故很少使用,38,3-3,二进制数值数据的编码与运算算法,补码,定义：, X ,补,=,X,2 + X,-1 X 0 MOD,2,0 X 1,【,例,】 X = 0.1011 -0.1011 + 0.0000 -0.0000, X ,补,= 01011 10101 00000,00000,结论：补码最高一位是符号位，,0,正,1,负,补码零只有一个编码，故能表示,-1,-1,补,=10000,补码能很好地用于加减（乘除）运算,39,3-3,二进制数值数据的编码与运算算法,2.,整数的编码方法,整数的原码、反码、补码 表示,与小数的三种表示基本相同，差别仅表现在小数点的位置，可以认为整数的小数点在最低数值位的右侧。,因此整数的模与整数位数有关。,【,例,】,整数六位编码：,X = +01110 X,原,= 0 01110 X,补,= 0 01110,X = - 01110 X,原,= 1 01110 X,补,= 1 10010,40,3-3,二进制数值数据的编码与运算算法,3.,原、反、补码表示小结,正数的 原码、反码、补码表示均相同，,符号位为,0,，数值位同数的真值。,零的原码和反码均有,2,个编码，补码只,1,个编码,负数的 原码，反码，补码表示均不同，,符号位为,1,数值位：原码为数的绝对值；反码为每一位均取反码；补码为反码再在最低位,+1,。,X,补,补,=X,原,41,3-3,二进制数值数据的编码与运算算法,二、补码加、减运算规则和电路实现,X + Y,补,= X,补,+ Y,补,X-Y,补,= X,补,+ -Y,补,-Y,补,=,对,Y,补,逐位取反,再在最低位加,1,（求补）,溢出判断：,正,+,正得负；负,+,负得正；正,-,负得负；负,-,正得正,数值位有向符号位的进位，但符号位不产生向更高位的进位；或数值位没有向符号位的进位，但符号位有向更高位的进位（,双进位判断、异或门实现,）,双符号位的值为,01,或,10,42,3-3,二进制数值数据的编码与运算算法,求补码,X,补,=01010 Y,补,=11011,-Y,补,=00101,0 1010,1 1011,0 0101,X,Y,补,=,0 0101,X+Y= + 0101,0 1010,0 0101,0 1111,X,Y,补,=,0 1111,X-Y=+1111,计算,【,例,】,已知,X=+1010,，,Y=-0101,，用补码计算,X+Y,和,X-Y,。,43,3-3,二进制数值数据的编码与运算算法,求补码,X,补,=01010 Y,补,=01001,0 1010,0 1001,1 0011,X,Y,补,=,1 0011,溢出，结果出错,（数值位有进位，符号位无进位）,计算,【,例,】,已知,X=+1010,，,Y=+1001,，用补码计算,X+Y,。,44,3-3,二进制数值数据的编码与运算算法,求补码,X,补,=,11,0110 Y,补,=,00,1001,-Y,补,=,11,0111,11,0110,00,1001,11,1111,X,Y,补,= 1,1 1111,符号位相同，结果正确,X+Y=- 0001,计算,【,例,】,已知,X=-1010,，,Y=+1001,，用补码计算,X+Y,和,X-Y,。,模,4,补码（双符号位）,11,0110,11,0111,10,1101,X,Y,补,= 1,0 1101,符号位不同，溢出,45,3-3,二进制数值数据的编码与运算算法,实现补码加减运算的逻辑电路,Fs F ALU,目的 寄存器,源 寄存器,选通门,二选通门,选通门,F 1,X,Y,F X,F Y,X F,0,1,0 1,F /Y,Fs,OVR,Z,C,累加器,X X+Y,X X-Y,加,减,【,例,】,实现,X+Y,X,或,X-Y,X,46,3-3,二进制数值数据的编码与运算算法,三、原码一位乘法的实现算法和电路实现,47,3-3,二进制数值数据的编码与运算算法,【,例,】,X = 0.1101,；,Y = - 0.1011,0. 1 1 0 1,* 0. 1 0 1 1,*,1 1 0 1,1 1 0 1,0 0 0 0,+ 1 1 0 1,*,0 . 1 0 0 0 1 1 1 1,手工运算过程,问题：,1.,加法器只有两个数据输入端,2.,加法器与乘运算数据位数相同,解决方案：,每次求出部分积，而不是一次总累加变每次左移被乘数为右移部分积，判乘数每一位的值用固定的一位线路。,48,3-3,二进制数值数据的编码与运算算法,49,3-3,二进制数值数据的编码与运算算法,50,3-3,二进制数值数据的编码与运算算法,51,3-3,二进制数值数据的编码与运算算法,52,3-3,二进制数值数据的编码与运算算法,准备,相乘,求符号,原码一位乘运算流程,变为绝对值,53,3-3,二进制数值数据的编码与运算算法,实现原码一位乘法的逻辑线路图,加 法 器,部 分 积,被 乘 数,乘 数,F,最低位,加运算,移位线路,每位,1,套,第,i,位,第,i,位,第,i +1,位,第,i -1,位,F/2,X,FX F*2X,移位电路,54,原码一位乘法,0 0 0 0 0 0,1 0 1 1,加 法 器,部 分 积,被 乘 数,乘 数,F,最低位,加运算,移位线路,每位,1,套,0 0 0 0 0 0,0 0 1 1 0 1,1 0 1 1,0 0 1 1 0 1,0 0 1 1 0 1,0 0 0 1 1 0,1,1 0 1,1 0 1 1,0 1 0 0 1 1,0 1 0 0 1 1,1 1 0 1,1 0,1 1,1 1,1 1,0 0 1 0 0 0,0 0 1 0 0 1,0 0 0 1 1 0,0 0 1 0 0 1,1 0,1 1,0 0 1 0 0 1,0 0 1 0 0 1,0 0 0 1 0 0,1 0,1 1,0 0 0 1 0 0,1 1,1 1,1,1 0 1,1 1 1,1,1 1 1,1,0 1 0 0 0 1,0 1 0 0 0 1,0 0 1 0 0 0,1 1,1 1,低位积,55,