基于FPGA的数字信号处理（19）--行波进位加法器

1、10进制加法是如何实现的？

        10进制加法是大家在小学就学过的内容，不过在这里我还是帮大家回忆一下。考虑2个2位数的10进制加法，例如：15 + 28 = 43，它的运算过程如下：

个位两数相加，结果为5 + 8 = 13，结果的1作为进位传递到十位，而3则作为和的低位保留

十位的两数相加同时加上来自低位的进位1，即1 + 2 + 1 = 4，且没有向高位产生进位

        因为没有产生进位也可以看做是产生了数值为0的进位，所以我们把十位和个位都添加上来自低位的进位，以及去往高位的进位，如下：

        这样的两位数加法，实际上就拆解成两个加法器的级联了。单个加法器和2进制全加器一样，可以计算2个1位数的加法，同时接受来自低位的进位，以及产生向高位的进位，就像这样：

2、行波进位加法器RCA

        同10进制加法相加类似，2个多bits的2进制数相加，也可以通过这种级联的形式来构成。考虑2个4bits数的加法，每个全加器都可以处理它对应位数的两个数的加法，同时接收来自低级的进位，并向高位产生进位，所以它的结构是这样的：

        这样的加法器叫做 行波进位加法器 或 纹波进位加法器（Ripple Carry Adder,RCA），这个取名大概是因为它的进位传递是一级一级往外（前）扩散的，就好像水面泛起的波纹一样。

        以两个4bits数相加为例：5 + 6 = 11，即 0101 + 0110 = 1011，它的过程如下：

        根据RCA的结构，可以很快地写出它的Verilog实现形式：

//使用多个全加器级联构建RCA加法器
module rca(input   [3:0]   x,      //加数1input   [3:0]   y,      //加数2input           cin,    //来自低位的进位output  [3:0]   sum,    //和output          cout    //向高位的进位
);
​
wire    c1,c2,c3;           //进位连接
​
//例化全加器来构建RCA加法器
full_adder  u0(.x      (x[0]),.y      (y[0]), .sum    (sum[0]),.cin    (cin),.cout   (c1)
);
full_adder  u1(.x      (x[1]),.y      (y[1]), .sum    (sum[1]),.cin    (c1),.cout   (c2)
);
full_adder  u2(.x      (x[2]),.y      (y[2]), .sum    (sum[2]),.cin    (c2),.cout   (c3)
);
full_adder  u3(.x      (x[3]),.y      (y[3]), .sum    (sum[3]),.cin    (c3),.cout   (cout)
);
​
endmodule 

        这里记得把全加器的代码也要添加进工程。生成的示意图如下（虽然这个排布不能很好地看出来层次结构，但确实没错）：

        然后写个TB测试一下这个加法器电路，因为4个bits即16×16=256种情况，加上低位进位的两种情况，也才256×2=512种情况，所以可以用穷举法来测试：

