引言

在全加器設(shè)計中運用PG邏輯是非常普遍的，本文在設(shè)計和研究全加器時，根據(jù)現(xiàn)有的PG邏輯公式推導(dǎo)出了一種新的邏輯公式，并論證了兩者之間的等價關(guān)系。這一新的公式能夠指導(dǎo)全加器設(shè)計中的連線方式，靈活更改連線策略。本文將從基本原理開始逐步引出該公式，對其進行論證，并應(yīng)用于全加器設(shè)計中。

　全加器設(shè)計的

基本原理

N位全加器將{AN，……，A1}、{BN，……，B1}和進位輸入Cin作為輸入，計算得到和{SN，……，S1}以及最高位的進位輸出Cout(見圖1)。每一位得到的和與進位輸出都直接受其上一位的影響，其進位輸出也會影響下一位。最終，整個全加器的和與輸出都受進位輸入Cin的影響。

圖1 N位全加器

圖2 多位組傳播Cin 或者直接產(chǎn)生進位輸出

全加器最簡單的構(gòu)成方法就是把每一位的進位輸出與下一位的進位輸入簡單地連接起來，得到的就是行波進位全加器。但在快速全加器中，是將加數(shù)和被加數(shù)中具有相同下標的位分成若干組，即多個多位組，并將各個多位組看作一個整體。通過計算多位組的PG邏輯，在求和之前可預(yù)測多位組的進位輸出是傳播進位輸入還是直接產(chǎn)生進位輸出。多位組所包括的位在i到j(luò)的范圍內(nèi)(見圖2)，如果該多位組的進位輸出是與進位輸入無關(guān)的“真”值，那么它就產(chǎn)生了一個進位;如果該多位組的進位輸出只有當進位輸入為“真”時才進位輸出“真”值，那么它就傳播了一個進位。對于i≥k≥j，這些信號能夠遞歸地定義為：

Gi:j=Gi:k+Pi:kGk-1:j;Pi:j=Pi:kPk-1:j

其中 Gi:i≡Gi=AiBi;Pi:i≡Pi=Aii;定義 G0:0=Cin;P0:0=0

通過觀察可知，第i位的進位輸出總是與Cin有關(guān)，所以有Ci=Ci:0，和Si=Ai臖i臗i-1=Pii臛i-1:0。由此可見，只要算出各位的Pi:i值和Gi:0值，就可以將各位的Si值求出。而其中最關(guān)鍵的就是利用遞歸公式快速算出各Gi:0值。上述遞歸表達式可以用如圖3所示的電路表示。

圖3 遞歸表達式的對應(yīng)電路

為了能夠更加簡潔地表達全加器電路結(jié)構(gòu)，可將圖3中的電路用圖4所示的黑色單元表示，并用圖4中的白色單元表示圖5所示的G邏輯產(chǎn)生電路。

圖4 黑色單元和白色單元

圖5 G邏輯產(chǎn)生電路

根據(jù)遞歸公式，可以得到各種不同結(jié)構(gòu)的全加器，他們的邏輯級數(shù)、扇出、布線通道數(shù)、所用單元數(shù)等各不相同，在此不再贅述，只給出一種Kogge-Stone樹型全加器PG網(wǎng)絡(luò)，如圖6所示。圖的上部即是各位的本位Pi:i和Gi:i產(chǎn)生邏輯，中部是PG傳播網(wǎng)絡(luò)，下部是各位的進位輸出Ci。這種樹型全加器具有理想的邏輯級數(shù)和扇出，但是連線復(fù)雜，也需要更多的單元。

圖6 Kogge-Stone樹型全加器PG網(wǎng)絡(luò)

　等價型PG邏輯的論證

對上文給出的遞歸表達式進行進一步推導(dǎo)，可得出如下結(jié)果：Gi:j=Gi:k+Pi:kGk-1:j=Gi:k+Pi:kGk:j(Gk-1:j可用Gk:j替代)

下面給出它的簡單推導(dǎo)過程：

因為，Gk:j=Gk:k+Pk:kGk-1:j

所以，Gi:k+Pi:kGk:j=Gi:k+Pi:k(Gk:k+Pk:kGk-1:j)=Gi:k+Pi:kGk:k+Pi:kPk:kGk-1:j

將Gi:k展開以后，上式=Gi:k+1+Pi:k+1Gk:k+Pi:kGk:k+Pi:kPk:k Gk-1:j

因為，Pi:k=Pi:k+1Pk:k=Pi:kPk:k

所以，上式=Gi:k+1+Pi:k+1Gk:k(1+Pk:k)+Pi:kGk-1:j

=Gi:k+1+Pi:k+1Gk:k+Pi:kGk-1:j

=Gi:k+1+Pi:kGk-1:j

=Gi:j

等價型PG邏輯的運用

運用新推導(dǎo)的等價型PG邏輯，可以改變PG傳播網(wǎng)絡(luò)的連接形式，如圖7所示，原來某些應(yīng)該獨立連接的節(jié)點，現(xiàn)在可以利用等價型邏輯表達式將它們連在一起，比如在圖7中的“5：4”和“4：3”兩個節(jié)點，在圖6中它們分別應(yīng)該按原始公式連接“3：2”和“2：1”兩點，現(xiàn)在可以根據(jù)新公式將它們都連接到“3：2”,其它節(jié)點以此類推。而且，在圖7中的“3：0”節(jié)點處負載較重，因此可以將“11：4”、“10：4”連接到“4：0”，以減輕“3：0”處的負載?？偟恼f來，改進以后的全加器在布線上可以相對于未改進的電路減少近一半，但負載相對來說也增加了一倍。因此，在實際電路中可以靈活調(diào)整連接關(guān)系，以平衡布線與負載之間的矛盾，同時對某些負載重的節(jié)點需要增加若干反相器，以增大該節(jié)點的驅(qū)動能力。

圖7 改進PG傳播網(wǎng)絡(luò)以后的全加器

　仿真與驗證

本文按照等價型PG邏輯的原理編寫了如上所述的15位加法器的Verilog描述，并用ModelSim對其進行了仿真，對隨機數(shù)進行相加，得到了正確的結(jié)果，說明在邏輯上該PG邏輯是正確的，如圖8所示。其中a、b為兩個15位的隨機數(shù)，ci為隨機的進位輸入，co為進位輸出，sum是最終的和(其最高位是co)。

圖8 運用等價型PG邏輯設(shè)計的15位加法器的仿真波形

結(jié)語

本文根據(jù)現(xiàn)有PG邏輯計算公式，推導(dǎo)出了一種新的與之等價的邏輯表達式。將這一邏輯表達式運用到加法器設(shè)計中去，能夠改變PG傳播網(wǎng)絡(luò)的結(jié)構(gòu)，減少連線數(shù)目，降低布線復(fù)雜度，這樣會更有利于后端的版圖布線。但此方法會相應(yīng)增大某些節(jié)點的負載，勢必帶來延遲的增加，因此需要精心設(shè)計晶體管尺寸或增加節(jié)點處的驅(qū)動能力，以使電路達到時序要求。

在今后的全加器設(shè)計中，可以根據(jù)具體情況靈活調(diào)整PG傳播網(wǎng)絡(luò)的結(jié)構(gòu)，盡量使得布線與負載達到一定程度的平衡。

　參考文獻：

1. P.M. Kogge, H.S. Stone. A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations. IEEE Trans, C-22(8): 831-838, Oct. 80

2. 汪東,李振濤,毛二坤,李寶鋒等譯. Neil H.E. Weste, David Harris著. CMOS超大規(guī)模集成電路設(shè)計(第三版). 北京：中國電力出版社，2006