第3章 数据表示与运算算法和逻辑电路实现(1).ppt

《第3章 数据表示与运算算法和逻辑电路实现(1).ppt》由会员分享，可在线阅读，更多相关《第3章 数据表示与运算算法和逻辑电路实现(1).ppt（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第3 3章章数据表示、数据运算算法和逻辑电路实现本章主要内容本章主要内容3.3 二进制数值数据的编码与运算算法二进制数值数据的编码与运算算法3.1 信息编码、码制转换与检错纠错码信息编码、码制转换与检错纠错码3.2 数据表示数据表示常用的信息编码常用的信息编码+0.1011+1100 1100 0.1011带符号的数带符号的数 符号数字化的数符号数字化的数真值真值 机器数机器数 0 1011 1 1011 0 1100 1 1100小小数数点点的的位位置置数据的实际值被称为数据的实际值被称为真值真值。数据在机器内要用规定的编码来表示，这种表示被数据在机器内要用规定的编码来表示，这种表示被称为

2、称为机器数机器数。机器数与真值机器数与真值定点小数原码定点小数原码定义：定义：X 原原=实例：实例：X1=0.10110 -0.10110 0.0000 X 原原=010110 110110 00000 10000 X 1-X -1 X 0 0 X 1结论：原码为符号位加数的绝对值，结论：原码为符号位加数的绝对值，0正正 1负负 原码零有两个编码，原码零有两个编码，+0 和和-0编码不同编码不同 原码难以用于加减运算，但乘除方便原码难以用于加减运算，但乘除方便定点小数反码定点小数反码定义：定义：X 反反=实例：实例：X1=0.10110 -0.10110 0.0000 X 反反 =010110

3、 101001 00000 11111 X(2-2-n)+X -1 X 0 MOD(2-2-n)0 X 1结论：结论：反码反码负数为符号位跟每位的反负数为符号位跟每位的反,0 正正 1 负负 反码反码零有二个编码，分零有二个编码，分+0 和和-0 反码反码难以用于加减运算，有循环进位问题难以用于加减运算，有循环进位问题定点小数模定点小数模2补码补码定义：定义：X 补补=实例：实例：X1=0.10110 -0.10110 0.0000 X 补补=0 10110 1 01010 00000 X 2+X -1 X 0 MOD 2 0 X 1结论：结论：补码补码最高一位是符号位，最高一位是符号位，0

4、正正 1 负负 补码补码表示为：表示为：2*符号位符号位+数的真值数的真值 补码补码零只有一个编码，故能表示零只有一个编码，故能表示-1 补码补码能很好地用于加减（乘除）运算能很好地用于加减（乘除）运算补码与真值之间的关系补码与真值之间的关系由由X补补（X0 X1X2Xn）求真值）求真值 XX补补=2X0+X X=X补补-2X0 =X0 X1X2Xn-2X0 =-X0+(-X0+X0 X-1X-2X-n)=-X0+0.X1X2Xn即补码的负系数与数值部分相加，可以得到其真值即补码的负系数与数值部分相加，可以得到其真值即补码的负系数与数值部分相加，可以得到其真值即补码的负系数与数值部分相加，可以

5、得到其真值例：例：例：例：XX补补补补=1 0110=1 0110，则：，则：，则：，则：X X的真值的真值的真值的真值=-1+0.0110=-1+0.0110 =-(1-0.0110)=-(1-0.0110)=-0.1010 =-0.1010负数的负数的 X补补、X原原、X反反之间的关系之间的关系负数的负数的 X补补与与X反反的关系的关系 由于由于X反反=(2 2-n)+X，X补补=2+X可得到：可得到：X补补 =X反反+2-n由上述关系，得求负数的补码的简便方法由上述关系，得求负数的补码的简便方法X补补的符号位取的符号位取 1，将，将X的各数值位取反，再在的各数值位取反，再在最低位加最低位

6、加1。负数的负数的X原原与与X补补的相互转换简便方法的相互转换简便方法 由由X原原求求X补补以及由以及由X补补求求 X原原，均是符号位，均是符号位不变，各数值位变反后再在最低位加不变，各数值位变反后再在最低位加 1 y补补=0 y1 y2 yny=0.y1 y2 yny=0.y1 y2 yn y补补=1 y1 y2 yn+2-n y补补=1 y1 y2 yn y原原=1 y1 y2 yn+2-n y=（0.y1 y2 yn+2-n）y=0.y1 y2 yn+2-n y补补=0 y1 y2 yn+2-n每位取反，每位取反，即得即得 y补补y补补连同符号位在内，连同符号位在内，末位加末位加 1每位