`timescale 1ns/1ns              //时间刻度：单位1ns,精度1ns
​
module tb_rca();            
​
//定义变量  
reg     [3:0]   x;      //加数1
reg     [3:0]   y;      //加数2
reg             cin;    //来自低位的进位
wire    [3:0]   sum;    //和
wire            cout;   //向高位进位
​
reg [3:0]   sum_real;   //和的真实值，作为对比
reg         cout_real;  //向高位进位的真实值，作为对比
wire        sum_flag;   //sum正确标志信号
wire        cout_flag;  //cout正确标志信号
​
assign sum_flag  = sum  == sum_real;    //和的结果正确时拉高该信号
assign cout_flag = cout == cout_real;   //进位结果正确时拉高该信号
​
integer z,i,j;  //循环变量
​
//设置初始化条件
initial begin//初始化x =1'b0;    y =1'b0;    cin =1'b0;  //穷举所有情况for(z=0;z<=1;z=z+1)begincin = z;for(i=0;i<16;i=i+1)beginx = i;for(j=0;j<16;j=j+1)beginy = j;if((i+j+z)>15)begin                 //如果加法的结果产生了进位sum_real = (i+j+z) - 16;        //减掉进位值cout_real = 1;                  //向高位的进位为1endelse begin                          //如果加法的结果没有产生了进位sum_real = i+j+z;               //结果就是加法本身cout_real = 0;                  //向高位的进位为0end#5;             end endend#10 $stop();    //结束仿真  
end
​
//例化被测试模块
rca u_rca(.x      (x),.y      (y),    .sum    (sum),.cin    (cin),.cout   (cout)
);endmodule

        TB中分别用3个嵌套的循环将所有情况穷举出来，即cin=0~1、x=0~15和y=0~15的所有情况。加法运算的预期结果也是很容易就可以找出来的，就是在TB中直接写加法就行。接着构建了两个标志向量sum_flag和cout_flag作为电路输出与预期正确结果的对比值，当二者一致时即拉高这两个信号。这样我们只要观察这两个信号，即可知道电路输出是否正确。仿真结果如下：

        可以看到，sum_flag和cout_flag都是一直拉高的，说明电路输出正确。

3、RCA加法器的缺陷

        因为RCA的结构是从低到高依次级联的，所以它的进位链特别长，比如加法 1111 + 0000 + 1（最后的1表示来自低位的进位即cin），它的进位从最低位开始，需要经过4级全加器才能传递到最高级，如下：

        这条进位cin传递的路径也是拖垮整个电路速度的关键路径（Critical Path），它的长度（延迟）为 4*全加器 的延迟。可以预见，随着加法器位宽的增加，这条路径也会越来越长，所以RCA不适合位宽很大的加法，因为它的延迟实在是太高了。

        以RCA的基础组成部分全加器FA为例，它的结构是这样的：

        图中的红色路径就是关键路径，即延迟最高的路径，它由 1个异或门延迟 + 1个与门延迟 + 1个或门延迟 + 布线延迟 组成，若忽略布线延迟（和门电路延迟比起来，布线延迟相对较小），并将3种门电路的延迟都近似看做同一个数值的话，则单个全加器的延迟是 3个门电路延迟。

        这么说，从直观上感觉多个全加器构成的行波进位加法器的关键路径延迟应该是 3×全加器数量（即加法位宽），比如两个4bits数相加，其关键路径延迟应该是 4×3=12个门电路延迟，但实际上不是，我们看下具体结构：

        除了在第一个全加器有3个门电路的延迟外，后面经过的全加器都只有两个门电路的延迟，所以总共的延迟是 3 + 3*2 = 9个，由此可以推广到Nbits数，其延迟为 3 + 2×（N - 1） = 2N + 1 个门电路。

        在RCA的基础上，工程师们又设计了很多种其他的加法器结构，它们的延迟较之RCA加法器有了显著的降低，其中比较有名的一种加法器是 超前进位加法器（Lookahead Carry Adder），我们将在下一篇文章介绍它。

4、RCA加法器的参数化设计

        在上面的内容种，对RCA的举例是两个4bits数相加实现的形式，为了满足不同位宽的加法，这里也给出参数化设计形式的Verilog代码：

//使用多个全加器级联构建RCA加法器
module rca 
#(parameter integer WIDTH = 4
)
(input   [WIDTH-1:0] x,      //加数1input   [WIDTH-1:0] y,      //加数2input               cin,    //来自低位的进位output  [WIDTH-1:0] sum,    //和output              cout    //向高位的进位
);
​
wire [WIDTH:0] c_wire;          //用来连线传递的进位变量
​
assign c_wire[0] = cin;         //最低位是输入的进位
assign cout = c_wire[WIDTH];    //最高位是输出的进位
​
//用generate来例化多个模块   
genvar i;    
generatefor(i=0;i<WIDTH;i=i+1)begin:full_adderfull_adder u_full_adder(.x      (x[i]       ),.y      (y[i]       ),.sum    (sum[i]     ),.cin    (c_wire[i]  ),.cout   (c_wire[i+1]));end
endgenerate  
​
endmodule 

配套的TB也改成参数化形式：

`timescale 1ns/1ns              //时间刻度：单位1ns,精度1ns
​
module tb_rca();
​
parameter integer WIDTH = 'd4;          
​
//定义变量  
reg     [WIDTH-1:0] x;      //加数1
reg     [WIDTH-1:0] y;      //加数2
reg                 cin;    //来自低位的进位
wire    [WIDTH-1:0] sum;    //和
wire                cout;   //向高位进位
​
reg [WIDTH-1:0] sum_real;   //和的真实值，作为对比
reg             cout_real;  //向高位进位的真实值，作为对比
wire            sum_flag;   //sum正确标志信号
wire            cout_flag;  //cout正确标志信号
​
assign sum_flag  = sum  == sum_real;    //和的结果正确时拉高该信号
assign cout_flag = cout == cout_real;   //进位结果正确时拉高该信号
​
integer z,i,j;  //循环变量
​
//设置初始化条件
initial begin//初始化x = 0;  y = 0;  cin = 0;    //穷举所有情况for(z=0;z<=1;z=z+1)begincin = z;for(i=0;i<(2**WIDTH);i=i+1)beginx = i;for(j=0;j<(2**WIDTH);j=j+1)beginy = j;if((i+j+z)>(2**WIDTH-1))begin           //如果加法的结果产生了进位sum_real = (i+j+z) - (2**WIDTH);    //减掉进位值cout_real = 1;                      //向高位的进位为1end else begin                              //如果加法的结果没有产生了进位sum_real = i+j+z;                   //结果就是加法本身cout_real = 0;                      //向高位的进位为0end#5;             end endend#10 $stop();    //结束仿真  
end
​
//例化被测试模块
rca #(.WIDTH  (WIDTH)
)
u_rca(.x      (x),.y      (y),    .sum    (sum),.cin    (cin),.cout   (cout)
);endmodule

（1）把位宽width改成4

        生成的4bits加法的RCA示意图：

        仿真结果证明电路设计无误：

（2）把位宽width改成8

        生成的8bits加法的RCA示意图：

        仿真结果证明电路设计无误：

5、RCA加法器的时序性能

        为了探究RCA加法器的时序性能，需要再原有代码的基础上，做一些小小的改变：在输入和输出分别添加上寄存器。如下：

