第5講 設(shè)計(jì)方法

1、2022-7-51第第5 5講講 設(shè)計(jì)方法設(shè)計(jì)方法設(shè)計(jì)步驟設(shè)計(jì)步驟系統(tǒng)設(shè)計(jì)系統(tǒng)設(shè)計(jì)算法設(shè)計(jì)算法設(shè)計(jì)幾種常用算法幾種常用算法算法結(jié)構(gòu)算法結(jié)構(gòu)并行設(shè)計(jì)技術(shù)并行設(shè)計(jì)技術(shù)系統(tǒng)同步系統(tǒng)同步2022-7-525.1 5.1 設(shè)計(jì)步驟設(shè)計(jì)步驟l 數(shù)字系統(tǒng)設(shè)計(jì)基本步驟 l 系統(tǒng)設(shè)計(jì)：對(duì)系統(tǒng)功能進(jìn)行模塊劃分，落實(shí)系統(tǒng)功能和技術(shù)指標(biāo)的分配，同時(shí)確定各功能模塊之間的接口關(guān)系。運(yùn)用框圖與層次的方法自頂向下進(jìn)行設(shè)計(jì)。l 算法設(shè)計(jì)：確定實(shí)現(xiàn)系統(tǒng)要求的算法。l 電路設(shè)計(jì)：確定電路形式，在電路級(jí)描述系統(tǒng)功能。l 芯片設(shè)計(jì)：按照確定的算法和電路形式，通過(guò)設(shè)計(jì)芯片內(nèi)部的邏輯功能來(lái)實(shí)現(xiàn)這些算法和電路。l PCB設(shè)計(jì)：實(shí)現(xiàn)系統(tǒng)整體功

2、能，同時(shí)進(jìn)行初步的工藝和機(jī)械結(jié)構(gòu)的設(shè)計(jì)。l 結(jié)構(gòu)設(shè)計(jì)：包括機(jī)箱和面板設(shè)計(jì)，屬工藝和工業(yè)造型的問(wèn)題。l 電路調(diào)試：檢查設(shè)計(jì)中存在的問(wèn)題。2022-7-535.1 5.1 設(shè)計(jì)步驟（續(xù)）設(shè)計(jì)步驟（續(xù)）l 數(shù)字系統(tǒng)設(shè)計(jì)基本準(zhǔn)則 l 分割準(zhǔn)則l 最底層的邏輯塊適合用基本邏輯電路來(lái)實(shí)現(xiàn)，或用邏輯語(yǔ)言進(jìn)行表達(dá)；l 相似功能的模塊應(yīng)該設(shè)計(jì)成共享的基本模塊；l 接口信號(hào)線最少結(jié)構(gòu)均稱，同層次的模塊之間在資源和I/O分配上，不應(yīng)出現(xiàn)懸殊的差異，沒(méi)有明顯的結(jié)構(gòu)和性能上的瓶頸；l 通用性好，易于移植。l 系統(tǒng)的可觀測(cè)性：在設(shè)計(jì)系統(tǒng)的同時(shí)設(shè)計(jì)觀測(cè)電路。l 系統(tǒng)的關(guān)鍵點(diǎn)信號(hào)，如時(shí)鐘、同步信號(hào)和狀態(tài)信號(hào)；l 具有代表性的

3、節(jié)點(diǎn)和線路上的信號(hào)；l 具備簡(jiǎn)單的“系統(tǒng)工作是否正?！钡呐袛嗄芰 同步和異步電路2022-7-545.1 5.1 設(shè)計(jì)步驟（續(xù)）設(shè)計(jì)步驟（續(xù)）l 盡可能采用同步電路進(jìn)行設(shè)計(jì)，避免使用異步電路；l 在必須使用異步電路的場(chǎng)合，應(yīng)采取措施來(lái)避免競(jìng)爭(zhēng)、增加穩(wěn)定性。l 最優(yōu)化設(shè)計(jì)l 器件資源利用率最高；l 系統(tǒng)工作速度最快，即延時(shí)最?。籰 布線最容易，即可實(shí)現(xiàn)性最好。l 理想的設(shè)計(jì)l 設(shè)計(jì)流暢、無(wú)拖泥帶水的感覺(jué)；l 資源分配、IO分配合理，沒(méi)有任何設(shè)計(jì)上和性能上的瓶頸；l 具有良好的可觀測(cè)性；l 易于修改和移植；l 電路器件的特點(diǎn)得到充分的發(fā)揮。2022-7-555.2 5.2 系統(tǒng)設(shè)計(jì)系統(tǒng)設(shè)計(jì)l 對(duì)

