摘 要：全加器實現的基本原理是基於進位傳播和進位產生的PG邏輯。根據現有的PG邏輯計算公式，本文推導出一種新的等價型邏輯表達式，並驗證了其正確性。將該等價型邏輯表達式用於全加器的設計中，能夠改變原有的全加器結構，並改變布線通道的連線數目和連線方式。
關鍵詞：全加器;PG邏輯;連線;負載
引言
在全加器設計中運用PG邏輯是非常普遍的，本文在設計和研究全加器時，根據現有的PG邏輯公式推導出了一種新的邏輯公式，並論證了兩者之間的等價關係。這一新的公式能夠指導全加器設計中的連線方式，靈活更改連線策略。本文將從基本原理開始逐步引出該公式，對其進行論證，並應用於全加器設計中。
全加器設計的
基本原理
N位全加器將{AN，……，A1}、{BN，……，B1}和進位輸入Cin作為輸入，計算得到和{SN，……，S1}以及最高位的進位輸出Cout(見圖1)。每一位得到的和與進位輸出都直接受其上一位的影響，其進位輸出也會影響下一位。最終，整個全加器的和與輸出都受進位輸入Cin的影響。
圖1 N位全加器
圖2 多位組傳播Cin 或者直接產生進位輸出
全加器最簡單的構成方法就是把每一位的進位輸出與下一位的進位輸入簡單地連接起來，得到的就是行波進位全加器。但在快速全加器中，是將加數和被加數中具有相同下標的位分成若干組，即多個多位組，並將各個多位組看作一個整體。通過計算多位組的PG邏輯，在求和之前可預測多位組的進位輸出是傳播進位輸入還是直接產生進位輸出。多位組所包括的位在i到j的範圍內(見圖2)，如果該多位組的進位輸出是與進位輸入無關的「真」值，那麼它就產生了一個進位;如果該多位組的進位輸出只有當進位輸入為「真」時才進位輸出「真」值，那麼它就傳播了一個進位。對於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有關，所以有Ci=Ci:0，和Si=Ai臖i臗i-1=Pii臛i-1:0。由此可見，只要算出各位的Pi:i值和Gi:0值，就可以將各位的Si值求出。而其中最關鍵的就是利用遞歸公式快速算出各Gi:0值。上述遞歸表達式可以用如圖3所示的電路表示。
圖3 遞歸表達式的對應電路
為了能夠更加簡潔地表達全加器電路結構，可將圖3中的電路用圖4所示的黑色單元表示，並用圖4中的白色單元表示圖5所示的G邏輯產生電路。
圖4 黑色單元和白色單元
圖5 G邏輯產生電路
根據遞歸公式，可以得到各種不同結構的全加器，他們的邏輯級數、扇出、布線通道數、所用單元數等各不相同，在此不再贅述，只給出一種Kogge-Stone樹型全加器PG網絡，如圖6所示。圖的上部即是各位的本位Pi:i和Gi:i產生邏輯，中部是PG傳播網絡，下部是各位的進位輸出Ci。這種樹型全加器具有理想的邏輯級數和扇出，但是連線複雜，也需要更多的單元。
圖6 Kogge-Stone樹型全加器PG網絡
等價型PG邏輯的論證
對上文給出的遞歸表達式進行進一步推導，可得出如下結果：Gi:j=Gi:k+Pi:kGk-1:j=Gi:k+Pi:kGk:j(Gk-1:j可用Gk:j替代)
下面給出它的簡單推導過程：
因為，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邏輯的運用
運用新推導的等價型PG邏輯，可以改變PG傳播網絡的連接形式，如圖7所示，原來某些應該獨立連接的節點，現在可以利用等價型邏輯表達式將它們連在一起，比如在圖7中的「5：4」和「4：3」兩個節點，在圖6中它們分別應該按原始公式連接「3：2」和「2：1」兩點，現在可以根據新公式將它們都連接到「3：2」,其它節點以此類推。而且，在圖7中的「3：0」節點處負載較重，因此可以將「11：4」、「10：4」連接到「4：0」，以減輕「3：0」處的負載。總的說來，改進以後的全加器在布線上可以相對於未改進的電路減少近一半，但負載相對來說也增加了一倍。因此，在實際電路中可以靈活調整連接關係，以平衡布線與負載之間的矛盾，同時對某些負載重的節點需要增加若干反相器，以增大該節點的驅動能力。
圖8 改進PG傳播網絡以後的全加器
仿真與驗證
本文按照等價型PG邏輯的原理編寫了如上所述的15位加法器的Verilog描述，並用ModelSim對其進行了仿真，對隨機數進行相加，得到了正確的結果，說明在邏輯上該PG邏輯是正確的，如圖8所示。其中a、b為兩個15位的隨機數，ci為隨機的進位輸入，co為進位輸出，sum是最終的和(其最高位是co)。
圖8 運用等價型PG邏輯設計的15位加法器的仿真波形
結語
本文根據現有PG邏輯計算公式，推導出了一種新的與之等價的邏輯表達式。將這一邏輯表達式運用到加法器設計中去，能夠改變PG傳播網絡的結構，減少連線數目，降低布線複雜度，這樣會更有利於後端的版圖布線。但此方法會相應增大某些節點的負載，勢必帶來延遲的增加，因此需要精心設計電晶體尺寸或增加節點處的驅動能力，以使電路達到時序要求。
在今後的全加器設計中，可以根據具體情況靈活調整PG傳播網絡的結構，儘量使得布線與負載達到一定程度的平衡。 ■
參考文獻：
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超大規模集成電路設計(第三版). 北京：中國電力出版社，2006