設(shè)計(jì)運(yùn)算功能塊

1、EE141 Digital Integrated Circuits2ndArithmetic Circuits1Jan M. RabaeyAnantha ChandrakasanBorivoje NikolicJan M. RabaeyAnantha ChandrakasanBorivoje Nikolic福州大學(xué)微電子系福州大學(xué)微電子系王仁平王仁平EE141 Digital Integrated Circuits2ndArithmetic Circuits2q應(yīng)用前面介紹的技術(shù)來設(shè)計(jì)數(shù)據(jù)通道中應(yīng)用前面介紹的技術(shù)來設(shè)計(jì)數(shù)據(jù)通道中經(jīng)常用到的一些電路如加法器、乘法器經(jīng)常用到的一些電路如加法器、乘法

2、器和移位器和移位器q考慮性能、面積或功耗的設(shè)計(jì)考慮性能、面積或功耗的設(shè)計(jì)q數(shù)據(jù)通道模塊的邏輯和系統(tǒng)優(yōu)化數(shù)據(jù)通道模塊的邏輯和系統(tǒng)優(yōu)化q數(shù)據(jù)通道中功耗與延時(shí)綜合考慮數(shù)據(jù)通道中功耗與延時(shí)綜合考慮EE141 Digital Integrated Circuits2ndArithmetic Circuits3INPUT-OUTPUTEE141 Digital Integrated Circuits2ndArithmetic Circuits4q是處理器的核心，它完成所有計(jì)算的場(chǎng)是處理器的核心，它完成所有計(jì)算的場(chǎng)所。所。q一個(gè)典型的數(shù)據(jù)通道由邏輯運(yùn)算和算術(shù)一個(gè)典型的數(shù)據(jù)通道由邏輯運(yùn)算和算術(shù)運(yùn)算等基本的組合

3、功能互連而成，中間運(yùn)算等基本的組合功能互連而成，中間結(jié)果存放在寄存器中。結(jié)果存放在寄存器中。q應(yīng)用決定了數(shù)據(jù)通道設(shè)計(jì)的約束條件應(yīng)用決定了數(shù)據(jù)通道設(shè)計(jì)的約束條件: 速度、功耗、面積。速度、功耗、面積。EE141 Digital Integrated Circuits2ndArithmetic Circuits5q邏輯層次上優(yōu)化：重新安排布爾方程以得到邏輯層次上優(yōu)化：重新安排布爾方程以得到一個(gè)速度較快或面積較小的電路一個(gè)速度較快或面積較小的電路q電路層優(yōu)化：改變管子尺寸及電路的拓?fù)溥B電路層優(yōu)化：改變管子尺寸及電路的拓?fù)溥B接來優(yōu)化速度接來優(yōu)化速度 是限制速度的元件，優(yōu)化可在邏輯層次和是限制速度的元件

4、，優(yōu)化可在邏輯層次和電路層上進(jìn)行。電路層上進(jìn)行。EE141 Digital Integrated Circuits2ndArithmetic Circuits6ABCoutSumCinFulladderEE141 Digital Integrated Circuits2ndArithmetic Circuits7SABCi=A=BCiABCiABCiABCi+CoABBCiACi+=ABCoutSumCinFulladderEE141 Digital Integrated Circuits2ndArithmetic Circuits8定義僅依賴定義僅依賴 A, BA, B的三個(gè)新變量的三個(gè)新變

5、量G G，P P，D D進(jìn)位產(chǎn)生進(jìn)位產(chǎn)生(G) = AB(G) = AB進(jìn)位傳播進(jìn)位傳播 (P) = A (P) = A B B進(jìn)位取消（進(jìn)位取消（D D） = = A A B B同樣也能推導(dǎo)出同樣也能推導(dǎo)出 S S、C C為為P P、D D和和CiCi的函數(shù)的函數(shù)o o EE141 Digital Integrated Circuits2ndArithmetic Circuits9最壞情況延時(shí)正比于輸入字的位數(shù)最壞情況延時(shí)正比于輸入字的位數(shù)N N在設(shè)計(jì)一個(gè)快速行波進(jìn)位加法器時(shí)，優(yōu)化在設(shè)計(jì)一個(gè)快速行波進(jìn)位加法器時(shí)，優(yōu)化t tcarrycarry比優(yōu)化比優(yōu)化t tsumsum重要的多重要的多FA

6、FAFAFAA0B0S0A1B1S1A2B2S2A3B3S3Ci,0Co,0(= Ci,1)Co,1Co,2Co,3td = O(N)tadder = (N-1)tcarry + tsum進(jìn)位位從一級(jí)波動(dòng)到另一級(jí)進(jìn)位位從一級(jí)波動(dòng)到另一級(jí)EE141 Digital Integrated Circuits2ndArithmetic Circuits1028 TransistorsABBACiCiAXVDDVDDABCiBABVDDABCiCiABACiBCoVDDSEE141 Digital Integrated Circuits2ndArithmetic Circuits11q進(jìn)行邏輯變換來減少

7、晶體管數(shù)目。只要不進(jìn)行邏輯變換來減少晶體管數(shù)目。只要不減慢進(jìn)位產(chǎn)生速度，可共享某些邏輯減慢進(jìn)位產(chǎn)生速度，可共享某些邏輯q這種需要這種需要2828個(gè)晶體管，面積大且速度慢個(gè)晶體管，面積大且速度慢q在進(jìn)位產(chǎn)生電路中堆疊許多在進(jìn)位產(chǎn)生電路中堆疊許多PMOSPMOS管管qC Co o信號(hào)的本征負(fù)載電容大，兩個(gè)擴(kuò)散電容、信號(hào)的本征負(fù)載電容大，兩個(gè)擴(kuò)散電容、6 6個(gè)個(gè)柵電容和布線電容柵電容和布線電容q進(jìn)位產(chǎn)生電路中信號(hào)傳播兩個(gè)反相級(jí)進(jìn)位產(chǎn)生電路中信號(hào)傳播兩個(gè)反相級(jí)1.1.和產(chǎn)生要求一個(gè)額外的邏輯級(jí)和產(chǎn)生要求一個(gè)額外的邏輯級(jí)EE141 Digital Integrated Circuits2ndArithm