4、系統(tǒng)功能進(jìn)行模塊劃分，落實(shí)系統(tǒng)功能和技術(shù)指標(biāo)的分配，同時(shí)確定各功能模塊之間的接口關(guān)系。系統(tǒng)設(shè)計(jì)的好壞直接決定系統(tǒng)的整體性能。例5.1 乘法器設(shè)計(jì)l 迭代方式：成本低l 陣列方式：速度快l 流水方式：浮點(diǎn)運(yùn)算l 大數(shù)乘法器：算很大的數(shù)l 低功耗方式：功耗低迭代式乘法器2022-7-565.2 5.2 系統(tǒng)設(shè)計(jì)（續(xù)）系統(tǒng)設(shè)計(jì)（續(xù)）陣列式乘法器2022-7-575.2 5.2 系統(tǒng)設(shè)計(jì)（續(xù)）系統(tǒng)設(shè)計(jì)（續(xù)）流水式乘法器2022-7-585.2 5.2 系統(tǒng)設(shè)計(jì)（續(xù)）系統(tǒng)設(shè)計(jì)（續(xù)）大整數(shù)乘法器控制器數(shù)據(jù)通路2022-7-595.3 5.3 算法設(shè)計(jì)算法設(shè)計(jì)l FPGA的作用l 簡(jiǎn)化：簡(jiǎn)化硬件設(shè)計(jì)與制作l

5、 提速：提高算法執(zhí)行速度l 通用CPU與FPGA差別l 通用CPU通過(guò)“很細(xì)小”的機(jī)器指令串行地執(zhí)行程序，每次執(zhí)行都要“取指”、“分析”、“執(zhí)行”、“保存”；l FPGA只執(zhí)行與系統(tǒng)速度相關(guān)的、規(guī)模較大的“特殊”操作，這些操作往往可由多個(gè)電路模塊并行執(zhí)行。l “硬件”算法最終由硬件來(lái)實(shí)現(xiàn)，其設(shè)計(jì)要求與硬件結(jié)構(gòu)良好對(duì)應(yīng)；軟件算法則完全用程序來(lái)實(shí)現(xiàn)，形式多樣。2022-7-5105.3 5.3 算法設(shè)計(jì)（續(xù)）算法設(shè)計(jì)（續(xù)）l 采用器件的結(jié)構(gòu)、規(guī)模、性質(zhì)不同時(shí)，將用不同的算法設(shè)計(jì)l 若使用通用芯片，則考慮系統(tǒng)結(jié)構(gòu)盡量簡(jiǎn)單，少用芯片；l 若采用單片機(jī)或DSP，則因?yàn)槠骷喈?dāng)豐富，算法設(shè)計(jì)也不盡相同。l

6、 算法設(shè)計(jì)中主要考慮的因素l 功能：系統(tǒng)應(yīng)完成的功能；l 速度：系統(tǒng)要達(dá)到的運(yùn)行速度，在實(shí)時(shí)系統(tǒng)中顯得很重要；l 功耗：手持設(shè)備的重要指標(biāo)；l 成本：幾乎是人人關(guān)心的問(wèn)題。l 各因素往往相互制約，必須協(xié)調(diào)，尋找到最佳方案。2022-7-5115.4 5.4 幾種常用算法幾種常用算法l 跟蹤法：按照確定的系統(tǒng)功能，由控制要求逐步細(xì)化、具體化系統(tǒng)的工作過(guò)程，從而導(dǎo)出系統(tǒng)的算法。 例5.1：設(shè)計(jì)一個(gè)簡(jiǎn)單的7位串行數(shù)字門(mén)鎖系統(tǒng)。該鎖在輸入完0110111時(shí)，綠燈亮，可以用鑰匙開(kāi)門(mén)。 解：用Mealy機(jī)來(lái)實(shí)現(xiàn)還有其它辦法嗎？2022-7-512l 歸納法：從特殊到一般的方法。先將比較抽象、概略的系統(tǒng)功能

