第二章 整数除法器

2.1 传统的除法器

整数除法器没有像整数乘法器那样丰富的种类，整数除法器的分类仅有传统型的循环型之分。老实说笔者也真的有点郁闷，翻了很多文章，论文，参考书，然后再衡量与Verilog HDL语言，笔者得到的都是零碎的线索。说一句真心话，真的真的有够郁闷“好想抽根烟，看夕阳”这样的心情。坏话当前，这一章笔记的内容会是非常短 ......

时光又回到笔者的小学时候，在数学这门课中，笔者最喜欢就是减法，最讨厌就是除法。喜欢减法的原因，因为小学的减法没有整数的概念，任何被减数小于减数都是零，所以笔者特别钟爱。但是当数学课本出现“除法”的字眼，小学的笔者忽然间觉得“它”很碍眼。

小时候的笔者还记得，老师教我们（笔者小时候的同学）除法是“乘法+减法”。（估计读者的小时候也是一样）但是那时候的笔者不晓得“只要有减法就能攻略除法”。传统除法的概念和传统乘法的概念是一样的，乘法是累加过程，反之除法是递减过程，直到减数大于被减数，剩下的就是余数。

先来简单的扫盲： 除数 Divisor , 被除数 Dividend，商数Quotient，余数 Reminder。

再来是苹果的故事：

假设有一只72HP（被除数）的苹果怪兽，勇者akuei2，一次的攻击是减少10 HP（除数）。但是勇者它不杀生，当苹果怪兽余下的HP小于勇者的攻击容量，勇者的攻击结束。

在上面“攻击过程中”，勇者一共攻击了7次，那么苹果怪兽也伤（商数）了7次，苹果怪兽余下（余数）的HP是2。

为什么笔者会说一个就连小朋友也知道的故事？你知道吗，当你翻开任何一本有关除法器的参考书，你就会看到一条非常普遍的除法约束公式：

被除数 = 商数·除数 + 余数

这一条公式就和上面的故事有关系。实际上这条公式非常的猥琐，笔者非常不喜欢它，笔记也不要讨论它，笔者只是告示读者，有这样“一条”东西的存在。

上面有关勇者大战苹果怪兽的故事就是传统除法器的概念。反之，和我们小时候所学习的除法方式有莫大的差别，那是一种“查表+心算”的除法方式。我们必须清楚，计算器是一个笨蛋，硬件比计算机更笨蛋，它什么都不会。

在这里笔者需要强调一点：

组合逻辑所组成的硬件除法器效率上远远是超过Verilog HDL语言所“编写”的硬件除法器（虽然Verilog HDL 语言也可以以组合逻辑的方式去描述硬件除法器）。但是这一本笔记的重点是“掌握 Verilog HDL语言”。笔者衷心希望读者们不要会错意，这本笔记确确实实是为Verilog HDL语言量身打造的，硬件除法器是其次。

硬件除法器和硬件乘法器同样也会遇上“除数和被除数的正负关系”的问题。

13 / 2 = 商6 , 余1

-13 / 2 = 商 -6，余 1

13 / -2 = 商 -6，余 1

-13 / -2 = 商 6，余1

4 - 2 = 4 + 2补

除数和被除数的正负关系反映了它们是“异或”的关系。为了设计的方便，在作除法的时候被除数取正值，除数去负值的补码，因为传统的除法就是被除数递减于除数的概念，所以除数取负值的补码的方式可以方便设计。然而结果是负值还是正值根据原来除数和原来被除数的正负关系再作决定。

实验八：传统除法器

传统除法器的设计非常单纯：

一、先取除数和被除数的正负关系，然后正值化被除数。传统除法器因为需要递减

    的关系，所以除数就取负值的补码，方便操作。

二、被除数递减与除数，每一次的递减，商数递增。

三、直到被除数小于除数，递减过程剩下的是余数。

四、输出的结果根据除数和被除数的正负关系。

divider_module.v

第7~13行是该模块的输入和输出，采用仿顺序操作的结构。第19~25行是该模块所使用的寄存器。Dend用来寄存被除数的正值，Dsor用来寄存除数负值的补码，Q用来寄存商数，isNeg用来寄存除数和被除数的正负关系。

