计算机算法和算法逻辑实现-课件.ppt

1、第六-八讲计算机算法和算法逻辑实现计算机算法和算法逻辑实现 1 1、定点数加减法运算及电路实现、定点数加减法运算及电路实现补码的加减法运算，全加器，溢出，快速加法补码的加减法运算，全加器，溢出，快速加法运算（进位链），运算（进位链），74181ALU74181ALU2 2、定点数乘除运算和电路实现、定点数乘除运算和电路实现原码、补码，布斯算法，原码恢复余数、不恢原码、补码，布斯算法，原码恢复余数、不恢复余数复余数3 3、快速乘除法运算技术和电路实现、快速乘除法运算技术和电路实现布斯高基乘法，阵列乘法器，阵列除法器布斯高基乘法，阵列乘法器，阵列除法器4 4、浮点数四则运算以及实现、浮点数四则运算

2、以及实现加减乘除加减乘除掌握计算机算法。掌握计算机算法。加减乘除运算方法和运算器的构成，加减乘除运算方法和运算器的构成，原码和补码的加减乘除四则运算，原码和补码的加减乘除四则运算，浮点数的四则运算。浮点数的四则运算。补码加、减法补码加、减法溢出概念与检测方法溢出概念与检测方法基本的二进制加法基本的二进制加法/减法器减法器十进制加法器十进制加法器加法规则：加法规则：先判符号位，若相同，绝对值相加，结果符号不变先判符号位，若相同，绝对值相加，结果符号不变;若不若不同，则作减法，同，则作减法，|大大|-|-|小小|，结果符号与，结果符号与|大大|相同。相同。减法规则：减法规则：两个原码表示的数相减，

3、首先将减数符号取反，然后将被减两个原码表示的数相减，首先将减数符号取反，然后将被减数与符号取反后的减数按原码加法进行运算。数与符号取反后的减数按原码加法进行运算。补码加法补码加法1.1.原码加原码加/减法运算减法运算补码加法的公式补码加法的公式:x x 补补 y y 补补 x xy y 补补 (mod 2)(mod 2)在模在模2 2意义下意义下,任意两数的补码之和等于该两数之和的补码任意两数的补码之和等于该两数之和的补码。这是补码加法的理论基础。这是补码加法的理论基础。2.2.补码加法运算补码加法运算特点：特点：不需要事先判断符号，符号位与码值位一起参加运算。不需要事先判断符号，符号位与码值

4、位一起参加运算。符号位相加后若有进位，则舍去该进位数字。符号位相加后若有进位，则舍去该进位数字。假设采用定点小数表示假设采用定点小数表示,因此证明的先决条件是因此证明的先决条件是:x1,y1,xy1。(1)x0,y0,则则xy0。相加两数都是正数相加两数都是正数,故其和也一定是正数。正数的补码和原码故其和也一定是正数。正数的补码和原码是一样的是一样的,可得：可得：x 补补y 补补xyxy 补补(mod2)公式证明公式证明:(2)x0,y0,则则xy0或或xy0时时,2+(x+y)2,进位进位2必丢失必丢失,又因又因(x+y)0，故故x补补y补补xyxy补补(mod2)当当xy0时时,2(xy)

5、2,又因又因(x+y)0，故故x补补y补补2(xy)xy补补(mod2)(3)x0,则则xy0或或xy0。同同(2),把把x 和和y 的位置对调即可。的位置对调即可。(4)x0,y0,则则xy0。相加两数都是负数相加两数都是负数,则其和也一定是负数。则其和也一定是负数。x补补2x,y补补2yx补补y补补2x2y2(2xy)因为因为|xy|1,1(2xy)2,2(2xy)进位进位2必丢失，又因必丢失，又因x+y0故故x补补y补补2(xy)xy补补(mod2)至此证明了在模至此证明了在模2 2意义下，任意两数的补码之和等于该两数意义下，任意两数的补码之和等于该两数之和的补码。之和的补码。其结论也适

6、用于定点整数。其结论也适用于定点整数。补码加法的特点：补码加法的特点：（1 1）符号位要作为数的一部分一起参加运算；）符号位要作为数的一部分一起参加运算；（2 2）在模）在模2 2的意义下相加，即大于的意义下相加，即大于2 2的进位要丢掉。的进位要丢掉。结论：结论：例例:x0.1001,y0.0101,求求xy。解解:x补补0.1001,y补补0.0101x补补0.1001y补补0.0101xy 补补0.1110所以所以xy0.1110例例:x0.1011,y0.0101,求求xy。所以所以xy0.0110解解:x补补0.1011,y补补1.1011x补补0.1011y补补1.1011xy补补

