406-除法器的实现
# 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位除法的运算。
现在这么复杂的除法,都已经被我们解决了, 我们已经有了一个可以正常工作的除法器,这可真是一个了不起的成果! 当然,这当中还有一些细节的问题我们没有谈到。 比如说,当一个正数和一个负数相除的时候那商应该是正数还是负数?余数又应该是正数还是负数呢? 类似这样的小问题,就留给大家回去自己思考了。