加法器

加法器是為了實現加法的。

即是產生數的和的裝置。

對於1位的二進位加法，相關的有五個的量：1，被加數A，2，加數B，3，前一位的進位CIN，4，此位二數相加的和S，5，此位二數相加產生的進位COUT。前三個量為輸入量，后兩個量為輸出量，五個量均為1位。

對於32位的二進位加法，相關的也有五個量：1，被加數A（32位），2，加數B（32位），3，前一位的進位CIN（1位），4，此位二數相加的和S（32位），5，此位二數相加產生的進位COUT（1位）。

要實現32位的二進位加法，一種自然的想法就是將1位的二進位加法重複32次（即逐位進位加法器）。這樣做無疑是可行且易行的，但由於每一位的CIN都是由前一位的COUT提供的，所以第2位必須在第1位計算出結果后，才能開始計算；第3位必須在第2位計算出結果后，才能開始計算，等等。而最後的第32位必須在前31位全部計算出結果后，才能開始計算。這樣的方法，使得實現32位的二進位加法所需的時間是實現1位的二進位加法的時間的32倍。

可以看出，上法是將32位的加法1位1位串列進行的，要縮短進行的時間，就應設法使上敘進行過程并行化。

逐位進位加法器，在每一位的計算時，都在等待前一位的進位。那麼不妨預先考慮進位輸入的所有可能，對於二進位加法來說，就是0與1兩種可能，並提前計算出若干位針對這兩種可能性的結果。等到前一位的進位來到時，可以通過一個雙路開關選出輸出結果。這就是進位選擇加法器的思想。提前計算多少位的數據為宜？同為32位的情況：線形進位選擇加法器，方法是分N級，每級計算32/N位；平方根進位選擇加法器，考慮到使兩個路徑（1，提前計算出若干位針對這兩種可能性的結果的路徑，2，上一位的進位通過前面的結構的路徑）的延時達到相等或是近似。方法，或是2345666即第一級相加2位，第二級3位，第三級4位，第四級5位，第五級6位，第六級6位，第七級6位；或是345677即第一級相加3位，第二級4位，第三級5位，第四級6位，第五級7位，第六級7位。

進一步分析加法進行的機制，可以使加法器的結構進一步并行化。

令G = AB，P = A⊕B，則COUT（G，P） = G + PCIN，S（G，P）=P⊕CIN。由此，A，B，CIN，S，COUT五者的關係，變為了G，P，CIN，S，COUT五者的關係。

再定義點運算（·），（G，P）·（G’，P’）=（G + PG’,PP’），可以分解（G 3：2,P3：2） =（G3，P3）·（G2，P2）。點運算服從結合律，但不符合交換律。

點運算只與G，P有關而與CIN無關，也就是可以通過只對前面若干位G，P進行點運算計算，就能得到第N位的GN：M，PN：M值，當取M為0時，獲得的GN：0，PN：0即可與初使的CIN一起代入COUT（G，P） = G + PCIN，S（G，P）=P⊕CIN，得到此位的COUT，S；而每一位的G，P值又只與該位的A，B值即輸入值有關，所以在開始進行運算后，就能并行的得到每一位的G，P值。

以上分析產生了超前進位加法器的思想：三步運算，1，由輸入的A，B算出每一位的G，P；2，由各位的G，P算出每一位的GN：0，PN：0；3，由每一位的GN：0，PN：0與CIN算出每一位的COUT，S。其中第1，3步顯然是可以并行處理的，計算的主要複雜度集中在了第2步。

第2步的并行化，也就是實現GN：0，PN：0的點運算分解的并行化。

設一個n位的加法器的第i位輸入為ai、bi、ci，輸出si和ci+1，其中ci是低位來的進位，ci+1（i=n-1，n-2，…，1，0）是向高位的進位，c0是整個加法器的進位輸入，而cn是整個加法器的進位輸出。則和

si=aiii+ibii+iici+aibici ，(1) 進位ci+1=aibi+aici+bici ，(2)

令 gi=aibi， (3)

pi=ai+bi， (4)

則 ci+1= gi+pici， (5)

