加法器

单个全加器

很简单：输入1bit的两个数以及前一级的进位，输出和与进位符。

1
2
3
4
5
6
7
8
9
module f_add (
    input  a,
    input  b,
    input  cin,
    output sum,
    output cout
);
    assign {cout, sum} = a + b + cin;
endmodule

行波进位加法器

我们把N个上面的全加器f_add首尾串联，便得到了一长串全加器链，它们的计算输入是N位，进位输入与输出均为1位。每次进行计算时，前一个的进位输出都会传进后一个的进位输入，看起来就像是进位在一整条全加器链上产生了波动，因此称其为“行波进位加法器”。

行波进位加法器

显然，行波进位加法器的优点是结构简单——只需串联就行，但缺点是延时太长。如上图所示，N个全加器串联后，总延时为tripple=N⋅tfat_{ripple} = N \cdot t_{fa}，这是很致命的。

超前进位加法器

上面的行波进位加法器之所以延时太长，是因为每一位的进位计算都依赖前一位，层层叠加导致计算只能串行进行。那有没有什么办法能提高计算速度，比如计算出后续的进位而不依赖前面的结果呢？有的兄弟有的。

为了方便，我们定义两个新的信号为产生信号和传播信号，并对输入数据A与B的每一位都进行计算：

  • 进位产生Generate：如果Ai和Bi均为1，那么第i位就会产生一个进位输出：

    Gi=Ai⋅BiG_i = A_i \cdot B_i

  • 进位传播Propagate: 如果Ai或Bi为1，那么第i位将把一个进位输入传播到进位输出:

    Pi=Ai+BiP_i = A_i + B_i

  • 进位输出CarryOut: 第i的进位输出Ci表达式为：

    Ci=Ai⋅Bi+Pi⋅Ci−1=Gi+PiCi−1C_i = A_i \cdot B_i + P_i \cdot C_{i-1} = G_i + P_iC_{i-1}

将上面的流程应用到每一位，因其进位求值不需要前一级的结果，而是可以直接由每一位计算出，因此称其为“超前进位加法器”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
module cla_3bit (
    input  [2:0] a,
    b,
    inputcin,
    output [2:0] cout,
    output [2:0] sum
);

    wire [3:0] p, g;

    assign p = a ^ b;  // propagate
    assign g = a & b;  // generate

    assign 
cout[0] = g[0] | (p[0] & cin),
cout[1] = g[1] | (p[1] & g[0]) |
    (p[1] & p[0] & cin),
cout[2] = g[2] |
    (p[2] & g[1]) | (p[2] & p[1] & g[0]) |
    (p[2] & p[1] & p[0] & cin);

    assign sum = p ^ {cout[1:0], cin};

endmodule

前缀加法器

观察上面的超前进位加法器，可以发现，我们并行计算每一位的进位，比原本的串行计算更快得出结果。还有什么地方可以提升速度呢？

我们使用“归约”的思想可以得到前缀加法器。前缀加法器是一种高性能的进位计算结构，其核心思想是通过前缀树结构实现多级并行归约，更高效地并行计算每一位的进位结果：

  • 计算每一位的 g 和 p;
  • 采用分层归约方式，逐步合并相邻位的 g 和 p，形成前缀树。例如Kogge-Stone结构：
    • 第一层合并相邻两位
    • 第二层合并更远的位
    • 直到所有进位都被并行计算出来
  • 进位的生成是通过多级归约实现的，层数为 log2(N)，N为位宽。
  • 最终和的计算与超前进位加法器类似。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 一个Kogge-Stone结构的3bit前缀加法器

module prefix_adder_3bit (
    input  [2:0] a,
    input  [2:0] b,
    inputcin,
    output [2:0] sum,
    output       cout
);

    wire [2:0] p, g;
    wire [2:0] c;

    // 1. 预处理
    assign p = a ^ b;  // 传递
    assign g = a & b;  // 产生

    // 2. 前缀进位计算（Kogge-Stone结构）
    // 第一层
    wire g1_0, p1_0;
    assign g1_0 = g[1] | (p[1] & g[0]);
    assign p1_0 = p[1] & p[0];

    wire g2_1, p2_1;
    assign g2_1 = g[2] | (p[2] & g[1]);
    assign p2_1 = p[2] & p[1];

    // 第二层
    wire g2_0;
    assign g2_0 = g[2] | (p[2] & g1_0);

    // 3. 进位
    assign c[0] = cin;
    assign c[1] = g[0] | (p[0] & cin);
    assign c[2] = g1_0 | (p1_0 & cin);

    // 4. 求和
    assign sum  = p ^ c;
    assign cout = g2_0 | (p[2] & p1_0 & cin);