8、etic Circuits12q在進(jìn)位產(chǎn)生電路第一個(gè)門的設(shè)計(jì)中信號(hào)在進(jìn)位產(chǎn)生電路第一個(gè)門的設(shè)計(jì)中信號(hào)C Ci i放在放在串聯(lián)級(jí)數(shù)較少的串聯(lián)級(jí)數(shù)較少的PMOSPMOS管支路上，使它的邏輯努管支路上，使它的邏輯努力降低為力降低為2 2q連接到連接到C Ci i的的NMOSNMOS管和管和PMOSPMOS管盡可能地放在靠近管盡可能地放在靠近這個(gè)門的輸出端（關(guān)鍵路徑）這個(gè)門的輸出端（關(guān)鍵路徑）q利用加法器的反相特性，即把一個(gè)全加器單元利用加法器的反相特性，即把一個(gè)全加器單元的所有輸入反相則它的所有輸出也反相，這種的所有輸入反相則它的所有輸出也反相，這種方法可以減少進(jìn)位路徑中反相級(jí)數(shù)目方法可以減少進(jìn)位路

9、徑中反相級(jí)數(shù)目EE141 Digital Integrated Circuits2ndArithmetic Circuits13ABSCoCiFAABSCoCiFAS A B CiS A B Ci=CoA B CiCoA B Ci=把一個(gè)全加器單元的所有輸入反相，則它的所有輸出也反相把一個(gè)全加器單元的所有輸入反相，則它的所有輸出也反相EE141 Digital Integrated Circuits2ndArithmetic Circuits14在一個(gè)進(jìn)位鏈中消除反相器在一個(gè)進(jìn)位鏈中消除反相器,偶數(shù)項(xiàng)用正向特性，奇數(shù)項(xiàng)用反相特性偶數(shù)項(xiàng)用正向特性，奇數(shù)項(xiàng)用反相特性A3FAFAFAEven ce

10、llOdd cellFAA0B0S0A1B1S1A2B2S2B3S3Ci,0Co,0Co,1Co,3Co,2EE141 Digital Integrated Circuits2ndArithmetic Circuits15VDDCiABBABAABKillGenerate1-Propagate0-PropagateVDDCiABCiCiBACiABBAVDDSCo24 transistorsEE141 Digital Integrated Circuits2ndArithmetic Circuits16q僅用僅用2424個(gè)管子個(gè)管子qNMOSNMOS和和PMOSPMOS鏈完全對(duì)稱，進(jìn)位產(chǎn)生電路

11、鏈完全對(duì)稱，進(jìn)位產(chǎn)生電路最多只有兩個(gè)晶體管串聯(lián)最多只有兩個(gè)晶體管串聯(lián)q連接連接C Ci i晶體管放在最接近門的輸出端處晶體管放在最接近門的輸出端處q只有進(jìn)位電路中的晶體管才需優(yōu)化尺寸只有進(jìn)位電路中的晶體管才需優(yōu)化尺寸以改善速度，求和電路的所有管子可最以改善速度，求和電路的所有管子可最小尺寸小尺寸EE141 Digital Integrated Circuits2ndArithmetic Circuits17棍棒圖棍棒圖EE141 Digital Integrated Circuits2ndArithmetic Circuits18ABPCiVDDAAAVDDCiAPABVDDVDDCiCiCo

12、SCiPPPPPSum GenerationCarry GenerationSetup 采用多路開關(guān)和采用多路開關(guān)和XORXOR來設(shè)計(jì)，使用來設(shè)計(jì)，使用2424個(gè)管子，個(gè)管子，P P為為A A和和B B的的XOR， P0，SCi，P1，SCi P0，CA，P1，CCiEE141 Digital Integrated Circuits2ndArithmetic Circuits19CoCiGiPiVDD 0_001,0,1,00,1,1iiiiiiiiiPCCPDA BDCDGC= 動(dòng)態(tài)實(shí)現(xiàn)使電路更加簡單，由動(dòng)態(tài)實(shí)現(xiàn)使電路更加簡單，由于動(dòng)態(tài)電路是單方向工作，則用于動(dòng)態(tài)電路是單方向工作，則用NMO

13、SNMOS管代替?zhèn)鬏旈T，預(yù)充電輸出管代替?zhèn)鬏旈T，預(yù)充電輸出使電路不需要使電路不需要D Di i靜態(tài)實(shí)現(xiàn)靜態(tài)實(shí)現(xiàn)動(dòng)態(tài)實(shí)現(xiàn)動(dòng)態(tài)實(shí)現(xiàn)EE141 Digital Integrated Circuits2ndArithmetic Circuits20G2 C3G3Ci,0P0G1VDD G0P1P2P3C3C2C1C0在預(yù)充電階段（在預(yù)充電階段（0 0），傳輸管進(jìn)位鏈中的所有中間節(jié)點(diǎn)都），傳輸管進(jìn)位鏈中的所有中間節(jié)點(diǎn)都被預(yù)充電到被預(yù)充電到VDDVDD，在求值階段，當(dāng)有輸入進(jìn)位且傳播信號(hào)為，在求值階段，當(dāng)有輸入進(jìn)位且傳播信號(hào)為P PK K為高電平，或進(jìn)位產(chǎn)生信號(hào)（為高電平，或進(jìn)位產(chǎn)生信號(hào)（G GK K）為