7、10.0110补码减法补码减法减法运算要设法化为加法完成减法运算要设法化为加法完成 补码减法运算的公式：补码减法运算的公式：xy 补补x 补补y 补补x 补补y 补补公式证明：公式证明：只要证明只要证明y补补y补补,上式即得证。上式即得证。xy补补x补补y补补(mod2)令令y=x0补补x补补+x补补故故x补补x补补 (mod2)证明：证明：例例:x0.1101,y0.0110,求求xy。解解:x补补0.1101y补补0.0110,y补补1.1010 x补补0.1101y补补1.1010 xy补补10.0111xy0.0111解解：x补补=1.0011y补补=1.1010-y补补=0.0110

8、 x补补1.0011+-y补补0.0110 x-y补补1.1001例例：x=-0.1101，y=-0.0110，求，求x-y=?x-y=-0.0111 溢出及与检测方法溢出及与检测方法 在定点小数机器中在定点小数机器中,数的表示范围为数的表示范围为|1|1。在运算过程中。在运算过程中如出现大于如出现大于1 1的现象的现象,称为称为 “溢出溢出”。机器定点小数表示机器定点小数表示上溢上溢下溢下溢1.1.概念概念解解：x补补=0.1011y补补=0.1001x补补0.1011+y补补0.1001x+y补补1.0100两个正数相加的结果成为负数，这显然是错误的。两个正数相加的结果成为负数，这显然是错

9、误的。例例:x=+0.1011,y=+0.1001,求求x+y。例例:x=-0.1101,y=-0.1011,求求x+y。解解：x补补=1.0011y补补=1.0101x补补1.0011+y补补1.0101x+y补补0.1000两个负数相加的结果成为正数，这同样是错误的。两个负数相加的结果成为正数，这同样是错误的。发生错误的原因，是因为运算结果产生了溢出。发生错误的原因，是因为运算结果产生了溢出。两个正数相加两个正数相加:结果大于机器所能表示的最大正数，称为上溢；结果大于机器所能表示的最大正数，称为上溢；两个负数相加：结果小于机器所能表示的最小负数，称为下溢。两个负数相加：结果小于机器所能表示

10、的最小负数，称为下溢。机器定点小数表示机器定点小数表示上溢上溢下溢下溢 分析分析 ：2.2.溢出的检测方法溢出的检测方法x补补0.1011+y补补0.1001x+y补补1.0100 x补补1.0011+y补补1.0101x+y补补0.1000溢出逻辑表达式为：溢出逻辑表达式为：VS1S2Sc+S1S2Sc(1)单符号位法单符号位法F AVz0y0 x0判 断电 路判断电路判断电路一个符号位只能表示正、负两种情况，当产生溢出时，符号一个符号位只能表示正、负两种情况，当产生溢出时，符号位的含义就会发生混乱。如果将符号位扩充为两位位的含义就会发生混乱。如果将符号位扩充为两位(Sf1、Sf2)，其所能

11、表示的信息量将随之扩大，既能判别是否溢出，又能指其所能表示的信息量将随之扩大，既能判别是否溢出，又能指出结果的符号。出结果的符号。(2)双符号位法双符号位法双符号位法双符号位法也称为也称为“变形补码变形补码”或或“模模4补码补码”。变形补码定义：变形补码定义：x补补=x 0 x24+x -2 x0（mod4)任何小于任何小于1的正数：的正数：两个符号位都是两个符号位都是“0”，即，即00.x1x2.xn;任何大于任何大于-1的负数：两个符号位都是的负数：两个符号位都是“1”，即，即11.x1x2xn两数变形补码之和等于两数和的变形补码两数变形补码之和等于两数和的变形补码，要求：，要求：两个符号

12、位都看做数码一样参加运算；两个符号位都看做数码一样参加运算；两数进行以两数进行以4为模的加法，即最高符号位上产生的进位要丢掉为模的加法，即最高符号位上产生的进位要丢掉模模4补码加法公式：补码加法公式：x补补+y补补=x+y补补（mod4)采用变形补码后数的表示：采用变形补码后数的表示：Sf1Sf200结果为正数，无溢出结果为正数，无溢出01结果正溢结果正溢10结果负溢结果负溢11结果为负数，无溢出结果为负数，无溢出即：即：结果的两个符号位的代码不一致时，表示溢出结果的两个符号位的代码不一致时，表示溢出;两个符号位的代码一致时，表示没有溢出。两个符号位的代码一致时，表示没有溢出。不管溢出与否，最

