加法器

維基百科,自由的百科全書
前往: 導覽搜尋

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

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

半加器[編輯]

一位半加器的符號

半加器的功能是將兩個一位二進制數相加。它具有兩個輸入和兩個輸出(分別是和、進位)。輸出的進位訊號代表了輸入兩個數相加溢出的高一位數值。因此,這兩2個一位二級制數的和等於2C + S。根據兩個一位二進制數相加的結果,可以通過真值表、卡諾圖得到右圖所描繪的簡易半加器設計。它使用了一個互斥或閘來產生和S,並使用了一個及閘來產生進位訊號C。如果再添加一個或閘來接收低位的進位輸出訊號,則兩個半加器就構成了一個全加器。[2]

全加器[編輯]

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

全加器將兩個一位二進制數相加,並根據接收到的低位進位訊號,輸出和、進位輸出。全加器的三個輸入訊號為兩個加數AB和低位進位Cin[3]全加器通常可以通過級聯(cascade)的方式,構成多位(如8位、16位、32位)二進制數加法器的基本部分。全加器的輸出和半加器類似,包括向高位的進位訊號Cout和本位的和訊號S,相加結果的總和表達為\mathrm{sum} = 2 \times C_{out} + S。一位全加器的真值表為:

全加器的符號
輸入 輸出
A B Cin Cout 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

將兩個輸入端AB連接到一個半加器上,然後將其和輸出訊號、進位輸出訊號分別作為第二個半加器的兩個輸入,並將兩個進位輸出訊號進行邏輯或運算。可以使用一個三輸入的互斥或閘來求和,再使用一個兩級與或結構來實現進位訊號對應的積之和(sum of products)式。

更複雜的加法器[編輯]

漣波進位加法器[編輯]

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

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

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

下面簡單計算訊號在加法器中的延遲。每一個全加器具有三級邏輯函數。在一個32位的漣波進位加法器中,隨之產生的邏輯閘延遲則可以根據關鍵路徑(critical path,即經歷最多邏輯閘的路徑)的延遲時間來決定,即3倍的最高位全加器輸入訊號、進位輸出延遲,加上31乘以2倍的其他全加器上的延遲,總共等於65倍的邏輯閘延遲。通過使用其他的連接方式,可以減少延遲時間。[5]

超前進位加法器[編輯]

四位超前進位加法器
一種2級門4bit加法器的設計

為了減少多位二進制數加減計算所需的時間,工程師設計了一種比脈動進位加法器速度更快的加法器電路,這種加法器被稱為「超前進位加法器(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 \oplus 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_1y_1x_0y_0c_0幾個訊號,而這幾個訊號都是計算電路外部的已知訊號,而非低一位的計算結果。上面考慮的是從最低位開始第三位的情況。採用類似的代入方法,可以用各位的生成訊號G_i、傳輸訊號P_i,以及最低位從外部獲取的進位訊號c_0來表示多位全加器的所有進位訊號。

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

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

參考文獻[編輯]

  1. ^ 1.0 1.1 1.2 Stephen Brown, Zvonko Vranesic. Fundamentals of Digital Logic with Verilog Design. McGraw-Hill Education. ISBN 0-07-283878-7. 
  2. ^ Geoffrey A. Lancaster. Excel HSC Software Design and Development. Pascal Press. 2004: 180. ISBN 9781741251753. 
  3. ^ M. Morris Mano. Digital Logic and Computer Design. Prentice-Hall. 1979: 119-123. ISBN 0-13-214510-3. 
  4. ^ 4.0 4.1 鄧元慶,關宇,賈鵬,石會. 數字設計基礎與應用. 清華大學出版社. ISBN 978-7-302-21406-9. 
  5. ^ Burgess, N. Fast Ripple-Carry Adders in Standard-Cell CMOS VLSI. 20th IEEE Symposium on Computer Arithmetic. 2011: 103–111. 
  6. ^ Fast Addition: Carry Lookahead Adders. University of Maryland. [2013-02-28]. 

外部連結[編輯]