第七章 時序電路的設(shè)計(1)

第七章時序電路的設(shè)計概述

電路分析比較有規(guī)律，對于一給定的線路，分析后的結(jié)論往往是唯一的。

電路設(shè)計：有規(guī)律，但不嚴(yán)格，一定程度上依賴于設(shè)計者的經(jīng)驗和技巧，對于一個給定命題，最終設(shè)計出來的線路不唯一，我們追求的是一個最小化的可靠的電路實現(xiàn)，由此引出了本章要討論的幾個命題。

第七章時序電路的設(shè)計時序電路數(shù)學(xué)模型

用有限狀態(tài)自動機M=(,Q,Z,,)表示輸入量集合：:(

0，1，…n)所有輸入的有限非空集合內(nèi)部狀態(tài)集合：Q:(S0，S1，…Sr)內(nèi)部狀態(tài)的有限非空集合輸出量集合：Z:(z0,z1，…zm)外部輸出的有限非空集合第七章時序電路的設(shè)計次態(tài)函數(shù)：Q

Q；內(nèi)部狀態(tài)轉(zhuǎn)換控制函數(shù)，是現(xiàn)態(tài)和輸入笛卡爾乘積至次態(tài)的一個映射。

(Si,j)=SkSi：現(xiàn)態(tài)

j：輸入Sk：次態(tài)輸出函數(shù)

：Q

Z；內(nèi)部狀態(tài)和外部輸入笛卡爾乘積到輸出的映射。

(Si,j)=Zk第七章時序電路的設(shè)計同步時序電路的設(shè)計

設(shè)計一般步驟

建立原始狀態(tài)圖和狀態(tài)表

確定輸入變量和輸出變量構(gòu)造狀態(tài)圖

產(chǎn)生原始狀態(tài)表狀態(tài)化簡消除原始狀態(tài)表中冗余狀態(tài)，以求取最簡狀態(tài)集Q狀態(tài)分配對每一個狀態(tài)賦予一個二進制代碼

第七章時序電路的設(shè)計產(chǎn)生控制函數(shù)和輸出函數(shù)根據(jù)不同觸發(fā)器的激勵表綜合出控制函數(shù)和輸出函數(shù)畫出邏輯線路圖

檢驗電路是否有自啟動能力采取措施重新設(shè)計第七章時序電路的設(shè)計設(shè)計引例（完全定義的同步時序電路設(shè)計）例1：“01”序列檢測器，即從一輸入狀態(tài)序列中檢測出“01”模式的子序列。形成原始狀態(tài)表和狀態(tài)圖

XSi01S0S1S1/0S1/0S0/0S0/1第七章時序電路的設(shè)計狀態(tài)化簡(略)狀態(tài)分配只有2個狀態(tài),只要一個觸發(fā)器,隨意分配。二進制狀態(tài)表：該電路是Mealy型電路

XQ01011/01/00/00/1第七章時序電路的設(shè)計控制函數(shù)與輸出函數(shù)

D觸發(fā)器控制函數(shù)

XQ01011/01/00/00/1輸出函數(shù):

第七章時序電路的設(shè)計邏輯電路關(guān)于D觸發(fā)器的反相輸出的應(yīng)用

第七章時序電路的設(shè)計原始狀態(tài)圖和狀態(tài)表的構(gòu)成建立原始狀態(tài)圖

確定狀態(tài)記憶何種信息四進制加法計數(shù)器

初始輸入序列識別器（識別X輸入序列中第一次出現(xiàn)的X＝111序列）

第七章時序電路的設(shè)計每一個狀態(tài)要考慮所有輸入組合下的狀態(tài)轉(zhuǎn)移狀態(tài)歸納：在可能的情況下要盡量使用已有的狀態(tài)作為下一個狀態(tài)

初始輸入X＝000或X＝111子序列識別器（識別X的第一序列是否為X＝000或X＝111）

第七章時序電路的設(shè)計串行輸入序列中的子序列識別分以下幾種情況：上例是初始第一個定長子序列檢測，且只檢測一次。任意起點，第一個子序列為X＝000或X＝111（一次檢測任意起點，所有X＝000或X＝111子序列（循環(huán)檢測）固定起點（3位一組）所有X＝000或X＝111的子序列（循環(huán)檢測）第七章時序電路的設(shè)計

第七章時序電路的設(shè)計建立原始狀態(tài)表前面討論了各種輸入序列識別器的設(shè)計，下面討論運算類電路的設(shè)計。

例：設(shè)計一個二進制串行加法器電路

建立原始的狀態(tài)圖與狀態(tài)表

ABSi00011011S0S1S0/0S0/1S0/1S1/0S0/1S1/0S1/0S1/1第七章時序電路的設(shè)計狀態(tài)化簡（略，此表已最簡）狀態(tài)分配：二個狀態(tài)只要一個觸發(fā)器就能表示控制函數(shù)與輸出函數(shù)

第七章時序電路的設(shè)計邏輯線路

第七章時序電路的設(shè)計

