【教學(xué)】第五章 同步時(shí)序電路設(shè)計(jì)

主講教師:溫志賢數(shù)字邏輯第五章同步時(shí)序電路設(shè)計(jì).4.5同步時(shí)序邏輯電路的設(shè)計(jì)本節(jié)討論的設(shè)計(jì)方法是一種經(jīng)典的方法，即由小規(guī)模集成電路構(gòu)成時(shí)序邏輯電路的設(shè)計(jì)方法，其基本指導(dǎo)思想是用盡可能少的觸發(fā)器和門(mén)電路來(lái)完成設(shè)計(jì)。.同步時(shí)序電路設(shè)計(jì)的一般步驟為：1.作原始狀態(tài)圖和狀態(tài)表；2.對(duì)原始狀態(tài)表化簡(jiǎn)；3.狀態(tài)分配；4.選定觸發(fā)器，求出輸出函數(shù)和激勵(lì)函數(shù)表達(dá)式；5.畫(huà)出邏輯電路圖。.4.5.1建立原始狀態(tài)圖狀態(tài)圖是同步時(shí)序電路設(shè)計(jì)的依據(jù)，它必須正確反映設(shè)計(jì)要求。狀態(tài)圖的作法沒(méi)有一成不變的方法，關(guān)鍵是要充分正確地理解設(shè)計(jì)要求。一個(gè)正確的狀態(tài)圖是指狀態(tài)圖中的狀態(tài)個(gè)數(shù)不能少，狀態(tài)之間的轉(zhuǎn)移關(guān)系不能錯(cuò)。作狀態(tài)圖的一個(gè)基本方法是“對(duì)于感興趣的東西應(yīng)區(qū)分對(duì)待，對(duì)于不感興趣的東西可不予區(qū)分”.例:某序列檢測(cè)器有一個(gè)輸入端x和一個(gè)輸出端Z。 從x端輸入一組按時(shí)間順序排列的串行二進(jìn)制 碼。 當(dāng)輸入序列中出現(xiàn)101時(shí)，輸出Z＝1， 否則 Z＝0。試作出該序列檢測(cè)器的Mealy型 和Moore型原始狀態(tài)圖和狀態(tài)表。.S0S1x/zS2S31/11/00/00/00/01/00/01/0.電路的Mealy型狀態(tài)表現(xiàn)態(tài)次態(tài)/輸出x=0x=1S0S1S2S3S0/0S2/0S0/0S2/0S1/0S1/0S3/1S1/0.S0/0S1/0S2/0S3/110100101.電路的Moore型狀態(tài)表現(xiàn)態(tài)次態(tài)x=0x=1S0S1S2S3S0S2S0S2S1S1S3S1輸出Z0001.例:假設(shè)某同步時(shí)序電路，用于檢測(cè)串行輸入 的8431BCD碼，其輸入的順序是先高位后 低位，當(dāng)出現(xiàn)非法數(shù)字(即輸入1010，1011， 1100，1101，1110，1111)時(shí)，電路的輸出 為1。試作出該時(shí)序電路的Mealy型原始狀 態(tài)圖和狀態(tài)表。.FDABCEG0/01/00/01/00/01/00/01/0解：.(e)HDAB1/00/0CEI0/00/01/01/0FG0/01/0NJKP0/00/01/01/0LM0/01/00/01/00/01/00/01/00/01/00/01/00/11/10/11/10/11/1電路的原始狀態(tài)圖.現(xiàn)態(tài)次態(tài)/輸出x=0x=1ABCDEFGHIJKLMNPB/0D/0J/0F/0H/0A/0A/0A/0A/0L/0N/0A/0A/1A/1A/1C/0E/0K/0G/0I/0A/0A/0A/0A/0M/0P/0A/0A/1A/1A/1電路的原始狀態(tài)圖.4.5.2狀態(tài)簡(jiǎn)化一般情況下，原始狀態(tài)圖和原始狀態(tài)表中存在著多余的狀態(tài)。狀態(tài)個(gè)數(shù)越多，電路中所需的觸發(fā)器的數(shù)目也越多，制造成本就越高。為降低制造成本，需要去掉多余的狀態(tài)，即要進(jìn)行狀態(tài)簡(jiǎn)化。所謂狀態(tài)簡(jiǎn)化，就是要獲得一個(gè)最小化的狀態(tài)表。這個(gè)表不僅能正確地反映設(shè)計(jì)的全部要求，而且狀態(tài)的數(shù)目最少。.完全確定狀態(tài)表：狀態(tài)表中的次態(tài)和輸出都有確定的 狀態(tài)和確定的輸出值。

