正在学习整数乘法器。
最基本的想法是阵列乘法器，即将n*n的乘法拆成n个n位数做加法。但是这样需要进行n轮加法，性能过差。
booth编码
首先采用基-4booth编码(虽然我觉得用直接4进制阵列加法器完全可以达到一样的效果，因为期望是相同的)。利用基-4booth编码，可以将被加数从n个降至n/2个，自然提高了效率。另外如果发现被加数为0，可以跳过做加法阶段(但是好像不能和wallace兼容，毕竟wallace并行运算，且电路固定，无法也不必跳过)。
考虑$y \times x$，改写2进制下n位数的补码y:
$$\begin{align*}y&=-y_{[n-1]}\cdot 2^{n-1}+y_{[n-2]}\cdot 2^{n-2}+y_{[n-3]}\cdot 2^{n-3}+…+y_{[0]}\cdot 2^{0}\\&=(-2y_{[n-1]}+y_{[n-2]}+y_{[n-3]})\cdot 2^{n-2}+(-2y_{[n-3]}+y_{[n-4]}+y_{[n-5]})\cdot 2^{n-4}+…+(-2y_{[1]}+y_{[0]}+y_{[-1]})\cdot 2^{0}\end{align*}$$
【其中$y_{[-1]}=0$】
记$-2y_{[k+1]}+y_{[k]}+y_{[k-1]}=z_{[k]}$，那么得到
$$y=z_{[n-2]}\cdot 2^{n-2}+…+z_{0}\cdot 2^0$$
考虑$z_{[k]}$的取值情况，列出真值表，并列出相应操作($x$ 是被乘数)
| $y_{[k+1]}$ | $y_{[k]}$ | $y_{[k-1]}$ | $z_{[k]}$ | 操作 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 无 |
| 0 | 0 | 1 | 1 | +x |
| 0 | 1 | 0 | 1 | +x |
| 0 | 1 | 1 | 2 | +(x<<1) |
| 1 | 0 | 0 | -2 | +((-x)<<1) |
| 1 | 0 | 1 | -1 | +(-x) |
| 1 | 1 | 0 | -1 | +(-x) |
| 1 | 1 | 1 | 0 | 无 |
$x,-x,x<<1,(-x)<<1$可以一次性算出。
Wallace树
采用wallace树结构，即不直接进行加法，而是在每位上用类似全加器的结构，将a+b+c处理为sum(无进位加和)+carry(每位上的进位)，即将三个数的加法化为两个数的加法。这样每一层都可以将被加数的数量化为原来的2/3，然后最后只剩两个数时再采用正常加法器。因为中间各层的全加器不依赖前后进位，且仅用简单门电路连接，因此延迟很小。而最后仅做一次正常加法，这样可以很好地提高性能。
采用Wallace树，基$-4\;booth$编码实现16位整数乘法器。
待解决的疑惑：
从期望上看，采用booth编码后，对于n位乘法，平均加法次数为n/2。然而，若不采用booth编码，显然平均加法次数亦为n/2。查阅资料后也证实booth编码并不能保证比传统乘法更好的性能。那么为何多此一举地采用这种编码方式？
采用随机数验证，确认以上分析正确。即使是每次采用booth编码和传统乘法中的加法次数较小者，结果大约有15%的优化，感觉和付出的消耗不成正比。
附验证代码：
#include <iostream>
#include <ctime>
int main() {
srand(time(nullptr));
int a[17];
a[0] = 0;
long long standard = 0, booth = 0, combine = 0;
for (int i = 1; i < 1000000; ++i) {
int tmp1 = 0, tmp2 = 0;
for (int j = 1; j < 17; ++j) {
a[j] = rand() % 2;
}
for (int j = 1; j < 17; ++j) {
if (a[j]) {
++tmp1;
}
if (a[j] != a[j - 1]) {
++tmp2;
}
}
standard += tmp1;
booth += tmp2;
combine += std::min(tmp1, tmp2);
}
std::cout << "standard:" << standard / (double) 1000000 << std::endl;
std::cout << "booth:" << booth / (double) 1000000 << std::endl;
std::cout << "combine:" << combine / (double) 1000000 << std::endl;
return 0;
}