只要aibi=1，就會產生向i+1位的進位，稱g為進位產生函數；同樣，只要ai+bi=1，就會把ci傳遞到i+1位，所以稱p為進位傳遞函數。把式(5)展開，得到：ci+1= gi+ pigi-1+pipi-1gi-2+…+ pipi-1…p1g0+ pipi-1…p0c0(6)。

隨著位數的增加式(6)會加長，但總保持三個邏輯級的深度，因此形成進位的延遲是與位數無關的常數。一旦進位（c1~cn-1）算出以後，和也就可由式（1）得出。

使用上述公式來并行產生所有進位的加法器就是超前進位加法器。產生gi和pi需要一級門延遲，ci 需要兩級，si需要兩級，總共需要五級門延遲。與串聯加法器（一般要2n級門延遲）相比，（特別是n比較大的時候）超前進位加法器的延遲時間大大縮短了。

以單位元的加法器來說，有兩種基本的類型：半加器和全加器，半加器有兩個輸入和兩個輸出，輸入可以標識為 A、B 或 X、Y，輸出通常標識為合 S 和進位 C。A 和 B 經 XOR 運算后即為 S，經 AND 運算后即為 C。

全加器引入了進位值的輸入，以計算較大的數。為區分全加器的兩個進位線，在輸入端的記作 Ci 或 Cin，在輸出端的則記作 Co 或 Cout。半加器簡寫為 H.A.，全加器簡寫為 F.A.。

半加器：半加器的電路圖半加器有兩個二進位的輸入，其將輸入的值相加，並輸出結果到和（Sum）和進位（Carry）。半加器雖能產生進位值，但半加器本身並不能處理進位值。

全加器：全加器三個二進位的輸入，其中一個是進位值的輸入，所以全加器可以處理進位值。全加器可以用兩個半加器組合而成。

注意，進位輸出端的最末個OR閘，也可用XOR閘來代替，且無需更改其餘的部分。因為 OR 閘和 XOR 閘只有當輸入皆為 1 時才有差別，而這個可能性已不存在。

直接使用式(6)形成的電路是不規則的，並且需要長線驅動，需要大驅動信號和大扇入門。當位數較多時，這種實現方式不太現實。

可以改進超前進位電路，使其具有規則性。對於一個n位（n>4）的加法器，按4位一組的形式對其分組，組內實行超前進位，組間也實行超前進位。相應地超前進位邏輯需要分級，級的數目L=Log4(n)。如圖1所示，第m(0～n-1)位的g,p可以表示為：g4k+j=a4k+jb4k+j，p4k+j=a4k+j+b4k+j；k為(m/4)的商，代表組的 位置；j為餘數，代表該位在該組中的位置。各個4位CLA的組進位產生函數G4k+3, 4k = g4k+3 + p4k+3 g4k+2 + p4k+3p4k+2g4k+1 +p4k+3p4k+2p4k+1g4k ；組進位傳遞函數P4k+3, 4k = p4k+3 p4k+2 p4k+1 p4k ；組進位C4k+4 = G4k+3, 4k + P4k+3, 4k c4k。

每個4位的CLA模塊分別計算各組內每一位的p、 g和組間的P、G，第二級LACG（look ahead carry generator）根據各組（包含第一級LACG邏輯）的P、G和c0計算出各組間的進位C4k+4 ，同樣，第三級LACG則根據第二級的P、G和c0計算出向高4組的進位C16k+16，依此類推。計算出的所有組進位都要送回各個4位的CLA模塊，并行算出每一位的和。

改造后，CLA的延時包括：用式(3)和式(4)產生pi和gi的1級門延時；用超前進位電路產生所有進位的2(2L-1)級門延時；用 (1) 式計算si的2級門延時。於是總的延時為[2] ：

Delay(CLA adder)=1+4Log4(n) (7)

與簡單的串聯加法器相比，超前進位加法器需要較多的邏輯電路來產生進位位。但它的延遲時間的數量級為log4(n)。當n較大時，速度的改進是很明顯的。

邏輯優化設計的主要目的是減少信號的翻轉活動[3]，它通過將電路的邏輯功能儘可能的分解、優化，減少邏輯深度，減少信號假翻轉，從而使翻轉活動最小，減小電路的功耗。

令gsi=ai⊙bi ，則式（1）可以改寫為si= gsi⊙ci ，先考察第一組CLA