13、高符号位永远表示结果的正确符号。不管溢出与否，最高符号位永远表示结果的正确符号。溢出逻辑表达式为：溢出逻辑表达式为：VSf1Sf2中中Sf1和和Sf2分别为最高符号位和第二符号位，此逻辑表达式分别为最高符号位和第二符号位，此逻辑表达式可用异或门实现。可用异或门实现。双符号位的含义如下：双符号位的含义如下：解解：x补补=00.1100y补补=00.1000 x补补00.1100+y补补00.100001.0100符号位出现符号位出现“01”，表示已溢出，正溢。即结果大于，表示已溢出，正溢。即结果大于+1例例x=+0.1100,y=+0.1000,求求x+y。解解：x补补=11.0100y补补=1

14、1.1000 x补补11.0100+y补补11.100010.1100符号位出现符号位出现“10”，表示已溢出，负溢出。即结果小于，表示已溢出，负溢出。即结果小于-1例例x=-0.1100,y=-0.1000,求求x+y。从上面例中看到：从上面例中看到：当最高有效位有进位而符号位无进位时当最高有效位有进位而符号位无进位时,产生上溢；产生上溢；当最高有效位无进位而符号位有进位时当最高有效位无进位而符号位有进位时,产生下溢。产生下溢。（简单地说是正数相加为负数或负数相加为正数则产生溢出）（简单地说是正数相加为负数或负数相加为正数则产生溢出）故溢出逻辑表达式为：故溢出逻辑表达式为：VCfCo 其中其

15、中Cf为符号位产生的进位为符号位产生的进位,Co为最高有效位产生的进位。为最高有效位产生的进位。此逻辑表达式也可用异或门实现。此逻辑表达式也可用异或门实现。(3)(3)利用进位值的判别法利用进位值的判别法x补补00.1100+y补补00.100001.1000 x补补11.0100+y补补11.100010.1100FAFAz1z0Vc1c0y1x1y0 x0FAFAVz1c0c1z0 x1y1y0 x0VC1Co VSf1Sf2判断电路判断电路基本的二进制加法基本的二进制加法/减法器减法器加法运算：加法运算：Ai+Bi+Ci=Si(Ci+1)加数加数进位输入进位输入和和进位输出进位输出一位全

16、加器真值表一位全加器真值表输入输入输出输出AiBiCiSiCi10000000110010100110110010101011100111111逻辑方程逻辑方程SiAi Bi CiCi1AiBiBiCiCiAi1.1.一位全加器一位全加器逻辑方程逻辑方程SiAi Bi CiCi1=AiBiBiCiCiAiCi=AiBi+(Ai Bi)Ci-1逻辑电路（一位全加器）逻辑电路（一位全加器）常用的全加器逻辑电路常用的全加器逻辑电路F AC i+1C iS iA iB i逻辑符号逻辑符号2.n2.n位的行波进位加减器位的行波进位加减器 n个个1位的全加器位的全加器(FA)可级联可级联成一个成一个n位的

17、行波进位加减器。位的行波进位加减器。T被定被定义为相应义为相应于单级逻于单级逻辑电路的辑电路的单位门延单位门延迟。迟。T通常通常采用一个采用一个“与非与非”门或一个门或一个“或非或非”门的时间门的时间延迟来作延迟来作为度量单为度量单位。位。3TXNOR异或非异或非3TXOT异或异或2TOR或或2TAND与与TNOT非非TNOR或非或非TNAND与非与非时间延迟时间延迟逻辑符号（正逻辑）逻辑符号（正逻辑）门的功能门的功能门的名称门的名称典型门电路的逻辑符号和延迟时间典型门电路的逻辑符号和延迟时间接线逻辑接线逻辑(与或非与或非)AOIT+TRC3.n3.n位的行波进位加法器的问题位的行波进位加法器

18、的问题时间延迟时间延迟(1)(1)对对一位全加器一位全加器(FA)来说来说，Si的时间延迟为的时间延迟为6T(每级每级 异或门延迟异或门延迟3T)；Ci1的时间延迟为的时间延迟为5T。3T3TTT(2)n位行波进位加法器位行波进位加法器的延迟时间的延迟时间ta为为:9T为为最低位上的两极最低位上的两极“异或异或”门再加上溢出门再加上溢出“异或异或”门的总时门的总时间；间；2T为每级进位链的延迟时间。为每级进位链的延迟时间。tan n2 2T T9 9T T(2(2n n9)9)T T考虑溢出检测时，有：考虑溢出检测时，有：当不考虑溢出检测时，有：当不考虑溢出检测时，有：ta(n-1)n-1)2

