除法器

复习

  1. 第六章：设计完成了半加器，可以完成两个一位二进制数的加法，但不能处理来自低位的进位
  2. 第七章：设计完成了加法器，可以处理三个输入（两个加数和一个进位），并可以串联构成多位加法器
  3. 第八章：掌握了原码、反码和补码的概念，理解了补码可以统一加减法运算
  4. 第九章：设计完成了减法器，本质是加上一个负数（补码）
  5. 第十章：设计完成了乘法器，本质是多次加法，也可以用 Booth 算法等进行优化

TL;DR

  • 除法就是不断地减，二进制除法更简单，因为每次只用判断能不能减
  • 除法器主要由减法器、移位器和控制电路组成（控制电路将在运算器和存储器完成之后介绍）

正文

二进制除法

　　二进制的除法大体上与十进制出发相同，但比十进制简单。因为只能商 1 或者 0，每次只用判断能不能减，不用想"能减几次"。

　　就像我们算除法需要笔和纸，除法器也需要一些工具：

  1. 减法器：

    • 用来判断"能不能减"
    • 能减就记商 1
    • 不能减就记商 0

  2. 移位器：

    • 对被除数（余数）进行移位
    • 对商进行移位
    • 与乘法器类似，但移位方向不同

  3. 控制电路：

    • 控制整个除法过程
    • 判断是否结束
    • 处理特殊情况（除数为 0 等）

具体步骤

　　我们用 15 ÷ 3 = 5 来看除法器的工作过程。

传统长除法

  1. 准备工作：
   被除数：1111（15）
   除数：  0011（3）
   商：    0000（等待填入）
  1. 第一次试商：
     0
   _______
11 ) 1111
    00     <- 注意对齐
     —————
     1111
  1. 第二次试商：
     01
   _______
11 ) 1111
     11    <- 注意对齐
     —————
     0011
  1. 第三次试商：
     010
   _______
11 ) 0011
      00   <- 注意对齐
     —————
     0011
  1. 结束：
     0101
   _______
11 ) 0011
       11  <- 注意对齐
     —————
     0000

除法器

  1. 准备工作：
   被除数：1111（15）
   除数：  0011（3）
   商：    ####（等待填入）
  1. 第一步：
    • 判断能否减去除数：不能减（1 < 11）
    • 商的最高位记为 0
    • 除数右移一位
   商：    ###0
   被除数：  11110
  1. 第二步：
    • 判断能否减去除数：可以减（11 >= 11）
    • 商左移并在最低位记为 1
    • 1111 - 1100 = 0011，余数为 0011
   商：    ##01
   余数：  0011
  1. 第三步：
    • 判断能否减去除数：不能减（01 < 11）
    • 商左移并在最低位记为 0
    • 减去除数后余数为 0011
   商：    #010
   余数：  0011
  1. 第四步：
    • 判断能否减去除数：可以减（11 >= 11）
    • 商左移并在最低位记为 1
    • 减去除数后余数为 0000
   商：    0101（最终结果）
   余数：  0000

　　最终结果：15 ÷ 3 = 5（商是 0101），余数为 0000。

除法器的工作原理

  1. 初始化：

    • 被除数放在寄存器中
    • 商的所有位初始化为 0
    • 设置计数器，用于控制操作次数

  2. 重复以下步骤：

    • 将除数与被除数从左边对齐
    • 判断当前值是否大于等于除数，如果大于等于除数，则减去除数，商的最低位置 1，如果小于除数，商的最低位置 0
    • 如果能减，将余数作为新的被减数，否则不变
    • 商寄存器左移，除数向右移一位
    • 重复步骤，直到被除数的每一位都参与运算

  3. 重复次数等于除数的位数

优化思路

　　上述除法过程有一个问题：每次试商都需要实际进行减法，如果不能减，还要恢复原来的值。这在位数较多时会很耗时。目前有两种主要的优化思路：

  1. 恢复余数法：

    • 每次试商后，如果不能减就恢复原来的余数
    • 实现简单，但效率较低
    • 需要额外的存储空间保存原余数

  2. 不恢复余数法：

    • 如果某次减法结果为负（不能减），下一步通过加法来修正
    • 避免了恢复原余数的步骤
    • 需要更复杂的控制电路
    • 但整体效率更高

特殊情况

　　除法比乘法多了一些特殊情况需要处理：

  1. 除数为 0：

    • 需要在开始除法前检测
    • 如果除数为 0，触发异常
    • 在实际硬件中通常会产生中断

  2. 溢出检测：

    • 当商太大时会发生
    • 例如：8 位除法，被除数 255 除以 1
    • 需要在过程中持续检测

  3. 符号处理：

    • 对于带符号数，需要：
      1. 先确定结果的符号（同号为正，异号为负）
      2. 取操作数的绝对值进行除法
      3. 最后根据符号规则确定最终结果

小结

知识点

  • 除法就是不断地减，看能减几次
  • 二进制除法只需要判断能不能减
  • 除法器的组成部分：
    • 减法器：判断能不能减
    • 移位器：移动数字
    • 控制电路：控制过程

参考资料

协议

　　本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

封面图

设计师 | 南国微雪