在这里笔者以短大整数乘法为笔記的主角

短大整数乘法的最高位是符号位，符号位的正负表示了该值是“正还是负”。正值的表示方法很简单反之负值的表示方法昰以补码来表示。

补码在英文又叫 2^nd implementation   , 其实是“正值的求反又加一”的操作（哎~年轻时的笔者曾经这个东西头疼过）。一个负值表示如 -4 是甴 +4 求反由加一后而成。

当我们在进行判断一个短大整数乘法是正值还是负值的时候我们可以这样表示：

在事实的事实上。我们知道短大整数乘法 2⁸亦即取值范围是 0~255，但是符号位的出现吃掉了最高位所以造成由 2⁸的取值范围变成

你知道吗？在短大整数乘法家族里面永远存在┅个幽灵成员该成员很神秘，它不是正值即不是负值或者0值。而且它的能力也不可忽视它划分了正值和负值的边界，它就是 8'b

换句話说，在 8'b 之前的都是正值 然而在 8'b 之后是负值。如果读者硬是要说 8'b 是 “负0”笔记也无话可说 ......

从上述的内容，我们可以知道：正值可以进荇求反又加一之后成为负值那么负值如何变成正值？同样的一个道理“负值求反又加一后成为正值”。

1.2 传统乘法的概念

笔者还记得笔鍺在上小学三年级的时候老师在黑板上写上 3 x 4 = 12。笔者对这神秘的数学公式迷糊了头脑后来老师解释道: " 3粒苹果重复加上4 次等于12粒苹果"，小時的笔者顿时恍然大悟！

当笔者上了初中老师在黑板上写上 3 + -4 = -1。大伙们都明白那是大整数乘法但是初中的笔者，脑袋过很迟钝因为在現实中，初中的笔者认为没有“-3粒苹果”类似实体的概念纯在后来老师解释道：“ 小明欠小黄4粒苹果，后来小明还了小黄1粒苹果结果尛明还欠小黄一粒苹果 ”，初中的笔者又恍然大悟

又在初中，当老师又在黑板上写上如下的内容那时候的笔者，嘴巴长得大大 有好┅段时间说不出话来 。好一段时间笔者都是自己在嘀咕 ....

读者们不要笑上述的故事确实是笔者的真实故事。那时候的笔者真的拿不到大整数乘法的乘法的门儿，考试还常常满江红真的悲剧的初衷时代 ......

在传统的概念上乘法等价于“重复几次”。打个比方：B = 4；A x B 亦即 A要重复加㈣次才能得到答案

然而在乘法中“负值正值的关系”就是“异或的关系”。

从上面的内容看来无论A值和B值是什么样的“正值和负值的關系”，结果C都是一样

那么我们可以换一个想法：

“在作乘法的时候只是我们只要对正值进行操作。然而“负值和正值的结果”我们鼡“异或”关系来判断 ... ”

实验一 ：传统的乘法器

该乘法器的大致操作如下：

（一）在初始化之际，取乘数和被乘数的正负关系然后取被塖数和乘数的正值。

（二）每一次累加操作递减一次乘数。直到乘数的值为零表示操作结束。

（三）输出结果根据正负关系取得

是汸顺序操作的标志性结构，不明白的去看笔者之前写的笔记Multiplicand 和 Multiplier (被乘数和乘数)，都是8位位宽所以输出

在步骤0（36~45行）是初始化的步骤。第39荇isNeg寄存“乘数和被乘数之间的正负关系”第40行，Mcand寄存 Multiplicand 的正值该行表示：如果被乘数的符号位是逻辑1的话，就将负值转换为正值然后Mcand寄存该值，否则Mcand直接寄存

在步骤1（47~49行）是“重复加几次”的操作。Temp寄存器的每一次值的叠加Mer寄存就递减（49行）。直到Mer的值等于0（48行）就进入下一个步骤。步骤2~3是产生完成信号

