加法（addition）是計算機中最基本的運算。

Presentation on theme: "加法（addition）是計算機中最基本的運算。"— Presentation transcript:

1 加法（addition）是計算機中最基本的運算。
4.1 計算機的加法 加法（addition）是計算機中最基本的運算。 減法（subtraction）、乘法（multiplication）或除法（division），都可以利用加法運算來完成。 實現加法的硬體電路稱為加法器（adder），是計算機算術的最基本元件。 進位是加法運算中最需要考量的因素之一，所有處理加法的電路，其設計重心都是放在如何解決進位的問題。

2 4.2 漣波進位加法器（RCA） 單一位元的加法器 由單位元全加器組成的漣波進位加法器 漣波進位加法器的時間延遲

3 4.2.1 單一位元的加法器 半加器（half adder，HA） ： 考慮兩個輸入位元相加之總和與進位值。 1個邏輯閘的時間延遲即可完成。
單一位元的加法器 半加器（half adder，HA） ： 考慮兩個輸入位元相加之總和與進位值。 1個邏輯閘的時間延遲即可完成。 單位元半加器的真值表與電路圖

4 原始全加器之和與進位邏輯式所繪出之電路圖
單一位元的加法器 全加器（full adder，FA）： 考慮2個輸入位元。 考慮前一位數完成加法運算後所產生的進位值。 需要經過3個邏輯閘的延遲時間。 原始全加器之和與進位邏輯式所繪出之電路圖

5 4.2.1 單一位元的加法器 全加器（full adder，FA）： 可將全加器所得到的邏輯式子進一步化簡，可產生簡化邏輯電路。
單一位元的加法器 全加器（full adder，FA）： 可將全加器所得到的邏輯式子進一步化簡，可產生簡化邏輯電路。 簡化後電路完成一次運算只需2個邏輯閘的時間。 加法器中的最基本單位。 簡化之單位元全加器之電路

6 4.2 漣波進位加法器（RCA） 單一位元的加法器 由單位元全加器組成的漣波進位加法器 漣波進位加法器的時間延遲

7 循序加法器（sequential adder）：
由單位元全加器組成的漣波進位加法器 循序加法器（sequential adder）： 從最低位數（又稱least significant sit，或簡稱LSB）往最高位數（又稱most significant bit，或簡稱ＭSB）一個位數接一個位數輸入並完成加法的設計。 每次只牽涉到3個輸入位元及2個輸出位元，有多少位數，就必須做多少次運算。 只需利用一個全加器與一個1位元的進位暫存器便可完成。 完成n位元數加法需要3n個邏輯閘延遲的時間。

8 循序加法器（sequential adder）：
由單位元全加器組成的漣波進位加法器 循序加法器（sequential adder）： 時脈 a輸入端 b輸入端 y (carry-in) s (sum) Y (carry-out) 1 0（預設） 2 3 4 循序加法器電路與運算過程實例

9 平行加法器（parallel adder）：
由單位元全加器組成的漣波進位加法器 平行加法器（parallel adder）： 又稱漣波進位加法器（Ripple Carry Adder，RCA）。 計算兩個n位元數的相加結果，則需同時輸入兩數共2n個位元。 每一位元的加法均需利用一個全加器來完成，所以n個位元的加法需要用到n個全加器。

10 平行加法器（parallel adder）：
由單位元全加器組成的漣波進位加法器 平行加法器（parallel adder）： n 個位元的平行RCA加法器結構：

11 4.2 漣波進位加法器（RCA） 單一位元的加法器 由單位元全加器組成的漣波進位加法器 漣波進位加法器的時間延遲

12 4.2.3 漣波進位加法器的時間延遲 考量n位元的RCA： 1個邏輯閘的延遲時間完成所有成對之xi與yi的AND與XOR兩個運算。
漣波進位加法器的時間延遲 考量n位元的RCA： 1個邏輯閘的延遲時間完成所有成對之xi與yi的AND與XOR兩個運算。 再使用 2個邏輯閘的時間來算出進位輸出（Carry-out），並傳給較高一位。 平行漣波加法器電路的總延遲應為2n+1個邏輯閘的延遲時間。

13 4.3 進位前瞻加法器（CLA） 進位產生條件的分析 預先算出進位的加法器設計

14 4.3.1 進位產生條件的分析 進位與和的運算： 對負責第i位數的全加器FAi而言，其運算產生的總和值Si與進位值Ci+1的布林代數式為：
進位產生條件的分析 進位與和的運算： 對負責第i位數的全加器FAi而言，其運算產生的總和值Si與進位值Ci+1的布林代數式為： 每個位元的進位值（Ci+1）都必須由較低一位元的進位值（Ci）來決定。 RCA加法器產生延遲的主要關鍵。

