加法器

在電子學中，加法器（英語：adder）是一種用於執行加法運算的數位電路部件，是構成電子計算機核心微處理器中算術邏輯單元的基礎。在這些電子系統中，加法器主要負責計算地址、索引等數據。除此之外，加法器也是其他一些硬體，例如二進制數的乘法器的重要組成部分。

儘管可以為不同計數系統設計專門的加法器，但是由於數位電路通常以二進制為基礎，因此二進制加法器在實際應用中最為普遍。在數位電路中，二進制數的減法可以通過加一個負數來間接完成。為了使負數的計算能夠直接用加法器來完成，計算中的負數可以使用二補數（補碼）來表示，具體的細節可以參考數位電路相關的書籍。^[1]^:244-248

半加器

一位元半加器的符號

（英語：half adder）的功能是將兩個一位元二進制數相加。它有兩個輸出：

和：記作 S，來自對應的英語 Sum；
進位：記作 C，來自對應的英語 Carry一位元的數位。因此，這兩個一位元二進制數的和用十進制表示即等於2C + S。右圖是一個最簡單的半加器設計，使用一個互斥或閘來產生 S，一個及閘來產生 C。和 S 的布林邏輯是 A'B+AB'，進位 C 的布林邏輯是 AB。如果再添加一個或閘處理兩個半加器的進位訊號，就構成了一個全加器。

^[2]

半加器將兩個輸入位加和，產生進位與和，是半加器的兩個輸出。半加器的輸入變量叫做被加數或被加位。輸出變量為和與進位。

半加器的真值表如下：

輸入		輸出
A	B	C	S
0	0	0	0
1	0	0	1
0	1	0	1
1	1	1	0

全加器

一位元全加器的符號，它與半加器不同之處在於它還能接收一個低位進位輸入訊號C_in。圖中的藍框是為了表明它作為一個整體可以級聯構成多位二進制數的加法器。

全加器（full adder）將兩個一位元二進制數相加，並根據接收到的低位進位訊號，輸出和、進位輸出。全加器的三個輸入訊號為兩個加數A、B和低位進位C_in。^[3]全加器通常可以通過級聯（cascade）的方式，構成多位（如8位、16位、32位）二進制數加法器的基本部分。全加器的輸出和半加器類似，包括向高位的進位訊號C_out和本位的和訊號S，相加結果的總和用十進位表達為 $\mathrm {sum} =2\times C_{out}+S$ 。一位元全加器的真值表為：

全加器的符號

輸入			輸出
A	B	C_in	C_out	S
0	0	0	0	0
1	0	0	0	1
0	1	0	0	1
1	1	0	1	0
0	0	1	0	1
1	0	1	1	0
0	1	1	1	0
1	1	1	1	1

在實際的應用中，全加器可以通過不同的方式製造，例如直接利用電晶體級的電路，或者由其他現成的邏輯閘來構成。和、進位訊號對應的邏輯函數表達式分別為 $S=A\oplus B\oplus C_{in}$ 以及 $C_{out}=(A\cdot B)+(B\cdot C)+(A\cdot C)$ 。另一種全加器電路與之前的方式略有不同，它用一個互斥或閘來代替或閘對其中兩個輸入訊號進行求和，其進位訊號對應的邏輯函數表達式分別為 $C_{out}=(A\cdot B)+(C_{in}\cdot (A\oplus B))$ 。通過適當的邏輯函數變化，可以證明它與前面的計算方法結果一致。^[1]^{:238, 260}

在這個實現中，將最後的或閘換成互斥或閘不會影響邏輯。如果電路使用的是每個晶片上只有一種閘的簡單積體電路晶片，僅使用兩種閘會比較方便。

全加器可以用兩個半加器來構造，將輸入端A和B連接到一個半加器上，然後將其和輸出訊號與進位輸入訊號分別作為第二個半加器的兩個輸入，並將兩個進位輸出訊號進行邏輯或運算。全加器的關鍵路徑（critical path，即經歷最多邏輯閘的路徑）經過兩個互斥或閘，終止於和位 $s$ 。假定互斥或閘耗費3個延遲來完成，一個全加器的關鍵路徑上施加的延遲等於

