加减交替法的证明过程

àì夳堔傛蜴生んèń 2022-07-21 12:21 128阅读 0赞

这是  [http://jpkc.hdu.edu.cn/computer/zcyl//upload/007.ppt][http_jpkc.hdu.edu.cn_computer_zcyl_upload_007.ppt] 的 HTML 档。  
**G o o g l e** 在网路漫游时会自动将档案转换成 HTML 网页来储存。

**第4章 运算方法与运算器**

**第4章 运算方法与运算器**

*  **4.1 定点数的加减运算及实现**
 *  **4.2 定点数的乘法运算及实现**
 *  [**4.3 定点数除法运算及实现**][4.3]
 *  [**4.4 定点运算器的组成与结构**][4.4]
 *  **4.5 浮点运算及运算器**
 *  [**作业**][Link 1]

**第4章 运算方法与运算器**

**4.3 定点数除法运算及实现**

*  
 *  
 *

**第4章 运算方法与运算器**

**一、原码除法算法**

*  
 *  
 *

**第4章 运算方法与运算器**

**1、手工除法算法**

*  **X=+0.1011，Y=-0.1101**
 *  **X÷Y**

*  **改进手工算法即可适合机器运算：**
    
     *  **计算机通过做减法测试来实现判断：结果大于等于0，表明够减，商1；结果小于0，表明不够减，商0。**
     *  **计算机将余数左移一位，再直接与不右移的除数相减。**

**第4章 运算方法与运算器**

**2、原码恢复余数算法**

*  **假设\[X\]****原****=X****S**** .X****1**** X****2**** ……X****n**** ，\[Y\]****原****=Y****S ****.Y****1**** Y****2**** ……Y****n**** ，Q是X÷Y的商，Q****S****是商的符号，R是X÷Y的余数，R****S****是余数的符号**
 *  **原码除法运算的规则是：**
    
     *  **1.Q****S**** = X****S**** ⊕Y****S**** ，R****S ****= X****S****，|Q| = |X|÷|Y|-|R|÷|Y|**
     *  **2.余数和被除数、除数均采用双符号位；初始余数为|X|。**
     *  **3.每次用余数减去|Y|（通过加上\[-|Y|\]****补****来实现），若结果的符号位为0，则够减，上商1，余数左移一位；若结果的符号位为1，则不够减，上商0，先加|Y|恢复余数，然后余数左移一位。**
     *  **4.循环操作步骤3，共做n+1次，最后一次不左移，但若最后一次上商0，则必须+|Y|恢复余数；若为定点小数除法，余数则为最后计算得到的余数右移n位的值。**

**第4章 运算方法与运算器**

**例如： X=+0.1011，**

**Y= - 0.1101**

**用原码恢复余数算法计算X÷Y。**

**解：\[X\]****原****=0.1011**

**\[Y\]****原****=1.1101 |X|=0.1011 |Y|=0.1101**

**\[-|Y|\]****补****=11.0011**

**Q****S**** = X****S**** ⊕Y****S**** = 1 R****S**** = 0**

**得\[Q\]****原****=1.1101**

**\[R\]****原****=0.00000111**

**第4章 运算方法与运算器**

**3、原码不恢复余数算法**

*  **又称为加减交替法：当某一次求得的差值（余数R****i****)为负时，不是恢复它，而是继续求下一位商，但用加上除数（+|Y|）的办法来取代（-|Y|）操作，其他操作不变。**
 *  **其原理证明如下：（注：其证明须借用 恢复余数法 的原理，如下所示：）**
    
     *  **在恢复余数除法中，若第i-1次求商的余数为R****i-1****，下一次求商的余数为R****i****，则：R****i****=2R****i-1****－|Y|**
     *  **如果R****i****>=0，商的第i位上1，并执行操作：余数左移一位，再减|Y|，得R****i+1****，则：R****i****＋1****=2R****i****－|Y|（注：乘以2代表余数左移一位）**
     *  **如果R****i****<0，商的第i位上0，并执行操作：恢复余数（+|Y|），将余数左移一位，再减|Y|，得R****i+1****。其过程可用公式表示如下：**

*  **R****i+1****=2（R****i****+|Y|）－|Y|=2R****i****+2|Y|－|Y|=2R****i****+|Y|（乘以2原因同上）**
    
    **红色字体的式子就是我们想要的结论：即 加减交替法 的理论依据。这些显然是建立在恢复余数法的理论基础上的。**

**第4章 运算方法与运算器**

**3、原码不恢复余数算法**