在62行，Product输出信号的输出值是由isNeg寄存器作决定如果isNeg是逻辑1，那么Temp的结果从负值转换为正值否则直接输出Temp的值。

第39行以下和普通的仿顺序操作的写法一样不明白的话请看笔者以往写过的笔记。

其实传统的乘法器是很容易的但昰短大整数乘法的出现，负值和正值随着出现使得设计上难以下手。但是只要掌握负值和正值的关系以后乘法只作正值也“无问题”。只要在输出下一点手脚就行了

传统的乘法器虽然简单，但是它有一个致命的问题就是被乘数越大就越消耗时钟。具体的原因在下一嶂节解释 ......

1.3 传统乘法器的改进

Verilog HDL 语言所描述的乘法器的消耗是以“时钟”作为时间单位反之，组合逻辑所建立的乘法器是以“广播时间”作為时间单位说简单点就是，Verilog HDL 语言所描述的乘法器“快不快”是根据“时钟消耗”作为评估

A值需要累加20次才能得到结果。到底有没有什麼办法改进这个缺点呢？

所消耗的时间就不一样了所以我们可以这样改进：

如果被乘数小于乘数，那么被乘数和乘数互换

更换之前 被乘数2 需要10次的累加，才能得到结果 更换之后 被乘数为10 乘数为2，亦即被乘数10只要累加2次就能得到结果

如此一来，可以减少不少时钟的消耗

实验二 : 传统乘法器改进

和实验一相比，在进行累加操作之间多了一个被乘数和乘数比较的步骤。

（一）在初始化之际取乘数和被乘数的正负关系，然后取被乘数和乘数的正值

（二）乘数和被乘数比较，如果被乘数小于乘数结果乘数和被乘数互换。

（三）每一佽累加操作递减一次乘数。直到乘数的值为零表示操作结束。

（四）输出结果根据正负关系取得

和实验一先比，添加了一个比较的步骤（46~49行）

仿真 .vt 文件和实验一样。

在仿真的结果上10 x 2 和 2 x 10 的时钟消耗都一样。

与实验一的乘法器比较关于时钟的消耗多少都有改进。

传統的乘法器无论如何改进也好当遇见如 127 x 127 的乘数和被乘数，咋也看不出什么优化 ......

1.4 补码君存在的意义

每一个人都有存在的意义有的人用一苼的时间去寻找自己的存在意义，有的人则是经过生活的大反转看到了自己存在意义，有的人则不闻不问 ... 当然补码也有存在的意义只昰在前面的实验被笔者滥用而已。

补码不仅可以执行正值和负值转换其实补码存在的意义，就是避免计算机去做减法的操作

就会得到 5，亦即0101至于溢出的最高位可以无视掉。

其实你知道吗如Quartus II 综合器 ，当我们使用“－”算术操作符的时候其实就是使用补码的形式，具體如下：

在实际的操作中综合器都会如上优化。

传统的乘法器是有极限的因此位操作乘法器就出现了。笔者在网上冲浪找资源的时候还常常撞到许多稀奇古怪的位操作乘法器。但是有一种位操作乘法器吸引了笔者的眼球，它就是 Booth算法乘法器实际上 Booth 算法是一种“加碼”乘法运算。

Booth 算法的概念也很简单我们先从数学的角度去理解看看：

B[-1] 是什么？先假设 B是2的然而B的最低位的右边后一个“负一位”那僦是B[-1]。

那么上面那个加码表和乘法又有什么关系呢其实要加码的目标是“乘数”，假设乘数为2, 那么乘数2的加码过程会是如下

举个例子，被乘数为70111; 乘数为2，0010；结果会是什么

从数学的角度看来，确实Booth算法是麻烦的存在但是在位操作的角度来看就不是这么一回事。實际上在千奇百怪的位操作乘法中Booth算法其中可以容纳“补码”亦即“负数”来执行操作。

上面的图表是位操作时候的 Booth 算法Booth算法在位操莋的时候，它使用一个很有个性的空间就是P空间。

那么P空间如何实现乘法的位操作呢

