二进制编码十进位课件.ppt

1、4.1 計算機的加法加法（addition）是計算機中最基本的運算。減法（subtraction）、乘法（multiplication）或除法（division），都可以利用加法運算來完成。實現加法的硬體電路稱為加法器（adder），是計算機算術的最基本元件。進位是加法運算中最需要考量的因素之一，所有處理加法的電路，其設計重心都是放在如何解決進位的問題。4.2 漣波進位加法器（RCA）單一位元的加法器由單位元全加器組成的漣波進位加法器漣波進位加法器的時間延遲4.2.1 單一位元的加法器半加器（half adder，HA）：考慮兩個輸入位元相加之總和與進位值。1個邏輯閘的時間延遲即可完成。xy+

2、c s00+0 001+0 110+0 111+1 0CarrycSums0 00 11 01 100010110 x yCarrySumxyxyscscHA單位元半加器的真值表與電路圖 4.2.1 單一位元的加法器全加器（full adder，FA）：考慮2個輸入位元。考慮前一位數完成加法運算後所產生的進位值。需要經過3個邏輯閘的延遲時間。0000111100110011010101010001011101101001011111cicici+1xixiyisiyi00 0111 10si=xi+yi+ci011111cixiyi00 0111 10ci+1=xiyi+xici+yiciSi

3、Ci+1xixiyixiciyiciyici原始全加器之和與進位邏輯式所繪出之電路圖 4.2.1 單一位元的加法器全加器（full adder，FA）：可將全加器所得到的邏輯式子進一步化簡，可產生簡化邏輯電路。簡化後電路完成一次運算只需2個邏輯閘的時間。加法器中的最基本單位。xici+1siyiciZXY簡化之單位元全加器之電路 4.2 漣波進位加法器（RCA）單一位元的加法器由單位元全加器組成的漣波進位加法器漣波進位加法器的時間延遲4.2.2 由單位元全加器組成的漣波進位加法器循序加法器（sequential adder）：從最低位數（又稱least significant sit，或簡稱L

4、SB）往最高位數（又稱most significant bit，或簡稱SB）一個位數接一個位數輸入並完成加法的設計。每次只牽涉到3個輸入位元及2個輸出位元，有多少位數，就必須做多少次運算。只需利用一個全加器與一個1位元的進位暫存器便可完成。完成n位元數加法需要3n個邏輯閘延遲的時間。4.2.2 由單位元全加器組成的漣波進位加法器循序加法器（sequential adder）：時脈a輸入端b輸入端y(carry-in)s(sum)Y(carry-out)1110（預設）01201101300110410010循序加法器電路與運算過程實例4.2.2 由單位元全加器組成的漣波進位加法器平行加法器（p

5、arallel adder）：又稱漣波進位加法器（Ripple Carry Adder，RCA）。計算兩個n位元數的相加結果，則需同時輸入兩數共2n個位元。每一位元的加法均需利用一個全加器來完成，所以n個位元的加法需要用到n個全加器。4.2.2 由單位元全加器組成的漣波進位加法器平行加法器（parallel adder）：n 個位元的平行RCA加法器結構：LSBx1y1x0c0s1s0c2c1y0MSBxn-1yn-1cn-1cnsn-1.FAn-1FA1FA04.2 漣波進位加法器（RCA）單一位元的加法器由單位元全加器組成的漣波進位加法器漣波進位加法器的時間延遲4.2.3 漣波進位加法器的

6、時間延遲考量n位元的RCA：1個邏輯閘的延遲時間完成所有成對之xi與yi的AND與XOR兩個運算。再使用 2個邏輯閘的時間來算出進位輸出（Carry-out），並傳給較高一位。平行漣波加法器電路的總延遲應為2n+1個邏輯閘的延遲時間。4.3進位前瞻加法器（CLA）進位產生條件的分析預先算出進位的加法器設計4.3.1 進位產生條件的分析進位與和的運算：對負責第i位數的全加器FAi而言，其運算產生的總和值Si與進位值Ci+1的布林代數式為：每個位元的進位值（Ci+1）都必須由較低一位元的進位值（Ci）來決定。RCA加法器產生延遲的主要關鍵。iiiiSABC1iiiiiiCABAB C4.3.1 進

7、位產生條件的分析進位產生與進位傳遞：進位產生值（generate，Gi）進位傳遞值（propagate，Pi）iiiGABiiiPAB4.3.1 進位產生條件的分析進位產生與進位傳遞：將Gi與Pi代入原始全加器的Ci+1與Si布林代數式，則可改寫為：iiiGA B iiiiiiSABCPC1 iiiiiiiiiCABAB CGPCiiiiSABC1iiiiiiCABAB CiiiPAB4.3.1 進位產生條件的分析進位產生與進位傳遞：使利用疊代技巧解開遞迴關係，即可達成進位前瞻的目的：4.3.1 進位產生條件的分析G跟P值的定義很抽象，不過其實只要發揮點想像力，把它想像成在玩推骨牌遊戲，把進位

