1、10進(jìn)制加法是如何實(shí)現(xiàn)的？

????????10進(jìn)制加法是大家在小學(xué)就學(xué)過的內(nèi)容，不過在這里我還是幫大家回憶一下?？紤]2個(gè)2位數(shù)的10進(jìn)制加法，例如：15 + 28 = 43，它的運(yùn)算過程如下：

個(gè)位兩數(shù)相加，結(jié)果為5 + 8 = 13，結(jié)果的1作為進(jìn)位傳遞到十位，而3則作為和的低位保留

十位的兩數(shù)相加同時(shí)加上來自低位的進(jìn)位1，即1 + 2 + 1 = 4，且沒有向高位產(chǎn)生進(jìn)位

????????因?yàn)闆]有產(chǎn)生進(jìn)位也可以看做是產(chǎn)生了數(shù)值為0的進(jìn)位，所以我們把十位和個(gè)位都添加上來自低位的進(jìn)位，以及去往高位的進(jìn)位，如下：

????????這樣的兩位數(shù)加法，實(shí)際上就拆解成兩個(gè)加法器的級(jí)聯(lián)了。單個(gè)加法器和2進(jìn)制全加器一樣，可以計(jì)算2個(gè)1位數(shù)的加法，同時(shí)接受來自低位的進(jìn)位，以及產(chǎn)生向高位的進(jìn)位，就像這樣：

2、行波進(jìn)位加法器RCA

????????同10進(jìn)制加法相加類似，2個(gè)多bits的2進(jìn)制數(shù)相加，也可以通過這種級(jí)聯(lián)的形式來構(gòu)成。考慮2個(gè)4bits數(shù)的加法，每個(gè)全加器都可以處理它對(duì)應(yīng)位數(shù)的兩個(gè)數(shù)的加法，同時(shí)接收來自低級(jí)的進(jìn)位，并向高位產(chǎn)生進(jìn)位，所以它的結(jié)構(gòu)是這樣的：

????????這樣的加法器叫做 行波進(jìn)位加法器 或 紋波進(jìn)位加法器（Ripple Carry Adder,RCA），這個(gè)取名大概是因?yàn)樗倪M(jìn)位傳遞是一級(jí)一級(jí)往外（前）擴(kuò)散的，就好像水面泛起的波紋一樣。

????????以兩個(gè)4bits數(shù)相加為例：5 + 6 = 11，即 0101 + 0110 = 1011，它的過程如下：

????????根據(jù)RCA的結(jié)構(gòu)，可以很快地寫出它的Verilog實(shí)現(xiàn)形式：

//使用多個(gè)全加器級(jí)聯(lián)構(gòu)建RCA加法器
module rca(input   [3:0]   x,      //加數(shù)1input   [3:0]   y,      //加數(shù)2input           cin,    //來自低位的進(jìn)位output  [3:0]   sum,    //和output          cout    //向高位的進(jìn)位
);
?
wire    c1,c2,c3;           //進(jìn)位連接
?
//例化全加器來構(gòu)建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 

????????這里記得把全加器的代碼也要添加進(jìn)工程。生成的示意圖如下（雖然這個(gè)排布不能很好地看出來層次結(jié)構(gòu)，但確實(shí)沒錯(cuò)）：

????????然后寫個(gè)TB測(cè)試一下這個(gè)加法器電路，因?yàn)?個(gè)bits即16×16=256種情況，加上低位進(jìn)位的兩種情況，也才256×2=512種情況，所以可以用窮舉法來測(cè)試：