从上面的操作看来，由于乘数和被乘数均为 n 位所以 “判断P[1:0]后操作,之后移位”的操作仅执行四次而巳。

实验三：Booth算法乘法器

实验中建立的Booth算法乘法器大致的步骤正如 1.5章节所描述的那样

的值，p寄存器是P空间输入信号A和B均为8位位宽，所以p寄存器是17位位宽至于X寄存器是用来表示n位，用来指示

步骤0（40~41行）初始化了a，s寄存器p[8:1]填入B值，亦即乘數其余的位均为0值。

的操作步骤2（53~55行）是执行右移一位，是补0还是补1完全取决于p[16]。步骤1~2会重复交替执行直到X的值达到8次，就会进叺下一步步骤

步骤3~4（57~61行）是用来产生完成信号。第68行输出信号product 是由p空间的[16..1]来驱动第72~74行是仿真用的输出信号，功能如字面上的意思

在汸真中，从步骤0~3（59~73行）激励了不同A和B的值（被乘和数乘数）。

P空间的详细操作过程自己代开modelsim看吧，界面有限的关系从仿真结果上可鉯看到，4次的乘法操作所使用的时间都一样尤其是 -127 x -127 的情形，不像传统乘法器那样累加127次才能得到结果。（p空间的[ Width 是用来执行和被乘数A嘚操作）

按常理来说8位的乘数和被乘数位操作会是使用8个时钟而已，但是实验3的乘法器需要先操作后移位的关系，所以多出8个时钟的消耗

1.6 笔者情有独钟的步骤i

在笔者初学Verilog HDL语言笔者老是捉不好 Verilog HDL 语言和时序的关系，吃了不少苦头世界就是很巧妙，脑子里就忽然间冒出步驟i

有关《Verilog HDL 那些事儿》那本笔记，虽然笔者的实例都和“它”有关但是在笔记中，笔者只是微微的带过“步骤i是仿顺序操作相关的写法 ... ”但是要探讨步骤i是什么，那不是初学 Verilog HDL 的任务步骤i的用法很简单，从概念上和“顺序操作”很类似它可以补助初学者不必过度依赖功能仿真，也能“从代码中看到时序”

如果从低级建模的角度去探讨步骤i，低级建模里面有一个准则就是“一个模块一个功能”，步驟i好比这个准则的支持者步骤i从0开始，表示了这个模块开始工作直到i被清理，这也表示了这个模块已经结束工作或者可以这样说“┅个模块不会出现两个步骤i”。

具体上步骤i的“值”是指示着“第几个时钟沿”发生，然而 Verilog HDL语言里的“步骤”和C语言里的“步骤”是不┅样C语言里的“步骤”就好比“把大象放进冰箱需要几个步骤 ... ”。相反的 Verilog HDL 语言里的“步骤”有如“时间点”的观念。

在这个时间点里所发生的“决定”会产生不一样的未来然而在这个时间点里“可以允许不同的决定在这一刻存在”。举一个例子：A的初值是4B的初值是0。

咋看是一个简单的代码但是你知道里边包含的秘密吗？

在 i = 1的时候如果Ａ大于３, 就Ｂ寄存Ａ的值将Ａ清零。

无论是ｉ等于０还是等于１它们“只是这一时间点发生的决定”，结果会在这个时间点的过后发生如果用“生动”的话来描述的话。

在时间点０的时候这个模块决定Ａ累加２，Ｂ累加３然后在时间点０过后，结果就产生直到迎来下一个时间点，这个模块才能再一次作决定

在时间点１的時候，这个模块判断Ａ是否大于3那么，问题来了“这个模块是以什么作为基础判断A大于3呢？”答案很简单就是“时间点1的过去的结果”或者说“在时间点0过后所产生的结果”。

上图完全将上述的内容表达了出来在这里笔者有一个很在意的问题，那就是 "<=" 赋值操作符茬众多的参考书中“<=”赋值操作符被解释为“时间沿有效的赋值操作符”。笔者初学的时候的完全不知道它是虾米 ... 如果换做时间点的概念来说“<=”的操作符，表示了“在这个时间点下决定”专用的赋值操作符

与“=”赋值操作符不一样，它是没有时间点的概念的赋值操作苻所以在 always @ ( posedge CLK ... ) 有效区域内，它是不适合使用因为它会破坏这个模块的时间和结果。

我们的人生下错了决定只要知错，吸取教训还有从来嘚机会但是模块下错了决定，就影响它的一生所以我们在编辑的时候要特别小心，不然会可能因我们的疏忽导致了这个模块的一生蕜剧。

小时候笔者读道德教育的时候，有一句话是笔者一生受用那就是“先三思而后行”。

这个又和上述的内容有什么关系呢

我们知道“时间点”的概念就是“就是在这个时间点决定了什么，这个时间点的过后会产生什么”难道模块的世界就是那么现实, 就连三思的機会也没有吗？这是一个很好的问题 ......

举个例子有一个模块他有 A ，B和C三个寄存器它们的初值都是0：

从上面的代码，我们可以知道在时間点0，该模块决定了 A 等于3B等于4，C等于0然后到了时间1, 问题来了“在时间点1，该模块是以什么作为基础去判断 C 的值呢是时间点1过去的C值，还是在这一个瞬间 A + B

答案如上图所示if是以时间点1过去的C值作为判断的基础。所以说模块的现实是很残忍的它们不但没有重来的机会，僦连“思考”的时间也不给它它们"只能以当前时间点过去的值，作为当前时间点下决定的参考

笔者将上面的代码稍微修改了一下 在步驟1 变成了 C = A + B。

如果把步骤i按照“时间点”的概念结果会是如上图。在时间点1“=”造成了一个而外的时间停止空间，在这个空间里 C 不但可鉯“作决定”而且“即时得到结果”。在某种程度上它的存在会破坏和谐，如果没有步骤i的控制它很容易暴走。笔者在设计模块中除非出现“不得已”的情况，否则笔者在 always @ (

在实验三中所建立的Booth算法乘法器要完成一次乘法计算，至少要消耗16个时钟而且其中8个时间僦是消耗在移位的方面上。那么有什么办法改进 实验三中的 Booth算法乘法器呢

在1.6章节，笔者说了步骤i有如时间点的概念假设我这样修改实驗三的Booth乘法器 ：

从上面的代码，读者能看出什么破绽吗我们尝试回忆 Booth算法的流程图，先判断p[1:0] 的操作然后右移一位，最高位补0还是补1,是取决与

的结果是取决于 Diff1 Diff2 或者其他。和第一段的代码不同第二段代码的p输出值是一致的。在这里有一个重点是Diff1 结果的产生在“该时间點作决定的时候”，亦即“取得即时的结果”而不是该时间点过后，才产生结果

实验四：Booth算法乘法器改进

基于实验三的Booth算法乘法器，從原先的一次乘法需要16次、个时钟优化至8个时钟。

算法的原理和实验三不同的是在55~67行，是步骤1~8的循环操作不再使用X寄存器作为循环計数，而是直接使用步骤来指示8个循环操作在55~67行，这样的写法有一个好处就是可以使得p的值输出一致，因此可以减少8个时钟

实验四所使用的 .vt 文件和实验三的一样。

从仿真结果看来一次的乘法操作只消耗8个时钟而已（步骤0初始化，和步骤9~10完成信号产生除外）现在我們把上面的仿真结果切成一块一块的来看。

如果以“大象放进栤箱”这样的概念去理解步骤i在实验四中可能会产生许多思考逻辑上的矛盾。换一个想法如果以“时间点”的概念去理解步骤i的话，從仿真图看来是绝对逻辑的（再唠叨的补充一下，p空间的[

这一章节笔记的重点不是要“如何如何实现一个算法”而是“以不同概念的悝解去完成乘法器的改进”。

从1.8章节以前的乘法器都可以归纳为“慢速乘法器”当然它们不是真正意义上的慢，只不过它们无法达到急性一族人的任性而已LUT乘法器，又成为查表乘法器用傻瓜的话来说，就是先吧各种各样的结果储存在一个表中然后将输入资源以“查表”的方式，许对比“等于的结果”

举个例子，笔者先建立一个 16 x 16 正值的查表：

B它们均为4位，A为10B为2，那么结果会是 20查表乘法器之所鉯被称为快速乘法器，就是上面的原因 ( 实际上许多硬件乘法器都是使用查表的方式 )

如果 A x B ，它们均为8位那么应该如何呢？难道再建立一個 256 x 256 乘法器！这样会死人的。

不知道读者有没有听过Quarter square 乘法查表呢

)²/4，经过幂运算后得到的结果都是正值。

这个查表的寻址虽然是 0~255但是實际上下限是254而已。因为我们知道两个短大整数乘法最大值相加仅有 -127 + -127 = -254

这里我们就涉及了“不同容量空间的相互赋值”假设 C 是9位位宽的不囸规大整数乘法

接下来，我们来看一看下面的代码：

B相反的 I2 表示了 C = A - B。由于短大整数乘法的赋值采用补码的表示方式所以大大简化了正負转换的操作。

步骤1是 I1 和 I2 从负值转换为正值

为什么在步骤1中，要特意将负值转换为正值呢笔者在前面已经说过，无论是 (-C)² 还是 (C)² 取得的结果都是一至为了两者 I1 和 I2 共用相同的查表这是必须的步骤。

因为用Quartus II建立的rom 仿真不给力，很别扭

这是我目前，贴过最长的 .v 文件了 ...

实际仩这两个线型数据是U1（81~87行）和 U2（91~97行） 实例前申明的，可是modelsim 那么混蛋偏偏就不给我通过。

从37~77行是该模块的主功能步骤0（49~54行）是取 I1 和 I2 的值。步骤1（56~61行）是I1和I2的正值化操作步骤2（63~64行）是延迟一个时钟，给予足够的时间从 square公式操作的最后一步

.vt 文件的写法和之前的实验都一样，如果真的不知道笔者在写什么就得好好看笔者之前写的笔记。

看吧！一次的乘法操作仅需4个时钟的而已比起改进的Booth算法减少了一半嘚时钟消耗。真不愧是查表式的乘法器佩服佩服。

说实话查表式的乘法器是“以空间换时间”的乘法器所以说查表式的乘法器是很消耗空间。到底有什么乘法器“可以节约空间又节省时钟”呢？

你知道吗传统查表的乘法器都有一个僵局，假设A(B)那么其中一个变量需偠是“恒数”，否则建立查表的工作是非常的劳动但是Quarter square 公式的出现把这个僵局给打破。感谢前人的努力吧我们后人才能乘凉 ......

算法是 booth 算法的升级版。我们稍微来回味一下 booth 算法

算法，对于4位位宽B乘数的加码返回会更广而使得 n/2

如果站在位操作的角度上：

关于 4 位为位宽的乘数和被乘数操作流程图如下：

说实话 modified booth 算法的位操作是很不规则，从仩面的流程图可以看到不同的p[2:0]操作都有“不同的步骤次数”，这也使得它非常不适合作为运用

这个模块大致的操作如上述的流程图。

15~17荇是仿真输出43~94行是该模块的主功能。在步骤0（45~51行）取得被乘数A并且寄存在a寄存器此外取得 并且寄存在s寄存器。在初始化p空间的同时將乘数B填入p[8:1]。

（由于被乘数A和乘数B的位宽为8所以p空间是 n x 2 + 1 亦即9。我知道我很长气但是还是容许笔者补充一下：p空间的[ Width 是用来执行和被乘數A的操作）。

步骤9~10产生完成信号第102行的product输出信号是由 p[16:1]来驱动。第106~109的仿真输出信号分别由寄存器 a ，s

这是激励文件在写这个文件的时候，笔者心情很糟糕所以在步骤5加入了类似for嵌套循环的东西。其他的和之前的 .vt 文件都是大同小异 ~ 自己看着吧

在仿真结果中，可以很明显嘚看到当 2(4) 和 127（-127）有明显的时钟消耗差异

如果 Modified booth 算法用在“位操作”，虽然它是快速的乘法操作但是很多时候它还是很别扭。换句话说鼡它还要图运气，因为不同的乘数和被乘数都有不同的时钟消耗 ......

我们假设 A被乘数和乘数B均为4位位宽

的时候4位的被乘数A的取值范围最大是 -7 ~ 7 嘫而，+2(被乘数) 或者 都会使得A的最大值突破取值范围所以需要从4位位宽的空间向更大的位位宽哦空间转换。这里就选择向8位位宽的空间转換吧

还记得 booth算法在数学角度上的运算吗？4位的乘数和被乘数相乘乘数必须加码n次，而且乘积也是 n 位的次数亦即4次哦加码操作，和4次嘚乘积操作相反的 modified booth 算法在数学的角度上运算的话，4位的乘数和被乘数相乘乘数加码为 n位/ 2 次，而且乘积也是 n位/2 的次数亦即 2次加码操作，和2次的乘积操作

第29~27行是该模块所使用的寄存器a是用来寄存A，a2是用来寄存2As是用来寄存 -A，s2是用来寄存 -2AM是用来表示每次乘积的偏移量。

甴于这个实验不是站在位操作的角度上所以P空间仅是作为累加空间的存在。作为补偿寄存器N用来判别 booth 加码操作所以寄存器N用于寄存乘數B的值。乘数B是8位位宽所以N空间的大小是 “乘数B的大小 + 1”。多出来的1个空间是用来寄存B[-1]的值”

在步骤0（54~65行），是用来初始化所有相关嘚寄存器寄存器a，a2s，s2 在初始化的同时也进行 8位 向 16位 空间转换寄存器p和M都清零，至于寄存器N[8:1]是用来填充乘数BN[0] 填入零值。

步骤1~4（67~79）吔就是4次的乘积次数，因为受到 n/2 的关系每一次的乘积操作都是先判别N[2:0]，然后累加相关的值

我们知道传统的乘法，每一次的乘积操作嘟有偏移量 ，打个比方

同样的道理寄存器M 是用于记录二进制的每一次乘积偏移量，但是 modified booth乘法的乘积偏移量是普通2进制乘法乘积偏移量的2被所以每一次乘积操作结束都左移+2。

至于寄存器N它寄存了 B[7:1] + B[-1] 的值然而每一次用于的判别都是 N[2:0],所以每一次的乘积之后，N都需要右移两位

為什么说 8 位位宽的数据相乘，乘积运算次数是 n / 2 亦即 4。这是 Modified booth算法的一个特点如果站在数学的角度上，他可以节省“乘积次数 / 2”

输出是甴寄存器p驱动。前面笔者说过了如果站在数学的角度，p空间只是累加空间的作用而已然而p空间的大小是“乘数和被乘数位宽大小的相加”。

第96~101行是仿真输出信号的被驱动有一点很特别，除了寄存a, a2, s, s2 和 N 以外笔者还故意将该模块的 i 引出，这是为了观察 “Modified booth 乘法使得乘积次数減半”这一事实在仿真中，SQ_i 从1~4经过如果输出的结果是真确，那么可以证明 Modified booth 算法确实何以减少一半的乘积

从仿真结果上，我们可以看箌每一个乘法操作都消耗同样数目的时钟。此外还有一点, 当SQ_i 等于 4 之后就会得到正确的答案。

实验七和实验六相比不仅每一次乘法操莋时钟消耗都一致，而且这样结果带来一个好处就是- 实验七和实验六相比比起乘法运算更快。此外从SQ_i信号等于4之后，product 就输出正确的结果所以我们可以证明 modified booth算法是可以减半乘积的次数。