【教學】第五章 同步時序電路設計

主講教師:溫志賢數(shù)字邏輯第五章同步時序電路設計.4.5同步時序邏輯電路的設計本節(jié)討論的設計方法是一種經(jīng)典的方法，即由小規(guī)模集成電路構成時序邏輯電路的設計方法，其基本指導思想是用盡可能少的觸發(fā)器和門電路來完成設計。.同步時序電路設計的一般步驟為：1.作原始狀態(tài)圖和狀態(tài)表；2.對原始狀態(tài)表化簡；3.狀態(tài)分配；4.選定觸發(fā)器，求出輸出函數(shù)和激勵函數(shù)表達式；5.畫出邏輯電路圖。.4.5.1建立原始狀態(tài)圖狀態(tài)圖是同步時序電路設計的依據(jù)，它必須正確反映設計要求。狀態(tài)圖的作法沒有一成不變的方法，關鍵是要充分正確地理解設計要求。一個正確的狀態(tài)圖是指狀態(tài)圖中的狀態(tài)個數(shù)不能少，狀態(tài)之間的轉移關系不能錯。作狀態(tài)圖的一個基本方法是“對于感興趣的東西應區(qū)分對待，對于不感興趣的東西可不予區(qū)分”.例:某序列檢測器有一個輸入端x和一個輸出端Z。 從x端輸入一組按時間順序排列的串行二進制 碼。 當輸入序列中出現(xiàn)101時，輸出Z＝1， 否則 Z＝0。試作出該序列檢測器的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.例:假設某同步時序電路，用于檢測串行輸入 的8431BCD碼，其輸入的順序是先高位后 低位，當出現(xiàn)非法數(shù)字(即輸入1010，1011， 1100，1101，1110，1111)時，電路的輸出 為1。試作出該時序電路的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)簡化一般情況下，原始狀態(tài)圖和原始狀態(tài)表中存在著多余的狀態(tài)。狀態(tài)個數(shù)越多，電路中所需的觸發(fā)器的數(shù)目也越多，制造成本就越高。為降低制造成本，需要去掉多余的狀態(tài)，即要進行狀態(tài)簡化。所謂狀態(tài)簡化，就是要獲得一個最小化的狀態(tài)表。這個表不僅能正確地反映設計的全部要求，而且狀態(tài)的數(shù)目最少。.完全確定狀態(tài)表：狀態(tài)表中的次態(tài)和輸出都有確定的 狀態(tài)和確定的輸出值。

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

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

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

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

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

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

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

(1)次態(tài)相同；(2)次態(tài)交錯；(3)次態(tài)循環(huán)；(4)次態(tài)對等效。.SiSj1/0Sl0/10/1Sk1/0次態(tài)相同.次態(tài)相同或交錯SiSj0/01/01/0Sk0/0.次態(tài)交錯或相同或循環(huán)SiSj1/01/0SkSl0/00/00/10/1Sm1/01/0.次態(tài)交錯或等效(Sk,Sl等效)SiSj1/01/0SlSk0/10/1.1.觀察法化簡例：簡化下表所示的狀態(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等效；最大等效類為{A}，{B}，{C,D},分別用A',B',C'表示；A和B在x=1時的次態(tài)不滿足四條件之一，因此A和B不等效;.最小化狀態(tài)表為現(xiàn)態(tài)次態(tài)/輸出x=0x=1A'B'C’A'/0A'/0A'/0B'/0C'/0C'/1.1.隱含表法化簡例：簡化下表所示的狀態(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)對

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

四個等效對(A,B),(A,E),(B,E),(C,F)

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

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

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

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

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

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

最大相容類：不被其它相容類所包含 的相容類.判別方法：

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

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

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

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

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

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

設最小化狀態(tài)表中的狀態(tài)數(shù)為N，編碼長度為n，N和n的關系為2n-1<N<2n用2n種組合來對N個狀態(tài)進行分配時，可能出現(xiàn)的分配方案的總數(shù)Ks為－.例如，n=2,N=4時有方 案狀態(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種方案中只有三種是獨立的(真正不相同的)方案－－然而，當n較大時，Ku仍然很大，要真正找到最佳的分配方案是十分困難的，況且分配方案的好壞還與所采用的觸發(fā)器的類型有關。因此，實際應用時都是采用工程的方法，依據(jù)以下四條件原則來進行狀態(tài)分配。.狀態(tài)分配的基本原則有四條：(1)在相同輸入條件下具有相同次態(tài)的現(xiàn)態(tài)，應盡可能分配相鄰的二進制代碼；(2)在相鄰輸入條件，同一現(xiàn)態(tài)的次態(tài)應盡可能分配相鄰的二進制代碼；(3)輸出完全相同的現(xiàn)態(tài)應盡可能分配相鄰的二進制代碼；.

一般情況下，第一條原則較為重要，需優(yōu)先考慮，其次要考慮由前三條原則得到的應分配相鄰代碼的狀態(tài)對出現(xiàn)的次數(shù)，次數(shù)多的狀態(tài)對應優(yōu)先分配相鄰的二進制代碼。(4)最小化狀態(tài)表中出現(xiàn)次數(shù)最多的狀態(tài)或初始狀態(tài)應分配邏輯0。.例：對下表所示的狀態(tài)表進行狀態(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應相鄰； 由規(guī)則(2)得C和D，C和A，B和D，A和B 應相鄰； 由規(guī)則(3)得A，B，C三者應相鄰，即A 和B，A和C，B和C應相鄰； 由規(guī)則(4)得A分配為邏輯0.ACDB0101y1y2A:B:C:D:y1y20 00 11 01 1.最后我們可以得到二進制狀態(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注意：有時滿足分配原則的分配方案不唯一，這時可任選一種。.4.5.4確定激勵函數(shù)和輸出函數(shù)1.觸發(fā)器的激勵表觸發(fā)器的激勵表反映觸發(fā)器從某種現(xiàn)態(tài)轉換到某種次態(tài)時，對觸發(fā)器輸入(激勵)的要求。在這種表中，現(xiàn)態(tài)和次態(tài)作為自變量，輸入(激勵)作為因變量。觸發(fā)器的激勵表可由觸發(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ā)器激勵表D觸發(fā)器激勵表.QQ(n+1)J K0 d1 dd 1d 00 00 11 01 1QQ(n+1)T01100 00 11 01 1J-K觸發(fā)器激勵表T觸發(fā)器激勵表.2.確定激勵函數(shù)兩種方法：根據(jù)次態(tài)方程來確定和通過激勵表來確定。常采用后一種方法。.例：若用T觸發(fā)器實現(xiàn)下表所示的二進制狀態(tài)表，試寫出激勵和輸出函數(shù)?，F(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.解：確定激勵函數(shù)現(xiàn)態(tài)y2y1次態(tài)y2(n+1)y1(n+1)0 00 11 11 00 00 11 11 0輸入x激勵函數(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畫出邏輯電路圖先畫出觸發(fā)器并給觸發(fā)器編號，再根據(jù)激勵函數(shù)和輸出函數(shù)畫出組合邏輯部分的電路，最后畫出同步時鐘信號線。.例如：.1D1CD2Cy2CPx&y1z1y21&y1.4.6同步時序邏輯電路設計舉例例：設計一個“111…”序列檢測器，用來檢測串行二進制序列，要求每當連續(xù)輸入3個(或3個以上)1時，檢測器輸出為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)圖