19、 2T T9 9T T ta ta为在加法器的输入端输入加数和被加数后为在加法器的输入端输入加数和被加数后,在最坏的情况在最坏的情况下加法器输出端得到稳定的求和输出所需要的最长时间。下加法器输出端得到稳定的求和输出所需要的最长时间。tata越小越好。越小越好。缺点缺点：(1)(1)串行进位串行进位,它的运算时间长；它的运算时间长；(2)(2)只能完成加法和减法两种操作而不能完成逻辑操作。只能完成加法和减法两种操作而不能完成逻辑操作。多功能算术多功能算术/逻辑运算单元逻辑运算单元(ALU):(ALU):不仅不仅具有多种算术运算和逻辑运算具有多种算术运算和逻辑运算的功能；的功能；而且具有而且具有先

20、行进位先行进位逻辑。逻辑。从而能实现高速运算。从而能实现高速运算。由一位全加器由一位全加器(FA)(FA)构成的行波进位加法器构成的行波进位加法器:1.1.基本思想基本思想SiAi Bi Ci一位全加器一位全加器(FA)(FA)的逻辑表达式为的逻辑表达式为:(1)(1)将将A Ai i和和B Bi i先组合成由控制参数先组合成由控制参数S S0 0,S,S1 1,S,S2 2,S,S3 3控制的组合函数控制的组合函数X Xi i和和Y Yi i；(2)(2)然后再将然后再将X Xi i,Y,Yi i和下一位进位数通过全加器进行全加。和下一位进位数通过全加器进行全加。这样这样,不同的控制参数可以