等效狀態(tài)：設(shè)狀態(tài)S1和S2是完全確定狀態(tài)表中的兩個(gè)狀態(tài),如果對(duì)于所有可能的輸入序列，分別從狀態(tài)S1 和狀態(tài)S2出發(fā)，所得到的輸出響應(yīng)序列完全相同， 則狀態(tài)S1和S2是等效的，記作(S1,S2), 或者說(shuō)，狀態(tài)S1和S2是等效對(duì)。等效狀態(tài)可以合并。這里“ 所有可能的輸入序列” 是指長(zhǎng)度和結(jié)構(gòu)是任意的，它包含無(wú)窮多位，且有無(wú)窮多種組合。一、完全確定狀態(tài)表的簡(jiǎn)化.

等效狀態(tài)傳遞性：(S1,S2),(S2,S3)(S1,S3)

等效類(lèi)：彼此等效的狀態(tài)集合

最大等效類(lèi)：不被其它等效類(lèi)所包含的等效類(lèi)。 一個(gè)狀態(tài)也可能是一個(gè)最大等效類(lèi)。例：S1S'1S2S'2S3S'3S4S'40/00/00/10/11/11/1……S1,S2等效.

狀態(tài)簡(jiǎn)化的任務(wù)是要在原始狀態(tài)表中找出全部最大等效類(lèi)(最大等效類(lèi)集合)，并將每一個(gè)最大等效類(lèi)用一個(gè)狀態(tài)來(lái)表示。

直接根據(jù)定義來(lái)尋找等效狀態(tài)或等效類(lèi)是不現(xiàn)實(shí)的，實(shí)際上是從狀態(tài)表中來(lái)尋找的，因?yàn)樵紶顟B(tài)表已在總體上反映了各個(gè)狀態(tài)在任意輸入序列下的輸出。.判別方法：第一、它們的輸出完全相同；第二、它們的次態(tài)滿(mǎn)足下列條件之一，即

假定狀態(tài)S1和S2是完全確定原始狀態(tài)表中的兩個(gè)現(xiàn)態(tài)，那么S1和S2等效的條件可歸納為在輸入的各種取值組合下：

(1)次態(tài)相同；(2)次態(tài)交錯(cuò)；(3)次態(tài)循環(huán)；(4)次態(tài)對(duì)等效。.SiSj1/0Sl0/10/1Sk1/0次態(tài)相同.次態(tài)相同或交錯(cuò)SiSj0/01/01/0Sk0/0.次態(tài)交錯(cuò)或相同或循環(huán)SiSj1/01/0SkSl0/00/00/10/1Sm1/01/0.次態(tài)交錯(cuò)或等效(Sk,Sl等效)SiSj1/01/0SlSk0/10/1.1.觀(guān)察法化簡(jiǎn)例：簡(jiǎn)化下表所示的狀態(tài)表現(xiàn)態(tài)次態(tài)/輸出x=0x=1ABCDA/0A/0A/0A/0B/0C/0D/1D/1.解：A和B，C和D的輸出完全相等；C和D在輸入的各種取值組合下，次態(tài)相同，因此C和D等效；最大等效類(lèi)為{A}，{B}，{C,D},分別用A',B',C'表示；A和B在x=1時(shí)的次態(tài)不滿(mǎn)足四條件之一，因此A和B不等效;.最小化狀態(tài)表為現(xiàn)態(tài)次態(tài)/輸出x=0x=1A'B'C’A'/0A'/0A'/0B'/0C'/0C'/1.1.隱含表法化簡(jiǎn)例：簡(jiǎn)化下表所示的狀態(tài)表現(xiàn)態(tài)次態(tài)/輸出x=0x=1ABCDEFGC/0F/0D/0D/1C/0D/0C/1B/0A/1G/0E/0E/1G/0D/0.解：作隱含表順序比較，尋找等效狀態(tài)對(duì)

