跳转至

加法器

加法器是我们在设计各种电路时最常用到的子模块之一，它的性能好坏可以显著影响到许多电路设计的性能。

在 Lab4 中，我们已经设计过了基于半加器和全加器的简单加法器。本次实验中，我们将会设计一个超前进位加法器，它能一定程度上降低加法器的延迟。

1.1 串行加法器

Lab4 中的 1bit 全加器对应的 Verilog 代码如下：

1bit 加法器
 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
module Adder_1b (
    input                   [ 0 : 0]        a, b, cin,
    output                  [ 0 : 0]        s, cout
);
wire temp_s, temp_c_1, temp_c_2;
HalfAdder ha1(
    .a(a),
    .b(b),
    .s(temp_s),
    .c(temp_c_1)
);

HalfAdder ha2(
    .a(temp_s),
    .b(cin),
    .s(s),
    .c(temp_c_2)
);
HalfAdder ha3(
    .a(temp_c_1),
    .b(temp_c_2),
    .s(cout),
    .c()
);
endmodule

那么，如何基于此搭建更多位宽的加法器呢？注意到加法运算实际上是从最低位依次向最高位进行的，来自低位的运算结果将参与高位的运算，并获得高位对应的进位结果。我们可以设计如下的 4bits 位宽加法器：

4bits 加法器
 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 Adder_4b (
    input                   [ 3 : 0]        a, b,
    input                   [ 0 : 0]        cin,
    output                  [ 3 : 0]        s,
    output                  [ 0 : 0]        cout
);
wire [ 2 : 0] temp_cin;
Adder_1b add0 (
    .a      (a[0]),
    .b      (b[0]),
    .cin    (cin),
    .s      (s[0]),
    .cout   (temp_cin[0])
);
Adder_1b add1 (
    .a      (a[1]),
    .b      (b[1]),
    .cin    (temp_cin[0]),
    .s      (s[1]),
    .cout   (temp_cin[1])
);
Adder_1b add2 (
    .a      (a[2]),
    .b      (b[2]),
    .cin    (temp_cin[1]),
    .s      (s[2]),
    .cout   (temp_cin[2])
);
Adder_1b add3 (
    .a      (a[3]),
    .b      (b[3]),
    .cin    (temp_cin[2]),
    .s      (s[3]),
    .cout   (cout)
);
endmodule

★ 1.2 超前进位加法器

串行进位加法器十分简单，但一点也不高效。对于 32bits 位宽的输入数据，输出结果需要等待低 31 位的加法进位计算完成后才能得到，这带来了极大的电路延迟。超前进位加法器就是为了解决这一问题而设计的。

简单来说，超前进位加法器的原理就是在输入的两个数的每一位上都进行预先的进位，然后再进行加法运算。这样，每位的进位都只由加数与被加数唯一决定，而与来自低位的进位无关，最终加法器的速度不会受到进位信号的限制。

超前进位的公式的推导是通过形式化地表示出加法的每一位的计算结果，再展开进位得到的。下面我们以 4 位超前进位加法器作为例子说明原理及实现。具体来说，考虑计算 \(A + B\) 的结果，其中输入的第 \(i\) 位记作\(A_i, B_i\)，进位为 \(C_i\)，和为 \(S_i\)，则有：

\[S_i=A_i\oplus B_i\oplus C_{i-1}\]
\[C_{i}=A_iB_i+(A_i\oplus B_i)C_{i-1}\]
S_i=A_i\oplus B_i\oplus C_{i-1}
C_{i}=A_iB_i+(A_i\oplus B_i)C_{i-1}

我们尝试做一代换，定义中间变量（注意，这里的中间变量都是可以直接由 A、B 计算出来的）\(G_i=A_iB_i\)，\(P_i=A_i\oplus B_i\)，则有

\[S_i=P_i\oplus C_{i-1}\]
\[C_i=G_i+P_iC_{i-1}\]
S_i=P_i\oplus C_{i-1}
C_i=G_i+P_iC_{i-1}

这一计算公式更加简洁，也更方便我们将每一位展开为以下形式：

\[C_0=G_0+P_0C_{-1}\]
\[C_1=G_1+P_1C_0=G_1+P_1G_0+P_1P_0C_{-1}\]
\[C_2=G_2+P_2C_1=G_2+P_2G_1+P_2P_1G_0+P_2P_1P_0C_{-1}\]
\[C_3=G_3+P_3C_2=G_3+P_3G_2+P_3P_2G_1+P_3P_2P_1G_0+P_3P_2P_1P_0C_{-1}\]
C_0=G_0+P_0C_{-1}
C_1=G_1+P_1C_0=G_1+P_1G_0+P_1P_0C_{-1}
C_2=G_2+P_2C_1=G_2+P_2G_1+P_2P_1G_0+P_2P_1P_0C_{-1}
C_3=G_3+P_3C_2=G_3+P_3G_2+P_3P_2G_1+P_3P_2P_1G_0+P_3P_2P_1P_0C_{-1}