7、取反，每位取反，即得即得 y补补y补补连同符号位在内，连同符号位在内，末位加末位加 1已知已知 y补补如何简单求如何简单求-y补补整数的编码表示整数的编码表示整数的整数的 原码原码 反码反码 补码补码 表示表示与小数的三种表示基本相同，小数点在最低数值位的与小数的三种表示基本相同，小数点在最低数值位的右侧右侧 N =Ns NnNn-1 NN =Ns NnNn-1 N2N N1 1因此整数的取值范围与整数因此整数的取值范围与整数位数位数有关。有关。(定点小数的取值范围与位数无关，精度与位数有关定点小数的取值范围与位数无关，精度与位数有关)例如：整数六位编码例如：整数六位编码 X=+01110 X

8、原原=0 01110 X补补=0 01110 X=-01110 X原原=1 01110 X补补=1 10010原原 反反 补码表示小结补码表示小结正数的正数的 原码、反码、补码原码、反码、补码表示均相同表示均相同，符号位为符号位为 0，数值位同数的真值。，数值位同数的真值。零的零的原码和反码均有原码和反码均有 2个编码，补码只个编码，补码只 1个码个码负数的负数的原码，反码，补码表示均不同，原码，反码，补码表示均不同，符号位为符号位为 1，数值位：原码为数的绝对值，数值位：原码为数的绝对值 反码为每一位均取反码反码为每一位均取反码 补码为反码再在最低位补码为反码再在最低位+1由由X补补求求-X

9、补补：每一位取反后：每一位取反后,再在最低位再在最低位+1 n由由 X补补 求求 X 的真值：的真值：X=-X0+Xi*2-ii=1补码加减法的实现补码加减法的实现X Y补补=X补补 Y补补X-Y 补补 =X补补 +-Y补补-Y补补=对对 Y补补逐位取反，再在最低位加逐位取反，再在最低位加 1溢出判断：溢出判断：(1)正正+正正 得得负负 或或 负负+负负 得得正正(2)数字位有向符号位的进位，但符号位不产生向更高数字位有向符号位的进位，但符号位不产生向更高位的进位位的进位(3)双符号位的值为双符号位的值为 01 或或 10补码加减法运算实例补码加减法运算实例X=0.1011 y=-0.010

10、1 模模 4 补码补码X补补=00 1011,Y补补=11 1011 -Y补补=00 0101 00 1011 00 1011+11 1011 +00 0101100 0110 01 0000X+Y X-Y(溢出溢出)下列下列 X补补+Y补补的情况：的情况：0 1011 1 0101 1 0100 +0 1000 +1 1000 +1 1001 1 0011 10 1101 10 1101 1 0111 00 1011 11 0111+1 0101 +00 1000 +11 010110 1100 01 0011 110 1100以上都是溢出的情况以上都是溢出的情况补码加减法运算实例补码加减法

11、运算实例双符号双符号F X实现补码加减运算的逻辑电路实现补码加减运算的逻辑电路Fs F ALU 目的目的 寄存器寄存器源源 寄存器寄存器 选通门选通门二选通门二选通门选通门选通门F 1XYF YX F010 1F /YFsOVRZC累加器累加器X X+YX X-Y加加减减溢出判断电路溢出判断电路单符号位判断：单符号位判断：正加正得负或负加负得正表明溢出正加正得负或负加负得正表明溢出补码表示中的符号位扩展补码表示中的符号位扩展由由 X补补 求求 X/2补补 的方法的方法 原符号位不变，原符号位不变，且符号位与数值位均右移一位，例如，且符号位与数值位均右移一位，例如，X补补=10010 则则 X/

12、2补补=110010 不同位数的整数补码相加减时，不同位数的整数补码相加减时，位数少的补码数的符号位向左扩展，位数少的补码数的符号位向左扩展，一直扩展到与另一数的符号位对齐。一直扩展到与另一数的符号位对齐。0101010111000011 0101010111000011+1111111110011100 +0000000000011100 0101010101011111 0101010111011111原码一位乘法原码一位乘法 例如：例如：X=0.1101 Y=-0.1011 0.1 1 0 1 问题：问题：*0.1 0 1 1 1.加法器只有两个数据输入端加法器只有两个数据输入端 1 1