`timescale 1ns/1ns              //時(shí)間刻度：單位1ns,精度1ns
?
module tb_rca();            
?
//定義變量  
reg     [3:0]   x;      //加數(shù)1
reg     [3:0]   y;      //加數(shù)2
reg             cin;    //來自低位的進(jìn)位
wire    [3:0]   sum;    //和
wire            cout;   //向高位進(jìn)位
?
reg [3:0]   sum_real;   //和的真實(shí)值，作為對(duì)比
reg         cout_real;  //向高位進(jìn)位的真實(shí)值，作為對(duì)比
wire        sum_flag;   //sum正確標(biāo)志信號(hào)
wire        cout_flag;  //cout正確標(biāo)志信號(hào)
?
assign sum_flag ?= sum ?== sum_real;    //和的結(jié)果正確時(shí)拉高該信號(hào)
assign cout_flag = cout == cout_real;   //進(jìn)位結(jié)果正確時(shí)拉高該信號(hào)
?
integer z,i,j;  //循環(huán)變量
?
//設(shè)置初始化條件
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                 //如果加法的結(jié)果產(chǎn)生了進(jìn)位sum_real = (i+j+z) - 16;        //減掉進(jìn)位值cout_real = 1;                  //向高位的進(jìn)位為1endelse begin                          //如果加法的結(jié)果沒有產(chǎn)生了進(jìn)位sum_real = i+j+z;               //結(jié)果就是加法本身cout_real = 0; ? ? ? ? ? ? ?    //向高位的進(jìn)位為0end#5;             end endend#10 $stop();    //結(jié)束仿真  
end
?
//例化被測(cè)試模塊
rca u_rca(.x      (x),.y      (y),    .sum    (sum),.cin    (cin),.cout   (cout)
);endmodule

????????TB中分別用3個(gè)嵌套的循環(huán)將所有情況窮舉出來，即cin=0~1、x=0~15和y=0~15的所有情況。加法運(yùn)算的預(yù)期結(jié)果也是很容易就可以找出來的，就是在TB中直接寫加法就行。接著構(gòu)建了兩個(gè)標(biāo)志向量sum_flag和cout_flag作為電路輸出與預(yù)期正確結(jié)果的對(duì)比值，當(dāng)二者一致時(shí)即拉高這兩個(gè)信號(hào)。這樣我們只要觀察這兩個(gè)信號(hào)，即可知道電路輸出是否正確。仿真結(jié)果如下：

????????可以看到，sum_flag和cout_flag都是一直拉高的，說明電路輸出正確。

3、RCA加法器的缺陷

????????因?yàn)镽CA的結(jié)構(gòu)是從低到高依次級(jí)聯(lián)的，所以它的進(jìn)位鏈特別長(zhǎng)，比如加法 1111 + 0000 + 1（最后的1表示來自低位的進(jìn)位即cin），它的進(jìn)位從最低位開始，需要經(jīng)過4級(jí)全加器才能傳遞到最高級(jí)，如下：

????????這條進(jìn)位cin傳遞的路徑也是拖垮整個(gè)電路速度的關(guān)鍵路徑（Critical Path），它的長(zhǎng)度（延遲）為 4*全加器 的延遲?？梢灶A(yù)見，隨著加法器位寬的增加，這條路徑也會(huì)越來越長(zhǎng)，所以RCA不適合位寬很大的加法，因?yàn)樗难舆t實(shí)在是太高了。

????????以RCA的基礎(chǔ)組成部分全加器FA為例，它的結(jié)構(gòu)是這樣的：

????????圖中的紅色路徑就是關(guān)鍵路徑，即延遲最高的路徑，它由 1個(gè)異或門延遲 + 1個(gè)與門延遲 + 1個(gè)或門延遲 + 布線延遲 組成，若忽略布線延遲（和門電路延遲比起來，布線延遲相對(duì)較小），并將3種門電路的延遲都近似看做同一個(gè)數(shù)值的話，則單個(gè)全加器的延遲是 3個(gè)門電路延遲。

????????這么說，從直觀上感覺多個(gè)全加器構(gòu)成的行波進(jìn)位加法器的關(guān)鍵路徑延遲應(yīng)該是 3×全加器數(shù)量（即加法位寬），比如兩個(gè)4bits數(shù)相加，其關(guān)鍵路徑延遲應(yīng)該是 4×3=12個(gè)門電路延遲，但實(shí)際上不是，我們看下具體結(jié)構(gòu)：

????????除了在第一個(gè)全加器有3個(gè)門電路的延遲外，后面經(jīng)過的全加器都只有兩個(gè)門電路的延遲，所以總共的延遲是 3 + 3*2 = 9個(gè)，由此可以推廣到Nbits數(shù)，其延遲為 3 + 2×（N - 1） = 2N + 1 個(gè)門電路。

????????在RCA的基礎(chǔ)上，工程師們又設(shè)計(jì)了很多種其他的加法器結(jié)構(gòu)，它們的延遲較之RCA加法器有了顯著的降低，其中比較有名的一種加法器是 超前進(jìn)位加法器（Lookahead Carry Adder），我們將在下一篇文章介紹它。

4、RCA加法器的參數(shù)化設(shè)計(jì)

????????在上面的內(nèi)容種，對(duì)RCA的舉例是兩個(gè)4bits數(shù)相加實(shí)現(xiàn)的形式，為了滿足不同位寬的加法，這里也給出參數(shù)化設(shè)計(jì)形式的Verilog代碼：

//使用多個(gè)全加器級(jí)聯(lián)構(gòu)建RCA加法器
module rca 
#(parameter integer WIDTH = 4
)
(input   [WIDTH-1:0] x,      //加數(shù)1input   [WIDTH-1:0] y,      //加數(shù)2input               cin,    //來自低位的進(jìn)位output  [WIDTH-1:0] sum,    //和output              cout    //向高位的進(jìn)位
);
?
wire [WIDTH:0] c_wire;          //用來連線傳遞的進(jìn)位變量
?
assign c_wire[0] = cin;         //最低位是輸入的進(jìn)位
assign cout = c_wire[WIDTH];    //最高位是輸出的進(jìn)位
?
//用generate來例化多個(gè)模塊 ? 
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也改成參數(shù)化形式：

`timescale 1ns/1ns              //時(shí)間刻度：單位1ns,精度1ns
?
module tb_rca();
?
parameter integer WIDTH = 'd4;          
?
//定義變量  
reg     [WIDTH-1:0] x;      //加數(shù)1
reg     [WIDTH-1:0] y;      //加數(shù)2
reg                 cin;    //來自低位的進(jìn)位
wire    [WIDTH-1:0] sum;    //和
wire                cout;   //向高位進(jìn)位
?
reg [WIDTH-1:0] sum_real;   //和的真實(shí)值，作為對(duì)比
reg             cout_real;  //向高位進(jìn)位的真實(shí)值，作為對(duì)比
wire            sum_flag;   //sum正確標(biāo)志信號(hào)
wire            cout_flag;  //cout正確標(biāo)志信號(hào)
?
assign sum_flag ?= sum ?== sum_real;    //和的結(jié)果正確時(shí)拉高該信號(hào)
assign cout_flag = cout == cout_real;   //進(jìn)位結(jié)果正確時(shí)拉高該信號(hào)
?
integer z,i,j;  //循環(huán)變量
?
//設(shè)置初始化條件
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           //如果加法的結(jié)果產(chǎn)生了進(jìn)位sum_real = (i+j+z) - (2**WIDTH);    //減掉進(jìn)位值cout_real = 1;                      //向高位的進(jìn)位為1end else begin                              //如果加法的結(jié)果沒有產(chǎn)生了進(jìn)位sum_real = i+j+z;                   //結(jié)果就是加法本身cout_real = 0; ? ? ? ? ? ? ?        //向高位的進(jìn)位為0end#5;             end endend#10 $stop();    //結(jié)束仿真  
end
?
//例化被測(cè)試模塊
rca #(.WIDTH  (WIDTH)
)
u_rca(.x      (x),.y      (y),    .sum    (sum),.cin    (cin),.cout   (cout)
);endmodule