//使用多个全加器级联构建RCA加法器
module rca 
#(parameter integer WIDTH = 32
)
(input               clk,input   [WIDTH-1:0] x,      //加数1input   [WIDTH-1:0] y,      //加数2input               cin,    //来自低位的进位output  [WIDTH-1:0] sum,    //和output              cout    //向高位的进位
);
​
reg                 cin_r,cout_r;
reg     [WIDTH-1:0] x_r,y_r,sum_r;
​
wire    [WIDTH:0]   c_wire;         //用来连线传递的进位变量
wire    [WIDTH-1:0] sum_w;          //用来连线传递和
​
​
//输入寄存
always@(posedge clk)beginx_r <= x;y_r <= y;cin_r <= cin;
end
​
assign c_wire[0] = cin_r;       //最低位是输入的进位 
​
//输出寄存
always@(posedge clk)beginsum_r <= sum_w;cout_r <= c_wire[WIDTH];    //最高位是输出的进位
end
​
assign sum = sum_r;
assign cout = cout_r;
​
//用generate来例化多个模块   
genvar i;    
generatefor(i=0;i<WIDTH;i=i+1)begin:full_adderfull_adder u_full_adder(.x      (x_r[i]     ),.y      (y_r[i]     ),.sum    (sum_w[i]   ),.cin    (c_wire[i]  ),.cout   (c_wire[i+1]));end
endgenerate  
​
endmodule 

        分别例化4位加法，8位加法，16位加法和32位加法，记录它们的逻辑级数logic levels、最差建立时间裕量WNS和电路面积，并算出最大运行频率Fmax。如下：

	4位	8位	16位	32位
WNS(ns)	8.777	8.155	6.917	4.429
Fmax(Mhz)	818	542	324	180
logic levels(级)	2	4	8	16
电路面积（不考虑FF）	4 LUT	8 LUT	16 LUT	32 LUT

        从上表可以看到：

• 随着加法器位宽的增加，逻辑级数也越来越大，这是导致时序性能变差的直接原因

• 时序性能从818M相关性地降低到180M，需要说明的是这里的最大频率Fmax只能作为一个参考，因为我整个工程只添加了这么一个加法器，而且Fmax一般还和FGPA的器件强挂钩，一般的器件肯定是跑不到800M的，这里我们主要是观察这个频率降低的趋势

• 电路面积上是几位加法就用几个LUT（因为1个全加器用1个LUT），而且都是直接级联的

        作为参考，我们不使用任何加法器，就直接用加法运算符 + 来实现加法，电路就让综合工具vivado来自动生成，代码如下：

//直接写加法，看Vivado综合的结果
module rca 
#(parameter integer WIDTH = 32
)
(input               clk,input   [WIDTH-1:0] x,      //加数1input   [WIDTH-1:0] y,      //加数2input               cin,    //来自低位的进位output  [WIDTH-1:0] sum,    //和output              cout    //向高位的进位
);
​
reg                 cin_r,cout_r;
reg     [WIDTH-1:0] x_r,y_r,sum_r;
​
wire    [WIDTH-1:0] sum_w;
wire                cout_w;
​
//输入寄存
always@(posedge clk)beginx_r <= x;y_r <= y;cin_r <= cin;
end
​
assign {cout_w,sum_w} = x_r + y_r + cin_r; //直接写加法
​
//输出寄存
always@(posedge clk)beginsum_r <= sum_w;cout_r <= cout_w;
end
​
//端口连接
assign sum = sum_r;
assign cout = cout_r;
​
endmodule

        看看时序性能如何：

	4位	8位	16位	32位
WNS(ns)	8.777	8.755	8.657	8.461
Fmax(Mhz)	818	803	745	650
logic levels(级)	2	3	5	9
电路面积（不考虑FF）	4 LUT	8 LUT + 3 CARRY4	16 LUT + 5 CARRY4	32 LUT + 9 CARRY4

        从上表可以看到：

• vivado综合出来的加法电路在时序性能上明显比RCA电路要强

• 逻辑级数的增加并没有RCA电路那么明显，哪怕是32位的加法也只有9级逻辑层级。这也是它频率能跑很高的直接原因

• 4位加法使用的电路面积和RCA是一样的，因为位宽较小，综合工具直接用LUT而不是CARRY4来生成电路，二者在小位宽时的时序性能差不多

• 之所以大位宽加法的时序性能仍然比较好是因为综合工具使用CARRY4来实现加法，这种结构的加法电路有很快的进位速度，而且可以合并很多个进位链上的LUT从而减少逻辑级数

• CARRY4的使用尽管可以提高时序性能，但是也会增大一部分电路面积。当然了，拿这点面积来换性能的提升，还是十分划算的

如果你不了解CARRY4，可以看看这篇文章：从底层结构开始学习FPGA（7）----进位链CARRY4

或者看看这个专栏：从底层结构开始学习FPGA

6、总结

        行波进位加法器RCA结构简单，进位链长，时序性能差，在实际应用尤其是FPGA设计中基本不会使用。对于FPGA设计来说，如今的综合工具已经非常智能了，一般的加法还是不要自己设计加法器了，直接让综合工具生成或者用IP就行。