7、設(shè)計(jì)具體化，然后再經(jīng)過(guò)一般規(guī)律性的歸納，從而導(dǎo)出系統(tǒng)的算法。5.4 5.4 幾種常用算法（續(xù)）幾種常用算法（續(xù)）輸入：LEFT，RIGHT，HAZ，（時(shí)鐘）；輸出：LC，LB，LA，RA，RB，RC。 例5.2：雷鳥(niǎo)車(chē)尾燈2022-7-5135.4 5.4 幾種常用算法（續(xù)）幾種常用算法（續(xù)）共有8個(gè)狀態(tài)，其中IDLE為空閑狀態(tài)（沒(méi)有燈發(fā)光）。問(wèn)題：在IDLE狀態(tài)時(shí)，如果LEFT和HAZ同時(shí)有效會(huì)怎么樣？2022-7-5145.4 5.4 幾種常用算法（續(xù)）幾種常用算法（續(xù)）l 狀態(tài)圖必須沒(méi)有二義性，即離開(kāi)每一個(gè)狀態(tài)的弧線上所標(biāo)出的轉(zhuǎn)移表達(dá)式都是互斥的，并且是完備的。l 互斥性：在離開(kāi)每一狀態(tài)

8、的弧線上所標(biāo)的任意一對(duì)轉(zhuǎn)移表達(dá)式的邏輯積等于0。l 完備性：在離開(kāi)每一狀態(tài)的弧線上所標(biāo)的所有轉(zhuǎn)移表達(dá)式的邏輯和等于1。l 右圖無(wú)二義性l 有沒(méi)有更好的改進(jìn)？2022-7-5155.4 5.4 幾種常用算法（續(xù)）幾種常用算法（續(xù)） 初態(tài)：000； 左轉(zhuǎn)：Q2=0，Q1 Q0用葛萊碼； 右轉(zhuǎn)：Q2=1，Q1 Q0用葛萊碼； 全亮：100。一個(gè)更好的改進(jìn)一個(gè)更好的改進(jìn)2022-7-516l 劃分法：把一個(gè)復(fù)雜系統(tǒng)按一定規(guī)則劃分成為一系列簡(jiǎn)單的子系統(tǒng)，而這些子系統(tǒng)可由簡(jiǎn)單的算術(shù)運(yùn)算和邏輯運(yùn)算來(lái)完成，從而導(dǎo)出系統(tǒng)的算法。5.4 5.4 幾種常用算法（續(xù)）幾種常用算法（續(xù)） 例5.3：設(shè)計(jì)一個(gè)時(shí)鐘同步狀態(tài)

9、機(jī)（“猜謎游戲”機(jī)），它有4個(gè)按鈕輸入G1G4和4個(gè)燈輸出L1L4，按鈕和燈都有一個(gè)編號(hào)。另外，還有一個(gè)輸出信號(hào)ERR與一個(gè)紅燈相連。4個(gè)燈在時(shí)鐘控制下，輪流地被點(diǎn)亮，時(shí)鐘頻率為4Hz。按下一個(gè)按鈕，就有一個(gè)輸入Gi為有效。如果在時(shí)鐘觸發(fā)沿所測(cè)得Gi與時(shí)鐘觸發(fā)沿到來(lái)前就有效的燈輸出不相同的話，ERR信息有效，紅燈被點(diǎn)亮。一旦完成了一次猜測(cè)，游戲就停止并且ERR輸出會(huì)維持1個(gè)或多個(gè)時(shí)鐘周期（猜錯(cuò)時(shí)），直到輸入Gi被取消，游戲又恢復(fù)進(jìn)行。2022-7-5175.4 5.4 幾種常用算法（續(xù)）幾種常用算法（續(xù)）?2022-7-5185.4 5.4 幾種常用算法（續(xù)）幾種常用算法（續(xù)）2022-7-5

10、19 例5.4：要使得游戲更具有挑戰(zhàn)性，可以使時(shí)鐘頻率為原來(lái)的2倍或是3倍，并且讓燈保持原來(lái)狀態(tài)的時(shí)間為任意長(zhǎng)（隨機(jī)的）。這樣游戲者就真正要做出判斷：某一盞燈在某一狀態(tài)上保持的時(shí)間是否足以讓他按下按鈕。5.4 5.4 幾種常用算法（續(xù)）幾種常用算法（續(xù)） 2022-7-5202022-7-5215.4 5.4 幾種常用算法（續(xù)）幾種常用算法（續(xù)）l 解析法：當(dāng)遇到難以分解的計(jì)算過(guò)程時(shí)，采用數(shù)學(xué)分析對(duì)其進(jìn)行數(shù)值近似，轉(zhuǎn)換成多項(xiàng)式或某種迭代過(guò)程，然后畫(huà)出其算法流程圖，從而導(dǎo)出系統(tǒng)的算法。xx 例5.5：設(shè)計(jì)一個(gè)求 y= 的電路。 分析：一種常用的求x的平方根的方法是牛頓逐次逼近法。方法的核心是給出

