基于邏輯結(jié)構(gòu)的超前進位加法器的設(shè)計*

白首華，胡天彤

(鄭州航空工業(yè)管理學院，河南鄭州450015)

在計算機處理器中，加法器的速度直接決定了整個電路的速度，為了提高整個電路的速度，需要提高加法器的速度。因此，如何設(shè)計更高性能的加法器以滿足需要成為設(shè)計者必須思考和解決的問題。

在了解了半加器和全加器的邏輯公式及構(gòu)造的基礎(chǔ)上，本文引出4位并行的超前進位加法器的設(shè)計，再用超前進位鏈樹對16位和32位加法器進行設(shè)計，如果將這種方法推導，理論上可以得到并行超前進位的任意位加法器。

1 串行進位鏈

串行進位鏈指的是在并行加法器中的進位信號采用串行的方式進行傳遞，以4位為例:

令 Gi=AiBi，Pi=Ai⊕Bi;推導出

其中:Gi—進位生成函數(shù);Pi—進位傳遞函數(shù)。

可以用與非來實現(xiàn)，以下電路中使用的邏輯門的延時設(shè)定［1］:與或非為 1.5ty，或非門的時間延時為 1ty，與非為 ty。那么Gi、Pi形成后共需要2ty×4=8ty，所以每增加一個全加器，進位的時間就要增加2ty。因此，對于n位全加器來說，采用串行進位鏈，最長的進位時間為2nty。對于多位加法器而言，這種加法器的缺點也是顯而易見的。

2 并行超前進位鏈

通過邏輯電路事先得出加到每一位全加器上的進位輸入信號，而不是從最低位開始逐位傳遞進位信號，就可以有效地提高運算速度，節(jié)省運算時間。把實現(xiàn)這種加法的器件叫做超前進位加法器［2］(Carry look-ahead adder，CLA)。超前進位鏈能夠有效減少進位的延遲，它由進位門產(chǎn)生進位，各進位彼此獨立，不依賴于進位傳播。因此延遲非常小，速度非常高［3］。

理想狀態(tài)下是n位的全加器的n個進位信號同時產(chǎn)生，但是在實際情況下實行起來有點困難，一般在實際中，采用的是一級分組和二級分組的方法［4］。

2.1 一級分組的超前進位

將n位全加器分成若干小組，在小組內(nèi)的進位同時產(chǎn)生;小組間采用串行進位。即:組內(nèi)并行，組間串行。以4位全加器為例，將(1)式分別代入得到公式組(2):

可以看出，進位Ci不是依賴Ci－1，而是均可以直接依賴于向最低位的進位信號C－1，即當C－1輸入后，經(jīng)過與或兩級的邏輯延時就可以并行地產(chǎn)生各位向高位的進位信號C0～C3。

所以，在 Gi、Pi形成后，產(chǎn)生全部的進位需要 2.5ty，這有效地縮短了進位信號的傳送時間。

所以，以16位的全加器來說:若以4位為一組，分4組，組并行進位，組間串行進位，那么產(chǎn)生全部的 Ci共需2.5ty×4=10ty。

若采用串行鏈實現(xiàn)全部16位全加器的進位共需要2nty=2 ×16ty=32ty。

2.2 16位兩級分組超前進位加法器的設(shè)計

以16位為例，4位為一個小組，共4組，組內(nèi)實現(xiàn)超前進位，組間也可以采用超前進位算法，具體實現(xiàn)過程如下。

圖1為兩級分組第二級的超前進位鏈路線圖，從圖中可以看出，由Ai、Bi和C－1可以直接產(chǎn)生每組內(nèi)的最高進位信號 C15、C11、C7、C3。圖 2 為 Ai、Bi信號產(chǎn)生的邏輯路線圖。

圖1 二級超前進位并行進位鏈路線圖

圖2 Ai和Bi產(chǎn)生路線圖

4位的超前進位模塊作為一個小組，每組內(nèi)都采用超前進位方式，同上所述，可以得出每組內(nèi)的進位C0～C15，把每組的最高進位表示出來，分別是:

跟前描述一樣，可以推出:

可以推出公式組(4):

那么，可以得出二級分組的16位超前進位加法器的邏輯結(jié)構(gòu)圖。

綜上所述，可以推導出各級進位信號的產(chǎn)生時序:

(1)由一級分組可得，當 Gi、Pi、C－1全部產(chǎn)生后，生成Ai、Bi和 C0～C2需要用 2.5ty;

(2)再形成 C15、C11、C7、C3，需要用 2.5ty;

(3)然后產(chǎn)生其余的 C4～C6、C8～C10、C12～C14，需要用2.5ty。

因此，16位的全加器用二級超前進位算法共需要2.5ty+2.5ty+2.5ty=7.5ty。

2.3 32位超前進位加法器的設(shè)計

可以采用兩級進位算法，將32位全加器分成兩個大組(高16位和低16位)。每組又劃分四個小組，大組內(nèi)采用二級超前進位，大組間采用串行進位鏈實現(xiàn)。

由上述可知，16位二級超前進位全加器需要7.5ty，分析如下:

(1)由 Gi、Pi、C－1形成 C0～C2以及所有 Ai、Bi(i從 1 ～32)需要 2.5ty;

(2)形成 C15、C11、C7、C3，需要用 2.5ty;

(3)再生成 C4～C6、C8～ C10、C12～ C14，需要 2.5ty，由于C15為高16位全加器的組內(nèi)的C″－1，所以由(2)步驟內(nèi)的進位生成后，經(jīng)過2.5ty也生成高一組的C16～C18(相當于第一組的 C0～ C2);Ai、Bi、C15形成后，產(chǎn)生 C31、C27、C23、C19也需要 2.5ty;

(4)C31、C27、C23、C19得到后，經(jīng)過 2.5ty，形成進位 C30～C28、C26～C24、C22～C20;

因此，由(1)、(2)、(3)、(4)步驟，可以推算出32 位全加器產(chǎn)生所有進位共需要2.5ty×4=10ty，而串行方式下需要2nty=64ty。

超前進位加法器(CLA)通常被認為是最快但是也是最復雜的加法器，它的復雜度與功耗相關(guān)，越復雜，功耗就越大［5］。進位的信號產(chǎn)生時序如圖3所示。

圖3 32位CLA的進位時序圖

3 結(jié)束語

超前進位加法器是為了降低加法器的時間延遲，在設(shè)計時采用增大版圖面積來提前計算進位信號的設(shè)計思想。理想狀態(tài)下，32位的超前進位加法器運算速度是串行方式下的6倍多。因此，超前進位加法器比傳統(tǒng)的串行鏈式加法器速度上有了極大的提高。而且理論上可以得到并行超前進位的任意位加法器。

［1］毛愛華.計算機組成原理［M］.北京:冶金工業(yè)出版社，2004:248－254.

［2］陳光夢.數(shù)字邏輯基礎(chǔ)［M］.上海:復旦大學出版社，2004.

［3］Pai Yuting，Chen Yukumg.The Fastest Carry Lookahead［C/OL］//Proceedings of the Second IEEE International Workshop on Electronic Design，Test and Applications Los Alamitos，CA，USA:IEEE，2004:434 －436.

［4］［美］Wakerly J F.數(shù)字設(shè)計原理與實踐［M］.第3版.林生，金京林，葛紅，等譯.北京:機械工業(yè)出版社，2003:65－66.

［5］Jia Song，LiuFei.Static CMOS Implementation of Logarithmic Skip Adder［J］，Chinese Journal Of Semiconductors，2003，24(11):1160 －1165.