（1）把位寬width改成4

????????生成的4bits加法的RCA示意圖：

????????仿真結(jié)果證明電路設(shè)計(jì)無(wú)誤：

（2）把位寬width改成8

????????生成的8bits加法的RCA示意圖：

????????仿真結(jié)果證明電路設(shè)計(jì)無(wú)誤：

5、RCA加法器的時(shí)序性能

????????為了探究RCA加法器的時(shí)序性能，需要再原有代碼的基礎(chǔ)上，做一些小小的改變：在輸入和輸出分別添加上寄存器。如下：

//使用多個(gè)全加器級(jí)聯(lián)構(gòu)建RCA加法器
module rca 
#(parameter integer WIDTH = 32
)
(input               clk,input   [WIDTH-1:0] x,      //加數(shù)1input   [WIDTH-1:0] y,      //加數(shù)2input               cin,    //來自低位的進(jìn)位output  [WIDTH-1:0] sum,    //和output              cout    //向高位的進(jìn)位
);
?
reg                 cin_r,cout_r;
reg     [WIDTH-1:0] x_r,y_r,sum_r;
?
wire    [WIDTH:0]   c_wire;         //用來連線傳遞的進(jìn)位變量
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;       //最低位是輸入的進(jìn)位 
?
//輸出寄存
always@(posedge clk)beginsum_r <= sum_w;cout_r <= c_wire[WIDTH];    //最高位是輸出的進(jìn)位
end
?
assign sum = sum_r;
assign cout = cout_r;
?
//用generate來例化多個(gè)模塊 ? 
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位加法，記錄它們的邏輯級(jí)數(shù)logic levels、最差建立時(shí)間裕量WNS和電路面積，并算出最大運(yùn)行頻率Fmax。如下：

	4位	8位	16位	32位