T_{FA}=2\cdot T_{XOR}=2\cdot 3D=6D

進位模塊(carry-block)包括2個邏輯閘，因此延遲為

T_{c}=2D

全加器還可以使用一個三輸入的互斥或閘來求和，再使用一個兩級與或結構來實現進位訊號對應的積之和（sum of products）式。

多位加法器

波紋進位加法器（脈動進位加法器）

用四個一位元全加器構成的四位波紋進位加法器

可以使用多個一位元全加器來構成N位加法器，其中對應低位的全加器將其進位輸出訊號C_out連接到高一位元的全加器的進入輸入端C_in。這種構成多位加法器的形式被稱為「波紋進位加法器」或「脈動進位加法器」（ripple-carry adder），「波紋」形象地描述了進位訊號依次向前傳遞的情形。如果不需要連接其他進位訊號，則最低位的全加器可以用半加器替換。

波紋進位加法器的電路布局形式較為簡單，設計這種電路花費時間較短。然而，波紋進位加法器的進位輸出、輸入所經過的路徑上比其他布局方式具有較多的邏輯閘，高位的計算必須等待低位的進位輸出訊號被計算出來才能開始，因此造成了更大的延遲時間。^[4]^:49

下面簡單計算訊號在加法器中的延遲。每一個全加器具有三級邏輯函數。在一個32位的波紋進位加法器中，有32個全加器，隨之產生的邏輯閘延遲則可以根據關鍵路徑的延遲時間來決定，即2倍的最高位全加器輸入訊號、進位輸出延遲，加上31乘以3倍的其他全加器上的延遲，總共等於95倍的邏輯閘延遲。一個 n 位波紋進位加法器的最壞情形延遲方程為

T_{CRA}(n)=T_{HA}+(n-1)\cdot T_{c}+T_{s}=T_{FA}+(n-1)\cdot T_{c}=6D+(n-1)\cdot 2D=(n+2)\cdot 2D

從位位置0到進位輸出的進位有一點不同：

T_{CRA_{[0:c_{out}]}}=T_{HA}+n\cdot T_{c}=3D+n\cdot 2D

輸入進位必須經過 n 個進位生成器模塊來得到進位輸出的效果

T_{CRA_{[c_{0}:c_{n}]}}(n)=n\cdot T_{c}=n\cdot 2D

交替進位極性和優化的與反或閘（英語：AND-OR-Invert）的設計可以減少一半的延遲時間。^[5]

超前進位加法器

四位超前進位加法器

為了減少多位二進制數加減計算所需的時間，工程師設計了一種比脈動進位加法器速度更快的加法器電路，這種加法器被稱為「超前進位加法器」（carry-lookahead adder）。

下面簡述超前進位加法器的主要原理。^[6]^[1]^:255-262我們先來考慮構成多位加法器的單個全加器從其低一位元獲得的進位訊號 $c_{i+1}=(x_{i}\cdot y_{i})+(x_{i}\cdot c_{i})+(y_{i}\cdot c_{i})$ ，我們可以將它變換為 $c_{i+1}=(x_{i}\cdot y_{i})+(x_{i}+y_{i})\cdot c_{i}$ 。現在為二進制數的每一位元構建兩個新訊號：

生成（Generate）訊號： $G_{i}=x_{i}\cdot y_{i}$
傳輸（Propagate）訊號： $P_{i}=x_{i}+y_{i}$