endmodule

再来一个8bit的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
module prefix_adder_8bit (
    input  [7:0] a,    // 加数a，8位
    input  [7:0] b,    // 加数b，8位
    inputcin,  // 输入进位
    output [7:0] sum,  // 求和输出
    output [7:0] cout  // 每一位的进位输出
);

    // 1. 预处理
    wire [7:0] p, g;
    assign p = a ^ b;
    assign g = a & b;

    // 2. 前缀进位计算（Kogge-Stone结构，分层归约）
    wire [7:0] g1, p1, g2, p2, g3, p3;

    // 第一层：相邻两位
    assign g1[0] = g[0];
    assign p1[0] = p[0];
    genvar i;
    generate
for (i = 1; i < 8; i = i + 1) begin : L1
    assign g1[i] = g[i] | (p[i] & g[i-1]);
    assign p1[i] = p[i] & p[i-1];
end
    endgenerate

    // 第二层：隔1位
    assign g2[0] = g1[0];
    assign p2[0] = p1[0];
    assign g2[1] = g1[1];
    assign p2[1] = p1[1];
    generate
for (i = 2; i < 8; i = i + 1) begin : L2
    assign g2[i] = g1[i] | (p1[i] & g1[i-2]);
    assign p2[i] = p1[i] & p1[i-2];
end
    endgenerate

    // 第三层：隔2位
    assign g3[0] = g2[0];
    assign p3[0] = p2[0];
    assign g3[1] = g2[1];
    assign p3[1] = p2[1];
    assign g3[2] = g2[2];
    assign p3[2] = p2[2];
    assign g3[3] = g2[3];
    assign p3[3] = p2[3];
    generate
for (i = 4; i < 8; i = i + 1) begin : L3
    assign g3[i] = g2[i] | (p2[i] & g2[i-4]);
    assign p3[i] = p2[i] & p2[i-4];
end
    endgenerate

    // 3. 进位生成
    wire [7:0] c;
    assign c[0] = g[0] | (p[0] & cin);
    assign c[1] = g1[1] | (p1[1] & cin);
    assign c[2] = g2[2] | (p2[2] & cin);
    assign c[3] = g2[3] | (p2[3] & cin);
    assign c[4] = g3[4] | (p3[4] & cin);
    assign c[5] = g3[5] | (p3[5] & cin);
    assign c[6] = g3[6] | (p3[6] & cin);
    assign c[7] = g3[7] | (p3[7] & cin);

    // 4. 求和
    assign sum = p ^ {c[6:0], cin};
    assign cout = c;

endmodule

也可以看这一篇：树形加法器（Brent-Kung加法器） - CSDN

ALU

ALU(Arithmetic Logic Unit)，即算术逻辑单元，是计算机中负责运算和逻辑处理的核心模块。下面是一个简易的ALU结构图，包含CPSR高位的条件码标志NZCV：

可输出NZCV的简易ALU

其Verilog实现也比较简单：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
module easyALU (
    input [3:0] a,
    input [3:0] b,
    input [2:0] op,
    output n,
    z,
    c,
    v,
    output reg [3:0] r
);

    wire [3:0] m_bus, sumout;
    wire c_t, v_t1, v_t2;

    assign n = r[3];
    assign z = ~|r;

    // 1'b0为加法，1'b1为减法
    assign {c_t, sumout} = a + (op[0] ? (~b + 1) : b);

    assign c = c_t & ~op[0];
    assign v_t1 = ~(a[3] ^ b[3]);
    assign v_t2 = a[3] ^ sumout[3];

    assign v = v_t1 & v_t2 & ~op[0];

    always @(*) begin
case (op[2:1])
    2'b10:   r = a & b;
    2'b11:   r = a | b;
    default: r = sumout;
endcase
    end

endmodule

波形看起来也没啥问题：

简单ALU波形仿真

乘法器

乘法器输入俩N位宽的值，输出一个2N位宽的值。

自动综合乘法器

没啥说的必要。

1
2
3
4
5
6
7
8
9
// 自动综合版
module mul4 (
    input  [3:0] a,  // 4位乘数
    input  [3:0] b,  // 4位被乘数
    output [7:0] p   // 8位乘积
);
    assign p = a * b;

endmodule

结构化移位加法乘法器

