簡介
儘管可以為不同計數系統設計專門的加法器,但是由於數字電路通常以二進制為基礎,因此二進制加法器在實際套用中最為普遍。在數字電路中,二進制數的減法可以通過加一個負數來間接完成。為了使負數的計算能夠直接用加法器來完成,計算中的負數可以使用二補數(補碼)來表示,具體的細節可以參考數字電路相關的書籍。
半加器
半加器(英語:half adder)的功能是將兩個一位二進制數相加。它有兩個輸出:
•和:記作S,來自對應的英語Sum;
•進位:記作C,來自對應的英語Carry。
進位信號代表在多位加法中需要溢出到更高一位的數字。因此,這兩個一位二級制數的和用十進制表示即等於2 C+ S。右圖是一個最簡單的半加器設計,使用一個異或門來產生 S,一個與門來產生 C。和S的布爾邏輯是A'B+AB',進位C的布爾邏輯是AB。如果再添加一個或門處理兩個半加器的進位信號,就構成了一個全加器。
半加器將兩個輸入位加和,產生進位與和,是半加器的兩個輸出。半加器的輸入變數叫做被加數或被加位。輸出變數為和與進位。
全加器
全加器(full adder)將兩個一位二進制數相加,並根據接收到的低位進位信號,輸出和、進位輸出。全加器的三個輸入信號為兩個加數 A、 B和低位進位 C。全加器通常可以通過級聯(cascade)的方式,構成多位(如8位、16位、32位)二進制數加法器的基本部分。全加器的輸出和半加器類似,包括向高位的進位信號 C和本位的和信號 S,相加結果的總和表達為 。一位全加器的真值表如圖:
在實際的套用中,全加器可以通過不同的方式製造,例如直接利用電晶體級的電路,或者由其他現成的邏輯門來構成。和、進位信號對應的邏輯函式表達式分別為 以及 。另一種全加器電路與之前的方式略有不同,它用一個異或門來代替或門對其中兩個輸入信號進行求和,其進位信號對應的邏輯函式表達式分別為 。通過適當的邏輯函式變化,可以證明它與前面的計算方法結果一致。
在這個實現中,將最後的或門換成異或門不會影響邏輯。如果電路使用的是每個晶片上只有一種閘的簡單積體電路晶片,僅使用兩種閘會比較方便。
全加器可以用兩個半加器來構造,將輸入端 A和 B連線到一個半加器上,然後將其和輸出信號與進位輸入信號分別作為第二個半加器的兩個輸入,並將兩個進位輸出信號進行邏輯或運算。全加器的關鍵路徑(critical path,即經歷最多邏輯門的路徑)經過兩個異或門,終止於和位{\displaystyle s}。假定異或門耗費3個延遲來完成,一個全加器的關鍵路徑上施加的延遲等於
進位模組(carry-block)包括2個邏輯門,因此延遲為
全加器還可以使用一個三輸入的異或門來求和,再使用一個兩級與或結構來實現進位信號對應的積之和(sum of products)式。
一位全加器的符號,它與半加器不同之處在於它還能接收一個低位進位輸入信號 。右圖中的藍框是為了表明它作為一個整體可以級聯構成多位二進制數的加法器。
更複雜的加法器
波紋進位加法器
可以使用多個一位全加器來構成 N位加法器,其中對應低位的全加器將其進位輸出信號 C連線到高一位的全加器的進入輸入端 C。這種構成多位加法器的形式被稱為“波紋進位加法器”或“脈動進位加法器”(ripple-carry adder),“波紋”形象地描述了進位信號依次向前傳遞的情形。如果不需要連線其他進位信號,則最低位的全加器可以用半加器替換。
波紋進位加法器的電路布局形式較為簡單,設計這種電路花費時間較短。然而,波紋進位加法器的進位輸出、輸入所經過的路徑上比其他布局方式具有較多的邏輯門,高位的計算必須等待低位的進位輸出信號被計算出來才能開始,因此造成了更大的延遲時間。
下面簡單計算信號在加法器中的延遲。每一個全加器具有三級邏輯函式。在一個32位的波紋進位加法器中,有32個全加器,隨之產生的邏輯門延遲則可以根據關鍵路徑的延遲時間來決定,即2倍的最高位全加器輸入信號、進位輸出延遲,加上31乘以3倍的其他全加器上的延遲,總共等於95倍的邏輯門延遲。一個 n位波紋進位加法器的最壞情形延遲方程為
從位位置0到進位輸出的進位有一點不同:
輸入進位必須經過 n個進位生成器模組來得到進位輸出的效果
交替進位極性和最佳化的與或非門的設計可以減少一半的延遲時間。
超前進位加法器
為了減少多位二進制數加減計算所需的時間,工程師設計了一種比脈動進位加法器速度更快的加法器電路,這種加法器被稱為“超前進位加法器”(carry-lookahead adder)。
下面簡述超前進位加法器的主要原理。我們先來考慮構成多位加法器的單個全加器從其低一位獲得的進位信號,我們可以將它變換為 。當前為二級制數的每一位構建兩個新信號:
生成(Generate)信號:
傳輸(Propagate)信號:
於是,某位全加器從低一位獲得的進位可以表示為 ,例如次低位全加器從最低位獲得的進位為 ,而從最低位開始第三位的那個全加器獲得的進位信號則為 。在多位脈動進位加法器中, 必須連線到低一位的進位輸出信號,如果使用這種方式構成多位全加器,則邏輯門的延遲會發生累加,導致降低電路的計算效率下降。超前進位加法器採取的方式是,將 的邏輯函式代入到 ,即 ,於是,這一位的進位輸出就只取決於 、 、 、 、 幾個信號,而這幾個信號都是計算電路外部的已知信號,而非低一位的計算結果。上面考慮的是從最低位開始第三位的情況。採用類似的代入方法,可以用各位的生成信號 、傳輸信號,以及最低位從外部獲取的進位信號 來表示多位全加器的所有進位信號。
通過列出多位加法器各位的進位輸出,可以發現高位的進位輸出表達式(積之和式)涉及的變數更多,對應的邏輯電路連線會變得更複雜,而且在實際套用中會遭遇邏輯門的扇入問題。因此有必要對位數過高的全加器進行邏輯劃分,如將六十四位全加器分為四個十六位超前進位加法器來實現(如右圖)。多位二進制數加法器的標準晶片通常具有超前進位的組成形式,例如:7400系列的7483、74283晶片。