8、當成是骨牌倒下，就不難知道其中的奧妙之處：4.3.1 進位產生條件的分析進位產生（G）：假使第i位數兩個輸入位元的值都是1（Gi=AiBi=1），那麼此處一定會產生（generate）進位；這就如同我們直接從這個地方把骨牌向前推倒一樣，而且緊鄰在它前方（第i+1位）只要有骨牌就會被它推倒。進位傳遞（P）假使兩個輸入位元中剛好有一個為1（Pi=AiBi=1），那麼只要進位輸入值也是1，就能產生進位輸出；就像放了一張骨牌在這個位子上一樣，當後面的骨牌倒過來，自己就會被往前推倒！4.3進位前瞻加法器（CLA）進位產生條件的分析預先算出進位的加法器設計4.3.2 預先算出進位的加法器設計 各單獨位元的

9、CLA部分全加電路：部分全加器（partially full adder，PFA）可計算每一單獨位元和Si的局部全加器。AiSiCiPiBiGi部分全加器電路 4.3.2 預先算出進位的加法器設計單位長度的進位前瞻加法器：將所有位元的部分全加器電路與進位前瞻邏輯電路組合，即可構成完整的進位前瞻加法器。B3A3B2A2B1A1B0A0C0C1C2C3C4S0G0P0S1G1P1S2G2P2S3G3P3PFAPFAPFAPFA 4位元進位前瞻加法器電路 4.3.2 預先算出進位的加法器設計CLA的延遲分析：1個邏輯閘延遲後就能產生所有的Gi和Pi。2個邏輯閘延遲後即可得到所有的Ci。1個邏輯閘延遲

10、後就能得到所有的Si。每個進位前瞻加法器的總延遲固定為4個邏輯閘延遲時間，而與它的長度（位元數）無關。4.4區塊漣波進位加法器（BRCA）CLA加法器：優點：改善RCA 加法器進位延遲問題。缺點：提高了進位電路的複雜度。進位前瞻邏輯電路卻會隨著全加器位元數的提高而越來越急遽地升高。無法針對所需要的任意位元數設計一個完整的CLA加法器。4.4區塊漣波進位加法器（BRCA）區塊漣波結構區塊漣波加法器的延遲分析用空間換取時間 進位選擇加法器（Carry-Select Adder，CSA）4.4.1 區塊漣波結構區塊漣波進位加法器（block ripple carry adder，BRCA）：將固定位

11、元的基本CLA加法區塊以漣波進位的方式串接起來。x31x30 x29x28CLA7y31y30y29y28s31c32c28c8c4c0s30s29s28x7x6x5x4y7y6y5y4s7s6s5s4x3x2x1x0y3y2y1y0s3s2s1s0.CLA1CLA0區塊漣波進位加法器電路 4.4區塊漣波進位加法器（BRCA）區塊漣波結構區塊漣波加法器的延遲分析用空間換取時間 進位選擇加法器（Carry-Select Adder，CSA）4.4.2 區塊漣波加法器的延遲分析延遲分析：一開始所有位元會產生1個共通邏輯閘延遲（產生Gi與Pi）。每個CLA加法區塊的進位運算產生2個邏輯閘延遲。代表最

12、高位的CLA加法區塊完成進位運算後，還需要再多1個邏輯閘延遲來計算最高幾個位數的和。4.4.2 區塊漣波加法器的延遲分析漣波進位加法器電路的總延遲公式：22ndmd：漣波進位加法器延遲m：CLA加法區塊位元n：加法運算位元 4.4區塊漣波進位加法器（BRCA）區塊漣波結構區塊漣波加法器的延遲分析用空間換取時間 進位選擇加法器（Carry-Select Adder，CSA）4.4.3 用空間換取時間 進位選擇加法器（Carry-Select Adder，CSA）進位選擇加法器：總延遲降為 。3nmc12s12s13s14s15s8s9s10s11s4s5s6s7s0s1s2s3c4c0c12c1

13、6c16c8c8101010進位選擇加法器電路，圖中每一對CLA區塊下方的小三角形就是多工器，它們會根據區塊的進位輸入值來選擇其中一個區塊所產生的輸出值。4.5 多層結構的快速加法器設計改變思維的設計觀念 平行處理實現雙層結構的加法器快速加法器的再延伸 三層的結構快速加法器的效能分析4.5.1 改變思維的設計觀念 平行處理平行處理：以加法器的設計來說，當我們擁有效能極佳的4位元CLA加法器單元之後，假使要組成更高位數的加法器，例如16位元的加法器，那麼除了直接串接成具有4個4位元CLA加法器的區塊漣波進位加法器之外，也可以利用進位產生（generate）與傳遞（propagate）觀念，以更快