11、一個(gè) 的估算值y0，用y1=(y0+x/y0)/2，求得y1，同理可求得y2，y3逐次遞進(jìn)，最后達(dá)到精度要求為止。 設(shè)x=3，令y0=1，其計(jì)算過(guò)程為： 序號(hào) y W=x/y V=y+W U=V/2 0 1 3 4 2 1 2 1.5 3.5 1.75 2 1.75 1.714 3.464 1.7321 3 1.7321 1.73200 3.4641 1.732052022-7-522 通過(guò)解析，將平方根的運(yùn)算轉(zhuǎn)化成W=x/y，=y+W，U=V/2三種基本運(yùn)算，由此可設(shè)計(jì)出如右所示的算法流程圖。5.4 5.4 幾種常用算法（續(xù)）幾種常用算法（續(xù)）開(kāi)始開(kāi)始w=x / yREAD x, y=y0u

12、=(y+w)/2u-y=允許的誤差允許的誤差結(jié)束結(jié)束Noy = u開(kāi)始開(kāi)始w=x / yREAD x, y=y0u=(y+w)/2u-y=允許的誤差允許的誤差結(jié)束結(jié)束Yesl 綜合法：在實(shí)際應(yīng)用中，大部分?jǐn)?shù)字系統(tǒng)的算法比較復(fù)雜，需要綜合、全面地考慮，逐步分解邏輯關(guān)系，最后獲得完整的算法流程圖。把跟蹤法、歸納法、劃分法、解析法等幾種設(shè)計(jì)算法組合起來(lái)應(yīng)用的方法稱為綜合法。2022-7-5235.5 5.5 算法結(jié)構(gòu)算法結(jié)構(gòu)l 數(shù)據(jù)依賴性：影響算法執(zhí)行速度的重要原因之一。OP1OP2OP3OP4OP50t1t2t3t4t5OP1OP2OP3OP4OP5OP6OP7OP80t1t2t3t4t5一組關(guān)聯(lián)

13、的子運(yùn)算l 順序算法結(jié)構(gòu)：在執(zhí)行算法的整個(gè)過(guò)程中，同一時(shí)間只進(jìn)行一種或一組相關(guān)的子運(yùn)算，前后運(yùn)算存在相關(guān)性。2022-7-5245.5 5.5 算法結(jié)構(gòu)（續(xù)）算法結(jié)構(gòu)（續(xù)）l 并行算法結(jié)構(gòu)：在同一時(shí)間段中，有多條路徑在同時(shí)進(jìn)行運(yùn)算，這些同時(shí)執(zhí)行的子運(yùn)算操作之間是相互獨(dú)立的。OP1OP2OP3OP4OP5OP6OP7OP8OP9OP10OP110t1t2t3t4l 從OP1到OP2、OP3、OP4不是順序算法中的條件轉(zhuǎn)移；l OP2、OP3、OP4之間互不關(guān)聯(lián)；l OP5和OP6、OP10和OP11為順序運(yùn)算路徑中的一組相關(guān)操作。2022-7-5255.5 5.5 算法結(jié)構(gòu)（續(xù)）算法結(jié)構(gòu)（續(xù)）l

