等價(jià)型PG邏輯及其在加法器設計中的應用

　　摘 要：全加器實(shí)現的基本原理是基于進(jìn)位傳播和進(jìn)位產(chǎn)生的PG邏輯。根據現有的PG邏輯計算公式，本文推導出一種新的等價(jià)型邏輯表達式，并驗證了其正確性。將該等價(jià)型邏輯表達式用于全加器的設計中，能夠改變原有的全加器結構，并改變布線(xiàn)通道的連線(xiàn)數目和連線(xiàn)方式。

　　關(guān)鍵詞：全加器;PG邏輯;連線(xiàn);負載

　　引言

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

　　全加器設計的

　　基本原理

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

　　圖1 N位全加器

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

　　全加器最簡(jiǎn)單的構成方法就是把每一位的進(jìn)位輸出與下一位的進(jìn)位輸入簡(jiǎn)單地連接起來(lái)，得到的就是行波進(jìn)位全加器。但在快速全加器中，是將加數和被加數中具有相同下標的位分成若干組，即多個(gè)多位組，并將各個(gè)多位組看作一個(gè)整體。通過(guò)計算多位組的PG邏輯，在求和之前可預測多位組的進(jìn)位輸出是傳播進(jìn)位輸入還是直接產(chǎn)生進(jìn)位輸出。多位組所包括的位在i到j(luò )的范圍內(見(jiàn)圖2)，如果該多位組的進(jìn)位輸出是與進(jìn)位輸入無(wú)關(guān)的“真”值，那么它就產(chǎn)生了一個(gè)進(jìn)位;如果該多位組的進(jìn)位輸出只有當進(jìn)位輸入為“真”時(shí)才進(jìn)位輸出“真”值，那么它就傳播了一個(gè)進(jì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

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

　　圖3 遞歸表達式的對應電路

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

　　圖4 黑色單元和白色單元

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

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

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

　　等價(jià)型PG邏輯的論證

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

　　下面給出它的簡(jiǎn)單推導過(guò)程：

　　因為，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展開(kāi)以后，上式=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

　　等價(jià)型PG邏輯的運用

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

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

　　仿真與驗證

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

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

　　結語(yǔ)

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

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

　　參考文獻：

　　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著(zhù). CMOS超大規模集成電路設計(第三版). 北京：中國電力出版社，2006