15 進位產生條件的分析 進位產生與進位傳遞： 進位產生值（generate，Gi） 進位傳遞值（propagate，Pi）

16 進位產生條件的分析 進位產生與進位傳遞： 將Gi與Pi代入原始全加器的Ci+1與Si布林代數式，則可改寫為：

17 進位產生條件的分析 進位產生與進位傳遞： 使利用疊代技巧解開遞迴關係，即可達成進位前瞻的目的：

18 進位產生條件的分析 G跟P值的定義很抽象，不過其實只要發揮點想像力，把它想像成在玩推骨牌遊戲，把進位當成是骨牌倒下，就不難知道其中的奧妙之處：

19 進位產生條件的分析 進位產生（G）：假使第i位數兩個輸入位元的值都是1（Gi=AiBi=1），那麼此處一定會產生（generate）進位；這就如同我們直接從這個地方把骨牌向前推倒一樣，而且緊鄰在它前方（第i+1位）只要有骨牌就會被它推倒。 進位傳遞（P）假使兩個輸入位元中剛好有一個為1（Pi=AiBi=1），那麼只要進位輸入值也是1，就能產生進位輸出；就像放了一張骨牌在這個位子上一樣，當後面的骨牌倒過來，自己就會被往前推倒！

20 4.3 進位前瞻加法器（CLA） 進位產生條件的分析 預先算出進位的加法器設計

21 4.3.2 預先算出進位的加法器設計 各單獨位元的CLA部分全加電路： 部分全加器（partially full adder，PFA）
預先算出進位的加法器設計 各單獨位元的CLA部分全加電路： 部分全加器（partially full adder，PFA） 可計算每一單獨位元「和」Si的局部全加器。 部分全加器電路

22 4.3.2 預先算出進位的加法器設計 單位長度的進位前瞻加法器：
預先算出進位的加法器設計 單位長度的進位前瞻加法器： 將所有位元的部分全加器電路與進位前瞻邏輯電路組合，即可構成完整的進位前瞻加法器。 4位元進位前瞻加法器電路

23 4.3.2 預先算出進位的加法器設計 CLA的延遲分析： 1個邏輯閘延遲後就能產生所有的Gi和Pi。 2個邏輯閘延遲後即可得到所有的Ci。
預先算出進位的加法器設計 CLA的延遲分析： 1個邏輯閘延遲後就能產生所有的Gi和Pi。 2個邏輯閘延遲後即可得到所有的Ci。 1個邏輯閘延遲後就能得到所有的Si。 每個進位前瞻加法器的總延遲固定為4個邏輯閘延遲時間，而與它的長度（位元數）無關。

24 4.4 區塊漣波進位加法器（BRCA） CLA加法器： 優點： 缺點： 改善RCA 加法器進位延遲問題。 提高了進位電路的複雜度。
進位前瞻邏輯電路卻會隨著全加器位元數的提高而越來越急遽地升高。 無法針對所需要的任意位元數設計一個完整的CLA加法器。

25 （Carry-Select Adder，CSA）
4.4 區塊漣波進位加法器（BRCA） 區塊漣波結構 區塊漣波加法器的延遲分析 用空間換取時間 － 進位選擇加法器 （Carry-Select Adder，CSA）

26 區塊漣波進位加法器（block ripple carry adder，BRCA）：
區塊漣波結構 區塊漣波進位加法器（block ripple carry adder，BRCA）： 將固定位元的基本CLA加法區塊以漣波進位的方式串接起來。 區塊漣波進位加法器電路

27 （Carry-Select Adder，CSA）
4.4 區塊漣波進位加法器（BRCA） 區塊漣波結構 區塊漣波加法器的延遲分析 用空間換取時間 － 進位選擇加法器 （Carry-Select Adder，CSA）

28 4.4.2 區塊漣波加法器的延遲分析 延遲分析： 一開始所有位元會產生1個共通邏輯閘延遲（產生Gi與Pi）。
區塊漣波加法器的延遲分析 延遲分析： 一開始所有位元會產生1個共通邏輯閘延遲（產生Gi與Pi）。 每個CLA加法區塊的進位運算產生2個邏輯閘延遲 。 代表最高位的CLA加法區塊完成進位運算後，還需要再多1個邏輯閘延遲來計算最高幾個位數的和。

29 區塊漣波加法器的延遲分析 漣波進位加法器電路的總延遲公式： d：漣波進位加法器延遲 m：CLA加法區塊位元 n：加法運算位元