*  **加减交替法的规则如下：**
    
     *  **余数为正时，商上1，求下一位商的办法，是余数左移一位，再减去除数；**
     *  **当余数为负时，商上0，求下一位商的办法，是余数左移一位，再加上除数。**
     *  **若最后一次上商为0，而又需得到正确余数，则在这最后一次仍需恢复余数。**

**第4章 运算方法与运算器**

**例如：X=+0.1011， Y=-0.1101，用原码不恢复余数算法计算X÷Y。**

**解：\[X\]****原****=0.1011 \[Y\]****原****=1.1101 |X|=0.1011 |Y|=0.1101**

**\[-|Y|\]****补****=11.0011**

**Q****S**** = X****S**** ⊕Y****S**** = 1 RS = 0**

**\[Q\]****原****=1.1101**

**\[R\]****原****=0.00000111**

**第4章 运算方法与运算器**

**二、原码除法的硬件实现**

**控制电路逻辑**

**第4章 运算方法与运算器**

**原码不恢复余数除法流程**

**第4章 运算方法与运算器**

**三、阵列除法器**

*  **被除数X=X****1**** X****2**** X****3**** X****4**** X****5**** X****6****，除数Ｙ=Ｙ****1****Ｙ****2****Ｙ****3****得到的商Q=Q****1****Q****2****Q****3****（Q0=0），R= R****4**** R****5**** R****6****。**
 *  **若为定点小数，则X=0.X****1**** X****2**** X****3**** X****4**** X****5**** X****6****，除数Ｙ=0.Ｙ****1****Ｙ****2****Ｙ****3****，得到的商Q=0.Q****1****Q****2****Q****3****（Q****0****=0），R=0.000 R****4**** R****5**** R****6**
 *  **构成的基本部件：可控加减单元CAS**

**第4章 运算方法与运算器**

**三、阵列除法器**

**第4章 运算方法与运算器**

**4.4 定点运算器的组成与结构**

*  
 *

**第4章 运算方法与运算器**

**一、定点运算器的组成**

*  **基本组成包括：**
    
     *  **算术逻辑运算单元ALU：核心部件**
     *  **暂存器：用来存放参与计算的数据及运算结果，它只对硬件设计者可见，即只被控制器硬件逻辑控制或微程序所访问**
     *  **通用寄存器堆：用于存放程序中用到的数据，它可以被软件设计者所访问。**
     *  **内部总线：用于连接各个部件的信息通道。**
     *  **其他可选电路**

**第4章 运算方法与运算器**

**一、定点运算器的组成**

*  **设计定点运算器，如何确定各部件的功能和组织方式是关键，这取决于以下几个方面：**
    
     *  **指令系统**
     *  **机器字长**
     *  **机器数及其运算原理**
     *  **体系结构**

**第4章 运算方法与运算器**

**二、定点运算器的总线结构**

*  **1、单总线结构**
    
     *  **单总线运算器的结构形式1**

**第4章 运算方法与运算器**

**二、定点运算器的总线结构**

*  **单总线运算器的结构形式2**

**第4章 运算方法与运算器**

*  **2、双总线结构**
    
     *  **双总线运算器的结构形式1**

**第4章 运算方法与运算器**

*  **双总线运算器的结构形式2**

**第4章 运算方法与运算器**

*  **3、三总线结构**

*  **最后必须指出的是，在分析某一种运算器的运算过程和通路时，一个基本的原则就是在一个CPU周期（一步）内，某条总线上的数据必须是唯一的，且不能保留（至下一个CPU周期）。**

**第4章 运算方法与运算器**

**作业**

*  **P108: 6，7**

**第4章 运算方法与运算器**

**The End !**

收藏于 2009-09-16

[http_jpkc.hdu.edu.cn_computer_zcyl_upload_007.ppt]: http://jpkc.hdu.edu.cn/computer/zcyl//upload/007.ppt
[4.3]: http://jpkc.hdu.edu.cn/computer/zcyl//upload/4.3%20%20%E5%AE%9A%E7%82%B9%E6%95%B0%E9%99%A4%E6%B3%95%E8%BF%90%E7%AE%97%E5%8F%8A%E5%AE%9E%E7%8E%B0
[4.4]: http://jpkc.hdu.edu.cn/computer/zcyl//upload/4.4%20%20%E5%AE%9A%E7%82%B9%E8%BF%90%E7%AE%97%E5%99%A8%E7%9A%84%E7%BB%84%E6%88%90%E4%B8%8E%E7%BB%93%E6%9E%84
[Link 1]: http://jpkc.hdu.edu.cn/computer/zcyl//upload/%E4%BD%9C%E4%B8%9A