s0=gs0⊙c0 (8)

s1=gs1⊙c1=gs1⊙(g0+p0c0) (9)

s2=gs2⊙c2=gs2⊙(g1+p1g0+p1p0c0) (10)

s3=gs3⊙c3=gs3⊙(g2+p2g1+p2p1g0+p2p1p0c0)(11)

因為g, p的值只有“00”、“01”、“11”這三種組合，結合布爾代數性質A⊙0=、A⊙1=A可知，s3的值最終可以歸結為3個表達式：gs3, 3和(gs3⊙c0)，同樣，s2值的3個表達式為gs2, 2和(gs2⊙c0)，s1為gs1, 1和(gs1⊙c0)。於是式(8)至式(11)就可以化為

s0=c0(gs0)+ 0 (0) (12)

s1=c0(gs1⊙p0)+0(gs1⊙g0) (13)

s2=c0(gs2⊙(g1+p1p0))+ 0 (gs2⊙(g1+p1g0))(14)

s3=c0(gs3⊙(g2+p2g1+p2p1p0))

+0(gs3⊙(g2+p2g1+p2p1g0)) (15)

其他組，如s4~s7、s8~s11等，情況和s0~s3一樣。

邏輯改造后，在進位產生邏輯上可以減少一些不必要的翻轉，減少了節點開關活動率，並且可以重複利用g,p積之和的相同部分，達到路徑平衡的效果，可以有效地消除假翻轉（glitch），同時與門和或門的最大扇入都減少了一個，較大程度地減小了功耗。

邏輯改造后，電路也應該相應地進行優化設計，因為如果用普通的門電路來實現式(12)~(15)的邏輯，晶體管數目（面積）會增加。另外，在電路級也可以採用減少節點翻轉和寄生電容的方法來降低功耗。

式(12)~(15)中多處要用到同或門，設計中，我們用基於旁路的靜態邏輯[4]實現產生gs的同或門，如圖2。旁路邏輯通過由附加管形成的旁路，可以把“串並交錯”的電路結構簡化為單一的串或者並的形式。它的電路和版圖都有很好的規整性，並且可以減小寄生電容。是兩種同或門N塊版圖不同部分的比較，（b）是基於旁路邏輯實現的，與（a）相比，少了一條金屬連線和兩個金屬接觸，使版圖變得十分規整，擴散區不會被隔斷。在拓撲上，兩條分支用公共的漏區，達到最少的接觸孔和金屬互連，比“串並”和“並串”的晶體管配置方式規整，且寄生電容小。

加法器電路上的延遲值

旁路邏輯不能實現傳輸門，因而不能用傳輸門實現同或和異或，但是容易證明，三態門在速度和功耗方面都比傳輸門優越。參照傳輸門的結合方式，我們用兩個三態反相器和一個反相器實現了同或門。

實現了式(13)括弧內的兩個同或邏輯，平均只需要1級門延時，而用普通門實現的“與非或與非”形式的同或門需要2級或3級門延時。由上面的同或門設計得到啟發，根據形如式(13)的邏輯，設計了一個10管單元utiandor2。

該單元電路實現s=c0CK+0CKN，只要把式(12)~(15)中的括弧部分從CK和CKN輸入，輸出就相應得到了s0~ s3。僅當CKN=時，電路(a)兩邊均是三態反相器，構成圖5（b）的同或門，兩個反相器交替導通，s=c0⊙CK ；當CKN=CK（發生幾率比較大），左邊P管和右邊N管，或者左邊N管和右邊P管交替導通，輸出s=CK，從而屏蔽了c0的變化。考察第一組4位CLA中的進位產生邏輯最複雜的s3，參考式（15），當g2,g1,g0均為0，p2,p1,p0均為1時，s3= gs3⊙c0，顯然這是一種特殊情況，即低位各位都不產生進位，但可以傳遞進位時，直接把c0傳至高位與gs同或即可產生和。c0在各位和生成邏輯的最後一級才加入，可以消除過早加入帶來的不必要的翻轉。左右兩塊交替導通，只存在下拉或上拉延時，有類似動態電路延遲小的優點。僅用了10個晶體管，比常規門實現的積之和節省8個。