狀態(tài)對(duì)等效，打“”；狀態(tài)對(duì)不等效，打“”；狀態(tài)對(duì)是否等效需進(jìn) 一步檢查，則標(biāo)記次態(tài)對(duì)。ABCDEFGFEDCBCFBEAECFCDDE.ABCDEFGFEDCBCFBEAECFCDDE 處于循環(huán)鏈中的每一個(gè)狀態(tài)對(duì)都是等效狀態(tài)對(duì)。關(guān)聯(lián)比較，確定等效狀態(tài)對(duì)AEBECF.確定最大等效類(lèi)，作最小化狀態(tài)表

四個(gè)等效對(duì)(A,B),(A,E),(B,E),(C,F)

四個(gè)最大等效類(lèi)(A,B,E),(C,F),(D),(G)

令以上四個(gè)最大等效類(lèi)依次為a,b,c,d..現(xiàn)態(tài)次態(tài)/輸出x=0x=1abcdb/0c/0c/1b/1a/1d/0a/0c/0.二、不完全確定狀態(tài)表的簡(jiǎn)化不完全確定狀態(tài)表：狀態(tài)表中存在不確定的次態(tài)或輸出，這些不確定的次態(tài)或輸出將有利于狀態(tài)簡(jiǎn)化。.

相容狀態(tài)：設(shè)狀態(tài)S1和S2是不完全確定狀態(tài)表 中 的兩個(gè)狀態(tài)，如果對(duì)于所有的有效 輸入序 列，分別從狀態(tài)S1和S2出發(fā)，所得到的輸出響 應(yīng)序 列(除不確定 的那些位之外)是完全相同的， 那 么狀態(tài)S1和S2是相容的，或者說(shuō)狀 態(tài)S1和S2 是 相容對(duì)，記作(S1,S2)。相容狀態(tài)可以合并。.

這里所謂有效輸入序列的含義是：從狀態(tài)表中的狀態(tài)S出發(fā)，如果給定某輸入序列所得的狀態(tài)響應(yīng)序列除最后一個(gè)次態(tài)外，其它狀態(tài)都是確定的，那么這個(gè)輸入序列對(duì)狀態(tài)S是有效的。而所有的有效輸入序列，則意味著有效輸入序列的長(zhǎng)度和結(jié)構(gòu)是任意的。.

相容狀態(tài)無(wú)傳遞性：SiSj1/10/00/00/0Sk0/0Sl1/01/dSi和Sj相容；Sj和Sk相容；但Si和Sk不相容。.

相容類(lèi)：彼此相容的狀態(tài)集合

最大相容類(lèi)：不被其它相容類(lèi)所包含 的相容類(lèi).判別方法：

在不完全確定狀態(tài)表中判斷兩個(gè)狀態(tài)是否相容也是根據(jù)表中給出的次態(tài)和輸出來(lái)決定的。假定狀態(tài)Si和Sj是不完全確定狀態(tài)表中的兩個(gè)現(xiàn)態(tài)，那么狀態(tài)Si和Sj相容的條件可歸納為在輸入的各種取值組合下。.第一、它們的輸出完全相同，或者其中的 一個(gè)(或兩個(gè))輸出為任意值。第二、它們的次態(tài)滿(mǎn)足下列條件之一：

