算法与实现

计算机硬件技术1计算机组成原理第六-八讲2020年2月7日计算机算法和算法逻辑实现计算机硬件技术21、定点数加减法运算及电路实现补码的加减法运算，全加器，溢出，快速加法运算（进位链），74181ALU2、定点数乘除运算和电路实现原码、补码，布斯算法，原码恢复余数、不恢复余数3、快速乘除法运算技术和电路实现布斯高基乘法，阵列乘法器，阵列除法器4、浮点数四则运算以及实现加减乘除本讲安排计算机硬件技术3本讲将解决的主要问题掌握计算机算法。加减乘除运算方法和运算器的构成，原码和补码的加减乘除四则运算，浮点数的四则运算。计算机硬件技术4补码加、减法溢出概念与检测方法基本的二进制加法/减法器十进制加法器计算机硬件技术5加法规则：先判符号位，若相同，绝对值相加，结果符号不变;若不同，则作减法，|大|-|小|，结果符号与|大|相同。减法规则：两个原码表示的数相减，首先将减数符号取反，然后将被减数与符号取反后的减数按原码加法进行运算。补码加法1.原码加/减法运算计算机硬件技术6补码加法的公式:[x]补＋[y]补＝[x＋y]补(mod2)在模2意义下,任意两数的补码之和等于该两数之和的补码。这是补码加法的理论基础。2.补码加法运算特点：不需要事先判断符号，符号位与码值位一起参加运算。符号位相加后若有进位，则舍去该进位数字。计算机硬件技术7假设采用定点小数表示,因此证明的先决条件是:︱x︱﹤1,︱y︱﹤1,︱x＋y︱﹤1。(1)x﹥0,y﹥0,则x＋y﹥0。相加两数都是正数,故其和也一定是正数。正数的补码和原码是一样的,可得：[x]补＋[y]补＝x＋y＝[x＋y]补(mod2)公式证明:计算机硬件技术8(2)x﹥0,y﹤0,则x＋y0或x＋y0。相加的两数一个为正,一个为负,因此相加结果有正、负两种可能。根据补码定义，∵[x]补＝x,[y]补＝2＋y∴[x]补＋[y]补＝x＋2＋y＝2＋(x＋y)当x+y0时,2+(x+y)2,进位2必丢失,又因(x+y)0，故[x]补＋[y]补＝x＋y＝[x＋y]补(mod2)当x＋y0时,2＋(x＋y)2,又因(x+y)0，故[x]补＋[y]补＝2＋(x＋y)＝[x＋y]补(mod2)计算机硬件技术9(3)x0,y0,则x＋y0或x＋y0。同(2),把x和y的位置对调即可。(4)x0,y0,则x＋y0。相加两数都是负数,则其和也一定是负数。∵[x]补＝2＋x,[y]补＝2＋y∴[x]补＋[y]补＝2＋x＋2＋y＝2＋(2＋x＋y)因为|x＋y|1,1(2＋x＋y)2,2＋(2＋x＋y)进位2必丢失，又因x+y0故[x]补＋[y]补＝2＋(x＋y)＝[x＋y]补(mod2)计算机硬件技术10至此证明了在模2意义下，任意两数的补码之和等于该两数之和的补码。其结论也适用于定点整数。补码加法的特点：（1）符号位要作为数的一部分一起参加运算；（2）在模2的意义下相加，即大于2的进位要丢掉。结论：计算机硬件技术11例:x＝0.1001,y＝0.0101,求x＋y。解:[x]补＝0.1001,[y]补＝0.0101[x]补0.1001＋[y]补0.0101[x＋y]补0.1110所以x＋y＝＋0.1110例:x＝＋0.1011,y＝－0.0101,求x＋y。所以x＋y＝0.0110解:[x]补＝0.1011,[y]补＝1.1011[x]补0.1011＋[y]补1.1011[x＋y]补10.0110计算机硬件技术12补码减法减法运算要设法化为加法完成补码减法运算的公式：[x－y]补＝[x]补－[y]补＝[x]补＋[－y]补公式证明：只要证明[–y]补＝–[y]补,上式即得证。∵[x＋y]补＝[x]补＋[y]补(mod2)令y=－x∴[0]补＝[x]补+[－x]补故[－x]补＝－[x]补(mod2)证明：计算机硬件技术13例:x＝＋0.1101,y＝＋0.0110,求x－y。解:[x]补＝0.1101[y]补＝0.0110,[－y]补＝1.1010[x]补0.1101＋[－y]补1.1010[x－y]补10.0111x－y＝＋0.0111解：[x]补=1.0011[y]补=1.1010[-y]补=0.0110[x]补1.0011+[-y]补0.0110[x-y]补1.1001例：x=-0.1101，y=-0.0110，求x-y=?∴x--y=-0.0111计算机硬件技术14溢出及与检测方法在定点小数机器中,数的表示范围为|ｘ|1。在运算过程中如出现大于1的现象,称为“溢出”。机器定点小数表示上溢下溢1.概念计算机硬件技术15解：[x]补=0.1011[y]补=0.1001[x]补0.1011+[y]补0.1001[x+y]补1.0100两个正数相加的结果成为负数，这显然是错误的。例:x=+0.1011,y=+0.1001,求x+y。例:x=-0.1101,y=-0.1011,求x+y。解：[x]补=1.0011[y]补=1.0101[x]补1.0011+[y]补1.0101[x+y]补0.1000两个负数相加的结果成为正数，这同样是错误的。计算机硬件技术16发生错误的原因，是因为运算结果产生了溢出。两个正数相加:结果大于机器所能表示的最大正数，称为上溢；两个负数相加：结果小于机器所能表示的最小负数，称为下溢。机器定点小数表示上溢下溢[分析]：计算机硬件技术172.溢出的检测方法[x]补0.1011+[y]补0.1001[x+y]补1.0100[x]补1.0011+[y]补1.0101[x+y]补0.1000溢出逻辑表达式为：V＝S1S2Sc+S1S2Sc(1)单符号位法FAVz0y0x0判断电路判断电路计算机硬件技术18一个符号位只能表示正、负两种情况，当产生溢出时，符号位的含义就会发生混乱。如果将符号位扩充为两位(Sf1、Sf2)，其所能表示的信息量将随之扩大，既能判别是否溢出，又能指出结果的符号。(2)双符号位法双符号位法也称为“变形补码”或“模4补码”。变形补码定义：[x]补=x0x24+x-2x0（mod4)计算机硬件技术19•任何小于1的正数：两个符号位都是“0”，即00.x1x2...xn;•任何大于-1的负数：两个符号位都是“1”，即11.x1x2…xn两数变形补码之和等于两数和的变形补码，要求：•两个符号位都看做数码一样参加运算；•两数进行以4为模的加法，即最高符号位上产生的进位要丢掉模4补码加法公式：[x]补+[y]补=[x+y]补（mod4)采用变形补码后数的表示：计算机硬件技术20Sf1Sf2＝00结果为正数，无溢出01结果正溢10结果负溢11结果为负数，无溢出即：结果的两个符号位的代码不一致时，表示溢出;两个符号位的代码一致时，表示没有溢出。不管溢出与否，最高符号位永远表示结果的正确符号。溢出逻辑表达式为：V＝Sf1⊕Sf2中Sf1和Sf2分别为最高符号位和第二符号位，此逻辑表达式可用异或门实现。双符号位的含义如下：计算机硬件技术21解：[x]补=00.1100[y]补=00.1000[x]补00.1100+[y]补00.100001.0100符号位出现“01”，表示已溢出，正溢。即结果大于+1例x=+0.1100,y=+0.1000,求x+y。解：[x]补=11.0100[y]补=11.1000[x]补11.0100+[y]补11.100010.1100符号位出现“10”，表示已溢出，负溢出。即结果小于-1例x=-0.1100,y=-0.1000,求x+y。计算机硬件技术22从上面例中看到：当最高有效位有进位而符号位无进位时,产生上溢；当最高有效位无进位而符号位有进位时,产生下溢。（简单地说是正数相加为负数或负数相加为正数则产生溢出）故溢出逻辑表达式为：V＝Cf⊕Co其中Cf为符号位产生的进位,Co为最高有效位产生的进位。此逻辑表达式也可用异或门实现。(3)利用进位值的判别法[x]补00.1100+[y]补00.100001.1000[x]补11.0100+[y]补11.100010.1100计算机硬件技术23FAFAz1z0Vc1c0y1x1y0x0FAFAVz1c0c1z0x1y1y0x0V＝C1⊕CoV＝Sf1⊕Sf2判断电路计算机硬件技术24基本的二进制加法/减法器加法运算：Ai+Bi+Ci=Si(Ci+1)加数进位输入和进位输出一位全加器真值表输入输出AiBiCiSiCi＋10000000110010100110110010101011100111111逻辑方程Si＝Ai⊕Bi⊕CiCi＋1＝AiBi＋BiCi＋CiAi1.一位全加器计算机硬件技术25逻辑方程Si＝Ai⊕Bi⊕CiCi＋1=AiBi＋BiCi＋CiAi逻辑电路（一位全加器）常用的全加器逻辑电路FACi+1CiSiAiBi逻辑符号计算机硬件技术262.n位的行波进位加减器n个1位的全加器(FA)可级联成一个n位的行波进位加减器。计算机硬件技术27T被定义为相应于单级逻辑电路的单位门延迟。T通常采用一个“与非”门或一个“或非”门的时间延迟来作为度量单位。3TXNOR异或非3TXOT异或2TOR或2TAND与TNOT非TNOR或非TNAND与非时间延迟逻辑符号（正逻辑）门的功能门的名称典型门电路的逻辑符号和延迟时间接线逻辑(与或非)AOIT+TRC3.n位的行波进位加法器的问题时间延迟计算机硬件技术28(1)对一位全加器(FA)来说，Si的时间延迟为6T(每级异或门延迟3T)；Ci＋1的时间延迟为5T。3T3TTT计算机硬件技术29(2)n位行波进位加法器的延迟时间ta为:•9T为最低位上的两极“异或”门再加上溢出“异或”门的总时间；•2T为每级进位链的延迟时间。ta＝n·2T＋9T＝(2n＋9)T考虑溢出检测时，有：当不考虑溢出检测时，有：ta＝(n-1)·2T＋9Tta为在加法器的输入端输入加数和被加数后,在最坏的情况下加法器输出端得到稳定的求和输出所需要的最长时间。ta越小越好。计算机硬件技术30缺点：(1)串行进位,它的运算时间长；(2)只能完成加法和减法两种操作而不能完成逻辑操作。多功能算术/逻辑运算单元(ALU):不仅具有多种算术运算和逻辑运算的功能；而且具有先行进位逻辑。从而能实现高速运算。由一位全加器(FA)构成的行波进位加法器:计算机硬件技术311.基本思想Si＝Ai⊕Bi⊕Ci一位全加器(FA)的逻辑表达式为:(1)将Ai和Bi先组合成由控制参数S0,S1,S2,S3控制的组合函数Xi和Yi；(2)然后再将Xi,Yi和下一位进位数通过全加器进行全加。这样,不同的控制参数可以得到不同的组合函数,因而能够实现多种算术运算和逻辑运算。解决方案：多功能算术/逻辑运算单元(ALU)将全加器的功能扩展以完成多种算术逻辑运算。Ci＋1=AiBi·(Ci·(Ai⊕Bi))=AiBi＋BiCi＋CiAi计算机硬件技术32S0S1S2S3X0Y0参数S0,S1,S2,S3分别控制输入Ai和Bi,产生Y和X的函数。其中：Yi是受S0,S1控制的Ai和Bi的组合函数；Xi是受S2,S3控制的Ai和Bi组合函数。函数关系如表所示。Xi＝S2S3＋S2S3(Ai＋Bi)＋S2S3(Ai＋Bi)＋S2S3AiYi＝S0S1Ai＋S0S1AiBi＋S0S1AiBi•核心部分是由两个半加器组成的全加器。•由M控制第二级半加器选择逻辑运算或算术运算（所需的低位进位Cn）。一位ALU基本逻辑电路计算机硬件技术33S0S1YiS2S3Xi00011011AiAiBiAiBi0000110111Ai＋BiAi＋BiAi进一步化简:Xi=S3AiBi+S2AiBiYi=Ai+S0Bi+S1BiAi+S0Bi+S1BiS3AiBi+S2AiBiXiYi==YiFi＝Yi⊕Xi⊕Cn+iCn＋i＋1＝Yi＋XiCn＋i计算机硬件技术34综上所述，ALU的一位逻辑表达式为：Xi=S3AiBi+S2AiBiYi=Ai+S0Bi+S1BiFi＝Yi⊕Xi⊕Cn+iCn＋i＋1＝Yi＋XiCn＋i