13、 0 1 2.加法器与乘运算数据位数相同加法器与乘运算数据位数相同 1 1 0 1 解决方案：解决方案：0 0 0 0 1.每次求出部分积，而不是一次总累加每次求出部分积，而不是一次总累加 +1 1 0 1 变每次左移被乘数为右移部分积变每次左移被乘数为右移部分积 0.1 0 0 0 1 1 1 1 2.判乘数每一位的值用固定的一位线路判乘数每一位的值用固定的一位线路 手工运算过程手工运算过程 例如：例如：X=0.1 1 0 1 Y=-0.1 0 1 1 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 10.1 0 0 0 1 1 1 1

14、 手工运算过程手工运算过程 原码一位乘运算原码一位乘运算 累加器初值取零值累加器初值取零值+初值加被乘数初值加被乘数 部分积右移部分积右移+前次部分积加被乘数前次部分积加被乘数 部分积右移部分积右移+前次部分积加前次部分积加+部分积右移部分积右移前次部分积加前次部分积加 部分积右移部分积右移最后两数符号异或求积的最后两数符号异或求积的符号：符号：X*Y=-0.10001111实现原码一位乘法的逻辑线路图实现原码一位乘法的逻辑线路图 加加 法法 器器 部部 分分 积积 被被 乘乘 数数 乘乘 数数 F最低位最低位加运算加运算移位线路移位线路每位每位1套套 第第 i 位位第第 i 位位第第 i+1

15、位位第第 i-1位位F/2X FX F*2X移位电路移位电路把乘数放在一把乘数放在一个移位寄存器个移位寄存器中，该寄存起中，该寄存起又用来接受加又用来接受加法器的移位输法器的移位输出，则判乘数出，则判乘数的某一位也更的某一位也更方便方便原码一位乘法原码一位乘法0 0 0 0 0 0 1 0 1 1 加加 法法 器器 部部 分分 积积 被被 乘乘 数数 乘乘 数数 F最低位最低位加运算加运算移位线路移位线路每位每位1套套0 0 0 0 0 00 0 1 1 0 1 1 0 1 10 0 1 1 0 10 0 1 1 0 10 0 0 1 1 0 1 1 0 1 1 0 1 10 1 0 0 1

16、10 1 0 0 1 11 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 低位积低位积 原码一位乘运算原码一位乘运算X*Y原原 =(X Y)(|X|*|Y|)例如：例如：X=0.1101 Y=-0.1011 0.1 1 0 1

17、 00 0 0 0 0 1 0 1 1 *0.1 0 1 1 00 0 1 1 0 1 1 0 1 1 1 0 1 00 1 0 0 1 1 1 1 0 1 1 0 1 00 0 1 0 0 1 1 1 1 0 0 0 0 00 1 0 0 0 1 1 1 1 +1 1 0 1 X 和和 Y 符号异或为负符号异或为负 0.1 0 0 0 1 1 1 1 最终乘积原码表示为：最终乘积原码表示为：1 1 0 0 0 1 1 1 1 手工运算过程手工运算过程 计算机内运算的实现方法计算机内运算的实现方法部分积部分积 乘数乘数已知：已知：X=0.1001，Y=0.1101，计算计算X*Y。原码一位乘运

18、算例原码一位乘运算例2部分积部分积乘数乘数X 右移一位右移一位 0 右移一位右移一位 X 右移一位右移一位 X 右移一位右移一位 乘积高位乘积高位乘积低位乘积低位 XY=.除法运算除法运算 在计算机内实现除运算时，存在与乘法运算类似的几在计算机内实现除运算时，存在与乘法运算类似的几个问题：个问题：加法器与寄存器的配合，加法器与寄存器的配合，被除数位数更长，商要一位一位地计算出来等。这可以被除数位数更长，商要一位一位地计算出来等。这可以用左移余数得到解决，且被除数的低位部分可以与最终的用左移余数得到解决，且被除数的低位部分可以与最终的商合用同一个寄存器，余数与上商同时左移。商合用同一个寄存器，余

