406-除法器的实现

现在，我们已经将除法的运算过程，用适合硬件实现的方法描述出来了， 那么就可以着手开始设计真正的硬件的除法器了。 那么在这一节，我们将首先整理出一个除法器的工作流程， 然后通过一个事例来分析除法器的结构和它的工作原理。

‍‍

我们首先来看一个 32 位除法器的工作流程。 首先进行初始化工作，然后进入正式的工作步骤。 我们要注意，余数和被除数是共享一个寄存器的。

所以第 1 步，是用余数寄存器的内容减去除数寄存器中的内容，并将结果保存到余数寄存器当中；

第 2 步，是检查余数寄存器的内容，如果当前的余数大于等于 0 那说明这次减法操作是正确的；

那下一步执行 2a 这个分支，将商寄存器中的内容左移一位，并将空出的最右边这位设为 1；

然后执行第 3 步，那就是将除数寄存器右移一位

但如果在第 2 步检查余数时，发现余数寄存器的内容小于 0， 那这就意味着，刚才这次减法操作是不应该进行的， 所以必须回退、消除这个影响，那么 2b 的这个分支，就是回退第 1 步的减法操作，然后还会将商寄存器左移一位，但是空出来的最右位是设为 0。 这一步做完之后，同样也会进入第 3 步；

完成第 3 步之后，第 4 步是判断当前是否为最后一轮循环。 这是一个 32 位的除法器，也就是除数是 32 位的，那么一共要进行 33 轮循环， 如果不到 33 轮循环，那就回到第 1 步继续执行； 如果已经是 33 轮循环，说明运算已经完成， 最终结果存放在当前的商寄存器和余数寄存器当中。 这就是 32 位除法器的工作流程。

​

‍

为了简便起见，我们还是用一个 4 位的除法器作为例子来进行说明。 一个 4 位的除法器需要一个 8 位的”余数“寄存器， 需要一个 8 位的”除数“寄存器，而且带右移的功能， 还需要一个 4 位的”商“寄存器，带左移的功能， 最后需要一个 8 位的 ALU，支持加法和减法运算。

​

这里我们要注意的是，在乘法器当中，只需要一个加法器， 而在除法器当中，需要支持加法和减法两种运算。 因为正常的流程中，是需要减法运算。而刚才我们在讲解工作流程时提到，有时候需要回退已经完成的减法操作，这就需要用到加法。 那么这个 ALU 的输入，就来自除数寄存器和余数寄存器， 它的输出还连到了余数寄存器。 那除了这些部件，我们同样还需要控制逻辑，控制这几个寄存器和 ALU 的工作。

‍

‍

‍

现在我们就来看一看这个除法器的工作过程。 我们注意右下角，我们还是结合这个 7 除以 2 的例子来进行说明。 首先是初始化工作。我们将 8 位的被除数放入”余数“寄存器， 然后将 4 位的除数放入”除数“寄存器的高 4 位， 并将”除数“寄存器的低 4 位补上 0， 最后是将 4 位的”商“寄存器置为 0。这就完成了初始化的工作。

​

‍

‍

现在正式进入工作的流程。第 1 步， 是执行减法运算，将当前余数寄存器的内容，减去除数寄存器的内容。 我们注意到，除数寄存器当中，现在保存的是 0010 0000， 而余数寄存器当中，保存的是 0000 0111。 那么控制逻辑会向 ALU 发出执行减法的控制信号， ALU 将输入的两个数进行减法运算， 得到结果是 1110 0111。 这个时候，控制逻辑还会向余数寄存器发出要写入的控制信号， 在下一个时钟上升沿到来的时候，ALU 的输出就会保存到余数寄存器当中。

​

‍

现在余数寄存器已经更新了，然后执行第 2 步， 就是检查余数寄存器， 如果大于等于零，就执行 2a 这个分支的操作； 如果小于零，则执行 2b 这个分支的操作； 那怎么检查是大于等于零，还是小于零呢？其实只要看余数寄存器的最高位就可以了。 根据补码的表示，我们知道，如果最高位为 1，则代表这个数小于零。

​

‍

那现在我们就要执行 2b 这个分支。 因为余数寄存器的内容小于零，意味着我们不应该做刚才那次减法。 所以首先需要回退第一步的操作，但是硬件的操作已经完成， 刚才的减法结果也保存到了余数寄存器当中，而余数寄存器之前的值，我们现在已经不知道了。 怎么回退呢？ 所以实际上没有真正的往回退的方法， 只是还好，我们知道如何找回跟刚才一样的那个数。 因为刚才执行的是一次减法，所以现在只要把余数寄存器的内容加上除数寄存器的内容，就可以得到刚才在余数寄存器当中的内容了。 所以现在，在 ALU 的输入端，两个输入信号早已准备好， 而控制逻辑会给出执行加法的控制信号， 很快 ALU 会完成加法运算，并得到运算结果。 当然，控制逻辑也会给出，让余数寄存器写入这个结果的控制信号，