21、得到不同的组合函数不同的控制参数可以得到不同的组合函数,因而能够实现多种因而能够实现多种算术运算和逻辑运算。算术运算和逻辑运算。解决方案：解决方案：多功能算术多功能算术/逻辑运算单元逻辑运算单元(ALU)(ALU)将全加器的功能扩展以完成多种算术逻辑运算。将全加器的功能扩展以完成多种算术逻辑运算。Ci1=AiBi(Ci(Ai Bi)=AiBiBiCiCiAiS0S1S2S3X0Y0 参数参数S0,S1,S2,S3分别控制输入分别控制输入Ai和和Bi,产生产生Y和和X的函数。其中：的函数。其中：Yi是受是受S0,S1控制的控制的Ai和和Bi的组合函数；的组合函数；Xi是受是受S2,S3控制的控制

22、的Ai和和Bi组合函数。组合函数。函数关系如表所示。函数关系如表所示。XiS2S3S2S3(AiBi)S2S3(AiBi)S2S3AiYiS0S1AiS0S1AiBiS0S1AiBi 核心部分是由两个半加器组成的全加器核心部分是由两个半加器组成的全加器。由由M控制第二级半加器选择逻辑运算或控制第二级半加器选择逻辑运算或 算术运算（所需的低位进位算术运算（所需的低位进位Cn n）。一位一位ALU基本逻辑电路基本逻辑电路S0S1YiS2S3Xi00011011AiAiBiAiBi0000110111AiBiAiBiAi 进一步化简进一步化简:Xi=S3AiBi+S2AiBiYi=Ai+S0Bi+S

23、1BiAi+S0Bi+S1BiS3AiBi+S2AiBiXiYi=YiFiYi Xi Cn+iCni1YiXiCni综上所述，综上所述，ALU的的一位逻辑一位逻辑表达式为：表达式为：Xi=S3AiBi+S2AiBiYi=Ai+S0Bi+S1BiFiYi Xi Cn+iCni1YiXiCni 4 4位之间采用先行进位（并行进位）公式。位之间采用先行进位（并行进位）公式。根据根据 Cni1YiXiCni ，每一位的进位公式可每一位的进位公式可递推递推如下：如下：第第0 0位向第位向第1 1位的进位公式为位的进位公式为:Cn1Y0X0Cn (其中其中C Cn n是向第是向第0 0位（末位）的进位位（

24、末位）的进位)第第1 1位向第位向第2 2位的进位公式为位的进位公式为:Cn2Y1X1Cn1Y1Y0X1X0X1Cn 第第2 2位向第位向第3 3位的进位公式为位的进位公式为:Cn3Y2X2Cn2Y2Y1X1Y0X1X2X0X1X2Cn 第第3 3位的进位输出（即整个位的进位输出（即整个4 4位运算进位输出）公式为位运算进位输出）公式为:Cn4=Y3+X3Cn3=Y3+Y2X3+Y1X2X3+Y0X1X2X3+X0X1X2X3Cn4位位ALU的进位关系及逻辑电路的进位关系及逻辑电路Cn1Y0X0CnCn2Y1X1Cn1Y1Y0X1X0X1CnCn3Y2X2Cn2Y2Y1X1Y0X1X2X0X1

25、X2CnCn4=Y3+X3Cn3=Y3+Y2X3+Y1X2X3+Y0X1X2X3+X0X1X2X3Cn Cn+4是最后进位输出。是最后进位输出。逻辑表达式表明逻辑表达式表明,这是一个先行进位逻辑。换句话说这是一个先行进位逻辑。换句话说,第第0位位的进位输入的进位输入Cn可以直接传送到最高位上去可以直接传送到最高位上去,因而可以实现高速因而可以实现高速运算。运算。下图为用上述原始推导公式实现的下图为用上述原始推导公式实现的4 4位算术位算术/逻辑运算单元逻辑运算单元(ALU)(ALU)74181ALU从进位关系上看从进位关系上看X0Y0X1Y1X2Y2X3Y3正逻辑表示的正逻辑表示的74181

26、第第3 3位的进位输出（即整个位的进位输出（即整个4 4位运算进位输出）公式为位运算进位输出）公式为:Cn4=Y3+X3Cn3=Y3+Y2X3+Y1X2X3+Y0X1X2X3+X0X1X2X3Cn设设 GY3Y2X3Y1X2X3Y0X1X2X3 PX0X1X2X3 则则 Cn4GPCn 其中其中G G称为称为进位发生输出进位发生输出,P P称为称为进位传送输出进位传送输出。在电路中多加这两个进位输出的目的在电路中多加这两个进位输出的目的,是为了便于实现多片是为了便于实现多片（组）（组）ALUALU之间的先行进位。之间的先行进位。P和和G的含义的含义负逻辑表示的负逻辑表示的74181X0Y0X1

27、Y1X2Y2X3Y3 2.2.算术逻辑运算的实现算术逻辑运算的实现上图中控制端上图中控制端用来控制用来控制ALU进行算术运算还是进行逻辑运算进行算术运算还是进行逻辑运算:0时：时：对进位信号没有任何影响。此时对进位信号没有任何影响。此时Fi不仅与本位的被操作数不仅与本位的被操作数Yi和操作数和操作数Xi有关有关,而且与向本位的进位值而且与向本位的进位值Cn+i有关有关,因此因此0时时,进行进行算术操作算术操作。1时：时：封锁了各位的进位输出封锁了各位的进位输出,即即Cn+i0,因此各位的运算结果因此各位的运算结果Fi仅与仅与Yi和和Xi有关有关,故故1时时,进行进行逻辑操作逻辑操作。下图为工作

28、于负逻辑和正逻辑操作方式的下图为工作于负逻辑和正逻辑操作方式的74181ALU方框图。方框图。两种操作是等效的。两种操作是等效的。对正逻辑操作数来说：对正逻辑操作数来说：算术运算称高电平操作；算术运算称高电平操作；逻辑运算称正逻辑操作逻辑运算称正逻辑操作(即高电平为即高电平为“1”,低电平为低电平为“0”)。对于负逻辑操作数来说对于负逻辑操作数来说:正好相反。正好相反。A A+BA+B减1A加AB（A+B）加ABA减B减1AB减1A加ABA加B（A+B）加ABAB减1A加A*（A+B）加A（A+B）加AA减1AA+BA B逻辑0A BBA BA BA+BA BBA B逻辑1A+BA+BA A减

29、1 AB减1 AB减1 减1A加（A+B）AB加（A+B）A减B减1A+BA加（A+B）A加BAB加（A+B）A+BA加A*AB加AAB加A A A A B A+B 逻辑1 A+B B A B A+B A B A B B A+B 逻辑0 A B A B A L L L LL L L HL L H LL L H HL H L L L H L HL H H LL H H HH L L LH L L HH L H LH L H HH H L LH H L HH H H L H H H H算术运算M=L Cn=H逻辑M=H算术运算M=L Cn=L逻辑M=H正逻辑输入与输出负逻辑输入与输出工作方式选择输

30、入S3 S2 S1 S0 (1)(1)H H高电平高电平,L,L低电平；低电平；(2)(2)*表示每一位均移到下一个更高位表示每一位均移到下一个更高位,即即A A*2A2A。(3)(3)算术运算操作是用补码表示法来表示的，其中：算术运算操作是用补码表示法来表示的，其中：“加加”是指算术加，运算时要考虑进位；是指算术加，运算时要考虑进位；符号符号“”是指是指“逻辑加逻辑加”。(4)(4)减法是用补码方法进行的，其中数的反码是内部产生的减法是用补码方法进行的，其中数的反码是内部产生的,而结果输出而结果输出“A A减减B B减减1 1”，因此做减法时需在最末位产生一个强，因此做减法时需在最末位产生一

31、个强迫进位迫进位(加加1),1),以便产生以便产生“A A减减B B”的结果。的结果。(5)(5)“A AB B”输出端可指示两个数是否相等；输出端可指示两个数是否相等；3.3.并行加法器的进位逻辑并行加法器的进位逻辑74181ALU为为4位并行加法器，位并行加法器，组成组成16位的并行加法器位的并行加法器怎么办？怎么办？4片片(组组)74181连接连接怎样连？怎样连？组与组之间串行连接组与组之间串行连接组与组之间并行连接组与组之间并行连接(1)(1)组间串行进位组间串行进位C4G0P0C0C8G1P1C4C12G2P2C8C16G3P3C12进位关系进位关系Cn1Y0X0CnCn2Y1X1C