(1)次態(tài)相容；

(2)次態(tài)交錯(cuò)； (3)次態(tài)循環(huán)；

(4)其中的一個(gè)(或兩個(gè))為任意狀態(tài)

(5)次態(tài)對(duì)相容；.例：簡(jiǎn)化下表所示的狀態(tài)表現(xiàn)態(tài)次 態(tài)x=0x=1ABCDEFBBAdFdDDEEdC輸出0d111d.解：作隱含表；順序比較，尋找相容對(duì)；ABDEABCDEFEDCBDEBFAFCECECDCD.CEAFCFCEDFCE以上三步與確定狀態(tài)表的化簡(jiǎn)相同關(guān)聯(lián)比較，確定相容對(duì)；ABDEABCDEFEDCBDEBFAFCECECDCDAFCDBCABDEBDDEBEBFCD.全部相容狀態(tài)對(duì)：(A,B),(A,F),(B,C),(B,D),(B,E),(B,F),(C,D),(C,D),(C,F),(D,F),(D,E),(E,F)。.作狀態(tài)合并圖，求最大相容類(lèi)。S1S2S33狀態(tài)相容S4S1S2S34狀態(tài)相容.S1S2S3S4S55狀態(tài)相容ABCDFE本例狀態(tài)合并圖，最大相容類(lèi)是(A,B,F),(B,C,D,E,F)。.作最小化狀態(tài)表。最小化狀態(tài)表(又稱(chēng)最小閉覆蓋)應(yīng)滿(mǎn)足下列三個(gè)條件：

覆蓋性－－所選相容類(lèi)集合應(yīng)包含原始狀態(tài)表中 的全部狀態(tài)。最小性－－所選相容類(lèi)集合中相容類(lèi)的個(gè)數(shù)應(yīng)最 少。閉合性－－所選相容類(lèi)集合中的任一相容類(lèi)，在 原始狀態(tài)表中任一輸入條件下產(chǎn)生的次態(tài)應(yīng) 該屬于該集合中的某一個(gè)相容類(lèi)。. 我們常采用閉覆蓋表來(lái)反映所選相容類(lèi)集合的覆蓋和閉合情況。本例的閉覆蓋表為最大相容類(lèi)ABFBCDEFABCDEF覆 蓋閉 合x(chóng)=0x=1BABFCDECD.所選相容類(lèi)集合{(A,B,F),(B,C,D,E,F)}滿(mǎn)足最小閉覆蓋條件，令A(yù)表示(A,B,F)，C表示(B,C,D,E,F)可得：現(xiàn)態(tài)次 態(tài)x=0x=1ACA,CACC輸出01.由于該表中只有兩個(gè)狀態(tài)，進(jìn)一步可以得到：現(xiàn)態(tài)次 態(tài)x=0x=1ACdACC輸出01.例：化簡(jiǎn)下表所不的狀態(tài)表現(xiàn)態(tài)次態(tài)/輸出x=0x=1ABCDED/dE/0D/0C/dC/1A/dA/dB/dC/dB/d.解：作隱含表，尋找相容狀態(tài)對(duì)ABCDEDCBABDEACCECDACABCDABDEBCBC由上圖得相容狀態(tài)對(duì)為(A,B),(A,C),(A,D),(A,E), (B,C),(C,D),(D,E)ABDEBCACABBDACCEAEABCDADBCCDAC.作狀態(tài)合并圖，尋找最大相容類(lèi)ABCDE得最大相容類(lèi)為(A,B,C),(A,C,D),(A,D,E).作最小化狀態(tài)表若選相容類(lèi)集合為{(A,B,C),(A,C,D)}則下表表明它不滿(mǎn)足閉合要求相容類(lèi)ABCADEABCDE覆 蓋閉 合x(chóng)=0x=1DECDABCABABCDE.但如果選相容類(lèi)(A,B,C)和(D,E)則能滿(mǎn)足最小閉覆蓋的要求相容類(lèi)ABCDEABCDEABCDE覆 蓋閉 合x(chóng)=0x=1DECBCABABCDE.令A(yù)'=(A,B,C),B'=(D,E),進(jìn)一步可得：現(xiàn)態(tài)次態(tài)/輸出x=0x=1A'B'B'/0A'/1A'/dA'/d尋找最小閉覆蓋通常不是一件容易的事情，其結(jié)果往往不唯一。.4.5.3狀態(tài)編碼(狀態(tài)分配)給最小化狀態(tài)表中的每一個(gè)狀態(tài)指定一個(gè)二進(jìn)制代碼，形成二進(jìn)制狀態(tài)表。通常情況下，狀態(tài)編碼的方案不一樣，所得到的輸出函數(shù)和激勵(lì)函數(shù)的表達(dá)式也不同，由此而設(shè)計(jì)出來(lái)的電路復(fù)雜度也不同。狀態(tài)分配的任務(wù)是：決定編碼的長(zhǎng)度 尋找一種最佳的或接近最佳的狀態(tài)分配方案。.