19、数与上商同时左移。原码一位除运算 Y/X 原原 =(X Y)(|Y|/|X|)原码一位除是指用原码表示的数相除，求出原码表示的原码一位除是指用原码表示的数相除，求出原码表示的商。除操作的过程中，每次求出一位商。商。除操作的过程中，每次求出一位商。恢复余数除法：确定上商应为还是为时，用被除数恢复余数除法：确定上商应为还是为时，用被除数或中间余数减去除数，若求出一个为负的余数来，通常应首或中间余数减去除数，若求出一个为负的余数来，通常应首先恢复其值为正，再求下一位商。先恢复其值为正，再求下一位商。不恢复余数除法：但计算机内从来不用恢复余数除法，不恢复余数除法：但计算机内从来不用恢复余数除法，而是直

20、接用求得的负余数求下一位商。而是直接用求得的负余数求下一位商。可以吗？可以吗？为什么？为什么？加减交替除法原理证明1.若第若第 i-1次求商余数为次求商余数为+Ri-1，则商，则商1，余数左移，余数左移得得 2Ri-1。2.则第则第 i 次求商次求商 Ri =2Ri-1 -Y3.则第则第 i+1次求商次求商 Ri+1 =2(Ri +Y)-Y =2Ri+1 +Y 实质是实质是:对上次负差直接左移对上次负差直接左移,本次用本次用+Y 求商即可求商即可。若若 Ri 0 则则若若 Ri 0 商商 0恢复余数为正且左移得恢复余数为正且左移得 2(Ri +Y)0 0 1 0 1 11 1 0 0 1 11

21、 1 1 1 1 01 1 1 1 0 00 0 1 1 0 10 0 1 0 0 10 1 0 0 101 1 0 0 1 10 0 0 1 0 10 0 1 0 1 01 1 0 0 1 11 1 1 1 0 11 1 1 0 1 00 0 1 1 010 0 0 1 1 10 0 0 0 0 开始情形开始情形 -Y0 0 0 0 0 0,商商10 0 0 1 0 左移左移1位位 -Y0 0 0 1 1 0,商商10 0 1 1 0 左移左移1位位 -Y0 0 1 1 0 0,商商1被除数被除数(余数余数)商商+)+)+)+)+)X=0.1011Y=0.1101X/Y=?Y补补=00 11

22、01-Y补补=11 0011原码一位除运算原码一位除运算原码一位除运算例如：例如：X=-0.1101 Y=0.1011 0.1101 00 1011 00000初态初态 0.1101 0.1011011 1100 00000第次第次 110101 0010 00010第次第次 1001000 1010 00110第次第次 110111 1010 01100第次第次1010000 0111 01101第次第次 1101 0111X 和和 Y 符号异或为负符号异或为负 最终商原码表示为：最终商原码表示为：1 1101 余数为：余数为：0.0111*2-4 F 加法器加法器A 被除数被除数(余数余数

23、)B 除数除数 1 0与或门与或门与或门与或门2FAFABF/BF 1FC 乘商寄存器乘商寄存器上商上商与或门与或门2CC计数器计数器 Cd实现原码一位除法运算的原理逻辑图将下列将下列将下列将下列1010进制数转换进制数转换进制数转换进制数转换成成成成8 8位二进制补码位二进制补码位二进制补码位二进制补码X1=127X1=127X2=-127X2=-127X3=-3X3=-3X4=17X4=17X5=-19X5=-19将下列将下列将下列将下列8 8位二进制补码转位二进制补码转位二进制补码转位二进制补码转换成换成换成换成1010进制数进制数进制数进制数Y1=1 1111111 Y1=1 1111

24、111 Y2=1 0000001Y2=1 0000001Y3=0 0111111Y3=0 0111111数据转换练习数据转换练习(1)(1)已知：已知：已知：已知：X=-0.1011,Y=0.0110X=-0.1011,Y=0.0110 计算计算计算计算X+YX+Y，并转换为真值并转换为真值并转换为真值并转换为真值解：解：解：解：X+Y=1 0101+0 0110=1 1011 X+Y=1 0101+0 0110=1 1011 真值：真值：真值：真值：-0.0101-0.0101补码计算练习补码计算练习(2)(2)教材教材教材教材P97P97，第，第，第，第1010题题题题(1)(1)、第、第、第、第1111题、第题、第题、第题、第1212题题题题