请选择 进入手机版 | 继续访问电脑版

fpga论坛|fpga设计论坛

 找回密码
 我要注册

QQ登录

只需一步,快速开始

搜索
查看: 1090|回复: 26

漫谈超前进位加法器CLA及其FPGA实现

[复制链接]
lcytms 发表于 2017-4-6 22:43:25 | 显示全部楼层 |阅读模式
漫谈超前进位加法器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具有复杂的算法,不易理解,但是它的优点是可以并行计算,能够用面积换时间,获得超快的计算速度。
 楼主| lcytms 发表于 2017-4-6 22:52:39 | 显示全部楼层
超前进位加法器的理解

参考信息:http://blog.csdn.net/rabbitxl/article/details/10164629


目前在所有的cpu中,为了提高加法的计算速度。都采用了超前进位加法器

普通的加法器我们很好理解,通常的16位行波进位加法器RCA结构图如下。

可以想象最简单的加法计算就是每一位都进行一次全加器计算,然后产生一个进行c,下一个全加器在取得进位以后再进行他的位的计算,循环下去直到最后一位。这样的问题是进行一次32位的加法计算就需要至少串行的经过32个全加器,如果CPU的频率是3Ghz,那么一个时钟周期,大约333皮秒内,是无法完成一次简单的加法运算的。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?我要注册

x
 楼主| lcytms 发表于 2017-4-6 22:54:20 | 显示全部楼层
那么超前进位加法器是如何做到高速计算的?
可以想象肯定是把计算平行化了,而且是用数量来换了速度。
但是具体是怎么做的呢?
我们来一起分析下。

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

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?我要注册

x
 楼主| lcytms 发表于 2017-4-6 23:04:48 | 显示全部楼层
本帖最后由 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中的图来说明。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?我要注册

x
 楼主| lcytms 发表于 2017-4-6 23:08:05 | 显示全部楼层
这里第一步的时候,所有的4个全加器对每一位计算出自身的和Si、Gi和Pi。
然后第二步,超前进位器计算出C1、C2、C3、C4,当然这里的C1、C2、C3、C4计算需要的逻辑门数量是逐步递增的。
然后C1、C2、C3对S1、S2、S3进行进位,C4会传递给更上面的位。
基本就是这样了。

但是由于成本的问题一般都会把32位或者64位的切割成多个16位的超前进位来进行计算,能保证在一个时钟周期内完成基本就可以了。
取得一个成本和性能上的平衡。
 楼主| lcytms 发表于 2017-4-6 23:25:23 | 显示全部楼层
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
 楼主| lcytms 发表于 2017-4-6 23:29:58 | 显示全部楼层
其调用的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
 楼主| lcytms 发表于 2017-4-6 23:34:54 | 显示全部楼层
本帖最后由 lcytms 于 2017-4-6 23:36 编辑

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

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?我要注册

x
 楼主| lcytms 发表于 2017-4-6 23:37:54 | 显示全部楼层
本帖最后由 lcytms 于 2017-4-6 23:44 编辑

编写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
 楼主| lcytms 发表于 2017-4-6 23:40:46 | 显示全部楼层
设置好仿真之后,cla4_adder仿真结果如下图。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?我要注册

x
您需要登录后才可以回帖 登录 | 我要注册

本版积分规则

QQ|小黑屋|手机版|Archiver|FPGA论坛 ( 京ICP备10035964号  

GMT+8, 2018-10-19 18:06 , Processed in 0.096143 second(s), 24 queries .

至芯科技 Powered by Discuz X3.2

© 2001-2014 Comsenz Inc.

快速回复 返回顶部 返回列表