结构化移位加法乘法器很简单：算四遍之后移位相加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 结构化移位加法实现版
module mul4_struct (
    input  [3:0] a,  // 4位乘数
    input  [3:0] b,  // 4位被乘数
    output [7:0] p   // 8位乘积
);
    wire [7:0] ab0, ab1, ab2, ab3;

    // 部分积生成
    assign ab0 = b[0] ? {4'b0, a} : 8'b0,        // a*1 or 0, 不移位
           ab1 = b[1] ? {3'b0, a, 1'b0} : 8'b0,  // a*2 or 0, 左移1位
           ab2 = b[2] ? {2'b0, a, 2'b0} : 8'b0,  // a*4 or 0, 左移2位
           ab3 = b[3] ? {1'b0, a, 3'b0} : 8'b0;  // a*8 or 0, 左移3位
    
    // 部分积相加
    assign p = ab0 + ab1 + ab2 + ab3;

endmodule

阵列乘法器

上面的乘法器依旧用到加法，最终计算是串行计算，会降低计算速度。考虑并行计算，提出了阵列乘法器：

阵列乘法器结构图 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
module array_mul4 (
    input  [3:0] a,
    input  [3:0] b,
    output [7:0] p
);
    wire [3:0] ab0 = {4{a[0]}} & b;
    wire [3:0] ab1 = {4{a[1]}} & b;
    wire [3:0] ab2 = {4{a[2]}} & b;
    wire [3:0] ab3 = {4{a[3]}} & b;

    // 第一列
    assign p[0] = ab0[0];

    // 第二列
    wire s1_0, c1_0;
    full_adder fa1_0 (.a(ab1[0]),.b(ab0[1]),.cin(1'b0),.sum(s1_0),.cout(c1_0));
    assign p[1] = s1_0;

    // 第三列
    wire s2_0, c2_0, s2_1, c2_1;
    full_adder fa2_0 (.a(ab2[0]),.b(ab1[1]),.cin(1'b0),.sum(s2_0),.cout(c2_0));
    full_adder fa2_1 (.a(s2_0),  .b(ab0[2]),.cin(c1_0),.sum(s2_1),.cout(c2_1));
    assign p[2] = s2_1;

    // 第四列
    wire s3_0, c3_0, s3_1, c3_1, s3_2, c3_2;
    full_adder fa3_0 (.a(ab3[0]),.b(ab2[1]),.cin(1'b0),.sum(s3_0),.cout(c3_0));
    full_adder fa3_1 (.a(s3_0),  .b(ab1[2]),.cin(c2_0),.sum(s3_1),.cout(c3_1));
    full_adder fa3_2 (.a(s3_1),  .b(ab0[3]),.cin(c2_1),.sum(s3_2),.cout(c3_2));
    assign p[3] = s3_2;

    // 第五列
    wire s4_0, c4_0, s4_1, c4_1, s4_2, c4_2;
    full_adder fa4_0 (.a(ab3[1]),.b(ab2[2]),.cin(c3_0),.sum(s4_0),.cout(c4_0));
    full_adder fa4_1 (.a(s4_0),  .b(ab1[3]),.cin(c3_1),.sum(s4_1),.cout(c4_1));
    full_adder fa4_2 (.a(s4_1),  .b(1'b0),  .cin(c3_2),.sum(s4_2),.cout(c4_2));
    assign p[4] = s4_2;

    // 第六列
    wire s5_0, c5_0, s5_1, c5_1;
    full_adder fa5_0 (.a(ab3[2]),.b(ab2[3]),.cin(c4_0),.sum(s5_0),.cout(c5_0));
    full_adder fa5_1 (.a(s5_0),  .b(c4_2),  .cin(c4_1),.sum(s5_1),.cout(c5_1));
    assign p[5] = s5_1;

    // 第七列
    wire s6_0, c6_0;
    full_adder fa6_0 (.a(ab3[3]),.b(c5_1),  .cin(c5_0),.sum(s6_0),.cout(c6_0));
    assign p[6] = s6_0;
    assign p[7] = c6_0;

endmodule

阵列乘法器的优点是其时间延时可预测，完成乘法所需最长时间由最右边的对角线以及最后一行来估算。两个N位数相乘的时间可以表示为：

tAM=tAND+2(N−1)tfat_{AM} = t_{AND} + 2(N-1)t_{fa}

其中tANDt_{AND}指所有的乘积项aibja_ib_j可以由一个与门阵列同时产生。

Booth编码