於是，某位全加器從低一位元獲得的進位可以表示為 $c_{i+1}=G_{i}+P_{i}\cdot c_{i}$ ，例如次低位全加器從最低位獲得的進位為 $c_{1}=G_{0}+P_{0}\cdot c_{0}$ ，而從最低位開始第三位的那個全加器獲得的進位訊號則為 $c_{2}=G_{1}+P_{1}\cdot c_{1}$ 。在多位脈動進位加法器中， $c_{2}$ 必須連接到低一位元的進位輸出訊號，如果使用這種方式構成多位全加器，則邏輯閘的延遲會發生累加，導致降低電路的計算效率下降。超前進位加法器採取的方式是，將 $c_{1}$ 的邏輯函數代入到 $c_{2}$ ，即 $c_{2}=G_{1}+P_{1}\cdot (G_{0}+P_{0}\cdot c_{0})$ ，於是，這一位元的進位輸出就只取決於 $x_{1}$ 、 $y_{1}$ 、 $x_{0}$ 、 $y_{0}$ 、 $c_{0}$ 幾個訊號，而這幾個訊號都是計算電路外部的已知訊號，而非低一位元的計算結果。上面考慮的是從最低位開始第三位的情況。採用類似的代入方法，可以用各位的生成訊號 $G_{i}$ 、傳輸訊號 $P_{i}$ ，以及最低位從外部獲取的進位訊號 $c_{0}$ 來表示多位全加器的所有進位訊號。

六十四位全加器可以邏輯劃分為四個十六位超前進位加法器

通過列出多位加法器各位的進位輸出，可以發現高位的進位輸出表達式（積之和式）涉及的變量更多，對應的邏輯電路連線會變得更複雜，而且在實際應用中會遭遇邏輯閘的扇入問題。因此有必要對位數過高的全加器進行邏輯劃分，如將六十四位全加器分為四個十六位超前進位加法器來實現（如右圖）。多位二進制數加法器的標準晶片通常具有超前進位的組成形式，例如:7400系列的7483、74283晶片。^[4]^:50

延伸

參考文獻

^ ^1.0 ^1.1 ^1.2 Stephen Brown, Zvonko Vranesic. Fundamentals of Digital Logic with Verilog Design. McGraw-Hill Education. 2002. ISBN 0-07-283878-7.
^ Geoffrey A. Lancaster. Excel HSC Software Design and Development. Pascal Press. 2004: 180 [2013-02-24]. ISBN 9781741251753. （原始內容存檔於2013-12-31）.
^ M. Morris Mano. Digital Logic and Computer Design. Prentice-Hall. 1979: 119-123. ISBN 0-13-214510-3.
^ ^4.0 ^4.1 鄧元慶，關宇，賈鵬，石會. 数字设计基础与应用. 清華大學出版社. ISBN 978-7-302-21406-9.
^ Burgess, N. Fast Ripple-Carry Adders in Standard-Cell CMOS VLSI (PDF). 20th IEEE Symposium on Computer Arithmetic. 2011: 103–111.
^ Fast Addition: Carry Lookahead Adders. University of Maryland. [2013-02-28]. （原始內容存檔於2013-03-04）.

外部連結

Hardware algorithms for arithmetic modules（頁面存檔備份，存於網際網路檔案館）, includes description of several adder layouts with figures.
8-bit Full Adder and Subtractor（頁面存檔備份，存於網際網路檔案館）, a demonstration of an interactive Full Adder built in JavaScript solely for learning purposes.

[Stephen-1] 1.0 ^1.1 ^1.2 Stephen Brown, Zvonko Vranesic. Fundamentals of Digital Logic with Verilog Design. McGraw-Hill Education. 2002. ISBN 0-07-283878-7.

[2] Geoffrey A. Lancaster. Excel HSC Software Design and Development. Pascal Press. 2004: 180 [2013-02-24]. ISBN 9781741251753. （原始內容存檔於2013-12-31）.

[Mano79-3] M. Morris Mano. Digital Logic and Computer Design. Prentice-Hall. 1979: 119-123. ISBN 0-13-214510-3.

[Deng-4] 4.0 ^4.1 鄧元慶，關宇，賈鵬，石會. 数字设计基础与应用. 清華大學出版社. ISBN 978-7-302-21406-9.

[5] Burgess, N. Fast Ripple-Carry Adders in Standard-Cell CMOS VLSI (PDF). 20th IEEE Symposium on Computer Arithmetic. 2011: 103–111.

[6] Fast Addition: Carry Lookahead Adders. University of Maryland. [2013-02-28]. （原始內容存檔於2013-03-04）.

[1]

[2]

[3]

[4]

[5]

[6]