最近整理了一下乘法器的设计方法，在此分享一下。
1.1 普通乘法器
普通乘法器的核心思想就是我们在中学时期学到的手算乘法。回想一下我们是如何计算十进制的乘法的？假设我们要计算12 x 13，首先我们计算3 x 12 = 36，左移0位得36，然后计算1 x 12 = 12，左移1位得120，然后将全部结果相加，得到36 + 120 = 156。如果将同样的方法类比到二进制的乘法上时，我们会发现，由于二进制中的比特位只有0和1两种状态，所以相乘的操作变成了a x 1 = a。因此，实际上在二进制世界中设计乘法器时，是不需要计算乘法的，只需要完成左移位操作即可。同样举个例子，假设我们要计算3'b010 x 3'b101的结果，首先是用3'b010 x 1 = 3'b010，左移0位得3'b010；然后计算3'b010 x 0 = 0，左移1位得0；最后计算3'b010 x 1 = 3'b010，左移2位得4'b1000。然后把三次计算的结果相加，得到3'b010 + 0 + 4'b1000 = 4'b1010，即是2 x 5 = 10的结果了。
算法的MATLAB代码如下：
[source lang="c"]
function [c] = mult(a,b)
c = 0;
s = 1;
if(a > b)
z = a;
a = b;
b = z;
end
while(a ~= 0)
if(bitget(a,s) == 1)
c = c + bitshift(b,s-1);
end
a = bitset(a,s,0);
s = s + 1;
end
end
[/source]
以上代码中的前段有一个乘数大小比较的部分，原因是该种乘法器的运算速度与乘数和被乘数的选取有关。正如我们在前文中提到的那样，该乘法器的主要运算工作量在于最后的移位结果相加，如果选择a和b中较小的那个数作为被乘数，则最后一步需要进行的加法运算次数就会变小。举一个极端的例子，假如我们想要计算10'b1010101010 x 1'b1的结果，如果我们选择10'b1010101010作为被乘数，按照上文描述的计算方法，则我们需要计算10'b1000000000 + 8'b10000000 + 6'b100000 + 4'b1000 + 2'b10 = 10'b1010101010。但如果我们选择1'b1作为被乘数，则我们只需要计算10'b1010101010 = 10'b1010101010即可。
由以上内容可知，在不明确乘数实际数值大小的前提下，这种普通乘法器的最大运算耗时为乘数位宽个周期，假设是32位处理器的话，则乘法器一次运算的耗时是32个周期。
1.2 布斯乘法器
普通乘法器显然还不够快，那么有没有更好的算法呢？有一个叫布斯的人发明了一种计算方法，这种方法可以在特定的情况下显著减少加法执行的次数。在讲解这种方法之前，首先我们换个思路来解释这种算法的核心思想。
假设有一个数8'b00111100，可以预见到，假设以这个数作为被乘数的话，按普通乘法的计算方式，任何数与这个数相乘都需要至少4次加法运算。但是，仔细观察我们会发现，这个数实际上可以表示为8'b01000000 - 8'b00000100，如果是这样的话，任何数乘以这个数，即a x 8'b00111100 = a x (8'b01000000 - 8'b00000100) = a x 8'b01000000 - a x 8'b00000100。在后面这个变体式中，a x 8'b01000000实际上等于将a左移6位，而a x 8'b00000100相当于将a左移2位，如果把式子中的减法看成是与一个负数相加的话，那么变形后的公式里实际上只需要执行2次加法就完成了。相比于原先普通乘法的4次加法，这是一个巨大的进步，而事实上随着乘数位数的增加，以及乘数中连续的1个数增加，这种运算量的差距会更大（当然，如果乘数中全部都是孤零零的1，则运算量反而变成了原先的2倍）。但是这种方法只可以用于计算无符号数，如果相乘的两个数是有符号数的话，需要首先判断符号位并将符号位相异或的结果保存下来（a[MSB] ^ b[MSB])，然后将负数通过取反加一的操作变成正数再完成运算。
该算法的MATLAB代码如下：
[source lang="c"]
function [c] = multbooth(a,b)
c = 0;
s = 0;
if(((a>0)&&(b<0))||((a<0)&&(b>0)))
sign = -1;
else
sign = 1;
end
a = abs(bitshift(a,1));
b = abs(b);
while(a ~= 0)
if(bitget(a,1:2) == [0,1])
c = c - bitshift(b,s);
else
c = c + bitshift(b,s);
end
a = bitshift(a,-1);
s = s + 1;
end
c = c * sign;
end
[/source]