14、高電平，節(jié)點(diǎn)）為高電平，節(jié)點(diǎn)C CK K放電放電EE141 Digital Integrated Circuits2ndArithmetic Circuits21Pi + 1Gi + 1CiInverter/Sum RowPropagate/Generate RowPiGiCi - 1Ci + 1VDDGND數(shù)據(jù)通道版圖由三排組織成位片式的單元組成數(shù)據(jù)通道版圖由三排組織成位片式的單元組成: :計(jì)算進(jìn)位傳播信號(hào)計(jì)算進(jìn)位傳播信號(hào)和進(jìn)位產(chǎn)生信號(hào)和進(jìn)位產(chǎn)生信號(hào)由左到右傳播進(jìn)位由左到右傳播進(jìn)位產(chǎn)生最終的和產(chǎn)生最終的和EE141 Digital Integrated Circuits2ndArithmet

15、ic Circuits22 加法器進(jìn)位鏈在最壞情形下的延時(shí)模擬成線性加法器進(jìn)位鏈在最壞情形下的延時(shí)模擬成線性RCRC網(wǎng)絡(luò)。則網(wǎng)絡(luò)。則11(1)0.69()0.692NipijijN NtCRRC= 進(jìn)位鏈上每一節(jié)點(diǎn)的電容等于四個(gè)擴(kuò)散電容、一個(gè)反相進(jìn)位鏈上每一節(jié)點(diǎn)的電容等于四個(gè)擴(kuò)散電容、一個(gè)反相器輸入電容以及導(dǎo)線電容。反相器和器輸入電容以及導(dǎo)線電容。反相器和PMOSPMOS預(yù)充電晶體管可保預(yù)充電晶體管可保持在單位尺寸，加上導(dǎo)線電容，這些固定電容估計(jì)為持在單位尺寸，加上導(dǎo)線電容，這些固定電容估計(jì)為15fF,15fF,若若一個(gè)寬度為一個(gè)寬度為W W0 0的單位尺寸晶體管的電阻為的單位尺寸晶體管的電阻

16、為10K10K，擴(kuò)散電容為，擴(kuò)散電容為2fF2fF，則寬度為，則寬度為W W的晶體管鏈的晶體管鏈RCRC時(shí)間常數(shù)為：時(shí)間常數(shù)為：00(615).10WWRCfFfFKWW=EE141 Digital Integrated Circuits2ndArithmetic Circuits23q進(jìn)位旁路加法器進(jìn)位旁路加法器q線性進(jìn)位選擇加法器線性進(jìn)位選擇加法器q平方根進(jìn)位加法器平方根進(jìn)位加法器 加法器速度與位數(shù)的線性關(guān)系使得采用逐位進(jìn)加法器速度與位數(shù)的線性關(guān)系使得采用逐位進(jìn)位加法器實(shí)現(xiàn)長字不現(xiàn)實(shí)，需要進(jìn)行邏輯優(yōu)化，使位加法器實(shí)現(xiàn)長字不現(xiàn)實(shí)，需要進(jìn)行邏輯優(yōu)化，使加法器加法器t tp pO(N)O(N)E

17、E141 Digital Integrated Circuits2ndArithmetic Circuits24FAFAFAFAP0G1P0G1P2G2P3G3Co,3Co,2Co,1Co,0Ci,0FAFAFAFAP0G1P0G1P2G2P3G3Co,2Co,1Co,0Ci,0Co,3MultiplexerBP=PoP1P2P3Idea: If (P0 and P1 and P2 and P3 = 1)then Co3 = C0, else “kill” or “generate”. 因增加旁路因增加旁路而增加的面積很而增加的面積很小，但破壞規(guī)則小，但破壞規(guī)則的位片式結(jié)構(gòu)的位片式結(jié)構(gòu) 用來加

18、速加法器用來加速加法器操作，當(dāng)操作，當(dāng)BPBP1 1時(shí)，時(shí)，進(jìn)位輸入通過旁路立進(jìn)位輸入通過旁路立即送到下一個(gè)模塊，即送到下一個(gè)模塊，若若BPBP0 0，則通過正，則通過正常路徑得到進(jìn)位輸出常路徑得到進(jìn)位輸出EE141 Digital Integrated Circuits2ndArithmetic Circuits25Carrypropaga t io nSetupBit 03SumM bitstsetuptsumCarrypropaga t io nSetupBit 47SumtbypassCarrypropaga t io nSetupBit 811SumCarrypropaga t io