設(shè)最小化狀態(tài)表中的狀態(tài)數(shù)為N，編碼長(zhǎng)度為n，N和n的關(guān)系為2n-1<N<2n用2n種組合來(lái)對(duì)N個(gè)狀態(tài)進(jìn)行分配時(shí)，可能出現(xiàn)的分配方案的總數(shù)Ks為－.例如，n=2,N=4時(shí)有方 案狀態(tài)1 2 3 4 5 6 7 8 9 10 11 12ABCD00

10 01

11

00 01 10 11 00 10 01 1101

11 00

10

10 11 00 01 11 01 10 0011

01 10

00

11 10 01 00 01 11 00 1010

00 11

01

01 00 11 10 10 00 11 01方 案狀態(tài)1 2 3 4 5 6 7 8 9 10 11 12ABCD00 10 01 11 00 01 10 11 00 10 01 1101 11 00 10 10 11 00 01 11 01 10 0011 01 10 00 11 10 01 00 01 11 00 1010 00 11 01 01 00 11 10 10 00 11 01.但是，在Ks種方案中只有三種是獨(dú)立的(真正不相同的)方案－－然而，當(dāng)n較大時(shí)，Ku仍然很大，要真正找到最佳的分配方案是十分困難的，況且分配方案的好壞還與所采用的觸發(fā)器的類(lèi)型有關(guān)。因此，實(shí)際應(yīng)用時(shí)都是采用工程的方法，依據(jù)以下四條件原則來(lái)進(jìn)行狀態(tài)分配。.狀態(tài)分配的基本原則有四條：(1)在相同輸入條件下具有相同次態(tài)的現(xiàn)態(tài)，應(yīng)盡可能分配相鄰的二進(jìn)制代碼；(2)在相鄰輸入條件，同一現(xiàn)態(tài)的次態(tài)應(yīng)盡可能分配相鄰的二進(jìn)制代碼；(3)輸出完全相同的現(xiàn)態(tài)應(yīng)盡可能分配相鄰的二進(jìn)制代碼；.