14、的方法先完成所有CLA進位輸入的計算，然後再讓4個CLA同時開始計算最後的和。4.5 多層結構的快速加法器設計改變思維的設計觀念 平行處理實現雙層結構的加法器快速加法器的再延伸 三層的結構快速加法器的效能分析4.5.2 實現雙層結構的加法器二維組合的觀念：利用二維實現16位元的快速加法器。x3x2x1x0y3y2y1y0s3s2s1s04位元CLAx7x6x5x4y7y6y5y4s7s6s5s44位元CLAx11x10 x9x8y11y10y9y8s11s10s9s84位元CLAx15x14x13x12y15y14y13y12s15s14s13s124位元CLAP3Ic16c12c8c4c0G

15、3IP2IG2IP1IG1IP0IG0I進位預測邏輯電路雙層的進位前瞻加法器電路4.5.2 實現雙層結構的加法器進位前瞻的計算方法：4個CLA分別為：CLA0、CLA1、CLA2、CLA3其進位輸入分別為：C0、C4、C8、C12其進位輸出則分別為：C4、C8、C12、C164.5.2 實現雙層結構的加法器進位前瞻的計算方法：II4000II8114IIII11000IIIII110100CGP CCGP CGPGP CGP GP P CII12228IIIIIII22110100IIIIIIIII2212102100CGP CGPGP GP P CGP GP P GP P P CII1633

16、12IIIIIIIIIII332212102100IIIIIIIIIIIIII332321321032100CGP CGPGP GP P GP P P CGP GP P GP P P GP P P P C4.5.2 實現雙層結構的加法器進位前瞻的計算方法：I4343424342414342414iiiiiiiiiiiGGPGPPGPPPGI4342414iiiiiPPPPP4.5.2 實現雙層結構的加法器雙層加法器的運作流程：步驟一：A、B兩數各16位元輸入後，各位數先分別計算Gi與Pi。步驟二：各位元之 與 （i=015）傳入4個第一級進位前瞻邏輯電路，然後分別計算出 與 （j=03）。步驟

17、三：4組 與 I傳入第二級進位前瞻邏輯電路後，配合C0的輸入，計算出C4、C8、C12、C16。IjGIjGIjGIjPIjPIjP4.5.2 實現雙層結構的加法器步驟四：C0、C4、C8、C12分別輸入4個第一級進位前瞻邏輯電路，配合所有的Gi與Pi（i=015），得到所有的Ci（i=015）。步驟五：所有Ci（i=015）傳回最上層的部分全加器，計算出最終的和。4.5 多層結構的快速加法器設計改變思維的設計觀念 平行處理實現雙層結構的加法器快速加法器的再延伸 三層的結構快速加法器的效能分析4.5.3 快速加法器的再延伸 三層的結構三層的64位元加法器：c8c4c0 x03y034位元CLA

18、s03P0IG0Ix47y474位元CLAs47P1IG1Ix811y8114位元CLAs811P2IG2I第一層進位前瞻預測電路(0)c12x1215y12154位元CLAs1215P3IG3IG0IIP0IIc16c64c24c20 x1619y16194位元CLAs1619P4IG4Ix2023y20234位元CLAs2023P5IG5Ix2427y24274位元CLAs2427P6IG6I第一層進位前瞻預測電路(1)c28x2831y28314位元CLAs2831P7IG7IG1IIP1IIc32c40c36x3235y32354位元CLAs3235P8IG8Ix3639y36394位

19、元CLAs3639P9IG9Ix4043y40434位元CLAs4043P10IG10I第一層進位前瞻預測電路(2)c44x4447y44474位元CLAs4447P11IG11IG2IIP2IIc48c56c52x4851y48514位元CLAs4851P12IG12Ix5255y52554位元CLAs5255P13IG13Ix5659y56594位元CLAs5659P14IG14I第一層進位前瞻預測電路(3)c60 x6063y60634位元CLAs6063P15IG15IG3IIP3II第二層進位前瞻預測電路三層的進位前瞻加法器電路 4.5.3 快速加法器的再延伸 三層的結構運作流程：步

20、驟一：A、B兩數所有位元輸入後，各位數先分別計算Gi與Pi。步驟二：各位數之Gi與Pi（i=063）傳入16個第一級進位前瞻邏輯電路，然後分別計算 與 （j=015）。步驟三：16組 與 傳入4個第二級進位前瞻邏輯電路後，分別計算出 與 （k=03）。IjGIjPIjGIjPIIkPIIkG4.5.3 快速加法器的再延伸 三層的結構步驟四：4組 與 傳入第三級進位前瞻邏輯電路後，配合C0的輸入，計算出C16、C32、C48、C64。步驟五：C0、C16、C32、C48分別輸入4個第二級進位前瞻邏輯電路，配合所有的 與 ，得到所有的C4j（j=015）。IIkGIIkPIjGIjP4.5.3 快