上面的式子中，任意的 \(C_i\) 均只与 \(G_j, P_j, C_{-1}\) 有关，而与低位的进位 \(C_{i-1}\) 无关，因此可以先并行计算与式，再对各部求或运算，从而加快了加法器的速度。因此，我们可以得到如下的 Verilog 代码：

Adder_LookAhead4.v
 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
module Adder_LookAhead4 (
    input                   [ 3 : 0]        a, b,
    input                   [ 0 : 0]        ci,
    output                  [ 3 : 0]        s,
    output                  [ 0 : 0]        co
);

    wire    [3:0] C;
    wire    [3:0] G;
    wire    [3:0] P;

    assign  G = a & b;
    assign  P = a ^ b;

    assign  C[0] = G[0] | ( P[0] & ci );
    assign  C[1] = G[1] | ( P[1] & G[0] ) | ( P[1] & P[0] & ci );
    assign  C[2] = G[2] | ( P[2] & G[1] ) | ( P[2] & P[1] & G[0] ) | ( P[2] & P[1] & P[0] & ci );
    assign  C[3] = G[3] | ( P[3] & G[2] ) | ( P[3] & P[2] & G[1] ) | ( P[3] & P[2] & P[1] & G[0] ) | ( P  [3] & P[2] & P[1] & P[0] & ci );

    assign  s[0] = P[0] ^ ci;
    assign  s[1] = P[1] ^ C[0];
    assign  s[2] = P[2] ^ C[1];
    assign  s[3] = P[3] ^ C[2];
    assign  co   = C[3];
endmodule

对应的电路图如下：

Image title

4bits 超前进位加法器

1.3 延迟降低的理论解释

为什么超前进位加法器的延迟会比普通的加法器低呢？我们这里给出一个简单的理论解释。

如果将每个逻辑门的延迟量化为 \(t_{pd}\)（这里的逻辑门认为是可以接受任意多个输入的），那么对于一个一位全加器，由公式 \(S_i=A_i\oplus B_i\oplus C_{i-1}\)，\(C_{i}=A_iB_i+(A_i\oplus B_i)C_{i-1}\) 可知，进位信号 \(C_i\) 需要经过异或门、与门、或门各一个，总共会产生 \(3t_{pd}\) 的延迟。

那么，对于一个 4 位的串行进位加法器，由于四个全加器前后相接，每一个的计算都依赖于前一个的进位，所以共需要 \(12t_{pd}\) 的延迟。

Image title

串行加法器示意图

然而，对于超前进位加法器，可以注意到，计算出 P、G 经过了一级门电路，利用 P、G 和 \(C_{-1}\) 计算出 C 的过程中，计算与或式共经过了与、或两级门电路，最后利用 C 与 P 计算出 S 的过程中，又经过了一级异或门电路。因此，总共的延迟为 \(4t_{pd}\)。

超前进位加法器的 \(4t_{pd}\) 的延迟，相比于串行进位的 \(12t_{pd}\) 的延迟，有着显著的降低。此外，可以注意到，超前进位加法器的延迟与位数几乎无关，当位数更多时，其优势更加明显。

Tips：理论与现实

以上的理论分析是建立在理想的逻辑门延迟上的，即任意数量输入的逻辑门都只经过 \(t_{pd}\) 的延迟。而实际上，逻辑门的延迟是与其输入的数量有关的，因此，超前进位加法器的延迟并不是完全与位数无关的，但其延迟的增长速度要比串行进位加法器慢得多。

此外，超前进位加法器也并不是位数越大效果越好的。实际上，超前进位加法器在获取高性能的同时并非完全没有代价，它占用的资源更多，需要的面积也更大。这正是硬件设计中常见的时间与空间的权衡问题，这也引出了层次扩展技术的产生。

★ 1.4 层次扩展：从 4 位到 32 位

正如前面所述，超前进位加法器并非毫无代价的，它是在用空间换取时间上的优势。当我们需要计算的位数足够大，比如 32 位或 64 位时，如果完全使用超前进位加法器的方式来设计，且不谈代码的编写复杂性，其资源使用量将会是串行进位加法器的几十倍甚至上百倍，这显然是不可接受的。

那么，有没有什么方法，能在保证延迟降低的同时，又不至于占用过多的资源呢？

答案是肯定的。我们可以模仿串行进位加法器的思路，将多个超前进位加法器首尾相接串联起来。如果说每个四位超前进位加法器的延迟和资源使用量分别为 T 和 S，那么这种设计就可以以 4S 的资源，换取 4T 的延迟——这将显著优于 32 位的串行加法器。

一个 32bits 位宽的层次扩展加法器的电路示意图如下：

Image title

在硬件设计中，我们常常要面临时间与空间的权衡，许多设计在获得较好的时间性能时，都要付出较大的空间牺牲。但是，我们往往可以尝试将高速但耗费资源的设计与节省资源但低速的设计以某种方式结合起来，从而得到一个在时间和空间上都不错的设计方案。本次实验的选择性必做 3 正是对这一设计理念的体现。

参考资料

最后更新: November 21, 2023

评论

Authors: XhyDds, wintermelon008