fpga論壇|fpga設計論壇

 找回密碼
 我要注冊

QQ登錄

只需一步,快速開始

搜索
查看: 3193|回復: 34
打印 上一主題 下一主題

漫談超前進位加法器CLA及其FPGA實現

[復制鏈接]
跳轉到指定樓層
1#
lcytms 發表于 2017-4-6 22:43:25 | 只看該作者 回帖獎勵 |倒序瀏覽 |閱讀模式
漫談超前進位加法器CLA及其FPGA實現

參考信息:
        http://blog.csdn.net/rabbitxl/article/details/10164629
        http://www.grhbks.tw/thread-3541-1-1.html


我們在基礎階段學習了行波進位加法器RCA(Ripple Carry Adder),這也是很多國外教材講到的一個范例。
想必同學們對其整齊的結構和自上而下的建模方式有了很深的印象。
這種加法器采用遞進式結構,非常易于理解,但是位數越多,想必運算周期也就越長。
實際應用中,通常采用的是我們今天提到的超前進位加法器CLA(Carry Look Ahead adder)

超前進位加法器CLA具有復雜的算法,不易理解,但是它的優點是可以并行計算,能夠用面積換時間,獲得超快的計算速度。
分享到:  QQ好友和群QQ好友和群 QQ空間QQ空間 騰訊微博騰訊微博 騰訊朋友騰訊朋友
收藏收藏1
2#
 樓主| 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
3#
 樓主| lcytms 發表于 2017-4-6 22:54:20 | 只看該作者
那么超前進位加法器是如何做到高速計算的?
可以想象肯定是把計算平行化了,而且是用數量來換了速度。
但是具體是怎么做的呢?
我們來一起分析下。

首先考慮所有的加法情況。

本帖子中包含更多資源

您需要 登錄 才可以下載或查看,沒有帳號?我要注冊

x
4#
 樓主| 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
5#
 樓主| 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位的超前進位來進行計算,能保證在一個時鐘周期內完成基本就可以了。
取得一個成本和性能上的平衡。
6#
 樓主| 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
7#
 樓主| 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
8#
 樓主| lcytms 發表于 2017-4-6 23:34:54 | 只看該作者
本帖最后由 lcytms 于 2017-4-6 23:36 編輯

4位超前進位加法器CLA的FPGA實現架構圖如下。

本帖子中包含更多資源

您需要 登錄 才可以下載或查看,沒有帳號?我要注冊

x
9#
 樓主| 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
10#
 樓主| lcytms 發表于 2017-4-6 23:40:46 | 只看該作者
設置好仿真之后,cla4_adder仿真結果如下圖。

本帖子中包含更多資源

您需要 登錄 才可以下載或查看,沒有帳號?我要注冊

x
您需要登錄后才可以回帖 登錄 | 我要注冊

本版積分規則

QQ|小黑屋|手機版|Archiver|FPGA論壇 ( 京ICP備10035964號  

GMT+8, 2019-6-28 17:01 , Processed in 0.107635 second(s), 23 queries .

至芯科技 Powered by Discuz X3.2

© 2001-2014 Comsenz Inc.

快速回復 返回頂部 返回列表
意甲吧