19、 nSetupBit 1215Sum 最壞情況下進(jìn)位產(chǎn)生于第一位的位置，逐位通過第一個(gè)模最壞情況下進(jìn)位產(chǎn)生于第一位的位置，逐位通過第一個(gè)模塊，躍過（塊，躍過（N/M-1)N/M-1)個(gè)旁路級(jí)，并且被吸收在最后一位的位置上個(gè)旁路級(jí)，并且被吸收在最后一位的位置上而不產(chǎn)生輸出進(jìn)位而不產(chǎn)生輸出進(jìn)位假設(shè)整個(gè)加法器被劃分成假設(shè)整個(gè)加法器被劃分成(N/M)(N/M)個(gè)等長的旁路級(jí)個(gè)等長的旁路級(jí), ,每一級(jí)含有每一級(jí)含有M M位位EE141 Digital Integrated Circuits2ndArithmetic Circuits26tadder = tsetup + Mtcarry + (N/M-1

20、)tbypass + (M-1)tcarry + tsum各部分參數(shù)含義：各部分參數(shù)含義：t tsetupsetup: :形成進(jìn)位產(chǎn)生信號(hào)和進(jìn)位傳播信號(hào)所需要的固定時(shí)間形成進(jìn)位產(chǎn)生信號(hào)和進(jìn)位傳播信號(hào)所需要的固定時(shí)間t tcarrycarry: :通過一位的傳播延時(shí)，最壞情況下通過具有通過一位的傳播延時(shí)，最壞情況下通過具有M M位的一個(gè)位的一個(gè)級(jí)進(jìn)位傳播延時(shí)為級(jí)進(jìn)位傳播延時(shí)為M M倍倍t tbypassbypass: :通過一級(jí)旁路多路開關(guān)的傳播時(shí)間通過一級(jí)旁路多路開關(guān)的傳播時(shí)間t tsumsum: :產(chǎn)生最后一級(jí)的產(chǎn)生最后一級(jí)的“和和”所需要的時(shí)間所需要的時(shí)間EE141 Digital Int

21、egrated Circuits2ndArithmetic Circuits27Ntpripple adderbypass adder4.8EE141 Digital Integrated Circuits2ndArithmetic Circuits28Setup0 Carry Propagation1 Carry PropagationMultiplexerSum GenerationCo,k-1Co,k+301P,GCarry Vector 在在 用一個(gè)最小的延時(shí)用一個(gè)最小的延時(shí)來完成，但增加硬件來完成，但增加硬件開銷開銷30%30%EE141 Digital Integrated Cir

22、cuits2ndArithmetic Circuits2901Sum Gen e r a t i onMultiple x e r1-Carry0-CarrySetupCi,0Co,3Co,7Co,11Co,15S03Bit 03Bit 47Bit 811Bit 121501Sum Gen e r a t i onMultiple x e r1-Carry0-CarrySetupS4701Sum Gen e r a t i onMultiple x e r1-Carry0-Carry0-CarrySetupS81101Sum Gen e r a t i onMultiple x e r1-Ca

23、rrySetupS1215EE141 Digital Integrated Circuits2ndArithmetic Circuits30q最壞情況下的傳播延時(shí)最壞情況下的傳播延時(shí)tadder = tsetup + Mtcarry + (N/M)tmux + tsum 傳播延時(shí)正比于傳播延時(shí)正比于N N，形成這一線性關(guān)系的，形成這一線性關(guān)系的原因是在最壞情形下選擇原因是在最壞情形下選擇0 0或或1 1的運(yùn)算結(jié)果模的運(yùn)算結(jié)果模塊選擇信號(hào)仍然必須逐一通過所有級(jí)塊選擇信號(hào)仍然必須逐一通過所有級(jí) 為優(yōu)化設(shè)計(jì)，假設(shè)全加器和多路開關(guān)具有相為優(yōu)化設(shè)計(jì)，假設(shè)全加器和多路開關(guān)具有相同的傳播延時(shí)，等于歸一化的值

24、同的傳播延時(shí)，等于歸一化的值1 1。在最壞情形。在最壞情形下將輸入時(shí)間信號(hào)到達(dá)節(jié)點(diǎn)的時(shí)間標(biāo)在圖上下將輸入時(shí)間信號(hào)到達(dá)節(jié)點(diǎn)的時(shí)間標(biāo)在圖上EE141 Digital Integrated Circuits2ndArithmetic Circuits31Setup0 Carry 1 Carry MultiplexerSum Generation01Setup0 Carry 1 Carry MultiplexerSum Generation01Setup0 Carry 1 Carry MultiplexerSum Generation01Setup0 Carry 1 Carry Multiplexer

25、Sum Generation01Bit 0-3Bit 4-7Bit 8-11Bit 12-15S0-3S4-7S8-11S12-15Ci,0(1)(1)(5)(6)(7)(8)(9)(10)(5)(5)(5)(5)EE141 Digital Integrated Circuits2ndArithmetic Circuits32q考慮最后一級(jí)加法器的多路開關(guān)門，輸考慮最后一級(jí)加法器的多路開關(guān)門，輸入為這一模塊的兩個(gè)進(jìn)位鏈（入為這一模塊的兩個(gè)進(jìn)位鏈（5 5）以及來）以及來自前一級(jí)模塊的多路開關(guān)的信號(hào)（自前一級(jí)模塊的多路開關(guān)的信號(hào)（8 8），），它們到達(dá)時(shí)間有明顯差別。進(jìn)位鏈的結(jié)它們到達(dá)時(shí)間有明顯差

26、別。進(jìn)位鏈的結(jié)果在多路開關(guān)到達(dá)之前很久已經(jīng)穩(wěn)定。果在多路開關(guān)到達(dá)之前很久已經(jīng)穩(wěn)定。q為使這兩條路徑延時(shí)相等，可通過在該為使這兩條路徑延時(shí)相等，可通過在該加法器中逐漸增加后續(xù)各級(jí)的位數(shù)來實(shí)加法器中逐漸增加后續(xù)各級(jí)的位數(shù)來實(shí)現(xiàn)，因而后續(xù)各級(jí)需要更多的時(shí)間來產(chǎn)現(xiàn)，因而后續(xù)各級(jí)需要更多的時(shí)間來產(chǎn)生進(jìn)位信號(hào)生進(jìn)位信號(hào)EE141 Digital Integrated Circuits2ndArithmetic Circuits33Setup0 Carry 1 Carry MultiplexerSum Generation01Setup0 Carry 1 Carry MultiplexerSum Gener