WNS(ns)	8.777	8.155	6.917	4.429
Fmax(Mhz)	818	542	324	180
logic levels(級(jí))	2	4	8	16
電路面積（不考慮FF）	4 LUT	8 LUT	16 LUT	32 LUT

????????從上表可以看到：

• 隨著加法器位寬的增加，邏輯級(jí)數(shù)也越來越大，這是導(dǎo)致時(shí)序性能變差的直接原因

• 時(shí)序性能從818M相關(guān)性地降低到180M，需要說明的是這里的最大頻率Fmax只能作為一個(gè)參考，因?yàn)槲艺麄€(gè)工程只添加了這么一個(gè)加法器，而且Fmax一般還和FGPA的器件強(qiáng)掛鉤，一般的器件肯定是跑不到800M的，這里我們主要是觀察這個(gè)頻率降低的趨勢(shì)

• 電路面積上是幾位加法就用幾個(gè)LUT（因?yàn)?個(gè)全加器用1個(gè)LUT），而且都是直接級(jí)聯(lián)的

????????作為參考，我們不使用任何加法器，就直接用加法運(yùn)算符 + 來實(shí)現(xiàn)加法，電路就讓綜合工具vivado來自動(dòng)生成，代碼如下：

//直接寫加法，看Vivado綜合的結(jié)果
module rca 
#(parameter integer WIDTH = 32
)
(input               clk,input   [WIDTH-1:0] x,      //加數(shù)1input   [WIDTH-1:0] y,      //加數(shù)2input               cin,    //來自低位的進(jìn)位output  [WIDTH-1:0] sum,    //和output              cout    //向高位的進(jìn)位
);
?
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

????????看看時(shí)序性能如何：

	4位	8位	16位	32位
WNS(ns)	8.777	8.755	8.657	8.461
Fmax(Mhz)	818	803	745	650
logic levels(級(jí))	2	3	5	9
電路面積（不考慮FF）	4 LUT	8 LUT + 3 CARRY4	16 LUT + 5 CARRY4	32 LUT + 9 CARRY4

????????從上表可以看到：

• vivado綜合出來的加法電路在時(shí)序性能上明顯比RCA電路要強(qiáng)

• 邏輯級(jí)數(shù)的增加并沒有RCA電路那么明顯，哪怕是32位的加法也只有9級(jí)邏輯層級(jí)。這也是它頻率能跑很高的直接原因

• 4位加法使用的電路面積和RCA是一樣的，因?yàn)槲粚捿^小，綜合工具直接用LUT而不是CARRY4來生成電路，二者在小位寬時(shí)的時(shí)序性能差不多

• 之所以大位寬加法的時(shí)序性能仍然比較好是因?yàn)榫C合工具使用CARRY4來實(shí)現(xiàn)加法，這種結(jié)構(gòu)的加法電路有很快的進(jìn)位速度，而且可以合并很多個(gè)進(jìn)位鏈上的LUT從而減少邏輯級(jí)數(shù)

• CARRY4的使用盡管可以提高時(shí)序性能，但是也會(huì)增大一部分電路面積。當(dāng)然了，拿這點(diǎn)面積來?yè)Q性能的提升，還是十分劃算的

如果你不了解CARRY4，可以看看這篇文章：從底層結(jié)構(gòu)開始學(xué)習(xí)FPGA（7）----進(jìn)位鏈CARRY4

或者看看這個(gè)專欄：從底層結(jié)構(gòu)開始學(xué)習(xí)FPGA

6、總結(jié)

????????行波進(jìn)位加法器RCA結(jié)構(gòu)簡(jiǎn)單，進(jìn)位鏈長(zhǎng)，時(shí)序性能差，在實(shí)際應(yīng)用尤其是FPGA設(shè)計(jì)中基本不會(huì)使用。對(duì)于FPGA設(shè)計(jì)來說，如今的綜合工具已經(jīng)非常智能了，一般的加法還是不要自己設(shè)計(jì)加法器了，直接讓綜合工具生成或者用IP就行。