設(shè)計一個串行的4位字符奇校驗電路，在一串行字符輸入時，每隔4位（即一字符）輸出一奇校驗結(jié)果1，其余時刻輸出為0。

第七章時序電路的設(shè)計狀態(tài)化簡

狀態(tài)表中狀態(tài)的個數(shù)決定著時序電路里所要用的觸發(fā)器的個數(shù)。為了實現(xiàn)最小化的電路設(shè)計，需對原始狀態(tài)表中的狀態(tài)個數(shù)進行壓縮或狀態(tài)化簡。狀態(tài)等價與判定

等價狀態(tài)（等效狀態(tài)）定義：若狀態(tài)p和q對所有的可能的輸入序列

（k為任意值）具有相同的輸出序列，即則狀態(tài)p與q等價，記為

第七章時序電路的設(shè)計例：給定如下狀態(tài)表

XS01q1q2q3q3/0q1

/1q3/0q2

/1q2

/0q2/1第七章時序電路的設(shè)計等價狀態(tài)性質(zhì)自反性pp對稱性:若pq則qp傳遞性若pq,qs則ps等價類:相互等價的狀態(tài)集合

最大等價類：若一個等價類不包含在任何其它等價之中，則該等價類為最大等價類。等價狀態(tài)判定定理

若pq

當(dāng)且僅當(dāng)

(p,x)=(q,x)且(p,x)(q,x)第七章時序電路的設(shè)計等價狀態(tài)判定方法

判定兩個狀態(tài)是否等價根據(jù)判定定理有兩個條件：輸出相同：要滿足現(xiàn)輸入X所有取值時都相同次態(tài)等價：次態(tài)相同次態(tài)交錯次態(tài)循環(huán)次態(tài)自循環(huán)后繼次態(tài)等效第七章時序電路的設(shè)計例1：給定原始狀態(tài)如下

XSi01ABCDEC/1C/1B/1D/0D/0B/0E/0E/0B/1B/1第七章時序電路的設(shè)計例2：給定原始狀態(tài)如下XSi01ABCDEFGC/0F/0C/0D/1C/0F/0C/1B/1A/1G/0E/0E/1G/0D/0第七章時序電路的設(shè)計利用隱含表進行狀態(tài)化簡

畫隱含表

順序比較

關(guān)連比較

列出最大等價類并求出最小復(fù)蓋求取簡化狀態(tài)表

第七章時序電路的設(shè)計例2的隱含表最大等價類：(A,B,E),(C,F),(D),(G)abcd簡化狀態(tài)表：XSi01abcdb/0b/0c/1b/1a/1d/0a/0c/0第七章時序電路的設(shè)計第七章時序電路的設(shè)計狀態(tài)分配最佳分配的復(fù)雜性

分配方案數(shù)

S：狀態(tài)數(shù)，K：狀態(tài)編碼的位數(shù)（觸發(fā)器數(shù)）從2k組二進制編碼中，取S組來表示S個狀態(tài)，可能出現(xiàn)的分配方案數(shù)為：第七章時序電路的設(shè)計實質(zhì)方案數(shù)

假定S＝4K＝2，4個狀態(tài)為NA=24

而實質(zhì)方案數(shù)NAe=3第七章時序電路的設(shè)計次佳分配規(guī)則

相鄰—兩狀態(tài)編碼中僅有1位不同，有利于觸發(fā)器控制函數(shù)化簡和輸出函數(shù)化簡R1：次態(tài)相同，現(xiàn)態(tài)相鄰

R1a不同輸入取值下的次態(tài)分別相同，則現(xiàn)態(tài)相鄰。

R1b不論輸入取值，若次態(tài)已相鄰則具有相同次態(tài)集合的現(xiàn)態(tài)應(yīng)相鄰。

R1c不同輸入取值下部分次態(tài)相同，則現(xiàn)態(tài)相鄰。R2：同一現(xiàn)態(tài)，次態(tài)相鄰R3：輸出完全相同，現(xiàn)態(tài)相鄰(有利于輸出函數(shù)化簡)第七章時序電路的設(shè)計例1：對下列狀態(tài)表進行分配XS01S0S1S2S3S4S5S6S1,0S3,0S2,0S5,1S6,0S0,0S0,1S2,0S2,0S3,0S6,0S5,0S1,1S1,0R1a：S5S6R1b：S3S4R1c：S0S1R2：S0

S1，

S1S2，S2

S3，S5S6R3：S0

S1

S2

S4，S3S6第七章時序電路的設(shè)計串行4位字符奇校驗電路的設(shè)計，其狀態(tài)表如下：

R1a：FGR1b：DE,BCR1c：R2：BC,DE,FGR3：ABCDE第七章時序電路的設(shè)計第七章時序電路的設(shè)計