14、 流水線操作結(jié)構(gòu)：針對(duì)連續(xù)輸入數(shù)據(jù)流的順序處理結(jié)構(gòu)，與基本的順序結(jié)構(gòu)相比具有如下特點(diǎn)：l 在流水線中操作運(yùn)算必須是連續(xù)任務(wù)，只有連續(xù)不斷地提供任務(wù)才能充分發(fā)揮流水線的效；l 把一個(gè)運(yùn)算（操作）分解為幾個(gè)有聯(lián)系的子運(yùn)算（子操作），每個(gè)子運(yùn)算由一個(gè)專門(mén)的功能部件來(lái)實(shí)現(xiàn)；l 在流水線的每一個(gè)功能部件后面都要有一個(gè)緩沖寄存器，用于保存本段的執(zhí)行結(jié)果；l 流水線中各段的時(shí)間應(yīng)盡量相等，否則將引起“堵塞”或“斷流”等現(xiàn)象；l 流水線需要有“裝入時(shí)間”和“排空時(shí)間”。只有流水線完全充滿時(shí)，整個(gè)流水線的效率才能得到充分發(fā)揮。l 在流水線中操作運(yùn)算必須是連續(xù)任務(wù)，只有連續(xù)不斷地提供任務(wù)才能充分發(fā)揮流水線的效率；

15、l 把一個(gè)運(yùn)算（操作）分解為幾個(gè)有聯(lián)系的子運(yùn)算（子操作），每個(gè)子運(yùn)算由一個(gè)專門(mén)的功能部件來(lái)實(shí)現(xiàn)；l 在流水線的每一個(gè)功能部件后面都要有一個(gè)緩沖寄存器，用于保存本段的執(zhí)行結(jié)果；l 流水線中各段的時(shí)間應(yīng)盡量相等，否則將引起“堵塞”或“斷流”等現(xiàn)象；l 流水線需要有“裝入時(shí)間”和“排空時(shí)間”。只有流水線完全充滿時(shí)，整個(gè)流水線的效率才能得到充分發(fā)揮。2022-7-5265.5 5.5 算法結(jié)構(gòu)（續(xù)）算法結(jié)構(gòu)（續(xù)）l 一個(gè)4級(jí)流水結(jié)構(gòu)2022-7-5275.5 5.5 算法結(jié)構(gòu)（續(xù)）算法結(jié)構(gòu)（續(xù)） 例5.6：試用順序操作和流水操作算法實(shí)現(xiàn) ，其中A、B、C均為數(shù)據(jù)流，數(shù)據(jù)流長(zhǎng)度為m。CBAl 采用順序算

16、法結(jié)構(gòu)：在t1，t2，t3分別完成這三種子運(yùn)算。為方便分析，設(shè)t1= t2= t3= t，完成整個(gè)運(yùn)算的時(shí)間為： Ts=3 m t2022-7-5285.5 5.5 算法結(jié)構(gòu)（續(xù)）算法結(jié)構(gòu)（續(xù)）l 采用流水線操作算法結(jié)構(gòu)：為提高運(yùn)算速度，又不增加運(yùn)算器的硬件成本，改用流水線操作算法結(jié)構(gòu)。 由圖可以看出，完成全部數(shù)據(jù)計(jì)算所需要的時(shí)間為： T=3t + (m-1) t顯然，流水線結(jié)構(gòu)比順序結(jié)構(gòu)所需要的運(yùn)算時(shí)間要少（(n-1)(m-1)）。2022-7-5295.6 5.6 并行設(shè)計(jì)技術(shù)并行設(shè)計(jì)技術(shù)l 非相關(guān)判別條件：設(shè)輸入集合為I1、I2，輸出集合為U1、U2：l I1U2=；l I2U1=；l

17、U1U2=Y=(A+B(C+DEF)+G 6Y=(A+G)+B(C+DEF) 5Y=(A+G+BC)+BD*EF 3l 并行設(shè)計(jì)技術(shù)l 劃分技術(shù)：將給定問(wèn)題分成p個(gè)獨(dú)立的幾乎等尺寸的子問(wèn)題由p個(gè)電路求解。如何分組，使得子問(wèn)題易于求解是關(guān)鍵。2022-7-5305.6 5.6 并行設(shè)計(jì)技術(shù)并行設(shè)計(jì)技術(shù)（續(xù)）（續(xù)）l 分治設(shè)計(jì)技術(shù)：將一個(gè)大而復(fù)雜的問(wèn)題分解成若干特征相同的子問(wèn)題分而治之，如大整數(shù)乘法。l 將輸入問(wèn)題分解成若干特征相同的子問(wèn)題l 并行地求解各個(gè)子問(wèn)題l 歸并各子問(wèn)題的解稱為源問(wèn)題的解l 緩沖操作技術(shù)l 乒乓操作l 串并轉(zhuǎn)換l 流水線設(shè)計(jì)技術(shù)2022-7-5315.7 5.7 系統(tǒng)同步系統(tǒng)同步l