32、n1Y1Y0X1X0X1CnCn3Y2X2Cn2Y2Y1X1Y0X1X2X0X1X2CnCn4=Y3+X3Cn3=Y3+Y2X3+Y1X2X3+Y0X1X2X3+X0X1X2X3Cn组内组内组间组间X0Y0X1Y1X2Y2X3Y3X0Y0X1Y1X2Y2X3Y3C4C8C4C00011GY3Y2X3Y1X2X3Y0X1X2X3PX0X1X2X3第第1组组4-1位位并行进位并行进位X3Y3X2Y1X1Y1X0Y0C4C3C2C1第第2组组8-5位位并行进位并行进位X7Y7X6Y6X5Y5X4Y4C8C7C6C5第第3组组12-9位位并行进位并行进位X11Y11X10Y10X9Y9X8Y8C12C

33、11C10C9第第4组组16-13位位并行进位并行进位X15Y15X14Y14X13Y13X12Y12C16C15C14C13进位传递时间进位传递时间C16C12C8C4C01.534.56tyC1CC16C12C8C4C01.534.57tyC1C5.589.5(2)(2)组间并行进位组间并行进位两级先行进位的两级先行进位的ALUALU由串行进位关系由串行进位关系C8=G1P1C4=G1+P1(G0P0C0)=G1+G0P1+P0P1C0得：得：C4G0P0C0C8G1P1C4C12G2P2C8C16G3P3C12C4=G0P0C0C12=G2P2C8=G2+P2(G1+G0P1+P0P1C

34、n)=G2+G1P2+G0P1P2+P0P1P2C0C16=G3+P3C12=G3+G2P3+G1P1P2+G0P1P2P3+P0P1P2P3C0=G*P*C0其中其中:P*P0P1P2P3G*G3G2P3G1P1P2G0P1P2P3根据上述公式实现逻辑电路根据上述公式实现逻辑电路:X0Y0X1Y1X2Y2X3Y3C12C8C4X0Y0X1Y1X2Y2X3Y3X0Y0X1Y1X2Y2X3Y30进位的传递时间进位的传递时间C16C12C8C4C01.534.56tyC1CC3第第1小组小组X30Y30C3C2C1P0G0第第2小组小组X74Y74C7C6C5P1G1第第3小组小组X118Y118

35、C11C10C9P2G2第第4小组小组X1512Y1512C15C14C3P3G3第二级进位链第二级进位链C0C4C8C12C16由上图可见由上图可见，当当X Xi和和Yi形成以后，经过形成以后，经过1.5ty，产生第一小组的，产生第一小组的C1，C2，C3和所有的和所有的G Gi、Pi；经过经过1.5ty，由第二级进位链产生，由第二级进位链产生C4，C8，C12，C16；再经再经1.5ty后，产生第后，产生第2，3，4小组内的小组内的C5C6C7，C9C10C11，C13C14C15。整个进位传递时间为整个进位传递时间为4.5ty。4.4.先行进位部件（先行进位部件（CLACLA）74182

36、7418274182是一个并行进位部件，其内部结构图如下：是一个并行进位部件，其内部结构图如下：其中其中G*称为称为成组进位发生输出成组进位发生输出，P*称为称为成组进位传送输出成组进位传送输出。Cn+=G0+P0CnCn+=G1+P1Cn+=G1+G0P1+P0P1CnCn+=G2+P2Cn+=G2+G1P2+G0P1P2+P0P1P2CnCn4=G3+P3Cn+=G3+G2P3+G1P1P2+G0P1P2P3+P0P1P2P3Cn=G*P*Cn其中其中:P*P0P1P2P3G*G3G2P3G1P1P2G0P1P2P3先行进位部件先行进位部件74182CLA74182CLA所提供的进位逻辑关

