很多學(xué)數(shù)字電路的朋友一開始接觸的都是分立的小規(guī)模邏輯門比如74LS系列里的與非門、或非門、反相器。那時(shí)候覺得挺簡單一個(gè)芯片里就那么幾個(gè)門連線也不復(fù)雜?？梢坏╅_始做課程設(shè)計(jì)、參加競賽或者接觸稍微復(fù)雜一點(diǎn)的工程板卡就會發(fā)現(xiàn)事情沒那么簡單了一個(gè)功能模塊動不動就要處理十幾路信號、幾十種狀態(tài)如果還抱著一個(gè)功能畫一片原理圖的老思路板子會越畫越亂時(shí)序收斂更是遙遙無期。這時(shí)候用排列組合的思路去重新審視邏輯器件的選型和連接方式就成了一個(gè)非常實(shí)用的突破口。我當(dāng)年第一次認(rèn)真琢磨這個(gè)主題是在做一個(gè)多路數(shù)據(jù)采集板的時(shí)候。板卡上要同時(shí)處理8路模擬開關(guān)的通道切換、3組編碼器的正交脈沖計(jì)數(shù)、還有一大堆狀態(tài)指示LED。如果每個(gè)功能都用獨(dú)立的邏輯芯片堆出來光是器件數(shù)量就夠讓人頭疼的。后來我換了個(gè)思路先把需求抽象成真值表再按排列組合的規(guī)律去合并、化簡、復(fù)用邏輯資源一下子就把設(shè)計(jì)簡化了大半。這篇文章就把我這些年在這條路上攢下的經(jīng)驗(yàn)做個(gè)系統(tǒng)梳理從基本原理到器件選型再到具體的組合設(shè)計(jì)案例和調(diào)試心得一次說清楚。1. 為什么排列組合是數(shù)字電路設(shè)計(jì)的隱藏主線很多人看數(shù)字電路教材開篇就是布爾代數(shù)、邏輯門電路然后就是組合邏輯、時(shí)序邏輯。但教材里很少直說一個(gè)底層道理數(shù)字電路里所有的組合邏輯本質(zhì)上都是在做排列組合的映射——輸入信號的全排列對應(yīng)輸出信號的全組合。你設(shè)計(jì)的每一張真值表其實(shí)就是在窮舉輸入端所有可能的取值組合然后為每一種組合指定輸出電平。1.1 排列組合與真值表的對應(yīng)關(guān)系先看一個(gè)最簡單的例子兩個(gè)輸入A和B每個(gè)輸入只有0和1兩種狀態(tài)那么它們的組合一共有224種。這就是排列組合里的乘法原理——每個(gè)輸入自由變化整體組合數(shù)是各輸入狀態(tài)數(shù)的乘積。放在數(shù)字電路里這個(gè)關(guān)系可以寫成一個(gè)很直白的公式n個(gè)輸入變量對應(yīng)的全部輸入組合數(shù)為2?種。這2?種組合恰好構(gòu)成一張完整真值表的行數(shù)。比如2個(gè)輸入4行真值表對應(yīng)4種排列組合3個(gè)輸入8行真值表對應(yīng)8種排列組合4個(gè)輸入16行真值表對應(yīng)16種排列組合也就是說排列組合是描述組合邏輯輸入空間的一種數(shù)學(xué)語言。你列的每一行真值表都是對輸入端某個(gè)具體排列組合狀態(tài)的響應(yīng)定義。不把這條主線理清楚后面設(shè)計(jì)多輸入邏輯函數(shù)時(shí)就容易掛一漏萬——漏一項(xiàng)功能就錯(cuò)了。1.2 從組合數(shù)理解邏輯器件的門數(shù)上限排列組合還決定了另一件重要的事一個(gè)邏輯函數(shù)的復(fù)雜程度由輸入組合數(shù)決定。輸入變量越多真值表越龐大對應(yīng)的邏輯表達(dá)式就越長需要的邏輯門就越多。這直接影響器件選型。一個(gè)3輸入的函數(shù)理論上最多需要8個(gè)最小項(xiàng)而一個(gè)6輸入的函數(shù)最小項(xiàng)數(shù)就膨脹到64個(gè)。你要是全用4輸入與非門去搭先不談門數(shù)光連線就可能把人繞暈。這也是為什么工程上超過4輸入的組合邏輯一般不建議用分立門電路去拼——排列組合的數(shù)量爆炸讓手工設(shè)計(jì)變得不現(xiàn)實(shí)需要換用譯碼器、數(shù)據(jù)選擇器、可編程邏輯器件等更高抽象層次的元件。從這個(gè)角度看排列組合不僅是一個(gè)題目里計(jì)算概率的公式更是數(shù)字電路設(shè)計(jì)中的工程邊界判斷工具。先數(shù)一數(shù)輸入變量的個(gè)數(shù)再算一算組合數(shù)你大概就能判斷這個(gè)邏輯該用什么級別的器件了。2. 用最小項(xiàng)展開式拆解任意邏輯需求不管需求多復(fù)雜組合邏輯設(shè)計(jì)的正規(guī)流程是先做邏輯抽象、列真值表、寫邏輯函數(shù)、化簡最后映射到具體器件。這個(gè)流程的每一步都在跟排列組合打交道。2.1 從文字需求到真值表舉個(gè)例子假設(shè)要設(shè)計(jì)一個(gè)三人表決器3個(gè)輸入A、B、C輸出Y當(dāng)2個(gè)或2個(gè)以上輸入為1時(shí)輸出1。這個(gè)需求聽起來很生活化但落到電路上第一步就是把所有輸入組合列全ABCY說明00000人同意00101人同意01001人同意01112人同意10001人同意10112人同意11012人同意11113人同意注意這張表的行數(shù)正好就是238種排列組合一種不多一種不少。很多新手容易犯的錯(cuò)誤是只列自己關(guān)心的幾種輸入狀態(tài)比如101輸出1110輸出1111輸出1剩下的組合不寫或者寫了但對不齊最后邏輯函數(shù)一化簡就出錯(cuò)了。我的習(xí)慣是列真值表時(shí)永遠(yuǎn)從000開始按二進(jìn)制遞增的順序一直列到全1像數(shù)數(shù)一樣把每一個(gè)排列組合都列出來。這個(gè)方法笨但最可靠能保證輸入空間一個(gè)不漏。2.2 最小項(xiàng)與標(biāo)準(zhǔn)與或式的寫法真值表列好之后接下來是把輸出為1的那些行對應(yīng)成最小項(xiàng)。三個(gè)變量的最小項(xiàng)有8個(gè)分別是m0 ABCABC000m1 ABCABC001m2 ABCABC010m3 ABCABC011m4 ABCABC100m5 ABCABC101m6 ABCABC110m7 ABCABC111所謂最小項(xiàng)就是包含了所有輸入變量的一個(gè)與項(xiàng)每個(gè)變量以原變量或反變量的形式出現(xiàn)且只出現(xiàn)一次。而最小項(xiàng)這個(gè)名字的來歷跟排列組合也有關(guān)n個(gè)變量能組成的所有這樣的與項(xiàng)正好是2?個(gè)每個(gè)與項(xiàng)對應(yīng)著輸入排列組合中的一種。上面表決器的例子Y為1的行是m3、m5、m6、m7所以標(biāo)準(zhǔn)與或式就是Y ABC ABC ABC ABC這個(gè)式子可以直接用與門和或門搭出來但顯然不夠簡潔。這時(shí)候就要用到卡諾圖化簡一種把幾何相鄰關(guān)系轉(zhuǎn)化成邏輯化簡的工具。排列組合在這里的妙處是卡諾圖的格子排列其實(shí)精心設(shè)計(jì)過相鄰格子的最小項(xiàng)只有一位變量不同。正因?yàn)橛羞@個(gè)排列上的特性你才能圈出那些可以合并、消掉變量的相鄰最小項(xiàng)。2.3 卡諾圖化簡的本質(zhì)是尋找組合冗余回到表決器例子把8個(gè)最小項(xiàng)排進(jìn)3變量卡諾圖你會看到m3、m5、m7可以圈成一個(gè)組m6、m7也可以和m3、m5交叉圈出一個(gè)更大組?；喗Y(jié)果是Y AB BC AC對比一下標(biāo)準(zhǔn)與或式和化簡后的式子門數(shù)從4個(gè)與門加1個(gè)或門變成3個(gè)與門加1個(gè)或門。看起來省得不多但如果把輸入變量擴(kuò)展到5個(gè)、6個(gè)化簡帶來的資源節(jié)省就是數(shù)量級的了。我見過不少同學(xué)做實(shí)驗(yàn)明明化簡一步就能做出來的東西非要按標(biāo)準(zhǔn)與或式硬搭結(jié)果芯片多了好幾片板上飛線密密麻麻還總出接觸不良的故障。化簡這步不光是省門更是省事、省調(diào)試時(shí)間。我在實(shí)際操作中的經(jīng)驗(yàn)是化簡以后盡量再看一眼化簡結(jié)果的物理意義。比如ABBCAC這個(gè)東西它語義上就是任意兩路為1就輸出1跟一開始的文字需求是對得上的。如果化簡結(jié)果跟直覺明顯不符那大概率是之前真值表或者化簡本身的某一步出了偏差。3. 器件選型的排列組合策略從小規(guī)模邏輯門到可編程器件需求抽象和化簡完成以后接下來就是讓邏輯落到實(shí)際的元器件上。這一節(jié)聊聊選型的問題面對同一個(gè)真值表你有多少種實(shí)現(xiàn)的手段它們各自適合什么樣的排列組合規(guī)模。3.1 分立邏輯門適合4變量以下的簡單組合小規(guī)模邏輯門芯片比如74LS08四重2輸入與門、74LS32四重2輸入或門、74LS04六反相器、74LS00四重2輸入與非門在變量少、邏輯簡單的時(shí)候依然是很好使的。拿表決器YABBCAC來說用3個(gè)2輸入與門和1個(gè)3輸入或門就能搭出來。如果是實(shí)驗(yàn)箱上驗(yàn)證這是最直觀的做法每個(gè)與門對應(yīng)一個(gè)乘積項(xiàng)輸入端接對應(yīng)的輸入變量輸出匯總到或門。但要注意74LS系列里常見的或門是2輸入的3輸入或門要另外找或者用2輸入或門級聯(lián)——比如74LS32里兩個(gè)2輸入或門串聯(lián)也能做3輸入或。這些都是小問題真正需要警惕的是輸入變量一多門數(shù)需求立刻爆炸。一個(gè)簡單的估算方法如果化簡后的與或式里總的乘積項(xiàng)數(shù)量超過10個(gè)或者單個(gè)與項(xiàng)涉及的變量數(shù)超過4個(gè)我就建議換一種實(shí)現(xiàn)方案了。因?yàn)榉至㈤T搭到這種復(fù)雜度布線混亂、功耗上升、傳輸延遲不一致帶來的毛刺問題都會冒出來。3.2 譯碼器/數(shù)據(jù)選擇器天生就是排列組合的最佳載體中規(guī)模集成電路里3-8譯碼器74LS138和8選1數(shù)據(jù)選擇器74LS151是我特別偏愛的一類器件因?yàn)樗鼈儽旧砭徒⒃谂帕薪M合的基礎(chǔ)上。3-8譯碼器的工作原理就是把3位輸入的全排列組合8種一一對應(yīng)到8個(gè)輸出端。每一個(gè)輸出端低電平有效正好對應(yīng)該輸入組合下的一個(gè)最小項(xiàng)。換句話說譯碼器可以直接輸出全部最小項(xiàng)你再把需要的幾個(gè)最小項(xiàng)用與非門合并起來就能得到任意3變量組合邏輯函數(shù)。8選1數(shù)據(jù)選擇器更有意思它通過3個(gè)選擇端從8個(gè)輸入通道里選一個(gè)連接到輸出。如果你把變量接到選擇端把常數(shù)0或1按真值表的輸出規(guī)律接到數(shù)據(jù)輸入端那么這個(gè)芯片本身就實(shí)現(xiàn)了一個(gè)任意3變量邏輯函數(shù)。不用額外的門電路一片74LS151加幾個(gè)上拉/下拉電阻就搞定了。數(shù)據(jù)輸入端接地表示邏輯0接VCC表示邏輯1。舉個(gè)例子還是表決器YABBCAC。把A、B、C接到74LS151的選擇端數(shù)據(jù)輸入端D0~D7分別接選擇端C,B,A對應(yīng)最小項(xiàng)Y值Dn接法000m00接地001m10接地010m20接地011m31接VCC100m40接地101m51接VCC110m61接VCC111m71接VCC這樣連完了以后74LS151的輸出端就直接等于表決器的輸出了。整個(gè)過程連一個(gè)邏輯門都不用加而且絕對不會出毛刺問題因?yàn)檫x用的是同一片芯片內(nèi)部的固有邏輯路徑。這種真值表直接映射到數(shù)據(jù)選擇器的方法我覺得是理解排列組合在器件層面應(yīng)用的最好例子。3.3 可編程邏輯器件組合數(shù)爆炸時(shí)的終極方案當(dāng)輸入變量繼續(xù)增加到5個(gè)、6個(gè)以上真值表的排列組合數(shù)到了32、64種無論是分立門還是數(shù)據(jù)選擇器都會變得難以招架。這時(shí)候該上可編程邏輯器件了從CPLD到FPGA它們內(nèi)部有大量可配置的邏輯單元理論上可以表示任意復(fù)雜的組合邏輯函數(shù)。FPGA里實(shí)現(xiàn)組合邏輯的底層結(jié)構(gòu)叫查找表LUT這個(gè)東西的原理本質(zhì)就是SRAM里存一張真值表。一個(gè)4輸入LUT里面有16個(gè)SRAM單元正好對應(yīng)4位輸入的全排列組合2?16。你在綜合工具里寫一句always組合邏輯或者assign語句工具就會自動把你的邏輯函數(shù)編譯成一張查找表的內(nèi)容。所以從某種意義上說FPGA設(shè)計(jì)組合邏輯直接就是在查排列組合表硬件門級結(jié)構(gòu)被軟件隱藏了。這就帶來一個(gè)很實(shí)用的小技巧你在寫Verilog或VHDL的時(shí)候與其費(fèi)勁化簡邏輯表達(dá)式不如直接用case語句把真值表原樣寫出來讓綜合工具幫你做優(yōu)化。比如always (*) begin case ({A, B, C}) 3b011: Y 1b1; 3b101: Y 1b1; 3b110: Y 1b1; 3b111: Y 1b1; default: Y 1b0; endcase end這種寫法在可讀性和可維護(hù)性上比手推化簡表達(dá)式要好得多。而且因?yàn)镕PGA底層LUT本身就是一張真值表case語句和LUT的映射關(guān)系非常直接很少會出現(xiàn)綜合結(jié)果不理想的情況。4. 組合邏輯器件級聯(lián)中的排列轉(zhuǎn)移多路選擇與優(yōu)先編碼實(shí)戰(zhàn)學(xué)會了單個(gè)器件實(shí)現(xiàn)組合邏輯下一個(gè)問題是一個(gè)功能模塊內(nèi)部器件與器件之間該怎么級聯(lián)這里同樣藏著排列組合的思想而且比單器件設(shè)計(jì)更容易踩坑。4.1 多片數(shù)據(jù)選擇器的擴(kuò)展從8選1到16選1設(shè)計(jì)中經(jīng)常遇到輸入信號通道數(shù)超過單芯片能力的情況。比如8個(gè)傳感器信號要選一路輸出用一片74LS151就夠了但項(xiàng)目里實(shí)際有16路信號這時(shí)候就得擴(kuò)展。16選1的思路不復(fù)雜用兩片8選1再加一個(gè)額外的選擇位。16路信號分成兩組各接一片74LS151的數(shù)據(jù)輸入。兩個(gè)芯片的選擇端A0、A1、A2并接在一起作為16選1的低3位地址第4位地址S接到其中一片的使能端低有效和另一片的使能端通過反相器接高有效。當(dāng)S0時(shí)第一片工作第二片禁止S1時(shí)反過來。最終兩片芯片的輸出再用一個(gè)2選1合并。這種結(jié)構(gòu)的本質(zhì)是把16種排列組合拆分成兩個(gè)8組的子排列。低3位地址在組內(nèi)選擇最高位地址在組間選擇。你可以在腦袋里把它理解成一個(gè)二維矩陣4位地址構(gòu)成了行和列組合尋址這樣去想就不會亂。不過這里面有一個(gè)工程細(xì)節(jié)很容易翻車2選1合并用與門和或門搭的話要么兩個(gè)與門的傳輸延遲不一致導(dǎo)致尖峰毛刺要么使能端翻轉(zhuǎn)的瞬間兩片芯片出現(xiàn)了短暫的同導(dǎo)通狀態(tài)。我在實(shí)驗(yàn)里遇到過兩片74LS151的使能端響應(yīng)時(shí)間不完全一致的情況導(dǎo)致輸出低電平瞬間被短暫拉高接到計(jì)數(shù)器上就產(chǎn)生了誤計(jì)數(shù)。更穩(wěn)的做法是用三態(tài)門或者直接選用帶擴(kuò)展功能的數(shù)據(jù)選擇器。74LS150是16選1的片子內(nèi)部已經(jīng)處理好了擴(kuò)展邏輯一片搞定省去級聯(lián)的麻煩。所以我的建議是能用單片高位數(shù)選擇器就別用多片低位數(shù)級聯(lián)芯片價(jià)格差距通常很小但可靠性差距不小。4.2 優(yōu)先編碼器的排列降維幾十種狀態(tài)只需幾位編碼再說說優(yōu)先編碼器它是另一類與排列組合強(qiáng)相關(guān)的器件。74LS148是8-3優(yōu)先編碼器輸入8根線I0~I7低有效輸出3位二進(jìn)制碼。它做的事情是把輸入端的哪一根線有效這一種排列狀態(tài)編碼成對應(yīng)的3位組合值。8種輸入狀態(tài)對應(yīng)8種輸出編碼本質(zhì)上就是一組一一對應(yīng)的排列映射。優(yōu)先編碼器特別適合處理中斷優(yōu)先級、按鍵掃描這類場景。你不需要知道全部按鍵的狀態(tài)只需要知道優(yōu)先級最高的那個(gè)是誰。電路里常見的一個(gè)問題是想擴(kuò)展輸入數(shù)量比如16路中斷源要用兩片74LS148級聯(lián)。級聯(lián)的方式有點(diǎn)巧妙兩片的輸出直接并接低優(yōu)先級片的EO輸出使能接到高優(yōu)先級片的EI輸入使能。這樣當(dāng)高優(yōu)先級片沒有輸入時(shí)它允許低優(yōu)先級片工作一旦高優(yōu)先級片有輸入就會禁止低優(yōu)先級片。優(yōu)先級的排列就這樣被硬件實(shí)現(xiàn)了。類似的還有二-十進(jìn)制優(yōu)先編碼器74LS147把10路輸入編碼成BCD碼。它實(shí)際上是在做10取1到4位碼的組合映射。雖然現(xiàn)在MCU很少用這種芯片了但在硬件面試、競賽方案中依然能看到優(yōu)先編碼器處理輸入壓縮的影子。4.3 奇偶校驗(yàn)器中的排列奇偶性奇偶校驗(yàn)是一個(gè)很有代表性的組合邏輯應(yīng)用它直接用到了排列組合里奇偶性的概念。9位奇偶校驗(yàn)器74LS280可以接受9路輸入輸出端分別給出1的個(gè)數(shù)為奇數(shù)和1的個(gè)數(shù)為偶數(shù)兩個(gè)信號。它的內(nèi)部實(shí)現(xiàn)其實(shí)是把9個(gè)輸入的所有排列分組凡是輸入中1的個(gè)數(shù)為奇數(shù)歸入一組輸出奇數(shù)標(biāo)志1的個(gè)數(shù)為偶數(shù)歸入另一組。這個(gè)分類完全是對輸入排列組合的一種劃分。用布爾代數(shù)的語言說它實(shí)現(xiàn)了9個(gè)變量的異或運(yùn)算——因?yàn)槭侵鸺壆惢蚨惢虮旧砭褪桥袛鄡蓚€(gè)數(shù)是否不同的基本門。在串行通信里發(fā)送端和接收端都需要做奇偶校驗(yàn)。發(fā)送端計(jì)算數(shù)據(jù)位的奇偶性把校驗(yàn)位附加到數(shù)據(jù)后面接收端對整個(gè)數(shù)據(jù)加校驗(yàn)位做奇偶校驗(yàn)如果結(jié)果與預(yù)定模式不符就知道傳輸過程中有一位發(fā)生了翻轉(zhuǎn)。這種在傳輸層保障數(shù)據(jù)完整性的做法底層邏輯就是排列組合的奇偶性判斷。寫代碼的話一個(gè)for循環(huán)異或所有位就能實(shí)現(xiàn)但在高速接口里硬件邏輯器件處理這種排布方式是有明顯速度優(yōu)勢的。5. 時(shí)域上的排列組合從競爭冒險(xiǎn)到對數(shù)字電路音樂電路的啟發(fā)到現(xiàn)在為止聊的都是靜態(tài)的、純組合的邏輯設(shè)計(jì)。但工程上有個(gè)繞不開的問題組合邏輯雖然有輸出卻不代表它一定穩(wěn)定無毛刺。當(dāng)輸入信號不是同時(shí)跳變的時(shí)候組合邏輯內(nèi)部各路徑的傳輸延遲不同就會導(dǎo)致短暫的錯(cuò)誤輸出。這個(gè)現(xiàn)象叫競爭冒險(xiǎn)它同樣可以用排列組合來理解。5.1 競爭冒險(xiǎn)不同路徑延遲的組合差異考慮最簡單的表達(dá)式Y(jié) A A。按照邏輯Y恒等于1沒有輸入能讓它變成0。實(shí)際電路里A由反相器產(chǎn)生信號到達(dá)或門輸入的時(shí)間會比原信號A晚一個(gè)反相器的傳輸延遲。在A從1跳變到0的那一瞬間或門兩個(gè)輸入端可能出現(xiàn)一小段同時(shí)為0的情況輸出Y就會產(chǎn)生一個(gè)短暫的負(fù)脈沖毛刺。這個(gè)現(xiàn)象的本質(zhì)是兩種可能的信號路徑A直達(dá)路徑和A經(jīng)過反相器的路徑在時(shí)間軸上形成了不同延遲的組合排列。如果A的跳變速度足夠慢或者兩條路徑延遲恰好相差較大毛刺就更明顯。消除毛刺的常用辦法是增加冗余項(xiàng)。比如表決器化簡成YABBCAC后實(shí)際上還會在A、B、C變化的某些瞬間出現(xiàn)毛刺加上AB這個(gè)冗余項(xiàng)通常來不及覆蓋所有跳變。真正的可靠做法要么是增加一個(gè)輸出濾波電容要么是在輸出端用D觸發(fā)器打一拍讓毛刺在時(shí)鐘邊沿到來之前消失。說到這我想起一個(gè)很常見的實(shí)際場景數(shù)字電路的實(shí)驗(yàn)箱上接了音樂電路。網(wǎng)上流傳的數(shù)字電路音樂電路設(shè)計(jì)原理其實(shí)是用計(jì)數(shù)器產(chǎn)生不同分頻去控制蜂鳴器的輸出頻率。不同音符對應(yīng)的是不同的計(jì)數(shù)循環(huán)長度這本質(zhì)上也是一種計(jì)數(shù)排列的變化。頻率越高計(jì)數(shù)值越小輸出翻轉(zhuǎn)越快音調(diào)越高。這些分頻和計(jì)數(shù)值的排列組合決定了樂曲能不能正確播放。如果你在實(shí)驗(yàn)里遇到了蜂鳴器聲音不對音符順序亂了這種問題最值得懷疑的地方不是蜂鳴器本身而是控制音符切換的邏輯。要是用組合邏輯直接驅(qū)動蜂鳴器切換音符的瞬間因?yàn)橛?jì)數(shù)器的各個(gè)輸出位不是同時(shí)翻轉(zhuǎn)的音符頻率會瞬間亂跳聽起來就是滋滋的雜音。處理方法也很簡單讓控制音符的寄存器只在時(shí)鐘邊沿更新相當(dāng)于把組合邏輯輸出的毛刺與外部世界隔離這就屬于從競爭冒險(xiǎn)角度去優(yōu)化一個(gè)已經(jīng)能工作的音樂電路。5.2 時(shí)序邏輯中的狀態(tài)計(jì)數(shù)排列組合的循環(huán)再往深一層時(shí)序邏輯里也有排列組合的影子。在一個(gè)模8計(jì)數(shù)器中Q2Q1Q0三個(gè)觸發(fā)器的狀態(tài)從000到111循環(huán)正好是3位二進(jìn)制數(shù)的一個(gè)完整排列。格雷碼計(jì)數(shù)器則是每次只改變一位本質(zhì)上是一種保證相鄰狀態(tài)距離為1的排列規(guī)則。這些狀態(tài)本身都是排列組合的具體實(shí)例。設(shè)計(jì)有限狀態(tài)機(jī)時(shí)狀態(tài)編碼方案的選擇同樣是一種排列組合。以四狀態(tài)為例狀態(tài)碼有000、001、010、011四種常用編碼以及格雷碼00、01、11、10這四種相鄰變化。不同編碼方案的優(yōu)劣在組合邏輯資源消耗和時(shí)序可靠性上有明顯差異。格雷碼在電機(jī)編碼器、異步FIFO指針等場景中是主流選擇因?yàn)樗鼙ＷC快到快讀的場景下不產(chǎn)生非法狀態(tài)跳變。另外異步FIFO的老生常談問題——讀寫指針跨時(shí)鐘域同步——實(shí)際也是一種特殊的排列組合問題。兩個(gè)時(shí)鐘域的讀寫指針各自在自己的域內(nèi)遞增只有在同步之后才能做比較。處理不好指針錯(cuò)位FIFO就會溢出或者下溢。這也是為什么很多工程師提到cdc mailbox這個(gè)概念跨時(shí)鐘域傳遞郵箱消息本質(zhì)上要求消息在目的時(shí)鐘域中穩(wěn)定可見而穩(wěn)定的前提是信號跳變時(shí)刻不能落在采樣的觸發(fā)沿上。排列組合在這里表現(xiàn)為什么時(shí)刻采樣什么信號是一種動態(tài)的時(shí)序組合。6. 可復(fù)用的設(shè)計(jì)套路從真值表到電路的提效方法聊了這么多原理接下來說幾個(gè)可以直接抄作業(yè)的方法。這些套路是我在實(shí)驗(yàn)室和項(xiàng)目中反復(fù)驗(yàn)證過的能實(shí)打?qū)崪p少設(shè)計(jì)時(shí)間。6.1 最小項(xiàng)查表法設(shè)計(jì)組合邏輯當(dāng)你拿到一個(gè)功能需求先別急著畫門電路。我的做法是嚴(yán)格按照下面四步走把需求抽象成輸入輸出信號明確變量個(gè)數(shù)列全真值表一行不漏在真值表里找到所有輸出為1的行寫最小項(xiàng)決定實(shí)現(xiàn)方式表達(dá)式化簡、數(shù)據(jù)選擇器直連、還是寫case語句這個(gè)方法對新手特別友好不容易出錯(cuò)。熟練了以后甚至可以跳過第3步的文字形式直接盯著真值表心中就有電路。6.2 用數(shù)據(jù)選擇器快速搭建任意3變量邏輯如果手頭正好有74LS151而且邏輯函數(shù)不超過3個(gè)輸入變量就直接用查表法一分鐘接完電路把變量A、B、C接到選擇端對照真值表把數(shù)據(jù)輸入端D0~D7接VCC或GND輸出端Y就是函數(shù)值這個(gè)方法比畫門電路快得多而且調(diào)試極其方便只要檢查數(shù)據(jù)端接對不對就行了。數(shù)據(jù)端接線一目了然出錯(cuò)了也能瞬間定位到具體那一行真值表。變量超過3個(gè)的時(shí)候也別急著放棄。4變量的函數(shù)可以用兩片74LS151加額外邏輯實(shí)現(xiàn)但性價(jià)比會下降。更實(shí)用的做法是用手頭現(xiàn)成的LUT型FPGA寫4行case語句。我經(jīng)常拿著小腳丫FPGA或者Artix-7的開發(fā)板做原型驗(yàn)證綜合后的資源報(bào)告里能看到每個(gè)LUT的利用率稍微優(yōu)化就能得到漂亮的布線結(jié)果。6.3 信號命名與模塊劃分中的組合管理最后一個(gè)套路聽起來比較軟但實(shí)際收益巨大。在模塊化設(shè)計(jì)時(shí)把相關(guān)聯(lián)的組合邏輯信號按位寬分組命名并對每組信號的排列順序做統(tǒng)一約定。比如多路選擇器的選擇端按A[2:0]命名數(shù)據(jù)端按D[7:0]命名所有真值表里位序和總線位序保持一致。這樣一來寫驗(yàn)證testbench的時(shí)候窮舉輸入組合只需寫一個(gè)循環(huán)和位移操作不易出錯(cuò)在仿真波形里觀察信號恢復(fù)起來也直觀。我在維護(hù)一個(gè)多人協(xié)作項(xiàng)目時(shí)深深體會過這個(gè)約定的價(jià)值。有人習(xí)慣把使能信號叫EN有人叫en有人叫ENABLE信號位序有的從高到低有的從低到高結(jié)果組合邏輯的排布五花八門最后聯(lián)調(diào)時(shí)花了好多時(shí)間對齊接口。后來統(tǒng)一規(guī)范所有使能叫en所有數(shù)據(jù)總線按bit0在最右所有狀態(tài)標(biāo)志按bit位與事件編號一致整個(gè)項(xiàng)目的排錯(cuò)效率瞬間提升了一截。7. 一次真實(shí)的調(diào)試經(jīng)歷數(shù)據(jù)選擇器級聯(lián)中的地址組合錯(cuò)亂前面講了很多理論最后分享一個(gè)實(shí)際的排查案例。這是我在設(shè)計(jì)一塊數(shù)據(jù)采集板時(shí)遇到的正好能串起排列組合與器件級聯(lián)的所有要點(diǎn)。7.1 現(xiàn)象通道選擇與預(yù)期不符的詭異錯(cuò)位板卡上一共有16路模擬信號我按前面的方案用了兩片74LS151通過一個(gè)反相器控制使能端組成了16選1。測試時(shí)發(fā)現(xiàn)選擇地址0x0和0x1時(shí)輸出的是正確的通道但選擇了0x2之后輸出就錯(cuò)亂了而且錯(cuò)亂規(guī)律看起來毫無章法——不是簡單的高位地址反了也不是個(gè)別通道接反。這個(gè)現(xiàn)象讓我第一反應(yīng)就是查接線。但查了幾遍數(shù)據(jù)端和選擇端都沒有發(fā)現(xiàn)焊錯(cuò)。最后用示波器逐個(gè)引腳測量才定位到問題根源。7.2 排查從排列組合矩陣找突破口我先列了一張表把實(shí)際輸出與預(yù)期通道一一對照然后把錯(cuò)誤模式寫下來。結(jié)果發(fā)現(xiàn)錯(cuò)誤的通道選擇和預(yù)期通道之間的差總是一個(gè)固定的偏移量而且只出現(xiàn)在高位地址為1的情況。這個(gè)規(guī)律讓我開始懷疑不是接線問題而是兩片芯片的使能邏輯有問題。翻看數(shù)據(jù)手冊74LS151的使能端是低電平有效但它的輸出并不是簡單的三態(tài)——當(dāng)使能無效時(shí)輸出并不是高阻態(tài)而是固定邏輯0。我之前的設(shè)計(jì)是讓兩片輸出直接短接再用與門/或門合并。當(dāng)使能無效的那片輸出固定0確實(shí)不會影響有效的另一片這個(gè)思路本身沒錯(cuò)。但問題出在我用來生成使能信號的反相器上。我用的反相器是74LS04輸入從高到低跳變時(shí)傳輸延遲大約十幾納秒但另一個(gè)芯片的使能路徑上經(jīng)過了兩個(gè)門的延遲。這樣在高位地址S翻轉(zhuǎn)的瞬間兩片芯片的使能端有一個(gè)短暫的重疊窗口導(dǎo)致兩片芯片同時(shí)處于有效狀態(tài)。此時(shí)兩片輸出直接短接在一起一個(gè)輸出0一個(gè)輸出1低的被高的拉高了一瞬或者高的被低的拉低了一瞬產(chǎn)生了毛刺。如果這個(gè)毛刺落在后續(xù)電路采樣的時(shí)鐘沿上就可能被記錄成完全不同的通道地址。7.3 修復(fù)給使能路徑做延遲對齊定位到問題后修復(fù)反而簡單了。兩個(gè)方案在輸出端加一個(gè)8選1的額外組合邏輯避免輸出端直接短接。但這個(gè)方案會增加一片芯片不值得。把反相器換成同相緩沖器74LS244并人為地在另一條路徑上也加一個(gè)同相緩沖器保證兩條使能路徑延遲嚴(yán)格一致。這樣無論地址怎么翻兩片芯片的使能狀態(tài)不會出現(xiàn)同時(shí)有效的情況。我采用了第二個(gè)方案改完以后用示波器反復(fù)觸發(fā)地址切換再也沒看到毛刺。后來我又把這套延遲對齊的思路用到其他項(xiàng)目里只要是多條并行信號路徑無論它們是地址線、數(shù)據(jù)線還是控制線都要盡量保證各條路徑的傳播延遲一致。這其實(shí)也是高速PCB設(shè)計(jì)中等長布線思想的邏輯門級版本。8. 動手做一個(gè)小項(xiàng)目用74LS151實(shí)現(xiàn)4變量多數(shù)表決器理論說了不少最后來一個(gè)可復(fù)現(xiàn)的小項(xiàng)目。4變量多數(shù)表決器輸入A、B、C、D輸出Y要求4個(gè)輸入中有3個(gè)或以上為1時(shí)輸出1。這個(gè)項(xiàng)目用分立門做很麻煩但用兩片74LS151可以做得又快又好。8.1 邏輯到芯片的映射4變量函數(shù)如果用一片8選1需要把4個(gè)變量都接進(jìn)去一片不夠。我的做法是用兩片74LS151把高兩位變量C、D作為片選控制低兩位變量A、B作為每片內(nèi)部的選擇地址。更具體地把兩片的選擇端A0、A1分別接A、B然后用C、D經(jīng)過簡單組合邏輯切換兩片的輸出。但這樣連線依然復(fù)雜。另一個(gè)更優(yōu)雅的做法是利用數(shù)據(jù)選擇器的高級用法——把一部分輸入變量接到數(shù)據(jù)輸入端而不是選擇端。這本質(zhì)上是對排列組合的一種降維處理。以4變量多數(shù)表決器為例先固定兩個(gè)變量比如C、D為分組變量它們形成4種組合CD00、01、10、11。在每一種CD組合下輸出Y僅由A、B決定于是可以寫出一張關(guān)于A、B的小真值表當(dāng)CD00時(shí)A、B無論怎樣都不可能有3個(gè)1所以Y恒為0當(dāng)CD01時(shí)要總共至少有3個(gè)1需要A和B都為1所以YAB當(dāng)CD10時(shí)同樣需要A和B都為1YAB當(dāng)CD11時(shí)已經(jīng)有兩個(gè)1了再加A或B任意一個(gè)1即可YAB這個(gè)分解很有意思原本16種輸入組合的4變量函數(shù)被拆成了4組2變量的子函數(shù)。這4個(gè)子函數(shù)可以用74LS151的數(shù)據(jù)輸入端來實(shí)現(xiàn)——每個(gè)數(shù)據(jù)輸入端接一個(gè)關(guān)于A、B的組合邏輯。8.2 具體接線步驟手頭有一片74LS151時(shí)接線如下把A、B接到74LS151的選擇端A0、A1把D0接0對應(yīng)CD00的情況D1、D2通過一個(gè)2輸入與門74LS08產(chǎn)生A和B相與對應(yīng)CD01、10D3通過一個(gè)2輸入或門74LS32產(chǎn)生A和B相或?qū)?yīng)CD11C、D通過一個(gè)2線-4線譯碼器或者用74LS139雙2-4譯碼器產(chǎn)生四路分組選通信號分別接到74LS151的四個(gè)選通使能端這個(gè)方案用了一片74LS151、一片74LS08、一片74LS32、一片74LS139一共4片小芯片比起直接用門電路搭4變量真值表需要十幾個(gè)門已經(jīng)省了不少。而且調(diào)試起來非常直觀通道0異常就查D0的接線通道3異常就查D3的或門輸出。8.3 驗(yàn)證與測試建議上電以后建議按下面的表一項(xiàng)一項(xiàng)測試ABCDY000000111110111110111110111111特別提醒測試時(shí)不要跳過恰好3個(gè)輸入為1和全1這兩種情況。多數(shù)表決器最容易出錯(cuò)的邊界就是這里。9. 最后的經(jīng)驗(yàn)補(bǔ)充組合邏輯排布中的幾個(gè)常見坑文章最后把這幾年來在組合邏輯排布上踩過、見過的一些坑集中說一下字不多但每條都是真金白銀。9.1 使能端的懸空數(shù)據(jù)選擇器、譯碼器這類的使能端無論你用不用都一定要接到確定的電平上。懸空相當(dāng)于輸入浮空噪聲一拉就可能讓芯片誤動作。特別是CMOS器件懸空輸入還會導(dǎo)致靜態(tài)功耗上升更嚴(yán)重的可能會損傷芯片內(nèi)部結(jié)構(gòu)。這個(gè)經(jīng)驗(yàn)我在一次多路采集板調(diào)試中體會很深使能端懸空導(dǎo)致的偶發(fā)錯(cuò)通道故障花費(fèi)了我一整個(gè)下午去定位。9.2 輸出端不要長期短接前面提到過讓兩個(gè)芯片的輸出端直接短接在使能路徑時(shí)間差存在的情況下是危險(xiǎn)的。標(biāo)準(zhǔn)的做法是用三態(tài)門配合輸出使能信號或者用多路選擇器在外部合并。如果實(shí)在要直接短接一定要確認(rèn)兩片器件在任何時(shí)刻最多只有一片處于輸出有效狀態(tài)。9.3 注意數(shù)據(jù)手冊里的輸出特性很多器件的輸出在高阻態(tài)時(shí)其實(shí)不是真正的高阻而是一個(gè)很大的電阻輸出端還會帶上一點(diǎn)殘余電壓。在高速開關(guān)場景下這個(gè)殘余電壓疊加到其他信號上可能造成邏輯誤判。所以我一般只在低頻或純數(shù)字邏輯場景里直接并接芯片輸出高速場景一定會加緩沖或三態(tài)隔離。9.4 不要輕視真值表的完整性最后還是回到這個(gè)主題的根本一張完整的真值表是你和電路之間的契約。任何一行遺漏都會導(dǎo)致邏輯函數(shù)與真實(shí)需求不符。列真值表不是走過場它本身就是設(shè)計(jì)的一半。我見過太多項(xiàng)目出問題最后追根溯源就是當(dāng)初某個(gè)輸入組合的輸出值沒定義清楚。把排列組合這個(gè)概念吃透了你會發(fā)現(xiàn)數(shù)字電路的世界并沒有那么復(fù)雜。從最小的與非門到上百萬門的FPGA底層遵循的規(guī)律其實(shí)是一樣的窮舉輸入空間映射輸出行為再用合適的器件把這張映射表物化出來。希望這篇整理能對你理解數(shù)字電路、駕馭邏輯器件有所幫助。有疑問歡迎在評論區(qū)交流我會盡量回復(fù)那些我實(shí)際碰到過、有具體場景的問題。