在步骤0 (40~47行)，取得被除的正值和除数负值的补码（42~43行），44行取得除数和被除数的正负关系。清理Q寄存器后（45行），i递增以示下一个步骤。

步骤1（49~51行），第51行表示了，除法的递减操作。被除数每一次被除数递减，Q寄存器都会递加。第50行的if条件表示了，除法操作的结束（当被除数小于除数）。根据isNeg的逻辑（除数和被除数的正负关系）来决定商数的结果是正值还是负值。然后步骤i递增。

步骤2~3是产生完成信号（53~57行）。

divider_module.vt

.vt 文件的写法，笔者就不多说了。自己看着办吧。

仿真结果：

仿真结果如上。哎~仿真图暴露了传统除法器的弱点。不一样的被除数，就有不一样的时钟消耗。

实验说明：

无论是传统的乘法器还是传统的除法器。它们都有不好的一面，只要除数（乘数）稍微大了一点，它就要“多吃”时钟。但是传统的乘法器还好，还可以优化，相反的传统的除法器就有点不妙了 ... 它无法改进也无法优化。

实验结论：

传统除法器的好处就是简单，但是实际的用途非常低。因为它对时钟的消耗是根据除数的“数量”来作决定 ......

2.2 循环型除法器

循环型的除法器，如果用笔者的话来说，就是位操作的除法器。循环型的除法器是典型的除法器，假设除数和被除数的位宽为N位，那么除法器就会循环N次的除法操作。

根据每一种除法操作的特点，求商得余。

典型的循环型除法器，有分为可恢复和不可恢复。我们知道无论是乘法器还是除法器，都有一个操作空间，对吧？所谓可恢复，当它完成某种条件，操作空间的值又恢复到初始化的状态，反之不可恢复的意思则是相反。

循环型的除法器，可恢复也好还是不可恢复也好 ... 这一点也不重要，因为在Verilog HDL语言的眼里，也是几段代码的故事。最重要的是那一种的循环型的除法器最“养眼”，笔者就选谁。

循环型的除法器的种类在网络上尽是千奇八怪。笔者在很偶然的情况下，发现其中一种的循环型除法器。故，是老外的东西，话说老外真的不简单。为了尊重原创者，就直接引用该除法器的原名字吧！Streamlined divider ! 来，再说一次！Streamlined divider！

"Streamlined" 是什么意思？笔者百度，谷歌一下还是搞不清楚那是什么？估计有特别的意义吧！？就像笔者给自己的建模习惯名为低级建模一样。该除法器的思路很简单：

假设被除数A = 7（0111），除数B = 2 ( 0010 )，它们均为4位位宽。那么操作空间就是 Temp 就是 2 * Width。Temp[ Width - 1 : 0 ]是用来填充被除数，Temp[ Width * 2 - 1：Width -1 ] 是用与除数递减操作。为了方便操作，我们建立 5位位宽的s空间用来寄存除数B的负值补码形式。此外还要考虑同步操作，Temp[ Width * 2 - 1：Width -1 ] 和 除数B的递减操作应该发生别的空间，亦即Diff空间。Diff空间和Temp操作空间拥有同样的位宽。

reg [7:0]Temp;

reg [7:0]Diff;

reg [4:0]s;

首先初始化 Temp空间和s空间。Temp空间的[ Width - 1 : 0 ] 填入 被除数A，然而s空间用于寄存 除数B负值的补码形式。最后顺便清理Diff空间。