例：一個串行輸入x,二進制序列3位一組，設(shè)計一個時序電路識別能到序列組編碼為010或100時輸出Z=1，其余情況Z=0狀態(tài)圖、表狀態(tài)化簡狀態(tài)分配用D觸發(fā)器和與非門實現(xiàn)輸出函數(shù)和控制函數(shù)邏輯電路第七章時序電路的設(shè)計第七章時序電路的設(shè)計設(shè)計一個以5為模的可逆計數(shù)器第七章時序電路的設(shè)計串行8421碼檢測器的設(shè)計X為一串行輸入序列，每一個子序列以“1”開頭，“1”之后4位代表8421碼(低位先出現(xiàn)：b0b1b2b3),一個8421碼后的“0…0”子序列表示間隔。要求設(shè)計一個8421碼的檢測電路，當(dāng)發(fā)現(xiàn)非8421碼時輸出Z=1。第七章時序電路的設(shè)計不完全定義同步時序電路的設(shè)計

不完全定義同步時序電路

完全定義同步時序電路：電路中每一個現(xiàn)態(tài)與輸入組合所對應(yīng)的次態(tài)和輸出都是確定的。

不完全定義同步電路：電路中存在某些現(xiàn)態(tài)與輸入組合，他們所對應(yīng)的次態(tài)或輸出是不確定的或是無關(guān)緊要的。產(chǎn)生不確定次態(tài)或輸出的根源

外部輸入存在某些不可能出現(xiàn)的序列

外部輸出僅在某些特定時刻才有意義

某確定時刻，外部輸入之后必跟隨一系統(tǒng)復(fù)位信號

第七章時序電路的設(shè)計示例：一個“1111”序列檢測電路用作一爆炸裝置的引爆控制，輸入X通常處于“0”狀態(tài)，一旦接受了連續(xù)4個“1”，（其中不會出現(xiàn)“0”），第4個“1”輸入時電路將產(chǎn)生Z＝1的輸出，引起爆炸，該電路也不復(fù)存在。

XSi01ABCDA/0d/dd/dd/dB/0C/0D/0d/1第七章時序電路的設(shè)計狀態(tài)相容

相容關(guān)系性質(zhì)：自反性pp對稱性:若pq則qp不傳遞性 可應(yīng)用輸入序列定義：給處于初態(tài)q的不完全定義時序電路加入一輸入序列，除最后一個次態(tài)外，每一個輸入總能導(dǎo)致下一個確定狀態(tài)，則這一輸入序列稱為對該電路在q狀態(tài)時是可應(yīng)用的輸入序列。

第七章時序電路的設(shè)計輸出相容定義:兩個輸出序列中各對應(yīng)輸出，在兩者均有定義時是一致的，則這二個輸出序列是相容的。狀態(tài)相容定義：在不完全定義同步時序電路中，分別以p和q為初始狀態(tài)，如果加入任何可應(yīng)用的輸入序列后，得到兩個輸出序列是相容的，則p和q是相容的，記

pq。狀態(tài)相容判定定理：若pq當(dāng)且僅當(dāng)

(p,x)(q,x)且(p,x)(q,x)第七章時序電路的設(shè)計相容類和最大相容類：狀態(tài)相容判定方法：輸出相容

次態(tài)相容次態(tài)相同次態(tài)交錯次態(tài)循環(huán)次態(tài)自循環(huán)后繼次態(tài)相容任一次態(tài)為無關(guān)項d第七章時序電路的設(shè)計隱含表化簡法

用隱含表找出相容對用合并圖找出最大相容類作最小化狀態(tài)表復(fù)蓋性：原始狀態(tài)表中，每個狀態(tài)至少屬于該組中某一個相容類。

閉合性：該組中任一相容類，在任何一種輸入取值時的次態(tài)屬于該組中一個相容類。最小性：滿足上述條件的相容類數(shù)最少。用復(fù)蓋閉合表求最小化相容類集。第七章時序電路的設(shè)計例：簡化狀態(tài)表XSi01ABCDED/dE/0D/0C/dC/1A/dA/dB/dC/dB/d(AB),(AC),(AD),(AE),(BC),(CD),(DE)第七章時序電路的設(shè)計

(ABC),(ACD),(ADE)XSi01A’B’B’/0A’/1A’/dA’/d第七章時序電路的設(shè)計

XSi01ZABCDEFBBAdFdDDEEdC0d111d第七章時序電路的設(shè)計不完全定義同步時序電路設(shè)計舉例：火車終點站，一輛火車Ti入站和另一輛火車To出站發(fā)生在同一時刻，要求設(shè)計一個火車出入站調(diào)度控制系統(tǒng)信號：X1/X2/X3為了3個監(jiān)視傳感器，當(dāng)Xi有脈沖時表示有火車通過，S1/S2為道叉控制開關(guān),L1/L2為紅綠燈，紅燈停，綠燈放行。初態(tài)：Ti欲進站，To欲出站；L1/L2=Red；S1連主軌，S2接側(cè)軌。過程：T0通過X3入側(cè)軌，停在L1處；Ti通過X1，入主軌，再經(jīng)過X2，停在L2處，當(dāng)Ti經(jīng)過X2時，L1=Green，S1連側(cè)軌；T0出側(cè)軌，經(jīng)過X1時，L2=Green，S2連主軌。Ti前進，經(jīng)過X1后系統(tǒng)恢復(fù)初態(tài)。約束條件：