【正文】 1和加 2計數器有一個輸入 x和一個輸出 Z。當電路計滿 5個狀態(tài)后，輸出 Z產生一個 1信號作為進位輸出，平時 Z輸出為 0。 – 解 : 該問題已指定電路模型為 Mealy型，且輸入和狀態(tài)、輸出之間的關系也非常清楚，所以狀態(tài)圖的建立很容易。根據題意可作出原始狀態(tài)圖如右圖所示，相應的原始狀態(tài)表如右表所示。 輸入端 x輸入一串隨機的二進制代碼，當輸入序列中出現 011時，輸出 Z產生一個 1輸出，平時 Z輸出 0。 輸入 x： l 0 1 0 1 1 1 0 0 1 1 0 輸出 Z： 0 0 0 0 0 1 0 0 0 0 1 0 試作出該序列檢測器的原始狀態(tài)圖和原始狀態(tài)表。 設電路的初始狀態(tài)為 A。 該轉換關系如圖 (a)所示。 部分狀態(tài)圖如圖 (b)所示。 部分狀態(tài)圖如圖 (c)所示。 至此，得到了該序列檢測器完整的 Mealy型狀態(tài)圖，如圖 (d)所示。 –從上述建立原始狀態(tài)圖的過程可知，實現一個序列檢測器的功能所需要的狀態(tài)數與要識別的序列長度相關，序列越長，需要記憶的代碼位數越多，狀態(tài)數也就越多。 輸入 狀態(tài) X=0 X=1 A B/0 A/0 B B/0 C/0 C B/0 D/1 D B/0 A/0 例 3 ? 例 Moore型同步時序電路實現上例“ 011”序列檢測器，則電路輸出完全取決于狀態(tài)，而與輸入無直接關系。 假定電路初始狀態(tài)為 A， 并用狀態(tài) B、 C、D分別表示收到了輸入 X送來的 0、 0 011。當狀態(tài)從初始開始，輸入端 X正好依次輸入 0、 1時，則狀態(tài)從 A轉到 B、 B轉到 C、 C轉到 D。然后，考慮到 A狀態(tài)下輸入為 1時，它不是指定序列中的第一位信號，不必記憶，可令狀態(tài)停留在A； B狀態(tài)下輸入為 0時，它不是指定序列的第二位，但可作為指定序列的第一位，故可令其停留在 B； C狀態(tài)下輸入為 0時，不是指定序列的第三位 ,但同樣可作為第一位 ,故令其轉向狀態(tài) B； D狀態(tài)下輸入 0時，同樣應轉向 B，而輸入為 1時，則應令其進入狀態(tài) A。 1 0 0 0 Z 輸出 A B D D B C C B B A B A X=1 X=0 現態(tài) 次態(tài) 例 4 ? 例 4. 某同步時序電路用于檢測串行輸入的 8421碼，其輸入的順序是先低位后高位，當出現非法數字 (即輸入 1010， 1011，1100， 1101， 1110， 1111)時，電路的輸出為 1。 ? 解：根據題意，電路有一個輸入和一個輸出。 假定起始狀態(tài)為 A， 當第一位輸入代碼到來時，有兩種可能的情況，即 1和 0，故需用兩個狀態(tài) B和 C來表示這兩種可能；從狀態(tài) B和 C出發(fā)，當 x輸入的第二位代碼到來時，又各有兩種可能的情況，分別用狀態(tài) D， E， F， G表示；從狀態(tài) D， E，F， G出發(fā)，當 x輸入的第三位代碼到來時，同樣，各有兩種可能，共有 8種不同的情況，分別用狀態(tài) H， I， J， K， L， M，N， P表示。對輸入的 8421碼進行判斷，若出現非法數字，電路的輸出為 1，否則為 0，并返回到起始狀態(tài) A。待 4位代碼檢測完后，則應轉向初始狀態(tài) A， 以便檢查下一組代碼。通常將這類狀態(tài)圖和狀態(tài)表稱為完全確定狀態(tài)圖和狀態(tài)表，由它們所描述的電路稱為完全確定電路。這種狀態(tài)圖和狀態(tài)表被稱為不完全確定狀態(tài)圖和狀態(tài)表，所描述的電路稱為不完全確定電路。 平時輸入 x始終為0，一旦需要引爆，則從 x連續(xù)輸入 4個 1信號 (不被 0間斷 )，電路收到第四個 1后在輸出端 Z產生一個 1信號點火引爆，該電路連同引爆裝置一起被炸毀。 解 : 該電路實際上是一個用于特殊場所的“ 1111”序列檢測器。一是輸入帶有約束條件，即一旦輸入出現 1，則一定是不被 0間斷的連續(xù) 4個 l； 二是收到 4個 1后產生的引爆信號，同時使電路自毀，故此時不再存在次態(tài)問題。根據題意， A狀態(tài)下 x為 1時，輸出為 0轉向狀態(tài) B； B狀態(tài)下 x為 1時，輸出為 0轉向狀態(tài) C； C狀態(tài)下 x為 1時，輸出為 0轉向狀態(tài)D； 而 D狀態(tài)下 x為 1時，輸出為 1，次態(tài)隨意 (實際上已不存在次態(tài) )。據此，可得到該電路的 Mealy型原始狀態(tài)圖如下圖所示，原始狀態(tài)表如下表所示。 – 在時序電路設計中，利用不完全確定狀態(tài)表中不確定次態(tài)和不確定輸出的隨意性，通常可使設計方案變得更簡單。 輸入 狀態(tài) X=0 X=1 A A/0 B/0 B d/d C/0 C d/d D/0 D d/d d/1 狀態(tài)化簡 ? 在建立原始狀態(tài)圖和原始狀態(tài)表時，主要考慮的是如何清晰、正確地反映設計要求，而沒有刻意追求如何使圖、表中包含的狀態(tài)數目達到最少。但在設計具體電路時，狀態(tài)數目的多少將直接決定電路中所需觸發(fā)器數目的多少。 ? 所謂狀態(tài)化簡 ，就是采用某種化簡技術從原始狀態(tài)表中消去多余狀態(tài)，得到一個既能正確地描述給定的邏輯功能，又能使所包含的狀態(tài)數目達到最少的狀態(tài)表，通常稱這種狀態(tài)表為最小化狀態(tài)表。在利用隱含表進行化簡時，對于完全給定原始狀態(tài)表和不完全給定原始狀態(tài)表引用了不同的概念，并且處理過程有所不同。 1．完全確定狀態(tài)表的化簡 –完全確定狀態(tài)表的化簡是建立在狀態(tài)等效這個概念的基礎之上的。 (1)等效狀態(tài)和等效類 ①等效狀態(tài)：假設狀態(tài) Si和 Sj是完全確定狀態(tài)表中的兩個狀態(tài)，如果對于所有可能的輸入序列，分別從 Si和 Sj出發(fā)，所得到的輸出響應序列完全相同，則狀態(tài) Si和 Sj是等效的，記作 (Si， Sj)， 或者說，狀態(tài) Si和 Sj是等效對。如果企圖通過檢測所有可能輸入序列下的輸出來確定兩個狀態(tài)是否等效，顯然是不現實的。從而，可以根據狀態(tài)表上所列出的一位輸入各種組合下的次態(tài)和輸出來判斷某兩個狀態(tài)是否等 效。 第一，它們的輸出相同。 這里，情況 b中所謂的次態(tài)交錯，是指在某種輸入取值下， Si的次態(tài)為 Sj， 而 Sj的次態(tài)為 Si。 情況 c中的次態(tài)循環(huán)是指確定兩個狀態(tài)是否等效的關聯(lián)狀態(tài)對之間，其依賴關系構成閉環(huán)。 – 例如， S1和 S2在某種輸入取值下的次態(tài)是 S3和 S4， 而 S3和S4在該種輸入取值下的次態(tài)又是 S1和 S2， 則稱這種情況為次態(tài)循環(huán)。例如， S1的次態(tài)是 S3， S2的次態(tài)是 S4， 盡管 S3和 S4既不相同，也不交錯或循環(huán)，但若以 S3和 S4作為現態(tài)，在一位輸入的各種取值下，其輸出相同且次態(tài)相同或交錯或循環(huán)，即 S3和 S4等效，那么， S1和 S2是等效的。即假如 S1和 S2等效， S2和 S3等效，那么，一定有 S1和 S3等效。在一個等效類中的任意兩個狀態(tài)都是等效的。例如，由 (S1， S2)和 (S2， S3)可以推出 (S1， S3)， 進而可知 SS S3屬于同一等效類，記作 (S1， S2)， (S2， S3)→{S1 ，S2， S3} 在等效關系中，等效對是狹義的概念，它是對兩個狀態(tài)而言的，等效類卻是廣義的概念，兩個狀態(tài)或多個狀態(tài)均可以組成一個等效類，甚至一個狀態(tài)也可以稱為等效類，因為任何狀態(tài)和它的自身必然是等效的。這里所指的最大，并不是指包含的狀態(tài)最多，而是指它的獨立性，即使是一個狀態(tài)，只要它不被包含在別的等效類中，也是最大等效類。 利用上述判別狀態(tài)等效的條件及狀態(tài)等效的性質，就可以進行狀態(tài)簡化。簡化后的狀態(tài)數等于最大等效類的個數。 ①作隱含表。隱含表中的方格是用狀態(tài)名稱來標注的，即橫向從左到右按原始狀態(tài)表中的狀態(tài)順序依次標上第一個狀態(tài)至倒數第二個狀態(tài)的狀態(tài)名稱，而縱向自上到下依次標上第二個狀態(tài)至最后一個狀態(tài)的名稱。 ②尋找等效對。 所謂順序比較是按照隱含表中從上至下、從左至右的順序，對照原始狀態(tài)表依次對所有狀態(tài)對進行逐一檢查和比較，并將檢查結果以簡單明了的方式標注在隱含表中的相應方格內。 所謂關聯(lián)比較是指對那些在順序比較時尚未確定是否等效的狀態(tài)對作進一步檢查。如果隱含表中某方格內有一個次態(tài)對不等效，則該方格所對應的兩個狀態(tài)就不等效，于是在相應方格中增加標志“／”。這種判別有時要反復多次，直到判別出狀態(tài)對等效或不等效為止。在找出原始狀態(tài)表中的所有等效對之后，可利用等效狀態(tài)的傳遞性，求出各最大等效類。 ?下面舉例說明化簡過程。 解 該表為具有 7個狀態(tài)的原始狀態(tài)表。 ①作隱含表。由于原始狀態(tài)表中有 AG共 7個狀態(tài)，所以隱含表的橫向和縱向各有 6個方格。 表中每個方格代表一個狀態(tài)對，如左上角的方格代表狀態(tài)對 A和 B， 右下角的方格代表狀態(tài)對 F和 G。根據求出的最大等效類，將每個最大等效類中的全部狀態(tài)合并為一個狀態(tài)，即可得到和原始狀態(tài)表等價的最小化狀態(tài)表。首先進行順序比較，根據等效狀態(tài)的判斷標準，依次檢查每個狀態(tài)對，可得到順序比較結果如下圖所示。 輸入 狀態(tài) X=0 X=1 A C/0 B/1 B F/0 A/1 C F/0 G/0 D D/1 E/0 E C/0 E/1 F C/0 G/0 G C/1 D/0