21、速加法器的再延伸 三層的結構步驟六：C4j（j=015）分別輸入16個第一級進位前瞻邏輯電路，配合所有的Gi與Pi，得到所有的Ci（i=063）。步驟七：所有Ci（i=063）傳回最上層的64個部分全加器，計算出最終的和S。4.5 多層結構的快速加法器設計改變思維的設計觀念 平行處理實現雙層結構的加法器快速加法器的再延伸 三層的結構快速加法器的效能分析4.5.4 快速加法器的效能分析16位元快速加法器效能分析：項次運算內容所需邏輯閘延遲步驟一計算Gi與Pi1步驟二計算GjI與PjI2步驟三計算出C4、C8、C12、C162步驟四計算所有位元的Ci2步驟五計算出最終的和1總 和完成16位元的加法

22、84.5.4 快速加法器的效能分析64位元快速加法器效能分析：項次運算內容所需邏輯閘延遲步驟一計算Gi與Pi1步驟二計算GjI與PjI2步驟三計算GkII與PkII2步驟四計算出C16、C32、C48、C642步驟五計算出所有的C4j，j=0152步驟六計算所有位元的Ci2步驟七計算出最終的和1總和完成64位元的加法124.6 減法與加減法器設計線路共用與加減法的選擇溢位的處理4.6.1 線路共用與加減法的選擇加減法器：減法器整合到加法器中的設計。原理：對於任一加法運算，如A+B，可視為加法運算A+B+0；而對於任一減法運算A-B，則可視為有號數A+(-B)的加法運算，若將(-B)用二補數表示

23、為(B)+1，則減法運算A-B 便可視為加法運算A+(B)+1。4.6.1 線路共用與加減法的選擇加/減法器電路：s0C0s1B0B1A0A1Bn-1An-1Cnsn-1AddSub控制輸入n 位元加法器4.6 減法與加減法器設計線路共用與加減法的選擇溢位的處理4.6.2 溢位的處理加減法器溢位現象的檢測規則：在加減法過程中，若符號位元（一般即最高位元）的進位輸入值等於符號位元的進位輸出值，則沒有溢位現象的發生；若符號位元的進位輸入值不等於符號位元的進位輸出值，則溢位現象便會發生。通常加減法器可能發生溢位的情況有以下四種：正+正、負+負、正-負、負-正。4.6.2 溢位的處理加減法器溢位現象的

24、檢測可利用XOR邏輯閘來完成。Cin：符號位元的進位輸入值。Cout：進位輸出值。CinCoutCin XOR Cout0000111011104.6.2 溢位的處理具有溢位檢測的加減法器電路：s0C0s1B0B1A0A1Bn-1An-1Cnsn-1cn-1AddSub控制輸入n 位元加法器溢位4.7 二進制編碼十十進位（BCD）加法器二進制編碼十進位（BCD）表示法：用二進位形式編碼十進位數目的每個位數。十進制數字與所對應的二元編碼 4.7 二進制編碼十十進位（BCD）加法器二進制編碼十進位加法的問題：兩個二進制編碼十進位數字的加法結構是較複雜的，事實上每個位數的和可能超過9，在這個情形下，

25、數字修正動作是必須要做的。4.7 二進制編碼十十進位（BCD）加法器加法問題的解決辦法：需要修正動作的兩種情形：兩個四位元數總和超過，但是沒有進位現象產生。兩個四位元數總和超過15，以致有進位現象產生。+1 1 0 0 0 1 1 1 0 1 0 1+X Y Z+7 5 12 0 1 1 0+1 0 0 1 0 進位+1 0 0 0 1 1 0 0 0 1 0 0 1+X Y Z+8 9 17 0 1 1 0+1 0 1 1 1 進位 S=2 S=7 4.7 二進制編碼十十進位（BCD）加法器加法問題的解決辦法：數字修正原則：ZXY如果 ，則 且 進位為 0；9Z SZ如果 ，則 且 進位為 1；6S Z 9Z 4.7 二進制編碼十十進位（BCD）加法器建構單位數BCD加法器：SZ0XY604位元加法器判斷sum 94位元加法器修正多工器進位輸出cout單位數BCD加法器的區塊圖4.7 二進制編碼十十進位（BCD）加法器建構單位數BCD加法器：cincoutx1x1x1x0y3y2y1y0z3z2z1z0s3s2s1s02位元加法器4位元加法器一位數二進制編碼十進位加法器電路