30 （Carry-Select Adder，CSA）
4.4 區塊漣波進位加法器（BRCA） 區塊漣波結構 區塊漣波加法器的延遲分析 用空間換取時間 － 進位選擇加法器 （Carry-Select Adder，CSA）

31 4.4.3 用空間換取時間 － 進位選擇加法器（Carry-Select Adder，CSA）
進位選擇加法器： 總延遲降為 。 進位選擇加法器電路，圖中每一對CLA區塊下方的小三角形就是多工器，它們會根據區塊的進位輸入值來選擇其中一個區塊所產生的輸出值。

32 改變思維的設計觀念 － 平行處理 實現雙層結構的加法器 快速加法器的再延伸 － 三層的結構 快速加法器的效能分析
4.5 多層結構的快速加法器設計 改變思維的設計觀念 － 平行處理 實現雙層結構的加法器 快速加法器的再延伸 － 三層的結構 快速加法器的效能分析

33 改變思維的設計觀念 － 平行處理 平行處理： 以加法器的設計來說，當我們擁有效能極佳的4位元CLA加法器單元之後，假使要組成更高位數的加法器，例如16位元的加法器，那麼除了直接串接成具有4個4位元CLA加法器的區塊漣波進位加法器之外，也可以利用進位產生（generate）與傳遞（propagate）觀念，以更快的方法先完成所有CLA進位輸入的計算，然後再讓4個CLA同時開始計算最後的和。

34 改變思維的設計觀念 － 平行處理 實現雙層結構的加法器 快速加法器的再延伸 － 三層的結構 快速加法器的效能分析
4.5 多層結構的快速加法器設計 改變思維的設計觀念 － 平行處理 實現雙層結構的加法器 快速加法器的再延伸 － 三層的結構 快速加法器的效能分析

35 實現雙層結構的加法器 二維組合的觀念： 利用二維實現16位元的快速加法器。 雙層的進位前瞻加法器電路

36 4.5.2 實現雙層結構的加法器 進位前瞻的計算方法： 4個CLA分別為： 其進位輸入分別為： 其進位輸出則分別為：
實現雙層結構的加法器 進位前瞻的計算方法： 4個CLA分別為： CLA0、CLA1、CLA2、CLA3 其進位輸入分別為： C0、C4、C8、C12 其進位輸出則分別為： C4、C8、C12、C16

37 實現雙層結構的加法器 進位前瞻的計算方法：

38 實現雙層結構的加法器 進位前瞻的計算方法：

39 4.5.2 實現雙層結構的加法器 雙層加法器的運作流程： 步驟一：A、B兩數各16位元輸入後，各位數先分別計算Gi與Pi。
實現雙層結構的加法器 雙層加法器的運作流程： 步驟一：A、B兩數各16位元輸入後，各位數先分別計算Gi與Pi。 步驟二：各位元之 與 （i= 0~15）傳入4個第一級進位前瞻邏輯電路，然後分別計算出 與 （j= 0~3）。 步驟三：4組 與 I傳入第二級進位前瞻邏輯電路後，配合C0的輸入，計算出C4、C8、C12、C16。

40 實現雙層結構的加法器 步驟四：C0、C4、C8、C12分別輸入4個第一級進位前瞻邏輯電路，配合所有的Gi與Pi（i = 0~15），得到所有的Ci（i = 0~15）。 步驟五：所有Ci（i = 0~15）傳回最上層的部分全加器，計算出最終的和Ｓ。

41 改變思維的設計觀念 － 平行處理 實現雙層結構的加法器 快速加法器的再延伸 － 三層的結構 快速加法器的效能分析
4.5 多層結構的快速加法器設計 改變思維的設計觀念 － 平行處理 實現雙層結構的加法器 快速加法器的再延伸 － 三層的結構 快速加法器的效能分析

42 快速加法器的再延伸 － 三層的結構 三層的64位元加法器： 三層的進位前瞻加法器電路

43 運作流程： 4.5.3 快速加法器的再延伸 － 三層的結構 步驟一：A、B兩數所有位元輸入後，各位數先分別計算Gi與Pi。
快速加法器的再延伸 － 三層的結構 運作流程： 步驟一：A、B兩數所有位元輸入後，各位數先分別計算Gi與Pi。 步驟二：各位數之Gi與Pi（i= 0~63）傳入16個第一級進位前瞻邏輯電路，然後分別計算 與 （j= 0~15）。 步驟三：16組 與 傳入4個第二級進位前瞻邏輯電路後，分別計算出 與 （k= 0~3）。

44 快速加法器的再延伸 － 三層的結構 步驟四：4組 與 傳入第三級進位前瞻邏輯電路後，配合C0的輸入，計算出C16、C32、C48、C64。 步驟五：C0、C16、C32、C48分別輸入4個第二級進位前瞻邏輯電路，配合所有的 與 ，得到所有的C4j（j = 0~15）。

