并行除法运算

1、计算机组成原理计算机组成原理12022年5月5日定点除法运算定点除法运算计算机组成原理计算机组成原理2被除数被除数 x，其原码为，其原码为x原原xf . xn1 x1 x0除数除数 y，其原码为，其原码为y原原yf . yn1 y1 y0 则有商则有商q/，其原码为，其原码为q原原(xf yf) + (0. xn1x1x0 / 0.yn1 y1y0) 商的符号运算商的符号运算qfxf yf 与原码乘法一样与原码乘法一样; 商的数值部分的运算，实质上是两个正数求商的运算。商的数值部分的运算，实质上是两个正数求商的运算。设有设有n位定点小数：位定点小数：定点除法运算定点除法运算原码除法运算原理原码

2、除法运算原理原码除法运算计算机组成原理计算机组成原理30.100100.010110.0011100.0010110.00001100.00010110.000011000.000010110.00000001不够减，商上零，-0.10110.1101除数右移1位，够减，减除数，商上1除数右移1位，够减，减除数，商上1除数右移1位，不够减，商上零除数右移1位，够减，减除数，商上1定点除法手工计算定点除法手工计算计算机组成原理计算机组成原理4原码一位除法原码一位除法 结果与手算相同结果与手算相同，但余数不是真正的余数但余数不是真正的余数，多乘了多乘了2n，故正确的余数应故正确的余数应为为2-nr

3、n，即：，即：0.0000000100.0001 第四次余数第四次余数r4 01.0010 被除数左移一位，被除数左移一位，2xy，商，商1+ 11.0101 减减y，即，即+-y补补00.0111 第一次余数第一次余数r1 00.1110 r1左移一位左移一位 ，2r1y，商，商1+ 11.0101 减减y00.0011 第二次余数第二次余数r2 00.0110 r2左移一位左移一位 ，2r2y，商，商1 + 11.0101 减减y00.1011 00.1001 xy，商，商000.1101x=0.1001, y=0.1011，-y补补=1.0101计算机组成原理计算机组成原理5原码恢复余数

4、除法恢复余数除法n如何判断是否够减n原码运算判断借位n利用补码作减法，判断余数符号即可n余数为负数时，必须恢复余数n即将余数加除数，恢复成原来的值。n求下一位商，必须将余数左移一位，再与除数比较n比较，上商（恢复），余数移位，再比较， 直到获得商所需要的位数为止。计算机组成原理计算机组成原理600.100101.001011.0101被除数被除数/ /余数余数00.011100.111011.010100.001100.011011.0101商商上商位上商位说明说明减Y比较左移一位减Y比较余数R00，商上1左移一位减Y比较R20，商上1左移一位减Y比较R30，商上111.111000.1011

5、00. 000100.011000.110011.010111.101100.1011 0.1100.11010.110 0.1 00 0.11 00.100111.0101+Y补+Y补+Y补+Y补+Y补+计算机组成原理计算机组成原理7恢复余数乘法问题恢复余数乘法问题n需要进行恢复余数的操作n恢复余数的操作次数不确定，故运算时间不固定，因此控制比较复杂。n实际中常用不恢复余数法，又称加减交替法。其特点是运算过程中如出现不够减，则不必恢复余数，根据余数符号，可以继续往下运算，因此步数固定，控制简单。计算机组成原理计算机组成原理8加减交替法加减交替法 上述恢复余数法由于要恢复余数，使得除法的步数不

6、固定，上述恢复余数法由于要恢复余数，使得除法的步数不固定，控制比较复杂。实际上常用的是控制比较复杂。实际上常用的是加减交替法加减交替法。特点：特点：当运算过程中出现不够减的情况，不必恢复余数，而是当运算过程中出现不够减的情况，不必恢复余数，而是根据余数的符号，继续往下运算，因此步数固定，控制简单。根据余数的符号，继续往下运算，因此步数固定，控制简单。不恢复余数法：不恢复余数法：若第若第i-1i-1次商的余数为次商的余数为R Ri-1i-1，下一次求商的办法是：，下一次求商的办法是：RiRi=2R=2Ri-1i-1-Y-Y当当RiRi00时，第时，第i i位商位商0 0，恢复余数法的结果为（，恢