37、系如下：所提供的进位逻辑关系如下：74181ALU 74181ALU设置了设置了P P和和G G两个本组先行进位输出端。两个本组先行进位输出端。如果将四片如果将四片7418174181的的P,GP,G输出端送入到输出端送入到7418274182先行进位部件先行进位部件（CLACLA）,又可实现第二级的先行进位又可实现第二级的先行进位,即组与组之间的先行进位。即组与组之间的先行进位。例：例：1616位字长位字长ALUALU的构成的构成G*P*C3、C7、C11是由是由74182同时形成的；同时形成的；其不同点是其不同点是74182还提供大组间的进位函数还提供大组间的进位函数G*和大和大 组传递条

38、件组传递条件P*，以便在位数更长时组成下一级先行进，以便在位数更长时组成下一级先行进 位链。位链。由图可知：由图可知：用若干个用若干个74181ALU位片位片,与配套的与配套的74182先行进位部件先行进位部件CLA在一起在一起,可构成一个全字长的可构成一个全字长的ALU。例：全字长的例：全字长的ALUALU的构成的构成用两个用两个1616位全先行进位部件级联组成的位全先行进位部件级联组成的3232位位ALUALU逻辑方框图。逻辑方框图。十进制加法器十进制加法器十进制加法器可由十进制加法器可由BCD码码(二二十进制码十进制码)来设计来设计,它可以在二它可以在二进制加法器的基础上加上适当的进制加

39、法器的基础上加上适当的“校正校正”逻辑逻辑来实现。来实现。70111+6+0110131101（=D）+011010011（=13）30011+5+010181000（=8）X+Y+C10调整调整故：故：1.1.和为和为10101515时，加时，加6 6校正；校正；2.2.和数有进位时，加和数有进位时，加6 6校正。校正。和数和数(4位位)有进位有进位调整调整 28 0010 1000 28 0010 1000+9 +9 0000 10010000 1001 37 0011 0001 37 0011 0001 （=31=31）0000 01100000 0110 0011 0111 (=37)

40、0011 0111 (=37)1.1.一位一位BCDBCD码行波式进位加法器一般结构：码行波式进位加法器一般结构：0111010101111001101111011112.n2.n位位BCDBCD码行波式进位加法器一般结构：码行波式进位加法器一般结构：原码乘法原码乘法补码乘法补码乘法定点乘法运算定点乘法运算设设n位位被乘数和乘数用定点小数表示被乘数和乘数用定点小数表示被乘数被乘数x原原xf.xn1 x1x0乘数乘数y原原yf.yn1 y1y0则乘积则乘积z原原(xf yf)(0.xn1 x1x0)(0.yn1 y1y0)式中式中，xf为被乘数符号为被乘数符号，yf为乘数符号为乘数符号。原码一位

41、乘法原码一位乘法1.1.乘法的手工算法乘法的手工算法(2)手工运算过程：手工运算过程：设设0.1101,0.10110.1101(x)0.1011(y)110111010000+11010.10001111(z)(1)(1)乘积符号的运算规则：乘积符号的运算规则：同号相乘为正，异号相乘为负。同号相乘为正，异号相乘为负。(1)机器通常只有机器通常只有n位长位长,两个两个n位数相乘位数相乘,乘积可能为乘积可能为2n位。位。(2)只有两个操作数相加的加法器难以胜任将只有两个操作数相加的加法器难以胜任将n位积位积一次相加一次相加起来的运算。起来的运算。机器与人们习惯的算法不同之处：机器与人们习惯的算法

42、不同之处：0.1 1 0 1 x 0.1 1 0 1 x 0.1 0 1 1 y 0.1 0 1 1 y 0.0 0 0 0 1 1 0 1 x 0.0 0 0 0 1 1 0 1 x共共4 4次右移次右移 0.0 0 0 1 1 0 1 x0.0 0 0 1 1 0 1 x共共3 3次右移次右移 0.0 0 0 0 0 0 x0.0 0 0 0 0 0 x共共2 2次右移次右移 +0.0 1 1 0 1 x+0.0 1 1 0 1 x共共1 1次右移次右移 0.1 0 0 0 1 1 1 10.1 0 0 0 1 1 1 1 2.2.适合定点机的形式适合定点机的形式为了适合两个操作数相加的加

43、法器，为了适合两个操作数相加的加法器，将将x y改写成下面形式：改写成下面形式：x y=x(0.1011)=0.1 x+0.00 x+0.001 x+0.0001 x=0.1 x+0.10+0.1(x+0.1 x)=2-1x+2-10+2-1(x+2-1x)根据此式，按式中括号可表达的层次，根据此式，按式中括号可表达的层次，从内向外从内向外逐次逐次进行移位累加。进行移位累加。一般而言，设被乘数一般而言，设被乘数x,x,乘数乘数y y都是小于都是小于1 1的的n n位定点正数位定点正数：x=0.xx=0.x1 1x x2 2.x.xn n 1 1 y=0.y y=0.y1 1y y2 2.y.y