一般情況下，第一條原則較為重要，需優(yōu)先考慮，其次要考慮由前三條原則得到的應(yīng)分配相鄰代碼的狀態(tài)對(duì)出現(xiàn)的次數(shù)，次數(shù)多的狀態(tài)對(duì)應(yīng)優(yōu)先分配相鄰的二進(jìn)制代碼。(4)最小化狀態(tài)表中出現(xiàn)次數(shù)最多的狀態(tài)或初始狀態(tài)應(yīng)分配邏輯0。.例：對(duì)下表所示的狀態(tài)表進(jìn)行狀態(tài)分配現(xiàn)態(tài)次態(tài)/輸出x=0x=1ABCDC/0C/0B/0A/1D/0A/0D/0B/1.解：確定n=2確定分配 由規(guī)則(1)得A和B，A和C應(yīng)相鄰； 由規(guī)則(2)得C和D，C和A，B和D，A和B 應(yīng)相鄰； 由規(guī)則(3)得A，B，C三者應(yīng)相鄰，即A 和B，A和C，B和C應(yīng)相鄰； 由規(guī)則(4)得A分配為邏輯0.ACDB0101y1y2A:B:C:D:y1y20 00 11 01 1.最后我們可以得到二進(jìn)制狀態(tài)表現(xiàn) 態(tài)y1y2次態(tài)y2(n+1)y1(n+1)/輸出x=0x=10 00 11 11 010/010/000/101/011/000/001/111/0注意：有時(shí)滿(mǎn)足分配原則的分配方案不唯一，這時(shí)可任選一種。.4.5.4確定激勵(lì)函數(shù)和輸出函數(shù)1.觸發(fā)器的激勵(lì)表觸發(fā)器的激勵(lì)表反映觸發(fā)器從某種現(xiàn)態(tài)轉(zhuǎn)換到某種次態(tài)時(shí)，對(duì)觸發(fā)器輸入(激勵(lì))的要求。在這種表中，現(xiàn)態(tài)和次態(tài)作為自變量，輸入(激勵(lì))作為因變量。觸發(fā)器的激勵(lì)表可由觸發(fā)器的狀態(tài)表直接推出。.QQ(n+1)R Sd 00 11 00 d0 00 11 01 1QQ(n+1)D01010 00 11 01 1R-S觸發(fā)器激勵(lì)表D觸發(fā)器激勵(lì)表.QQ(n+1)J K0 d1 dd 1d 00 00 11 01 1QQ(n+1)T01100 00 11 01 1J-K觸發(fā)器激勵(lì)表T觸發(fā)器激勵(lì)表.2.確定激勵(lì)函數(shù)兩種方法：根據(jù)次態(tài)方程來(lái)確定和通過(guò)激勵(lì)表來(lái)確定。常采用后一種方法。.例：若用T觸發(fā)器實(shí)現(xiàn)下表所示的二進(jìn)制狀態(tài)表，試寫(xiě)出激勵(lì)和輸出函數(shù)。現(xiàn) 態(tài)y2y1次態(tài)y2(n+1)y1(n+1)/輸出Zx=0x=10 00 11 11 011/000/000/101/001/000/110/111/0.解：確定激勵(lì)函數(shù)現(xiàn)態(tài)y2y1次態(tài)y2(n+1)y1(n+1)0 00 11 11 00 00 11 11 0輸入x激勵(lì)函數(shù)T2T11 10 00 00 10 10 01 01 11 10 11 11 10 10 10 10 100001111QQ(n+1)T01100 00 11 01 1.1110000101y1xy211100000T2T1=1.Z=y2y1+xy10010000101y1xy211100011Z確定輸出函數(shù).4.5.5畫(huà)出邏輯電路圖先畫(huà)出觸發(fā)器并給觸發(fā)器編號(hào)，再根據(jù)激勵(lì)函數(shù)和輸出函數(shù)畫(huà)出組合邏輯部分的電路，最后畫(huà)出同步時(shí)鐘信號(hào)線(xiàn)。.例如：.1D1CD2Cy2CPx&y1z1y21&y1.4.6同步時(shí)序邏輯電路設(shè)計(jì)舉例例：設(shè)計(jì)一個(gè)“111…”序列檢測(cè)器，用來(lái)檢測(cè)串行二進(jìn)制序列，要求每當(dāng)連續(xù)輸入3個(gè)(或3個(gè)以上)1時(shí)，檢測(cè)器輸出為1，否則輸出為0。其典型輸入輸出序列如下：輸入x：0 1 1 1 0 1 1 1 1 0輸出Z：0 0 0 1 0 0 0 1 1 0 .解：作狀態(tài)圖