27、ation01Setup0 Carry 1 Carry MultiplexerSum Generation01Setup0 Carry 1 Carry M ultiplexerSum Generation01B it 0-1Bit 2-4Bit 5-8Bit 9-13S0-1S2-4S5-8S9-13Ci,0(4)(5)(6)(7)(1)(1)(3)(4)(5)(6)MuxSumS14-19(7)(8)Bit 14-19(9)(3)EE141 Digital Integrated Circuits2ndArithmetic Circuits34q假設(shè)假設(shè)N N位加法器含有位加法器含有P P級(jí)，

28、第一級(jí)相加級(jí)，第一級(jí)相加M M位，后位，后續(xù)各級(jí)依次增加一位，則續(xù)各級(jí)依次增加一位，則： 2N=M+(M+1)+(M+2)+.+(M+P-1)P(P-1)P1 =MP+()222P M=2PN22PN若若M MN N，則，則：addsetupcarrymuxsumttt( 2)ttMN=EE141 Digital Integrated Circuits2ndArithmetic Circuits35Square r o o t se lectLinear s e l e ctRipple a d d e r2040Ntp(in unit d e l ay s)60010020304050EE1

29、41 Digital Integrated Circuits2ndArithmetic Circuits36在在N N位加法器中每一位的位置上都存在下列關(guān)系：位加法器中每一位的位置上都存在下列關(guān)系：Co kf AkBkCo k1GkPkCo k1+=通過對(duì)通過對(duì) C Co,k-1o,k-1展開可消除展開可消除C Co,ko,k對(duì)對(duì)C Co,k-1o,k-1的依賴的依賴Co kGkPkGk1Pk1Co k2+=C Co,ko,k的完全展開式：的完全展開式：Co kGkPkGk1Pk1P1G0P0Ci 0+=其中其中C Ci,0i,0通常為通常為0 0EE141 Digital Integrate

30、d Circuits2ndArithmetic Circuits37G = ABD = ABP = A+BCo = G + PCiS = P Ci = ABCi + (A+B+Ci)CoEE141 Digital Integrated Circuits2ndArithmetic Circuits38AN-1, BN-1A1, B1P1S1 SN-1PN-1Ci, N-1S0P0Ci,0Ci,1A0, B0EE141 Digital Integrated Circuits2ndArithmetic Circuits39 利用超前進(jìn)位公式的利用超前進(jìn)位公式的自對(duì)偶性和遞歸性建立自對(duì)偶性和遞歸性建立

31、了一個(gè)鏡像結(jié)構(gòu)，對(duì)于了一個(gè)鏡像結(jié)構(gòu)，對(duì)于N N位的超前進(jìn)位組，它的位的超前進(jìn)位組，它的晶體管實(shí)現(xiàn)具有晶體管實(shí)現(xiàn)具有N N個(gè)并行個(gè)并行分支并且有分支并且有N+1N+1個(gè)晶體管個(gè)晶體管堆疊。在堆疊。在N N值較大時(shí)極慢值較大時(shí)極慢，只在，只在N N值較小時(shí)有效值較小時(shí)有效Co,3Ci,0VDDP0P1P2P3G0G1G2G3EE141 Digital Integrated Circuits2ndArithmetic Circuits40G3C0C0C0C0P0P0P0P0G0G0G0G0C1 3P1P1P1P1P1P1G1G1G1C2 3P2P2P2P2P2P2G2G2C3 3P3P3P3P3C4

32、 3Pi 1 gate delayCiSi 2 gate delaysBiAiGi 1 gate delayq帶傳播和產(chǎn)生信號(hào)的加法器單元帶傳播和產(chǎn)生信號(hào)的加法器單元在超過在超過4 4位時(shí)，電路所位時(shí)，電路所需的邏輯門扇入非常大需的邏輯門扇入非常大計(jì)算多位相加時(shí)，進(jìn)位輸出僅需計(jì)算多位相加時(shí)，進(jìn)位輸出僅需3 3個(gè)門延時(shí)，和僅需個(gè)門延時(shí)，和僅需4 4個(gè)門延時(shí)個(gè)門延時(shí)EE141 Digital Integrated Circuits2ndArithmetic Circuits41A0B00S0 2A1B1C1 2S1 3A2B2C2 4S2 5A3B3C3 6S3 7Cout 8A0B00S0 2A

33、1B1C1 3S1 4A2B2C2 3S2 4A3B3C3 3S3 4C4 3C4 3q超前進(jìn)位邏輯產(chǎn)生獨(dú)立的并行超前進(jìn)位邏輯產(chǎn)生獨(dú)立的并行計(jì)算輸出的和，比較快計(jì)算輸出的和，比較快 然而，進(jìn)位邏輯成本增加然而，進(jìn)位邏輯成本增加好多倍進(jìn)位好多倍進(jìn)位Pi 1 gate delayCiSi 2 gate delaysBiAiGi 1 gate delayC0P0G0C1EE141 Digital Integrated Circuits2ndArithmetic Circuits42Co 0G0P0Ci 0+=Co 1G1P1G0P1P0Ci 0+=Co 2G2P2G1P2P1G0P+2P1P0Ci