44、n n 1 0所以：所以：补补补补补补x)yyy.(xyxn 210)yyy.(xn1021 补补(mod2)niiiyy102=x补补=x补补y为推导出逻辑实现的分步算法，将上式展开得到各项部分积为推导出逻辑实现的分步算法，将上式展开得到各项部分积累加的形式。累加的形式。(yn+1是增加的附加位，初值为是增加的附加位，初值为0)补补yx)(nnyyyyx 22222110补补)()()()(nnnnyyyyyyyx 22222122121110补补)()()()()(nnnnnyyyyyyyx 20221111201补补)()()(nnnyyyyyyx 22111201补补 niiiiyyx

45、012)(补补公式展开公式展开将上式改为接近于分步运算逻辑实现的递推关系。将上式改为接近于分步运算逻辑实现的递推关系。补补z 00 补补补补补补x)yy(zz nn12112 补补补补补补x)yy(zz ininii12112 补补补补补补x)yy(zz nn11112 补补补补补补x)yy(zz nn 10112 MM递推公式递推公式补补补补补补补补x)yy(z z yxnn011 最后一步不移位最后一步不移位由此可见：由此可见：每次都是在前次部分积的基础上，由每次都是在前次部分积的基础上，由（yi+1-yi)决定对决定对x补补的操作，然后再右移一位，得到新的部分积；重复进行。的操作，然后再

46、右移一位，得到新的部分积；重复进行。yn+1，yn的作用：的作用：开始操作时，补充一位开始操作时，补充一位yn+1,使其初始为使其初始为0。由。由yn+1yn判断进判断进行什么操作；然后再由行什么操作；然后再由ynyn-1判断第二步进行什么操作判断第二步进行什么操作。若若 yn nyn n1 1=1 1 则则 yi1 1-yi=1 =1 做加做加xx补运算；补运算；yn nyn n1 1=则则 yi1 1-yi=-做加做加-x-x补运算补运算；yn nyn n1 1=1 1yn nyn n1 1=0=0则则 yi1 1-yi=0 zzi i 加加0 0，即保持不变；，即保持不变；补码一位乘的运

47、算规则补码一位乘的运算规则(1)如果如果yn=yn+1，则部分积，则部分积zi加加0，再右移一位；，再右移一位；(2)如果如果ynyn+1=01，则部分积，则部分积zi加加x补补，再右移一位；，再右移一位；(2)如果如果ynyn+1=10，则部分积，则部分积zi加加-x补补,再右移一位；再右移一位；如此重复如此重复n+1n+1步，步，但最后一步不移位但最后一步不移位。包括一位符号位，所得包括一位符号位，所得乘积为乘积为2n+12n+1位位，其中，其中n n为尾数位数。为尾数位数。算法流程图算法流程图开始开始结束结束zi补补+x补补zi补补zi补补+-x补补zi补补z补补=0,i=0ynyn+1

48、=?zi补补不变不变i=n+1？zi补补,y右移一位，右移一位，i=i+1011001或或11YN00.00001.00110yn+1=0+00.1011ynyn+1=10,加加-x补补00.101100.0101110011右移一位右移一位+00.0000ynyn+1=11,加加000.010100.0010111001右移一位右移一位+11.0101ynyn+1=01,加加x补补11.011111.1011111100右移一位右移一位+00.0000ynyn+1=00,加加011.101111.1101111110右移一位右移一位+00.1011ynyn+1=10,加加-x补补00.100

49、0111110最后一位不移位最后一位不移位例例：x补补=1.0101，y补补=1.0011,求求xy补补=？-x补补=0.1011xy补补=0.10001111算法步骤存在错误算法步骤存在错误!部分积部分积乘数乘数ynyn+1说明说明000000101100yn+1=0+000000ynyn+1=00,加加0000000000000010110右移一位右移一位+110011ynyn+1=10,加加-x补补110011111001101011右移一位右移一位+000000ynyn+1=11,加加011.100111.1100110101右移一位右移一位+001101ynyn+1=01,加加x补补

50、001001000100111010右移一位右移一位+110011ynyn+1=10,加加-x补补110111111010最后一位不移位最后一位不移位x补补=001101，y补补=10110,-x补补=110011xy补补=101111110部分积部分积乘数乘数ynyn+1说明说明例例：x=13,y=-10求求xy=？xy=-010000010=-82H=-1304.4.补码一位乘逻辑原理图补码一位乘逻辑原理图 R0 R1 y yn ny yn+1n+1R2 计数器计数器i i 部分积部分积z 被乘数被乘数x x乘数乘数y+1LDR0LDR1 T1,T2,+1 Ti QQ加法器加法器RS启动启