Temp <= { 4'd0 , A };

s <= B[3] ? { B[3] , B } ? { ~B[3] , ~B + 1'b };  //如果除数B为负值，就直接填入，

                                        //否则转换为负值后填入。

Diff <= 8'd0;

s空间寄存B的负值的动作，其实是“小空间向大空间转换 + B绝对负值化”。

接下来的动作，是核心的部分。每一次的操作，

一、在Diff空间先取 Temp[ Width * 2 - 1 : Width - 1 ] - B 或者 Temp[ 7:3] + s

二、然后判断Diff空间的“最高位”, 亦即符号位，是逻辑1还是逻辑0。

三、如果是逻辑1表示Temp[7:3] 的值小于除数B，Temp空间左移一位补0。

反之如果是逻辑0，表示 Temp[7:3] 的值大于除数B，Temp空间被赋予Diff

空间的值，并且左移一位补1。

case( i )

......

1,2,3,4:  // 因为除数B和被除数A的位宽均为4位，所以循环4次。

begin

    Diff = Temp + { s , 3'b0 } ;  // “=”表示当前步骤取得结果

    if( Diff[7] ) Temp <= { Temp [6:0], 1'b0};

    else Temp <= { Diff[6:0] , 1'b1 };

    i <= i + 1'b1;

end

当经过 4 次的循环操作后。Temp空间的 [ Width - 1 : 0 ] 是商数，[ Width * 2 -1: Width ] 是余数。在这里，重点是“=”这一段代码，Diff取得的即时结果是在当前步骤，而不是在该步骤的未来。

assign Quotient = Temp[3:0];

assign Reminder = Temp[7:4];

注：在操作的过程中，无视最高位的溢出

Streamlined divider 的除法过程大致上是这样！笔者懒得画流程图了~读者自己看着吧。

实验九：循环型除法器

该除法器的大致操作如上述那样，这里就不重复了。不同的是除数和被除数均为8位位宽。

streamlined_divider_module.v

第16~17行是仿真输出，分别针对操作空间Temp和Diff。该除法器和传统除法器有几分相识。在步骤0（42~51行）isNeg寄存器取除数和被除数的正负关系（45行）。s寄存从8位空间向9位位宽空间的不正规整数转换，并且取除数的负值的补码形式（46行）。47行的Temp空间[Width : 0 ] 取被除数的正值化。48行是Diff空间的清零。

步骤1~8（53~63行）是该除法器的循环操作，具体的操作过程上述内容已经讲过了。不同的只是除数和被除数的位宽而已。步骤9~10（65~69）是产生完成信号。

streamlined_divider_module.vt

.vt 文件的编写方法还是一如既往，自己看着办吧！

仿真结果:

嗯 ~ 仿真结果显示了3次的除法操作，都很和谐，时钟的消耗也是一致，很好很好。

实验说明：

循环操作的除法器（或者称为位操作的除法器），实际上有很多种类。不知为什么，笔者就是喜欢它。阿~废话多了。从仿真图中，除了初始化使用一个时钟以外，然后再加上8个时钟的循环操作，那么我们可以知道一次性的除法操作使用了9个时钟。在某种程度上是可以接受的。

在 streamlined_divider_module.v 文件中的步骤1~8，它多少有实验四·booth算法乘法器改进的影子。只要读者了解“时间点”的概念，就可以完全看透操作过程。（实验九和实验四有许多相似的地方。）

实验结论：

实验九的除法器，在一般的应用上还是切切有余。如果读者要它和DSP般一样任性，那么它会有点力不从心 ......

2.3 循环除法运算的原理

说一句实话，笔者是一个不喜欢“吃”课本的家伙，当然更不喜欢课本的一套作风。整数除法器不像整数乘法器那样，拥有多姿多彩的算法来简化运算，所以笔者不得不把课本中的循环除法原理往茶几上摆放。用一种傻瓜的话来说，只要了解了这些简单的原理，就算没有其他算法的补助，也能轻松的实现整数除法器。

来看一看一个公式：

被除数 = 商数*除数 + 余数

对，就是让笔者觉得厌恶的公式。如果要把这个公式以循环的方式去实现除法运算，

这个公式需要再变化：

被除数 - 商数*除数 = 余数

然后再加上简单的修改：

被除数 - 除数 = 余数    // 商数被除外

再加上一个约束：

在初始的时候：除数必须大于被除数 ： 被除数 < 除数

读者可能会产生疑问? 如果这个约束成立，那么这个公式还用得了呢？其实它是有苦衷的 .... 继续修改公式：

被除数 - 除数 * 2^M  = 余数*2 ；

如果 被除数小于除数* 2^M ，余数不变而且倍增，以示下一次运算用。商为1。

如果 被除数大于除数* 2^M ，余数等于结果并且倍增，以示下一次运算用。商为0。

啊~笔者开始烦躁起来了，还是直接用实例来解释。

实例1： 我们先不固定除数和被除数的取值范围，假设被除数A = 10 ， 除数B = 3。为了是除数 B 大于被除数 A，让 B' = B.2^m，假设m = 3 ... （ R 为余数 ， Q为商 ）

循环结束 R = 8 * 2 = 16，正确结果的 R ，Q亦即 :

正确的 R' = R / 2^m+1 = 16 / 16 = 1                                   

Q = 0011

结论：当m等于3, R = R / 2^m+1 = R / 16，循环次数等于 m +１,亦即4。

实例2： 再假设被除数A = 10 ， 除数B = 3。为了是除数 B 大于被除数 A，让 B' = B.2^m

，假设m = ４ ... （ R 为余数 ， Q为商 ）

循环结束 R = 16* 2 = 32，正确结果的 R ，Q亦即 :

正确的 R' = R / 2^m+1 = 32/ 32 = 1                                    

Q = 0 0011

结论：当m等于4, R = R / 2^m+1 = R / 32，循环次数等于 m +１,亦即5。

实例3： 再假设被除数A = 10 ， 除数B = 3。为了是除数 B 大于被除数 A，让 B' = B.2^m

，假设m = 5 ... （ R 为余数 ， Q为商 ）

循环结束 R = 32* 2 = 64，正确结果的 R ，Q亦即 :

正确的 R' = R / 2^m+1 = 64/ 64 = 1                                    

Q = 00 0011

结论：当m等于5, R = R / 2^m+1 = R / 64，循环次数等于 m +１,亦即6。

实例4： 再假设被除数A = 10 ， 除数B = 3。为了是除数 B 大于被除数 A，让 B' = B.2^m

，假设m = 6 ... （ R 为余数 ， Q为商 ）

循环结束 R = 64* 2 = 128，正确结果的 R ，Q亦即 :

正确的 R' = R / 2^m+1 = 128/ 128 = 1                                       

Q = 000 0011

结论：当m等于6, R = R / 2^m+1 = R /128，循环次数等于 m +１,亦即7。

实例5： 再假设被除数A = 10 ， 除数B = 3。为了是除数 B 大于被除数 A，让 B' = B.2^m

，假设m = 7 ... （ R 为余数 ， Q为商 ）

循环结束 R = 128* 2 = 256，正确结果的 R ，Q亦即 :

正确的 R' = R / 2^m+1 = 256/ 256 = 1                                       

Q = 0000 0011

结论：当m等于7, R = R / 2^m+1 = R /256，循环次数等于 m +１,亦即8。

从上面 5 个实例中 ，被除数A = 10，除数 B = 3 ， m 从 3 ~ 7 。上面的实例告诉了，我们一个事实。

如果以 “被除数 = 商数*除数 + 余数 ”公式实现循环除法运算，那么它必须先向该公式“修改”符合循环除法运算的形式。此外为了符合“被除数 < 除数”，“ 除数*2^m ”是必须的。当 m 从 3 ~ 7 的变化，循环除法运算都拥有一个共同点，那就是“正确的 R' = R / 2^m+1 , 然而循环次数是 m + 1。”

先给自己5分钟消化吧，笔者也消化了3天（笔者是笨蛋的关系）。比起笔者给出的例子实际上的原理还要猥琐的多。

============================ 5 分钟 ...... =============================

在循环除法运算在原理上（纯数学上），我们不会去考虑被除数A和除数B的空间（位宽）。相反的，如果把它放在Verilog HDL上，大伙也不得不谨慎。假设被除数A和除数B均为 8位 位宽。考虑到 “被除数 < 除数”的约束，m 到底要取多大呢？

我们知道 8位空间的整数，取值范围是 -127~127 ，如果抛开负值（笔者一般上都不喜欢把负值往里边算），那么取值范围会是 0~127。为了使除数B“完全”大于被除数A，m取值为 Width - 1 为最佳，亦即 7。A = { 0~127 }  小于  B = { 0 ~ 127} * 2⁷。

除此之外，我们还要考虑另一个问题：就是操作空间的大小。在这里余数 R便会成为操作空间，操作空间最理想的大小是 Width * 2 , 亦即 16位位宽。

假设被除数A和除数B均为 8位 位宽，m等于 7，那么循环次数会是 m + 1 = 8。正确的R' ，亦即 R' = R / 2⁽⁷⁺¹⁾ = R/2⁽⁸⁾。

当一切就绪以后，我们面临了最大的一个问题 ... 为了不浪费更多的时钟消耗，我们必须把步骤i看成时间点的概念，但是要如何实现呢?

case( i )

1,2,3,4,5,6,7,8; // 循环次数等于 m + 1

begin

    // " Result << 1" 倍增，亦即乘以2的意思

    if( R < Divisor ) begin R <= R << 1; Q[8-i] = 1'b0; end 

    else begin R <= ( R - ( Divisor << 7 ) ) << 1; Q[8-i] = 1'b1; end

    i <= i + 1'b1;

end

上述一段代码就是最关键的！

当完成 8 次的循环运算过后，我们知道当 m = 7 ，那么R' = R / 2^(m+1)，亦即 R' = R / 256 。如果操作空间R为 16 位位宽，那么要取得 R'也非常简单：

assign Reminder = R[15:8];

这样写就表示R' = R / 256。

好了，再给自己5分钟休息吧。如果上面的内容读者不能完全明白笔者在说什么，这也是人之常情，因为到目前为止笔者都是在强调一些零星的重点。关键还是在实验。

实验十：从原理到实现的循环除法器

other_divider_module.v

在16行是仿真输出用的 SQ_R。24~30行是该模块所使用的寄存器 ，Dsor 是用来寄存 除数的正值。_Dsor 是用来寄存除数的负值的补码形式，_Dsor 寄存器的位宽和操作空间R 一样，除了为了迎合与“时间点”概念的步骤操作外，还为了协调与操作空间R。

寄存器R 是操作空间。

在步骤0（46~56行），isNeg用来寄存除数和被除数的正负关系（49行）。Dsor 用来寄存除数的正值（50行），为了比较用。_Dsor 用来寄存除数的负值的补码形式，为了方便 A － B' 的操作（51行）。操作空间R在初始化中[7..0]是用来填入被除数的正值。

步骤1~8 ( 58~66行 )，是该模块的核心部分，也是循环操作。在每一次的循环中，先判断 R的值 是否小于 Dsor << 7 ，亦即 B' = B.2^m，m = 7。如果 if条件成立 ，操作空间R的值翻倍后，Q[8-i] 等于0。反之 R的值 大于 Dsor ，R的值减与 _Dsor << 7 ，亦即 B' = B.2^m 的值，然后将相减过后的值翻倍，并且 Q[8-i] 等于1。

步骤9~10（68~72行）是完成信号的产生。

在80行 Quotient 的输出是根据 isNeg ，亦即除数和被除数的正负关系。在81行 Reminder 的输出是 R[15:8] 驱动，同样的道理 R[15:8] 的编写方式 , 简化了

R' = R / 2^m+1 的编写。85行是操作空间R的输出仿真。

other_divider_module.vt

激励文件中 被除数和除数分别是 10 , 3 和 127 , 10 。

根据上图的仿真结果，当Dividend 为 10 ，Divisor 为 3，得到的结果 Quotient 和 Reminder 是 3 与 1。但是重点还是在步骤i（时间点·蓝色箭头），当步骤i = 0的时候，该模块“决定”初始化所有相关的寄存器，其中就包括操作空间R的[7..0]填入被除数的正值。当步骤i = 1 ~ 8，每一个时间点的“决定”，都参考该时间点“过去”的结果。

SQ_R 输出的值和上面实例5，A的值完全是一模一样。不同的是实例中是用“把大象放进冰箱”的步骤概念，实验所使用的是“时间点”的步骤概念。

实验结论：

实验九的除法器实际上是实验十除法器的简化版，它们所使用的原理都一样。由于整数除法器的种类很少，所以明白原理是一件重要的工作。