​

‍

‍

然后等到下一个时钟上升沿到来的时候，余数寄存器就把这个值保存进去了。 我们发现，这个值就是我们刚才执行第 1 步之前的余数寄存器的内容， 也就是十进制的 7。

​

‍

现在我们已经完成了回退的工作，那我们还要记录这一步所对应的商，也就是将商寄存器要左移一位，并将新的最右位设为 0，我们注意右边的这个商寄存器。 那好，现在这一步的工作就已经完成了。

​

‍

第 3 步， 是将除数寄存器的内容右移一位，为下一次的减法操作做好准备。 我们注意除数寄存器，除数寄存器右移之后，最左边会补入一个 0， 而最右边移出的数就直接丢掉了。

​

‍

‍

我们再来看第 4 步， 第 4 步，是检查这是不是最后一轮循环，因为这是一个 4 位的除法器， 所以我们要检查的是，当前是不是第 5 轮循环， 那经过检查，现在不是第 5 轮循环，所以我们还需要继续除法器的工作。

​

‍

‍

现在我们进入第 2 轮，第 2 轮的第 1 步和第 1 轮的第 1 步实际上是一样的， 也是执行减法操作，余数寄存器减去除数寄存器。 在控制逻辑的控制下，ALU 很快就可以得到减法的结果。 我们现在就可以注意一下，这个减法运算的结果最高位是 1， 所以等一会儿我们还得回退这个操作。

​

‍

后面要做的事情，就和我们刚才第一轮所解释过的一样，我们就不再一步一步详细描述了。 那我们用一个表，来总体说明从第二轮到第四轮发生的事情。 刚才我们看到的 是第二轮当中的第 1 步，将余数减除数，得到的结果会保存到余数寄存器当中。 这个表中，红颜色的部分，代表在这一步当中发生改变的数值。 在这里我们会注意到，余数寄存器当中的最高位为 1，说明这是一个小于 0 的数。 所以在下一步，会进行回退的操作，也就是将余数加上除数，再放回到余数寄存器当中， 同时将商左移，最右边补 0， 然后将除数寄存器右移，这就完成了第二轮的操作。

然后是第三轮，我们同时也注意到第三轮进行的减法，得到的结果最高位还是 1， 所以还要执行回退，然后将商的最右边移入一个 0， 再将除数进行右移。

然后是第四轮， 第四轮执行完了减法，我们注意到最高位是 0， 那这就表明这次减法运算不用回退， 所以在下一轮余数寄存器并没有发生变化，而商左移之后，最右边补入了一个 1， 然后再将除数进行右移，这样就完成了四轮的工作。

​

‍

‍

现在我们回到这个结构图，来看第五轮的第 1 步。这时候继续执行减法操作， 除数寄存器的输出，余数寄存器的输出，控制逻辑发出减法的控制信号， ALU 得出运算的结果，运算的结果是 1， 在下一个时钟沿到来的时候，它会被存到余数寄存器当中

​

‍

我们注意，余数寄存器现在发生了改变。 然后是第五轮的第 2 步，检查余数寄存器的最高位， 发现最高位为 0，说明这是一个大于等于 0 的数，进入 2a 这个分支进行操作。

​

‍

2a 这个分支，就是将商寄存器左移一位，并将新的最右位设为 1。 我们注意商寄存器，左移后，最右边设了 1。

​

‍

然后是第五轮的第 3 步，将除数寄存器右移 1 位。 我们从一个旁观者的角度可以看到，因为这已经是最后一轮了，所以除数寄存器的这一次右移，是没有必要的，但是作为硬件来说，它现在并不知道这是最后一轮，所以它仍然在为下一轮进行准备工作

​

‍

直到在第 4 步，在进行检查是否为第五轮的时候，硬件的控制逻辑才会知道，这已经是最后一轮循环，这个除法运算已经完成了。

​

现在除法运算的结果就已经在余数寄存器和商寄存器当中。 注意我们要做的是这个例子，7 除以 2，商为 3，也就是现在的 0011，而余数为 1， 这和我们用纸笔运算的结果是一样的。 那这就是一个四位的除法器的结构和工作的流程。

‍

‍

与之类似，我们就可以得到一个 32 位的除法器， 那这个 32 位的除法器当中，有一个 64 位的余数寄存器，一个 64 位的除数寄存器，带右移功能， 一个 32 位的商寄存器，带左移的功能， 一个 64 位的 ALU，支持加法和减法运算。 那这样一个除法器，用刚才同样的流程就可以完成 32 位除法的运算。

​

‍

现在这么复杂的除法，都已经被我们解决了， 我们已经有了一个可以正常工作的除法器，这可真是一个了不起的成果！ 当然，这当中还有一些细节的问题我们没有谈到。 比如说，当一个正数和一个负数相除的时候那商应该是正数还是负数？余数又应该是正数还是负数呢？ 类似这样的小问题，就留给大家回去自己思考了。