Wallace树形乘法器，自动生成器(C/C++版)
学过《数字逻辑》课程的同学，对于Wallace树形乘法器应该不陌生（手拙，灵魂画师……建议读者参考网上的图片）。
总的来说，就是一个无符号数乘法器。特点是速度快，使用逻辑电路完成乘法，但是占用的资源也比较多（对于位数比较多的乘法而言）。
之前在学习李亚明老师写的书《计算机原理与设计——Verilog HDL版》时，由于其中用到了26x26的Wallace乘法器，分析了该乘法器的特点，并按照自己的思路利用C/C++语言编写了一下Wallace乘法器的生成器（设置好几位乘几位的参数后，生成可以执行的Verilog代码）。
生成器的关键在于，将项（）放到合适的一位全加器的一个输入上。全加器的当前输出位仍然在当前列，但是进位应该放到下一层的前一列全加器的输入中。
下面是6x4的Wallace代码（其中add1表示一位全加器，s表示加法结果，c表示进位）：
module wallace_tree6x4(
input [5:0] a,
input [3:0] b,
//output [5:0] sum,
//output [6:0] carry,
//output [2:0] z3,
output [9:0] z
);
wire zero = 1'b0;
reg [3:0] p[5:0];
integer i, j;
always @*
begin
for(i=0; i<6; i=i+1)
for(j=0; j<4; j=j+1)
p[i][j] = a[i] & b[j];
end
//level 1
wire [1:0] s1[10:00];
wire [1:0] c1[10:00];
// p[05][03]
add1 fa01_07_00 (p [04][03], p [05][02], zero , s1[07][00], c1[08][00]);
add1 fa01_06_00 (p [03][03], p [04][02], p [05][01], s1[06][00], c1[07][00]);
add1 fa01_05_00 (p [02][03], p [03][02], p [04][01], s1[05][00], c1[06][00]);
// p[05][00]
add1 fa01_04_00 (p [01][03], p [02][02], p [03][01], s1[04][00], c1[05][00]);
// p[04][00]
add1 fa01_03_00 (p [00][03], p [01][02], p [02][01], s1[03][00], c1[04][00]);
// p[03][00]
add1 fa01_02_00 (p [00][02], p [01][01], p [02][00], s1[02][00], c1[03][00]);
add1 fa01_01_00 (p [00][01], p [01][00], zero , s1[01][00], c1[02][00]);
// p[00][00]
//level 2
wire [10:00] s2;
wire [10:00] c2;
add1 fa02_08_00 (p [05][03], c1[08][00], zero , s2[08], c2[09]);
add1 fa02_07_00 (s1[07][00], c1[07][00], zero , s2[07], c2[08]);
add1 fa02_06_00 (s1[06][00], c1[06][00], zero , s2[06], c2[07]);
add1 fa02_05_00 (p [05][00], s1[05][00], c1[05][00], s2[05], c2[06]);
add1 fa02_04_00 (p [04][00], s1[04][00], c1[04][00], s2[04], c2[05]);
add1 fa02_03_00 (p [03][00], s1[03][00], c1[03][00], s2[03], c2[04]);
add1 fa02_02_00 (s1[02][00], c1[02][00], zero , s2[02], c2[03]);
// s1[01][00]
// p[00][00]
assign z[2] = s2[02];
assign z[1] = s1[01][00];
assign z[0] = p [00][00];
//assign z3 = z[2:0];
//assign sum = s2[08:03];
//assign carry = {s2[09]|c2[09], c2[08:03]};
assign z[09:03] = s2[09:03] + c2[09:03];
endmodule
以下是64x64位的Wallace乘法器的仿真结果：
我的计算机自带计算器只能进行32x32的乘法，没有尝试用其他语言模拟大数运算（感觉应该不会有错）。
以下是代码生成器代码：
/* 其中参数有N和M，LEVEL三个宏定义了的参数
* N和M表示乘法器位数为N*M的乘法器
* 其中LEVEL需要根据设定的N和M测试，例如（N，M，LEVEL）有（24，24，7），（8，8，4）
* 生成的代码在文件名：test1.txt
* 生成的模块的主要输入有：a[N-1:0], b[M-1:0];
* 主要输出有：z[N+M-1:0];
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define N 6
#define M 4
#define LEVEL 2
int p[N+M][N+M];
int s[LEVEL+1][N+M][N+M];
int c[LEVEL+1][N+M][N+M];
char w[3];
int a[3];
int b[3];
int t[3];
char functionName[] = "add1";
void init();
void clean(char w, int a, int b, int c);
void print(int f, int sum, int n, int l);
int fill_w_a_b(int sum, int l);
void sub_P_wab(char w, int a, int b, int c);
void getend();
int main()
{
freopen("test1.txt", "w", stdout);
init();
int T = LEVEL;
int l = 1;
int L = max(N, M);
while(T--){
cout<<"//level "<<l<<endl;
if(T > 0){
printf("\twire [%d:0] s%d[%2d:00];\n", (L-2)/3, l, N+M);
printf("\twire [%d:0] c%d[%2d:00];\n", (L-2)/3, l, N+M);
}
else{
printf("\twire [%2d:00] s%d;\n", N+M, l);
printf("\twire [%2d:00] c%d;\n", N+M, l);
}
for(int i=N+M; i>=0; i--){
int n = 0;
int sum = i;
//cout<<sum<<endl;
while(1){
int num = 0;
num = fill_w_a_b(sum, l);
print(num, sum, n++, l);
if(num <= 1)
break;
}
}
cout<<endl;
l++;
}
getend();
return 0;
}
int fill_w_a_b(int sum, int l)
{
int n = 0;
for(int i=0; i<N+M && n<3; i++){
for(int j=0; j<N+M && n<3; j++){
if((i+j)==sum && p[i][j]){
w[n] = 'p';
a[n] = i;
b[n] = j;
t[n] = -1;
n++;
}
}
}
for(int z=0; z<LEVEL; z++){
for(int i=0; i<N+M && n<3; i++){
for(int j=0; j<N+M && n<3; j++){
if(i==sum && z<l && s[z][i][j]){
w[n] = 's';
a[n] = i;
b[n] = j;
t[n] = z;
if(z == 0)
cout<<"???????1111"<<endl;
n++;
}
}
}
}
for(int z=0; z<LEVEL; z++){
for(int i=0; i<N+M && n<3; i++){
for(int j=0; j<N+M && n<3; j++){
if(i==sum && z<l && c[z][i][j]){
w[n] = 'c';
a[n] = i;
b[n] = j;
t[n] = z;
if(z == 0)
cout<<"???????2222"<<endl;
n++;
}
}
}
}
return n;
}
void print(int f, int sum, int n, int l)
{
if(f == 3){
printf("\t");
printf("%s ", functionName);
printf("fa%02d_%02d_%02d ", l, sum, n);
printf("(");
sub_P_wab(w[0], a[0], b[0], t[0]);
sub_P_wab(w[1], a[1], b[1], t[1]);
sub_P_wab(w[2], a[2], b[2], t[2]);
if(l != LEVEL)
printf("s%d[%02d][%02d], ", l, sum, n);
else
printf("s%d[%02d], ", l, sum);
s[l][sum][n] = 1;
if(l != LEVEL)
printf("c%d[%02d][%02d]", l, sum+1, n);
else
printf("c%d[%02d]", l, sum+1);
c[l][sum+1][n] = 1;
printf(");\n");
}
else if(f == 2){
printf("\t");
printf("%s ", functionName);
printf("fa%02d_%02d_%02d ", l, sum, n);
printf("(");
sub_P_wab(w[0], a[0], b[0], t[0]);
sub_P_wab(w[1], a[1], b[1], t[1]);
printf("zero , ");
if(l != LEVEL)
printf("s%d[%02d][%02d], ", l, sum, n);
else
printf("s%d[%02d], ", l, sum);
s[l][sum][n] = 1;
if(l != LEVEL)
printf("c%d[%02d][%02d]", l, sum+1, n);
else
printf("c%d[%02d]", l, sum+1);
c[l][sum+1][n] = 1;
printf(");\n");
}
else if(f == 1){
if(w[0]=='s' || w[0]=='c'){
if(t[0] != 0)
printf("\t//\t%c%d[%02d][%02d]\n", w[0], t[0], a[0], b[0]);
}
else
printf("\t//\t%c[%02d][%02d]\n", w[0], a[0], b[0]);
}
}
void sub_P_wab(char w, int a, int b, int c)
{
if(w == 'p'){
printf("%-2c[%02d][%02d], ", w, a, b);
clean(w, a, b, c);
}
else if(w == 's' || w == 'c'){
printf("%c%d[%02d][%02d], ", w, c, a, b);
clean(w, a, b, c);
}
}
void clean(char w, int a, int b, int t)
{
switch(w){
case 'p' : p[a][b] = 0; break;
case 's' : s[t][a][b] = 0; break;
case 'c' : c[t][a][b] = 0; break;
default : break;
}
}
void init()
{
memset(p, 0, sizeof(p));
memset(s, 0, sizeof(p));
memset(c, 0, sizeof(p));
for(int i=0; i<N; i++)
for(int j=0; j<M; j++)
p[i][j] = 1;
printf("module wallace_tree%dx%d(\n", N, M);
printf("\t\tinput [%d:0] a,\n", N-1);
printf("\t\tinput [%d:0] b,\n", M-1);
printf("\t\t//output [%d:0] sum,\n", N+M-LEVEL-3);
printf("\t\t//output [%d:0] carry,\n", N+M-LEVEL-2);
printf("\t\t//output [%d:0] z%d,\n", LEVEL, LEVEL+1);
printf("\t\toutput [%d:0] z\n", N+M-1);
printf("\t);\n\n");
printf("\twire zero = 1\'b0;\n");
printf("\treg [%d:0] p[%d:0];\n\n", M-1, N-1);
printf("\tinteger i, j;\n");
printf("\talways @*\n");
printf("\tbegin\n");
printf("\t\tfor(i=0; i<%d; i=i+1)\n", N);
printf("\t\t\tfor(j=0; j<%d; j=j+1)\n", M);
printf("\t\t\t\tp[i][j] = a[i] & b[j];\n");
printf("\tend\n\n");
}
void getend()
{
printf("\tassign z[%d] = s%d[%02d];\n", LEVEL, LEVEL, LEVEL);
for(int i=LEVEL-1; i>0; i--){
printf("\tassign z[%d] = s%d[%02d][00];\n", i, i, i);
}
printf("\tassign z[0] = p [00][00];\n");
printf("\t//assign z%d = z[%d:0];\n", LEVEL+1, LEVEL);
printf("\t//assign sum = s%d[%02d:%02d];\n", LEVEL, N+M-2, LEVEL+1);
printf("\t//assign carry = {s%d[%02d]|c%d[%02d], c%d[%02d:%02d]};\n", LEVEL, N+M-1, LEVEL, N+M-1, LEVEL, N+M-2, LEVEL+1);
printf("\tassign z[%02d:%02d] = s%d[%02d:%02d] + c%d[%02d:%02d];\n\n",
N+M-1, LEVEL+1, LEVEL, N+M-1, LEVEL+1, LEVEL, N+M-1, LEVEL+1);
printf("endmodule\n");
}
有疑问或者有问题或者想要提意见的读者，可以给我留言哈！