漫谈超前进位加法器CLA及其FPGA实现
漫谈超前进位加法器CLA及其FPGA实现参考信息：
http://blog.csdn.net/rabbitxl/article/details/10164629
http://www.fpgaw.com/thread-3541-1-1.html
我们在基础阶段学习了行波进位加法器RCA（Ripple Carry Adder），这也是很多国外教材讲到的一个范例。
想必同学们对其整齐的结构和自上而下的建模方式有了很深的印象。
这种加法器采用递进式结构，非常易于理解，但是位数越多，想必运算周期也就越长。
实际应用中，通常采用的是我们今天提到的超前进位加法器CLA（Carry Look Ahead adder）。
超前进位加法器CLA具有复杂的算法，不易理解，但是它的优点是可以并行计算，能够用面积换时间，获得超快的计算速度。
超前进位加法器的理解
参考信息：http://blog.csdn.net/rabbitxl/article/details/10164629
目前在所有的cpu中，为了提高加法的计算速度。都采用了超前进位加法器。
普通的加法器我们很好理解，通常的16位行波进位加法器RCA结构图如下。
可以想象最简单的加法计算就是每一位都进行一次全加器计算，然后产生一个进行c，下一个全加器在取得进位以后再进行他的位的计算，循环下去直到最后一位。这样的问题是进行一次32位的加法计算就需要至少串行的经过32个全加器，如果CPU的频率是3Ghz，那么一个时钟周期，大约333皮秒内，是无法完成一次简单的加法运算的。
那么超前进位加法器是如何做到高速计算的？
可以想象肯定是把计算平行化了，而且是用数量来换了速度。
但是具体是怎么做的呢？
我们来一起分析下。
首先考虑所有的加法情况。
本帖最后由 lcytms 于 2017-4-7 15:38 编辑
我们用这公式来描述所有2进制加法的进位的计算公式。
Ci+1 = Xi Yi + Xi Ci + Yi Ci
这里C表示的是进位。
举个例子来说就是第一位的进位C1，它是由第零位的X0*Y0+X0*C0+Y0*C0， 这里很明显C0是始终为0的。那么C1=X0*Y0
然后这个提取公因子公式就变成了
Ci+1 = XiYi + Ci(Xi + Yi)
然后是不是发现，这样一来只有Ci是不确定的。
其它的Xi和Yi都是直接输入。
但是Ci其实呢通过循环inline（迭代）的一个替换，其实会变成类似
Ci+1 = XiYi + (Xi + Yi)（Xi-1 Yi-1 + Ci-1(Xi-1 + Yi-1)）
然后可以一直这样替换下去，直到C0这一层。或者是最右端的输入。
一般的通常会把这几个变量成为G、P变量（Generate和Propagate）
Gi = XiYi
Pi = Xi + Yi
这样理论上可以实现任何位数都在有限次内完成，但是这样的代价是位数越多需要的电路也就越多。
这里附上一张wiki中的图来说明。
这里第一步的时候，所有的4个全加器对每一位计算出自身的和Si、Gi和Pi。
然后第二步，超前进位器计算出C1、C2、C3、C4，当然这里的C1、C2、C3、C4计算需要的逻辑门数量是逐步递增的。
然后C1、C2、C3对S1、S2、S3进行进位，C4会传递给更上面的位。
基本就是这样了。
但是由于成本的问题一般都会把32位或者64位的切割成多个16位的超前进位来进行计算，能保证在一个时钟周期内完成基本就可以了。
取得一个成本和性能上的平衡。 4位超前进位加法器CLA的FPGA实现
module cla4_adder (a, b, cin, s, cout); //顶层模块
input a, b;
input cin;
output s;
output cout;
wire gg, gp; //
bitslice4 b0 (a[ 3: 0], b[ 3: 0], cin, s[ 3: 0], gp, gg);
assign cout = gg | (gp & cin);
endmodule
其调用的4个子模块如下。
以后不论位数怎么变，只会修改顶层调用的模块，以下4个子模块均不需变化。
//求和并按输出a,b,cin分组
module bitslice4 (a, b, cin, s, gp, gg);
input a,b;
input cin;
output s;
output gp,gg;
wire p,g,c;
pg4 i1 (a, b, p, g);
cla4 i2 (p, g, cin, c, gp, gg);
sum4 i3 (a, b, c, s);
endmodule
//计算传播值和产生值的PG模块
module pg4 (a, b, p, g);
input a, b;
output p, g;
assign p = a | b;
assign g = a & b;
endmodule
//计算sum值的sum模块
module sum4 (a, b, c, s);
input a,b,c;
output s;
wire t = a ^ b;
assign s = t ^ c;
endmodule
//n-bit 超前进位模块
module cla4 (p, g, cin, c, gp, gg);
input p,g; //输出的propagate bit 和generate bit
input cin; //进位输入
output c; //为每一位产生进位
output gp, gg; //传播值和进位制
assign {c,gp,gg} = do_cla4 (p, g, cin);
// function do_cla4; //该函数内将为每个位计算其进位值
function do_cla4; //该函数内将为每个位计算其进位值
input p, g;
input cin;
begin: label
integer i;
reg gp, gg;
reg c;
gp = p;
gg = g;
c = cin;
for (i=1;i<4;i=i+1)
begin
//C0=G0+P0C_1
//C1=G1+P1C0=(G1+P1G0)+P1P0C_1
gp = gp & p;
gg = (gg & p) | g;
c = (c & p) | g;
end
do_cla4 = {c,gp,gg};
end
endfunction
endmodule
本帖最后由 lcytms 于 2017-4-6 23:36 编辑
4位超前进位加法器CLA的FPGA实现架构图如下。
本帖最后由 lcytms 于 2017-4-6 23:44 编辑
编写cla4_adder的testbench。
编写cla4_adder_tb.v代码如下。
`timescale 1ns/1ps
module cla4_adder_tb;
reg a, b;
reg cin;
wire s;
wire cout;
cla4_adder dut(.a(a), .b(b), .cin(cin), .s(s), .cout(cout));
integer i;
initial begin
a = 0; b = 0; cin = 0;
forever begin
for (i=0; i<16; i=i+1) begin
#10 a = i; b = i; cin = 0;
#10 a = i; b = i; cin = 1;
end
end
end
initial #1000 $stop;
endmodule
设置好仿真之后，cla4_adder仿真结果如下图。
