白首華，胡天彤

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

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

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

1 串行進(jìn)位鏈

串行進(jìn)位鏈指的是在并行加法器中的進(jìn)位信號(hào)采用串行的方式進(jìn)行傳遞，以4位為例:

令 Gi=AiBi，Pi=Ai⊕Bi;推導(dǎo)出

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

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

2 并行超前進(jìn)位鏈

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

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

2.1 一級(jí)分組的超前進(jìn)位

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

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

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

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

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

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

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

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

圖1 二級(jí)超前進(jìn)位并行進(jìn)位鏈路線圖

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

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

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

可以推出公式組(4):

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

綜上所述，可以推導(dǎo)出各級(jí)進(jìn)位信號(hào)的產(chǎn)生時(shí)序:

(1)由一級(jí)分組可得，當(dāng) 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位的全加器用二級(jí)超前進(jìn)位算法共需要2.5ty+2.5ty+2.5ty=7.5ty。

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

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

由上述可知，16位二級(jí)超前進(jìn)位全加器需要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ìn)位生成后，經(jīng)過2.5ty也生成高一組的C16～C18(相當(dāng)于第一組的 C0～ C2);Ai、Bi、C15形成后，產(chǎn)生 C31、C27、C23、C19也需要 2.5ty;

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

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

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

圖3 32位CLA的進(jìn)位時(shí)序圖

3 結(jié)束語(yǔ)

超前進(jìn)位加法器是為了降低加法器的時(shí)間延遲，在設(shè)計(jì)時(shí)采用增大版圖面積來提前計(jì)算進(jìn)位信號(hào)的設(shè)計(jì)思想。理想狀態(tài)下，32位的超前進(jìn)位加法器運(yùn)算速度是串行方式下的6倍多。因此，超前進(jìn)位加法器比傳統(tǒng)的串行鏈?zhǔn)郊臃ㄆ魉俣壬嫌辛藰O大的提高。而且理論上可以得到并行超前進(jìn)位的任意位加法器。

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

［2］陳光夢(mèng).數(shù)字邏輯基礎(chǔ)［M］.上海:復(fù)旦大學(xué)出版社，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è)計(jì)原理與實(shí)踐［M］.第3版.林生，金京林，葛紅，等譯.北京:機(jī)械工業(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.