7、复余数法的结果为（ RiRi=R=Ri i+Y+Y ）第第i+1i+1次商的余数为次商的余数为R Ri+1i+1， R Ri+1i+1= 2= 2R Ri i- Y- YR Ri+1i+1=2(=2(R Ri i+Y+Y)-Y=2R)-Y=2Ri i + Y + Y原码加减交替法原码加减交替法 ：通式：通式 Ri+1=2Ri+(1-2Qi)YRi+1=2Ri+(1-2Qi)YQiQi为为第第i i次次所得的商。若部分所得的商。若部分余数为正，则余数为正，则Qi=1 加（加（-y） 若部分若部分余数为负，则余数为负，则Qi=0 加加 y2Ri + y 2Ri + y 的结果与恢复余数后左移一位再

8、减的结果与恢复余数后左移一位再减y y是等效的是等效的计算机组成原理计算机组成原理911.111011.110000.1011被除数被除数/余数余数00.011100.111011.010100.001100.011011.0101商商上商位上商位说明说明减Y比较R0 0，商上1左移一位，减Y比较R20，商上1左移一位，减Y比较R30，商上100. 000111.101111.011000.1011 0.1100.1101 0.1 0 0.11 00.100111.0101+Y补+Y补+Y补+Y补+Y补计算机组成原理计算机组成原理10上商位移位控制R00控制逻辑R2 除数加法器cR0 被除数/

9、余数 R1 商不恢复余数除法逻辑结构不恢复余数除法逻辑结构Qn计数器计算机组成原理计算机组成原理11例n用原码不恢复余数法计算X补Y补。 (1) X = 0.10101，Y = 0.11011 -Y补=1.00101计算机组成原理计算机组成原理1211.1101011.1010000.11011被除数被除数/余数余数00.0111100.1111011.0010100.0001100.0011011.00101商商上商位上商位说明说明减Y比较R0 0，商上1左移一位，减Y比较R20，商上1左移一位，减Y比较R30 商上零左移一位，加Y比较R40，商上0左移一位，加Y比较11. 1000111.

10、 0001000.1101111.0101110.1011000.11011 0.1100.1100 0.1 0 0.11 00.1010111.00101+Y补+Y补+Y补+Y补+Y补 +Y补 11. 111010.11000R50 商上零计算机组成原理计算机组成原理13阵列阵列除法器除法器1.1.可控加法可控加法/ /减法减法(CAS)(CAS)单元单元阵列除法器有多种多样形式，如不恢复余数阵列除法器，阵列除法器有多种多样形式，如不恢复余数阵列除法器，补码阵列除法器等等。补码阵列除法器等等。首先介绍可控加法首先介绍可控加法/ /减法减法(CAS)(CAS)单元，它将用于并行除法流单元，它将

11、用于并行除法流水逻辑阵列中，它有四个输出端水逻辑阵列中，它有四个输出端S Si i、 C Ci i1 1 、B Bi i、P P和四个输入和四个输入端端A Ai i、B Bi i、P P、C Ci i 。当输入线当输入线P P0 0时，时，CASCAS作加法运算作加法运算；当；当P P1 1时，时，CASCAS作减法运算作减法运算。 CASCAS单元的输入与输出的关系可用如下一组逻辑方程来表单元的输入与输出的关系可用如下一组逻辑方程来表示：示： S Si iA Ai i(B(Bi iP)CP)Ci i C Ci i1 1(A(Ai iC Ci i)(B)(Bi iPP) )A Ai iC Ci

12、 i 当当P P0 0时，上式即是我们熟悉的一位全加器时，上式即是我们熟悉的一位全加器(FA)(FA)的公式：的公式： S Si iA Ai iBBi iCCi iC Ci i1 1A Ai iB Bi iB Bi iC Ci iA Ai iC Ci i 计算机组成原理计算机组成原理14当当P P1 1时，则得求差公式：时，则得求差公式：S Si iA Ai iBBi iCCi iC Ci i1 1A Ai iB Bi iB Bi iC Ci iA Ai iC Ci iCi+1PCiSiYiXi(a) 电路FAiPCiYiXiCi+1Si(b) 符号表示CASi计算机组成原理计算机组成原理15Q4Q3CASCASCASCASCAS0.Q1Q2P=10.Y1Y2Y3Y40.X1X2X3X4X5X6X7X8R4R5R6R7R8CASCASCASCASCASCASCASCASCASCASCASCASCASCASCASCASCASCASCASCAS原码阵列除法器原码阵列除法器1.Cf=Qn 符号位进位=商 计算机组成原理计算机组成原理16Q40.Q1Q2P=10.Y1Y2Y3Y40.X1X2X3X