45 快速加法器的再延伸 － 三層的結構 步驟六：C4j（j = 0~15）分別輸入16個第一級進位前瞻邏輯電路，配合所有的Gi與Pi，得到所有的Ci（i = 0~63）。 步驟七：所有Ci（i = 0~63）傳回最上層的64個部分全加器，計算出最終的和S。

46 改變思維的設計觀念 － 平行處理 實現雙層結構的加法器 快速加法器的再延伸 － 三層的結構 快速加法器的效能分析
4.5 多層結構的快速加法器設計 改變思維的設計觀念 － 平行處理 實現雙層結構的加法器 快速加法器的再延伸 － 三層的結構 快速加法器的效能分析

47 4.5.4 快速加法器的效能分析 16位元快速加法器效能分析： 項次 運算內容 所需邏輯閘延遲 步驟一 計算Gi與Pi 1 步驟二
快速加法器的效能分析 16位元快速加法器效能分析： 項次 運算內容 所需邏輯閘延遲 步驟一 計算Gi與Pi 1 步驟二 計算GjI與PjI 2 步驟三 計算出C4、C8、C12、C16 步驟四 計算所有位元的Ci 步驟五 計算出最終的和Ｓ 總 和 完成16位元的加法 8

48 4.5.4 快速加法器的效能分析 64位元快速加法器效能分析： 項次 運算內容 所需邏輯閘延遲 步驟一 計算Gi與Pi 1 步驟二
快速加法器的效能分析 64位元快速加法器效能分析： 項次 運算內容 所需邏輯閘延遲 步驟一 計算Gi與Pi 1 步驟二 計算GjI與PjI 2 步驟三 計算GkII與PkII 步驟四 計算出C16、C32、C48、C64 步驟五 計算出所有的C4j，j = 0~15 步驟六 計算所有位元的Ci 步驟七 計算出最終的和Ｓ 總　和 完成64位元的加法 12

49 4.6 減法與加減法器設計 線路共用與加減法的選擇 溢位的處理

50 4.6.1 線路共用與加減法的選擇 加／減法器： 減法器整合到加法器中的設計。 原理：
線路共用與加減法的選擇 加／減法器： 減法器整合到加法器中的設計。 原理： 對於任一加法運算，如A+B，可視為加法運算A+B+0；而對於任一減法運算A-B，則可視為有號數A+(B)的加法運算，若將(B)用二補數表示為(~B)+1，則減法運算AB 便可視為加法運算A+(~B)+1。

51 線路共用與加減法的選擇 加/減法器電路：

52 4.6 減法與加減法器設計 線路共用與加減法的選擇 溢位的處理

53 溢位的處理 加減法器溢位現象的檢測規則： 在加減法過程中，若符號位元（一般即最高位元）的進位輸入值等於符號位元的進位輸出值，則沒有溢位現象的發生；若符號位元的進位輸入值不等於符號位元的進位輸出值，則溢位現象便會發生。 通常加減法器可能發生溢位的情況有以下四種：正+正、負+負、正-負、負-正。

54 加減法器溢位現象的檢測可利用XOR邏輯閘來完成。
溢位的處理 加減法器溢位現象的檢測可利用XOR邏輯閘來完成。 Cin：符號位元的進位輸入值。 Cout：進位輸出值。 Cin Cout Cin XOR Cout 1

55 溢位的處理 具有溢位檢測的加減法器電路：

56 4.7 二進制編碼十進位（BCD）加法器 二進制編碼十進位（BCD）表示法： 用二進位形式編碼十進位數目的每個位數。
十進制數字與所對應的二元編碼

57 4.7 二進制編碼十進位（BCD）加法器 二進制編碼十進位加法的問題 ：
兩個二進制編碼十進位數字的加法結構是較複雜的，事實上每個位數的和可能超過9，在這個情形下，數字修正動作是必須要做的。

58 4.7 二進制編碼十進位（BCD）加法器 加法問題的解決辦法： 需要修正動作的兩種情形： 兩個四位元數總和超過，但是沒有進位現象產生。
兩個四位元數總和超過15，以致有進位現象產生。

59 4.7 二進制編碼十進位（BCD）加法器 加法問題的解決辦法： 數字修正原則： 如果 ，則 且 進位為 0； 如果 ，則 且 進位為 1；

60 4.7 二進制編碼十進位（BCD）加法器 建構單位數BCD加法器： 單位數BCD加法器的區塊圖

61 4.7 二進制編碼十進位（BCD）加法器 建構單位數BCD加法器： 一位數二進制編碼十進位加法器電路