漫谈超前进位加法器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皮秒内，是无法完成一次简单的加法运算的。

那么超前进位加法器是如何做到高速计算的？
可以想象肯定是把计算平行化了，而且是用数量来换了速度。
但是具体是怎么做的呢？
我们来一起分析下。

首先考虑所有的加法情况。

我们用这公式来描述所有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 [3:0] a, b;
        input cin;
       
        output [3:0] 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 [3:0] a,b;
        input cin;
        output [3:0] s;
        output gp,gg;

        wire [3:0] 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 [3:0] a, b;

        output [3:0] p, g;

        assign p = a | b;
        assign g = a & b;

endmodule

//计算sum值的sum模块
module sum4 (a, b, c, s);

        input [3:0] a,b,c;
       
        output [3:0] s;
       
        wire [3:0] t = a ^ b;
         
        assign s = t ^ c;

endmodule



//n-bit 超前进位模块
module cla4 (p, g, cin, c, gp, gg);

        input [3:0] p,g; //输出的propagate bit 和generate bit
        input cin; //进位输入
        output [3:0] c; //为每一位产生进位
        output gp, gg; //传播值和进位制

        assign {c,gp,gg} = do_cla4 (p, g, cin);

//        function [99:0] do_cla4; //该函数内将为每个位计算其进位值
        function [5:0] do_cla4; //该函数内将为每个位计算其进位值
                input [3:0] p, g;
                input cin;

                begin: label
                        integer i;
                        reg gp, gg;
                        reg [3:0] c;
                        gp = p[0];
                        gg = g[0];
                        c[0] = 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[i-1] & p[i-1]) | g[i-1];
                                end
                        do_cla4 = {c,gp,gg};
                end
        endfunction

endmodule

4位超前进位加法器CLA的FPGA实现架构图如下。

编写cla4_adder的testbench。
编写cla4_adder_tb.v代码如下。
`timescale 1ns/1ps

module cla4_adder_tb;

        reg [3:0] a, b;
        reg cin;
       
        wire [3:0] 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仿真结果如下图。