34、0+=G2P2G1+=P2P1 G0P0Ci 0+G2:1P2:1Co 0+= 在上式中，進(jìn)位傳播過程被分解成兩位的子組合，在上式中，進(jìn)位傳播過程被分解成兩位的子組合，G Gi:ji:j和和P Pi:ji:j分別表示從第分別表示從第i i位至第位至第j j位的進(jìn)位產(chǎn)生和進(jìn)位傳播信號(hào)位的進(jìn)位產(chǎn)生和進(jìn)位傳播信號(hào), ,稱為塊稱為塊進(jìn)位產(chǎn)生和塊進(jìn)位傳播信號(hào)進(jìn)位產(chǎn)生和塊進(jìn)位傳播信號(hào) 為了建立非?？斓募臃ㄆ?，把進(jìn)位傳播和進(jìn)位產(chǎn)生組為了建立非?？斓募臃ㄆ?，把進(jìn)位傳播和進(jìn)位產(chǎn)生組織成遞歸的樹形結(jié)構(gòu)?？棾蛇f歸的樹形結(jié)構(gòu)。EE141 Digital Integrated Circuits2ndArithmetic

35、 Circuits43q針對(duì)這些成對(duì)的函數(shù)并且允許對(duì)一個(gè)塊的位進(jìn)針對(duì)這些成對(duì)的函數(shù)并且允許對(duì)一個(gè)塊的位進(jìn)行組合和運(yùn)算行組合和運(yùn)算( , ) ( ,)(,)G PGPGPGPP=3:23:2332233232(,)( ,) ( ,)(,)GPGPGPGPGP P=3:03:0332211003:23:21:01:0(,) ( ,) ( ,) ( ,) ( ,) (,) (,)GPGPGPGPGPGPGP=) 0 ,() 0 ,(),() 0 ,(0 ,0 : 30 : 30 :0 : 30 : 33 ,iioCPGCPGC=EE141 Digital Integrated Circuits2nd

36、Arithmetic Circuits44傳播產(chǎn)生傳播產(chǎn)生(P)(P)進(jìn)位產(chǎn)生進(jìn)位產(chǎn)生(G)(G) 該模塊產(chǎn)生進(jìn)位傳播和進(jìn)位產(chǎn)生信號(hào)。反相器在驅(qū)動(dòng)較該模塊產(chǎn)生進(jìn)位傳播和進(jìn)位產(chǎn)生信號(hào)。反相器在驅(qū)動(dòng)較大扇出的門中很有用。大扇出的門中很有用。EE141 Digital Integrated Circuits2ndArithmetic Circuits45點(diǎn)操作，代表計(jì)算塊級(jí)的進(jìn)位傳播和進(jìn)位產(chǎn)生信號(hào)的兩個(gè)點(diǎn)操作，代表計(jì)算塊級(jí)的進(jìn)位傳播和進(jìn)位產(chǎn)生信號(hào)的兩個(gè)門門:1:1:21:21:21:21(,) (,)(,)i i ki i ki k iki k iki iki ikGPGPGP =EE141 Dig

37、ital Integrated Circuits2ndArithmetic Circuits46在位置在位置2 2i i-1-1上的進(jìn)位只需要上的進(jìn)位只需要i i步就可以計(jì)算出來步就可以計(jì)算出來互連結(jié)構(gòu)規(guī)則，實(shí)現(xiàn)容易互連結(jié)構(gòu)規(guī)則，實(shí)現(xiàn)容易關(guān)鍵路徑上扇出基本上是一個(gè)常數(shù)關(guān)鍵路徑上扇出基本上是一個(gè)常數(shù)4949個(gè)點(diǎn)操作，面積和功耗較大個(gè)點(diǎn)操作，面積和功耗較大(A0, B0)(A1, B1)(A2, B2)(A3, B3)(A4, B4)(A5, B5)(A6, B6)(A7, B7)(A8, B8)(A9, B9)(A10, B10)(A11, B11)(A12, B12)(A13, B13)(A1

38、4, B14)(A15, B15)S0S1S2S3S4S5S6S7S8S9S10S11S12S13S14S15建立建立P P和和G G信號(hào)信號(hào)進(jìn)行點(diǎn)操作進(jìn)行點(diǎn)操作產(chǎn)生和產(chǎn)生和EE141 Digital Integrated Circuits2ndArithmetic Circuits47(A0, B0)(A1, B1)(A2, B2)(A3, B3)(A4, B4)(A5, B5)(A6, B6)(A7, B7)(A8, B8)(A9, B9)(A10, B10)(A11, B11)(A12, B12)(A13, B13)(A14, B14)(A15, B15)S0S1S2S3S4S5S6S7

39、S8S9S10S11S12S13S14S15 正向樹只實(shí)現(xiàn)在正向樹只實(shí)現(xiàn)在2 2N N-1-1位置上的進(jìn)位信號(hào)，為產(chǎn)生全部進(jìn)位，位置上的進(jìn)位信號(hào)，為產(chǎn)生全部進(jìn)位，需要一個(gè)反向二進(jìn)制樹。需要一個(gè)反向二進(jìn)制樹。2727個(gè)點(diǎn)操作并且所需的導(dǎo)線少，但布個(gè)點(diǎn)操作并且所需的導(dǎo)線少，但布線結(jié)構(gòu)不規(guī)則，并且各個(gè)門的扇出不相同，優(yōu)化性能困難。線結(jié)構(gòu)不規(guī)則，并且各個(gè)門的扇出不相同，優(yōu)化性能困難。C14C14最長，需要最長，需要6 6個(gè)點(diǎn)操作電路的延時(shí)。個(gè)點(diǎn)操作電路的延時(shí)。EE141 Digital Integrated Circuits2ndArithmetic Circuits48(A0, B0)(A1, B1

40、)(A2, B2)(A3, B3)(A4, B4)(A5, B5)(A6, B6)(A7, B7)(A8, B8)(A9, B9)(A10, B10)(A11, B11)(A12, B12)(A13, B13)(A14, B14)(A15, B15)S0S1S2S3S4S5S6S7S8S9S10S11S12S13S14S15EE141 Digital Integrated Circuits2ndArithmetic Circuits49Lookahead Carry UnitC0P3:0 G3:0P7:4 G7:4P11:8G11:8P15:12G15:12C11C7C3C0P15-0G15-

41、0C15324325325325530C15A15-12 B15-12C12S15-12A11-8B11-8C8S11-8A7-4B7-4C4S7-4788A3-0B3-0C0S3-004444PG4-bit Adder444PG4-bit Adder444PG4-bit Adder444PG4-bit Adderq超前進(jìn)位加法器超前進(jìn)位加法器 4 4個(gè)個(gè)4 4位加法器內(nèi)部包含自身的位加法器內(nèi)部包含自身的4 4位超前進(jìn)位邏輯位超前進(jìn)位邏輯 第二級(jí)超前進(jìn)位單元延到第二級(jí)超前進(jìn)位單元延到1616位位（8 8個(gè)門延時(shí)完成計(jì)算個(gè)門延時(shí)完成計(jì)算）G3:0 = G3 + P3 G2 + P3 P2 G1

42、+ P3 P2 P1 G0P3:0 = P3 P2 P1 P0C3 = G3:0 + P3:0 C0C7 = G7:4 + P7:4 C3C0P0G0C1 2C15 = G15:12 + P15:12(G11:7 + P11:7 ( G7:4 + P7:4( G3:0 + P3:0 C0)EE141 Digital Integrated Circuits2ndArithmetic Circuits50(a0, b0)(a1, b1)(a2, b2)(a3, b3)(a4, b4)(a5, b5)(a6, b6)(a7, b7)(a8, b8)(a9, b9)(a10, b10)(a11, b1

43、1)(a12, b12)(a13, b13)(a14, b14)(a15, b15)S0S1S2S3S4S5S6S7S8S9S10S11S12S13S14S15 減少樹的結(jié)構(gòu)深度的一種選擇是在每一結(jié)構(gòu)層次上組減少樹的結(jié)構(gòu)深度的一種選擇是在每一結(jié)構(gòu)層次上組合四個(gè)信號(hào)。一個(gè)合四個(gè)信號(hào)。一個(gè)1616位的加法器只需要兩級(jí)進(jìn)位邏輯位的加法器只需要兩級(jí)進(jìn)位邏輯EE141 Digital Integrated Circuits2ndArithmetic Circuits51 第一級(jí)點(diǎn)操作的輸入是在每相鄰第一級(jí)點(diǎn)操作的輸入是在每相鄰4 4位位P Pi i和和G Gi i，如，如計(jì)算計(jì)算G3:0G3:0和和P3

44、:0P3:0的點(diǎn)操作如下式，即將下面原理圖中的點(diǎn)操作如下式，即將下面原理圖中的的P Pi iP Pi-3i-3分別接到分別接到P P3 3P P0 0、 G Gi iG Gi-3i-3分別接到分別接到G G3 3G G0 0。(G(G3:03:0,P,P3:03:0)=(G)=(G3 3,P,P3 3)(G)(G2 2,P,P2 2)(G)(G1 1,P,P1 1)(G)(G0 0,P,P0 0) ) 第二級(jí)點(diǎn)操作的輸入是在第一級(jí)輸出的基礎(chǔ)上每第二級(jí)點(diǎn)操作的輸入是在第一級(jí)輸出的基礎(chǔ)上每隔隔4 4位進(jìn)行，如計(jì)算位進(jìn)行，如計(jì)算G G15:015:0和和P P15:015:0的點(diǎn)操作如下式，將的點(diǎn)操

45、作如下式，將下面原理圖中的下面原理圖中的P Pi iP Pi-3i-3分別接到分別接到P P15:1215:12P P3:03:0、G Gi iG Gi-i-3 3分別接到分別接到G15:12G15:12G G3:03:0。(G(G15:015:0,P,P15:015:0)=(G)=(G15:1215:12,P,P15:1215:12)(G)(G11:811:8,P,P11:811:8)(G)(G7:47:4, , P P7:47:4)(G)(G3:03:0,P,P3:03:0) ) EE141 Digital Integrated Circuits2ndArithmetic Circuits

46、523:03:001231232330 : 3GPPPGPPGPGG= 若用這種表達(dá)式設(shè)計(jì)若用這種表達(dá)式設(shè)計(jì)PDNPDN和和PUNPUN網(wǎng)絡(luò)則各需網(wǎng)絡(luò)則各需1010個(gè)個(gè)MOSMOS管，而且繪制的邏輯圖在管，而且繪制的邏輯圖在PDNPDN和和PUNPUN網(wǎng)絡(luò)中不存網(wǎng)絡(luò)中不存在一致的歐拉路徑在一致的歐拉路徑 EE141 Digital Integrated Circuits2ndArithmetic Circuits5332101230 : 3)(GGGGPPPG= 對(duì)這種結(jié)構(gòu)電路，可用基于啟發(fā)式的歐拉路徑算法來進(jìn)行版對(duì)這種結(jié)構(gòu)電路，可用基于啟發(fā)式的歐拉路徑算法來進(jìn)行版圖設(shè)計(jì)。啟發(fā)式歐拉路徑算法理

47、論基礎(chǔ)是：對(duì)于多級(jí)與或結(jié)構(gòu)圖設(shè)計(jì)。啟發(fā)式歐拉路徑算法理論基礎(chǔ)是：對(duì)于多級(jí)與或結(jié)構(gòu)的組合邏輯，如果每一個(gè)與的組合邏輯，如果每一個(gè)與/ /或門的輸入端數(shù)目為奇數(shù)，則在相或門的輸入端數(shù)目為奇數(shù)，則在相應(yīng)的邏輯圖中，下拉網(wǎng)絡(luò)應(yīng)的邏輯圖中，下拉網(wǎng)絡(luò)PDNPDN和上拉網(wǎng)絡(luò)和上拉網(wǎng)絡(luò)PUNPUN存在一致歐拉路徑存在一致歐拉路徑。 圖中實(shí)線部分，為圖中實(shí)線部分，為6 6級(jí)兩輸入與或結(jié)構(gòu)級(jí)兩輸入與或結(jié)構(gòu)EE141 Digital Integrated Circuits2ndArithmetic Circuits54 對(duì)于多級(jí)與或結(jié)構(gòu)的組合邏輯，如果每一個(gè)與對(duì)于多級(jí)與或結(jié)構(gòu)的組合邏輯，如果每一個(gè)與/ /或門的輸入

48、或門的輸入端數(shù)目為奇數(shù)，則在相應(yīng)的邏輯圖中，下拉網(wǎng)絡(luò)端數(shù)目為奇數(shù)，則在相應(yīng)的邏輯圖中，下拉網(wǎng)絡(luò)PDNPDN和上拉網(wǎng)絡(luò)和上拉網(wǎng)絡(luò)PUNPUN存在一致的歐拉路徑。為滿足啟發(fā)式歐拉路徑算法輸入端數(shù)存在一致的歐拉路徑。為滿足啟發(fā)式歐拉路徑算法輸入端數(shù)目為奇數(shù)要求，在每個(gè)與目為奇數(shù)要求，在每個(gè)與/ /或門加入一個(gè)用虛線表示的或門加入一個(gè)用虛線表示的“假想假想”輸入，這些輸入，這些“假想假想”輸入統(tǒng)一放在圖的上方。輸入統(tǒng)一放在圖的上方。 EE141 Digital Integrated Circuits2ndArithmetic Circuits55 選擇歐拉路徑為選擇歐拉路徑為G3P3G2P2G1P1G

49、0X0X1X2X3X4X5G3P3G2P2G1P1G0X0X1X2X3X4X5，而，而X0X1X2X3X4X5X0X1X2X3X4X5這些是假想輸入在版圖設(shè)計(jì)中是不存在這些是假想輸入在版圖設(shè)計(jì)中是不存在EE141 Digital Integrated Circuits2ndArithmetic Circuits56減少減少M(fèi)OSMOS管數(shù)目實(shí)現(xiàn)減少面積和提高性能。管數(shù)目實(shí)現(xiàn)減少面積和提高性能。 EE141 Digital Integrated Circuits2ndArithmetic Circuits57EE141 Digital Integrated Circuits2ndArithmet

50、ic Circuits58 先計(jì)算每位的進(jìn)位產(chǎn)生信號(hào)先計(jì)算每位的進(jìn)位產(chǎn)生信號(hào)P Pi i和進(jìn)位傳播信號(hào)和進(jìn)位傳播信號(hào)G Gi i，再，再通過前綴運(yùn)算單元計(jì)算塊進(jìn)位產(chǎn)生信號(hào)通過前綴運(yùn)算單元計(jì)算塊進(jìn)位產(chǎn)生信號(hào)P Pi:ji:j和塊進(jìn)位傳播和塊進(jìn)位傳播信號(hào)信號(hào)G Gi:ji:j，并將所有的前綴運(yùn)算單元按照一定的規(guī)律組織，并將所有的前綴運(yùn)算單元按照一定的規(guī)律組織成遞歸的進(jìn)位樹，這樣每一位的進(jìn)位信號(hào)就可通過進(jìn)位成遞歸的進(jìn)位樹，這樣每一位的進(jìn)位信號(hào)就可通過進(jìn)位樹的傳遞作用在運(yùn)算結(jié)點(diǎn)中一步一步地計(jì)算出來。樹的傳遞作用在運(yùn)算結(jié)點(diǎn)中一步一步地計(jì)算出來。 這種算法計(jì)算塊函數(shù)的最長時(shí)間是這種算法計(jì)算塊函數(shù)的最長時(shí)間

51、是 級(jí)門延遲級(jí)門延遲，其中，其中N N是加法器位數(shù)，如計(jì)算其最高位的塊函數(shù)是加法器位數(shù)，如計(jì)算其最高位的塊函數(shù)G G63:063:0和和P P63:063:0時(shí)間為時(shí)間為3 3級(jí)門的延遲。級(jí)門的延遲。 )(log4NO第三級(jí)點(diǎn)操作的輸入是在第二級(jí)輸出基礎(chǔ)上每隔第三級(jí)點(diǎn)操作的輸入是在第二級(jí)輸出基礎(chǔ)上每隔1616位進(jìn)行位進(jìn)行),(),(),(),(),(0 :150 :1516:3116:3132:4732:4748:6348:630 :630 :63PGPGPGPGPG=EE141 Digital Integrated Circuits2ndArithmetic Circuits59Y0Y1X3X2X1X0X3HAX2FAX1FAX0HAY2X3FAX2FAX1FAX0HAZ1Z3Z6Z7Z5Z4Y3X3FAX2FAX1FAX0HAZ2Z0 與手工乘法之間在拓?fù)浣Y(jié)與手工乘法之間在拓?fù)浣Y(jié)構(gòu)上一一對(duì)應(yīng)。產(chǎn)生構(gòu)上一一對(duì)應(yīng)。產(chǎn)生N N個(gè)部分個(gè)部分積需要積需要N N* *M M個(gè)兩位的與門。還個(gè)兩位的與門。還需要有需要有N-1N-1個(gè)個(gè)M M位的加法器位的加法器EE141 Digital Integrated Cir