邏輯電路設(shè)計

邏輯電路設(shè)計第1頁，共56頁，2023年，2月20日，星期四設(shè)計的一般過程：

1.建立給定問題的邏輯描述這一步的關(guān)鍵是弄清楚電路的輸入和輸出，建立輸入和輸出之間的邏輯關(guān)系，得到描述給定問題的邏輯表達式。求邏輯表達式有兩種常用方法，即真值表法和分析法。

2.求出邏輯函數(shù)的最簡表達式為了使邏輯電路中包含的邏輯門最少且連線最少，要對邏輯表達式進行化簡，求出描述設(shè)計問題的最簡表達式。

3.選擇邏輯門類型并將邏輯函數(shù)變換成相應(yīng)形式根據(jù)簡化后的邏輯表達式及問題的具體要求，選擇合適的邏輯門，并將邏輯表達式變換成與所選邏輯門對應(yīng)的形式。

4.畫出邏輯電路圖

根據(jù)實際問題的難易程度和設(shè)計者熟練程度，有時可跳過其中的某些步驟。設(shè)計過程可視具體情況靈活掌握。第2頁，共56頁，2023年，2月20日，星期四1.2設(shè)計舉例

解

分析:

“多數(shù)表決電路”是按照少數(shù)服從多數(shù)的原則對某項決議進行表決，確定是否通過。

令

邏輯變量A、B、C---分別代表參加表決的3個成員，并約定邏輯變量取值為0表示反對，取值為1表示贊成；

邏輯函數(shù)F----表示表決結(jié)果。F取值為0表示決議被否定，F(xiàn)取值為1表示決議通過。按照少數(shù)服從多數(shù)的原則可知，函數(shù)和變量的關(guān)系是：當3個變量A、B、C中有2個或2個以上取值為1時，函數(shù)F的值為1，其他情況下函數(shù)F的值為0。

例

設(shè)計一個三變量“多數(shù)表決電路”。第3頁，共56頁，2023年，2月20日，星期四

①建立給定問題的邏輯描述

假定采用“真值表法”，可作出真值表如下表所示。

00000010010001111000101111011111ABCF由真值表可寫出函數(shù)F的最小項表達式為

F(A,B,C)=∑m(3,5,6,7)第4頁，共56頁，2023年，2月20日，星期四②求出邏輯函數(shù)的最簡表達式

作出函數(shù)F(A,B,C)=∑m(3,5,6,7)的卡諾圖如下圖所示。用卡諾圖化簡后得到函數(shù)的最簡“與-或”表達式為

③選擇邏輯門類型并進行邏輯函數(shù)變換

假定采用與非門構(gòu)成實現(xiàn)給定功能的電路，則應(yīng)將上述表達式變換成“與非-與非”表達式。即第5頁，共56頁，2023年，2月20日，星期四

④畫出邏輯電路圖

由函數(shù)的“與非-與非”表達式，可畫出實現(xiàn)給定功能的邏輯電路圖如下圖所示。本例采用的是“真值表法”，真值表法的優(yōu)點是規(guī)整、清晰；缺點是不方便，尤其當變量較多時十分麻煩。第6頁，共56頁，2023年，2月20日，星期四2同步時序邏輯電路的設(shè)計

同步時序邏輯電路的設(shè)計是指根據(jù)特定的邏輯要求，設(shè)計出能實現(xiàn)其邏輯功能的時序邏輯電路。顯然，設(shè)計是分析的逆過程，即：

同步時序邏輯電路設(shè)計追求的目標是，使用盡可能少的觸發(fā)器和邏輯門實現(xiàn)預(yù)定的邏輯要求！邏輯電路邏輯功能分析設(shè)計第7頁，共56頁，2023年，2月20日，星期四

2．狀態(tài)化簡，求得最小化狀態(tài)表；

設(shè)計的一般步驟如下：

1．形成原始狀態(tài)圖和原始狀態(tài)表；

3．狀態(tài)編碼，得到二進制狀態(tài)表；

4．選定觸發(fā)器的類型，并求出激勵函數(shù)和輸出函數(shù)最簡

表達式；

5．畫出邏輯電路圖。原始狀態(tài)圖是對設(shè)計要求最原始的抽象,根據(jù)邏輯問題的文字描述理解電路的輸入、輸出及狀態(tài)轉(zhuǎn)移關(guān)系，進而形成狀態(tài)圖和狀態(tài)表。由于開始得到的狀態(tài)圖和狀態(tài)表可能包含多余的狀態(tài)，所以稱為原始狀態(tài)圖和原始狀態(tài)表。

采用狀態(tài)化簡技術(shù)，消去原始狀態(tài)表中的多余的狀態(tài)，求得最小化狀態(tài)表。

目的：簡化電路結(jié)構(gòu)。

把狀態(tài)表中用字母或數(shù)字標注的每個狀態(tài)用二進制代碼表示，以便和電路中觸發(fā)器的狀態(tài)一致。根據(jù)選定的觸發(fā)器類型，列出激勵函數(shù)真值表，并求出激勵函數(shù)和輸出函數(shù)的最簡表達式。其中，激勵函數(shù)是由二進制狀態(tài)表和觸發(fā)器激勵表共同確定的。

以上步驟是就一般設(shè)計問題而言的。實際中設(shè)計者可以根據(jù)具體問題靈活掌握。當設(shè)計方案中包含有冗余狀態(tài)時，必須對冗余狀態(tài)的處理結(jié)果加以討論，以確保電路邏輯功能的可靠實現(xiàn)。第8頁，共56頁，2023年，2月20日，星期四5.3.1建立原始狀態(tài)圖和原始狀態(tài)表

原始狀態(tài)圖和原始狀態(tài)表是對設(shè)計要求的最原始的抽象，是構(gòu)造相應(yīng)電路的依據(jù)。由于狀態(tài)圖比狀態(tài)表更形象、靈活，一般先畫狀態(tài)圖后作狀態(tài)表。如果原始狀態(tài)圖不能正確地反映設(shè)計要求，則依此設(shè)計出來的電路必然是錯誤的。因此，建立正確的原始狀態(tài)圖和狀態(tài)表是同步時序電路設(shè)計中最關(guān)鍵的一步。

原始狀態(tài)圖的形成是建立在對設(shè)計要求充分理解的基礎(chǔ)之上的，設(shè)計者必須對給定的問題進行認真、全面地分析，弄清楚電路輸出和輸入的關(guān)系以及狀態(tài)的轉(zhuǎn)換關(guān)系。

一、確定電路模型

設(shè)計成Mealy型？Moore型？

形成原始狀態(tài)圖時一般應(yīng)考慮如下幾個方面問題：二、設(shè)立初始狀態(tài)

時序邏輯電路在輸入信號開始作用之前的狀態(tài)稱為初始狀態(tài)。同一個電路用不同狀態(tài)作為初始狀態(tài)時，對相同輸入序列所產(chǎn)生的狀態(tài)響應(yīng)序列和輸出響應(yīng)序列一般是不相同的。因此，在建立原始狀態(tài)圖時，應(yīng)首先設(shè)立初始狀態(tài)，然后從初始狀態(tài)出發(fā)考慮在各種輸入作用下的狀態(tài)轉(zhuǎn)移和輸出響應(yīng)。

第9頁，共56頁，2023年，2月20日，星期四

三、根據(jù)需要記憶的信息增加新的狀態(tài)

同步時序電路中狀態(tài)數(shù)目的多少取決于需要記憶和區(qū)分的信息量。一般來說，若在某個狀態(tài)下出現(xiàn)的輸入信號能用已有狀態(tài)表示，則應(yīng)轉(zhuǎn)向已有狀態(tài)。僅當某個狀態(tài)下出現(xiàn)的輸入信號不能用已有狀態(tài)表示時，才令其轉(zhuǎn)向新的狀態(tài)。這樣，從初始狀態(tài)出發(fā)，逐個增加和完善，直到每個狀態(tài)下各種輸入取值均已考慮而沒有新的狀態(tài)出現(xiàn)為止。

四、確定各時刻電路的輸出

在建立原始狀態(tài)圖時，必須確定各時刻的輸出值。在Moore型電路中，應(yīng)指明每種狀態(tài)下對應(yīng)的輸出；在Mealy型電路中應(yīng)指明從每一個狀態(tài)出發(fā)，在不同輸入作用下的輸出值。在描述一個邏輯問題的原始狀態(tài)圖和原始狀態(tài)表中，狀態(tài)數(shù)目不一定能達到最少，這一點無關(guān)緊要，因為可以對它再進行狀態(tài)化簡。設(shè)計者應(yīng)把清晰、正確地描述設(shè)計要求放在第一位。其次，由于在開始時往往不知道描述一個給定的邏輯問題需要多少狀態(tài)，因此，在原始狀態(tài)圖和狀態(tài)表中一般用字母或數(shù)字表示狀態(tài)。第10頁，共56頁，2023年，2月20日，星期四

例某序列檢測器有一個輸入端x和一個輸出端Z。輸入端x輸入一串隨機的二進制代碼，當輸入序列中出現(xiàn)“011”時，輸出Z產(chǎn)生一個1輸出，平時Z輸出0。典型輸入、輸出序列如下。輸入x:101011100110輸出Z:000001000010試作出該序列檢測器的原始狀態(tài)圖和原始狀態(tài)表。

解1.假定用Mealy型同步時序邏輯電路實現(xiàn)該序列檢測器的邏輯功能.

設(shè):

狀態(tài)A------電路的初始狀態(tài)；

狀態(tài)B------表示收到了序列“011”中的第一個信號“0”；

狀態(tài)C------表示收到了序列“011”中的前面兩位“01”；

狀態(tài)D------表示收到了序列“011”。第11頁，共56頁，2023年，2月20日，星期四※當電路處在狀態(tài)A輸入x為0時，應(yīng)令輸出Z為0轉(zhuǎn)向狀態(tài)B；而處在狀態(tài)A輸入x為1時，應(yīng)令輸出Z為0停留在狀態(tài)A，因為輸入1不是序列"011"的第一個信號，故不需要記住。該轉(zhuǎn)換關(guān)系如圖所示。

※當電路處于狀態(tài)B輸入x為0時，盡管它不是序列"011"的第二個信號，但仍可作為序列中的第一個信號，故可令電路輸出為0，停留在狀態(tài)B；若輸入x為1，則意味著收到了序列"011"的前面兩位01，可令電路輸出0轉(zhuǎn)向狀態(tài)C。如圖所示。

第12頁，共56頁，2023年，2月20日，星期四※當電路處于狀態(tài)C輸入x為0時，則收到的連續(xù)3位代碼為010，不是關(guān)心的序列011，但此時輸入的0依然可以作為序列的第一個信號，故應(yīng)輸出0轉(zhuǎn)向狀態(tài)B；若輸入x為1，則表示收到了序列"011"，可用一個新的狀態(tài)D記住，可令電路輸出1轉(zhuǎn)向狀態(tài)D。如圖所示?！旊娐诽幱跔顟B(tài)D輸入x為0時，應(yīng)輸出0轉(zhuǎn)向狀態(tài)B；若輸入x為1，則應(yīng)輸出0，轉(zhuǎn)向狀態(tài)A。

至此，得到了該序列檢測器完整的Mealy型狀態(tài)圖，如圖(d)所示。相應(yīng)的原始狀態(tài)表如表所示。第13頁，共56頁，2023年，2月20日，星期四可畫出狀態(tài)圖如下：

相應(yīng)狀態(tài)表如下：

第14頁，共56頁，2023年，2月20日，星期四

2．假定用Moore型同步時序邏輯電路實現(xiàn)該序列檢測器的邏輯功能.由于電路輸出完全取決于狀態(tài)，而與輸入無直接聯(lián)系。在作狀態(tài)圖時，應(yīng)將輸出標記在代表各狀態(tài)的圓圈內(nèi)。

設(shè)電路初始狀態(tài)為A，并用狀態(tài)B、C、D分別表示收到了輸入x送來的0、01、011。顯然，根據(jù)題意，僅當處于狀態(tài)D時電路輸出為1，其他狀態(tài)下輸出均為0。第15頁，共56頁，2023年，2月20日，星期四當從初始狀態(tài)開始，輸入端x正好依次輸入0、1、1時，則狀態(tài)從A轉(zhuǎn)至B、B轉(zhuǎn)至C、C轉(zhuǎn)至D。據(jù)此可得到部分狀態(tài)圖如圖左圖所示。若A狀態(tài)下輸入為1，則不是指定序列中的第一位信號，不必記憶，可令狀態(tài)停留在A；B狀態(tài)下輸入為0時，它不是指定序列的第二位，但可作為指定序列的第一位，故可令其停留在B；C狀態(tài)下輸入0時，它不是指定序列的第三位，但同樣可作為第一位，故令其轉(zhuǎn)向狀態(tài)B；D狀態(tài)下輸入0時，同樣應(yīng)轉(zhuǎn)向B，而輸入為1時，則應(yīng)令其進入狀態(tài)A。完整的Moore型原始狀態(tài)圖如圖右圖所示。1第16頁，共56頁，2023年，2月20日，星期四構(gòu)造Moore型原始狀態(tài)圖如下：相應(yīng)的原始狀態(tài)表如下表所示。1第17頁，共56頁，2023年，2月20日，星期四

例

設(shè)計一個用于引爆控制的同步時序電路，該電路有一個輸入端x和一個輸出端Z。平時輸入x始終為0，一旦需要引爆，則從x連續(xù)輸入4個1信號(不被0間斷)，電路收到第四個1后在輸出端Z產(chǎn)生一個1信號點火引爆，該電路連同引爆裝置一起被炸毀。試建立該電路的Mealy型狀態(tài)圖和狀態(tài)表。

（該問題的實際意義？----------施工的安全性?。?/p>

解分析:該電路實際上是一個用于特殊場所的“1111”序列檢測器。它與一般序列檢測器有兩點不同：

1.輸入帶有約束條件，即一旦輸入出現(xiàn)1，則一定是不被0間斷的連續(xù)4個1；

2.收到4個1后，輸出產(chǎn)生的引爆信號使電路自毀，故此時不再存在次態(tài)問題。第18頁，共56頁，2023年，2月20日，星期四

設(shè)：狀態(tài)A---電路初始狀態(tài)；

狀態(tài)B---表示收到了第一個1輸入；

狀態(tài)C---表示收到了連續(xù)2個1輸入；

狀態(tài)D---表示收到了連續(xù)3個1輸入。根據(jù)題意，可得到該電路的Mealy型原始狀態(tài)圖和原始狀態(tài)表如下。圖、表中用“d”表示不確定次態(tài)或不確定輸出。第19頁，共56頁，2023年，2月20日，星期四

注意:

在時序電路設(shè)計中，狀態(tài)化簡時利用不完全確定狀態(tài)表中不確定次態(tài)和不確定輸出的隨意性，通常可使設(shè)計方案變得更簡單。這一點類似包含無關(guān)最小項的組合電路設(shè)計，只不過在處理上要復(fù)雜一些。第20頁，共56頁，2023年，2月20日，星期四2.2狀態(tài)化簡

什么叫狀態(tài)化簡？

所謂狀態(tài)化簡，是指采用某種化簡技術(shù)從原始狀態(tài)表中消去多余狀態(tài)，得到一個既能正確地描述給定的邏輯功能，又能使所包含的狀態(tài)數(shù)目達到最少的狀態(tài)表，通常稱這種狀態(tài)表為最小化狀態(tài)表。

目的：簡化電路結(jié)構(gòu)。狀態(tài)數(shù)目的多少直接決定電路中所需觸發(fā)器數(shù)目的多少。設(shè)狀態(tài)數(shù)目為n,所需觸發(fā)器數(shù)目為m,則應(yīng)滿足如下關(guān)系：2m≥n＞2m-1

方法：常用方法有觀察法、輸出分類法、隱含表法等。下面討論最常用的一種方法----隱含表法。在利用隱含表進行化簡時，對于完全給定原始狀態(tài)表和不完全給定原始狀態(tài)表引用了不同的概念，并且處理過程有所不同。

第21頁，共56頁，2023年，2月20日，星期四一、完全確定狀態(tài)表的化簡1．幾個概念(1)等效狀態(tài)

①定義設(shè)狀態(tài)Si和Sj是完全確定狀態(tài)表中的兩個狀態(tài)，若對于所有可能的輸入序列，分別從狀態(tài)Si和狀態(tài)Sj出發(fā)，所得到的輸出響應(yīng)序列完全相同，則狀態(tài)Si和Sj是等效的，記作(Si，Sj)，又稱狀態(tài)Si和Sj為等效對。請注意掌握三點：定義、判斷方法和性質(zhì)。第22頁，共56頁，2023年，2月20日，星期四

②判斷方法若狀態(tài)Si和Sj是完全確定的原始狀態(tài)表中的兩個現(xiàn)態(tài)，則Si和Sj等效的條件可歸納為在一位輸入的各種取值組合下滿足如下兩條：

第一，輸出相同；第二，次態(tài)屬于下列情況之一：a.次態(tài)相同；b.次態(tài)交錯或為各自的現(xiàn)態(tài)；c.次態(tài)循環(huán)或為等效對。第23頁，共56頁，2023年，2月20日，星期四③性質(zhì)等效狀態(tài)具有傳遞性。即假若S1和S2等效，S2和S3等效,那么，一定有S1和S3等效。記作(S1，S2)，(S2，S3)(S1，S3)

(2)等效類

等效類：由若干彼此等效的狀態(tài)構(gòu)成的集合。在同一個等效類中的任意兩個狀態(tài)都是等效的。例如，由(S1，S2)和(S2，S3)可以推出(S1，S3)，進而可知S1、S2、S3屬于同一等效類，記作{S1，S2，S3}，即(S1，S2)，(S2，S3){S1，S2，S3}第24頁，共56頁，2023年，2月20日，星期四

(3)最大等效類

所謂最大等效類，是指不被任何別的等效類所包含的等效類。

注意：

這里所指的最大，并不是指包含的狀態(tài)最多，而是指它的獨立性，即使是一個狀態(tài)，只要它不被包含在別的等效類中，也是最大等效類。換而言之，如果一個等效類不是任何其他等效類的子集，則該等效類稱為最大等效類。完全給定原始狀態(tài)表的化簡過程，就是尋找出表中的所有最大等效類，然后將每個最大等效類中的狀態(tài)合并為一個新的狀態(tài)，從而得到最小化狀態(tài)表。

簡化后的狀態(tài)數(shù)等于最大等效類的個數(shù)！第25頁，共56頁，2023年，2月20日，星期四2．狀態(tài)化簡(1)隱含表化簡法的一般步驟

①作隱含表

隱含表是一個直角三角形階梯網(wǎng)格，橫向和縱向格數(shù)相同，即等于原始狀態(tài)表中的狀態(tài)數(shù)減1。隱含表中的方格是用狀態(tài)名稱來標注的，即橫向從左到右按原始狀態(tài)表中的狀態(tài)順序依次標上第一個狀態(tài)至倒數(shù)第二個狀態(tài)的狀態(tài)名稱，而縱向自上到下依次標上第二個狀態(tài)至最后一個狀態(tài)的名稱。表中每個方格代表一個狀態(tài)對。

作隱含表找等效對求最大等效類

狀態(tài)合并作最簡狀態(tài)表12345第26頁，共56頁，2023年，2月20日，星期四

順序比較：按照隱含表中從上至下、從左至右的順序，對照原始狀態(tài)表依次對所有“狀態(tài)對”進行逐一檢查和比較，并將檢查結(jié)果標注在隱含表中的相應(yīng)方格內(nèi)。比較結(jié)果標注如下：

等效-------在相應(yīng)方格內(nèi)填上“∨”；

不等效-----在相應(yīng)方格內(nèi)填上“×”；

與其他狀態(tài)對相關(guān)----在相應(yīng)方格內(nèi)填上相關(guān)的狀態(tài)對。

關(guān)聯(lián)比較：指對那些在順序比較時尚未確定是否等效的狀態(tài)對作進一步檢查。直到判別出狀態(tài)對等效或不等效為止。②尋找等效對

利用隱含表尋找狀態(tài)表中的全部"等效對"一般需要進行兩輪比較，首先進行順序比較，然后進行關(guān)聯(lián)比較。第27頁，共56頁，2023年，2月20日，星期四

關(guān)聯(lián)比較時，首先要確定隱含表中待檢查的那些次態(tài)對是否等效，并由此確定原狀態(tài)對是否等效。如果隱含表中某方格內(nèi)有一個次態(tài)對不等效，則該方格所對應(yīng)的兩個狀態(tài)就不等效，并在相應(yīng)方格中增加標志"/"。若方格內(nèi)的次態(tài)對均為等效狀態(tài)對，則與該方格對應(yīng)的狀態(tài)為等效狀態(tài)，該方格不增加任何標志。這種判別有時要反復(fù)多次，直到判別出狀態(tài)對等效或不等效為止。

第28頁，共56頁，2023年，2月20日，星期四

③求出最大等效類

在找出原始狀態(tài)表中的所有等效對之后，可利用等效狀態(tài)的傳遞性，求出各最大等效類。

④狀態(tài)合并，作出最小化狀態(tài)表將每個最大等效類中的全部狀態(tài)合并為一個狀態(tài)，即可得到和原始狀態(tài)表等價的最小化狀態(tài)表。確定各最大等效類時應(yīng)注意兩點：

※各最大等效類之間不應(yīng)出現(xiàn)相同狀態(tài)，因為若兩個等效類之間有相同狀態(tài)，則根據(jù)等效的傳遞性可令其合為一個等效類；

※原始狀態(tài)表中的每一個狀態(tài)都必須屬于某一個最大等效類，換句話說，各最大等效類所包含的狀態(tài)之和必須覆蓋原始狀態(tài)表中的全部狀態(tài)，否則，化簡后的狀態(tài)表不能描述原始狀態(tài)表所描述的功能。

第29頁，共56頁，2023年，2月20日，星期四(2)化簡舉例例化簡下表所示原始狀態(tài)表。解①作隱含表給定原始狀態(tài)表具有7個狀態(tài)，根據(jù)畫隱含表的規(guī)則，可畫出隱含表框架如下。第30頁，共56頁，2023年，2月20日，星期四

②尋找等效對根據(jù)等效狀態(tài)的判斷標準，依次檢查每個狀態(tài)對，可得到順序比較結(jié)果如圖(a)所示。關(guān)聯(lián)比較的結(jié)果如圖(b)所示。圖(a)圖(b)第31頁，共56頁，2023年，2月20日，星期四由判斷結(jié)果可知，原始狀態(tài)表中的7個狀態(tài)共有四個等效對：(A，B)，(A，E)，(B，E)，(C，F(xiàn))。第32頁，共56頁，2023年，2月20日，星期四

④狀態(tài)合并，作出最小化狀態(tài)表令{A,B,E}----a、{C,F}---b、{D}---c、{G}---d，并代入原始狀態(tài)表中，即可得到化簡后的狀態(tài)表如下邊右表所示。

③求出最大等效類由所得到的等效對和最大等效類的定義可知，原始狀態(tài)表中的7個狀態(tài)共構(gòu)成{A,B,E},{C,F},{D},{G}四個最大等效類。第33頁，共56頁，2023年，2月20日，星期四二、不完全確定狀態(tài)表的化簡不完全確定狀態(tài)表中存在不確定的次態(tài)或輸出，這些不確定的狀態(tài)和輸出對于狀態(tài)化簡是有利的，關(guān)鍵是必須恰當處理，以確?；喦昂鬆顟B(tài)表的邏輯功能不變。為此，引入出了一個新的概念--相容狀態(tài)。1．相容狀態(tài)和相容類

（1）相容狀態(tài)

①定義

假定狀態(tài)Si和Sj是不完全確定狀態(tài)表中的兩個狀態(tài)，如果對于所有的有效輸入序列，分別從狀態(tài)Si和Sj出發(fā)，所得到的輸出響應(yīng)序列(除不確定的那些位之外)是完全相同的，那么，狀態(tài)Si和Sj是相容的，或者說狀態(tài)Si和Sj是相容對，記作(Si，Sj)。

有效輸入序列：從狀態(tài)表中的狀態(tài)S出發(fā)，如果給定某輸入序列所得到的狀態(tài)響應(yīng)序列除最后一個次態(tài)外，其他次態(tài)都是確定的，那么，這個輸入序列對狀態(tài)S是有效的。所有的有效輸入序列，是指有效輸入序列的長度和結(jié)構(gòu)是任意的。第34頁，共56頁，2023年，2月20日，星期四②相容狀態(tài)的判斷

假定狀態(tài)Si和Sj是不完全確定狀態(tài)表中的兩個現(xiàn)態(tài)，狀態(tài)Si和Sj相容的條件可歸納為在一位輸入的各種取值組合下滿足如下兩條。

第一，它們的輸出完全相同，或者其中的一個(或兩個)輸出不確定。

第二，它們的次態(tài)屬于下列情況之一：

a.次態(tài)相同；

b.次態(tài)交錯或為各自的現(xiàn)態(tài)；

c.次態(tài)循環(huán)或為相容對；

d.其中的一個(或兩個)為不確定狀態(tài)。③注意!!相容狀態(tài)不具有傳遞性。這是因為判斷兩個狀態(tài)是否相容時，對于不給定的輸出和不給定的次態(tài)可以隨意指定的緣故。例如，在表中，有狀態(tài)A、B相容，狀態(tài)A、C相容，但狀態(tài)B、C不相容。現(xiàn)態(tài)y次態(tài)/輸出(y（n+1）/Z)x=0x=1ABCDA/0A/0A/0B/1D/dD/0D/1d/1第35頁，共56頁，2023年，2月20日，星期四(2)相容類

相容類是由彼此相容的狀態(tài)構(gòu)成的集合。處于同一相容類中的所有狀態(tài)之間都是兩兩相容的。例如，若有相容對(S1,S2)、(S2，S3)和(S1,S3)，則可構(gòu)成相容類{S1,S2，S3}。(3)最大相容類

若一個相容類不是任何其他相容類的子集，則該相容類稱為最大相容類。由于相容狀態(tài)無傳遞性，所以，同一原始狀態(tài)表的各最大相容類之間可能存在相同狀態(tài)，即同一狀態(tài)可能出現(xiàn)在不同的最大相容類中。第36頁，共56頁，2023年，2月20日，星期四2.不完全確定狀態(tài)表的化簡

(1)化簡步驟

一般步驟如下：

①作隱含表，尋找相容狀態(tài)對。

利用隱含表尋找相容對的過程與化簡完全確定狀態(tài)表時尋找等效對的過程是相同的，僅僅是狀態(tài)相容與狀態(tài)等效的標準有所不同而已。即在順序比較完成后，可利用已建立的隱含表繼續(xù)進行關(guān)聯(lián)比較，直至判斷出所有狀態(tài)對相容或不相容為止，便可列出原始狀態(tài)表中的全部相容對。

②利用狀態(tài)合并圖，求出最大相容類。

狀態(tài)合并圖：狀態(tài)合并圖是求最大相容類工具。它將狀態(tài)表的所有狀態(tài)以"點"的形式均勻地繪在圓周上，然后把所有相容對用線段連接起來。若某些頂點任意兩點之間都有連線，則其頂點狀態(tài)的集合構(gòu)成一個最大相容類。第37頁，共56頁，2023年，2月20日，星期四圖(a)、(b)、(c)分別表示包含3個、4個和5個狀態(tài)的最大相容類狀態(tài)合并圖。

第38頁，共56頁，2023年，2月20日，星期四③利用閉覆蓋表，求最小閉覆蓋。

最小閉覆蓋-----是從最大相容類(或相容類)中選出一個相容類的集合，該相容類集合滿足以下3個條件：

a.覆蓋性，即所選相容類集合應(yīng)包含原始狀態(tài)表的全部狀態(tài)。

b.最小性，即所選相容類集合中相容類個數(shù)應(yīng)最少。

c.閉合性，即所選相容類集合中的任一相容類，在原始狀態(tài)表中任一輸入條件下產(chǎn)生的次態(tài)應(yīng)該屬于該集合中的某一個相容類。

（思考：為什么要滿足覆蓋？為什么要滿足閉合？）

化簡不完全確定狀態(tài)表的關(guān)鍵，就是尋找一個最小閉覆蓋。

閉覆蓋表：所謂閉覆蓋表是指反映閉合和覆蓋這兩個性質(zhì)的表格，該表反映相容類集合對狀態(tài)的覆蓋情況和相容類的閉合關(guān)系。表的左邊自上而下列出所選相容類，表的中間覆蓋部分列出各相容類對原始狀態(tài)表中狀態(tài)的覆蓋情況，表的右邊閉合部分列出各相容類在一位輸入各種取值組合下的次態(tài)組合。（注意，這里所說的相容類包括最大相容類和它們的子類。）④作出最小化狀態(tài)表。

將最小閉覆蓋中的每個相容類用一個新的狀態(tài)符號表示，再將其代入原始狀態(tài)表中，即可得到與原始狀態(tài)表功能相同的最小化狀態(tài)表。

第39頁，共56頁，2023年，2月20日，星期四例化簡下表所示的原始狀態(tài)表。

解表中所示是一個具有5個狀態(tài)的原始狀態(tài)表，表中存在不確定的次態(tài)和輸出，因此，屬于不完全確定狀態(tài)表。

①作隱含表，尋找相容狀態(tài)對。

作出隱含表，并根據(jù)相容狀態(tài)的判斷標準對各狀態(tài)對進行順序比較和關(guān)聯(lián)比較后的結(jié)果如圖所示。第40頁，共56頁，2023年，2月20日，星期四②作狀態(tài)合并圖，找出最大相容類。

根據(jù)相容狀態(tài)對可作出狀態(tài)合并圖如圖5.25所示。從狀態(tài)合并圖得到最大相容類為{A,B,D}、{A,C,D}、{A,C,E}。

由隱含表中的標注可知，該狀態(tài)表中的相容狀態(tài)對有：(A,B)、(A，C)、(A，D)、(A，E)、(B，D)、(C，D)、(C，E)。第41頁，共56頁，2023年，2月20日，星期四③作閉覆蓋表，求最小閉覆蓋。

由得到的3個最大相容類，可作出其閉覆蓋表如表所示由表所示閉覆蓋表和選擇最小閉覆蓋的3個條件可知，該例的最小閉覆蓋可由最大相容類{A,B,D}和{A,C,E}組成。

a.覆蓋性，即所選相容類集合應(yīng)包含原始狀態(tài)表的全部狀態(tài)。

b.最小性，即所選相容類集合中相容類個數(shù)應(yīng)最少。

c.閉合性，即所選相容類集合中的任一相容類，在原始狀態(tài)表中任一輸入條件下產(chǎn)生的次態(tài)應(yīng)該屬于該集合中的某一個相容類。

第42頁，共56頁，2023年，2月20日，星期四④作出最小化狀態(tài)表。

假定最小閉覆蓋中的相容類{A,B,D}用狀態(tài)a表示，相容類{A,C,E}用狀態(tài)b表示，將其代入表所示原始狀態(tài)表中，可得到最小化狀態(tài)表如表所示。

注意：在填寫最小化狀態(tài)表中的輸出值時，若原始狀態(tài)表中的相應(yīng)輸出值有確定的和不確定的兩種類型，則應(yīng)填入確定的輸出值。例如，原始表中的狀態(tài)A、B、D在輸入x=0時的輸出有1和d兩種，合并后的狀態(tài)a在x=0時的輸出應(yīng)為1。

最小化狀態(tài)表現(xiàn)態(tài)次態(tài)/輸出x=0x=1ab/1a/0ba/0b/1

值得指出的是，在化簡不完全給定狀態(tài)表時，構(gòu)成最小閉覆蓋的相容類并不一定是最大相容類。例如，本例中選最大相容類{A,B,D}和相容類{C,E}作為最小閉覆蓋，可得到相同的結(jié)果。在某些情況下，如果僅僅從最大相容類中去選擇最小閉覆蓋，則合并后的狀態(tài)表不一定是最簡的。而如果在滿足最小覆蓋的前提下，在最大相容類和非最大相容類之間作恰當?shù)倪x擇，卻能得到最簡的狀態(tài)表。

第43頁，共56頁，2023年，2月20日，星期四2.3狀態(tài)編碼

狀態(tài)編碼：是指給最小化狀態(tài)表中用字母或數(shù)字表示的狀態(tài)，指定一個二進制代碼，形成二進制狀態(tài)表。狀態(tài)編碼也稱狀態(tài)分配，或者狀態(tài)賦值。一般情況下，采用的狀態(tài)編碼方案不同，所得到的輸出函數(shù)和激勵函數(shù)的表達式也不同，從而設(shè)計出來的電路其復(fù)雜程度也不同。

狀態(tài)編碼的任務(wù)是：

①確定狀態(tài)編碼的長度(即二進制代碼的位數(shù)，或者說所需觸發(fā)器個數(shù))；②尋找一種最佳的或接近最佳的狀態(tài)分配方案。以便使所設(shè)計的時序電路最簡單。第44頁，共56頁，2023年，2月20日，星期四一、確定二進制代碼的位數(shù)

設(shè)最小化狀態(tài)表的狀態(tài)數(shù)為N，狀態(tài)編碼的長度為m,則狀態(tài)數(shù)N與狀態(tài)編碼長度m的關(guān)系為

2m-1<N≤2m例如，若某狀態(tài)表的狀態(tài)數(shù)N=7，則狀態(tài)分配時,二進制代碼的位數(shù)應(yīng)為m=3?；蛘哒f狀態(tài)變量個數(shù)為3。二、確定狀態(tài)分配方案狀態(tài)與代碼之間的對應(yīng)關(guān)系可以有許多種。一般說來，用m位二進制代碼的2m種組合來對N個狀態(tài)進行分配時，可能出現(xiàn)的狀態(tài)分配方案數(shù)Ks為例如，當N=4,

m=2時，KS=24。第45頁，共56頁，2023年，2月20日，星期四例如，當N=4,m=2時，KS=24。隨著狀態(tài)數(shù)目的增加，分配方案的數(shù)目急劇增加。如何從眾多的分配方案中尋找出一種最佳方案，使所設(shè)計的電路最簡單，是一件十分困難的事情。而且，分配方案的好壞還與所采用的觸發(fā)器類型相關(guān)，即一種分配方案對某種觸發(fā)器是最佳的，但對另一種觸發(fā)器則不一定是最佳的。因此，狀態(tài)分配是一個比較復(fù)雜的問題。盡管做了大量研究工作，但從理論上講，尋求最佳狀態(tài)編碼的問題尚未完全解決。在實際工作中，工程技術(shù)人員通常按照一定的原則、憑借設(shè)計的經(jīng)驗去尋找相對最佳的編碼方案。

第46頁，共56頁，2023年，2月20日，星期四一種常用方法稱為相鄰分配法。

相鄰分配法的基本思想是：在選擇狀態(tài)編碼時，盡可能使激勵函數(shù)和輸出函數(shù)在卡諾圖上的“1”方格處在相鄰位置，從而有利于激勵函數(shù)和輸出函數(shù)的化簡。第47頁，共56頁，2023年，2月20日，星期四

相鄰分配法的狀態(tài)編碼原則如下：

①次態(tài)相同，現(xiàn)態(tài)相鄰。(即在相同輸入條件下，具有相同次態(tài)的現(xiàn)態(tài)應(yīng)盡可能分配相鄰的二進制代碼；)②同一現(xiàn)態(tài)，次態(tài)相鄰。(即在相鄰輸入條件下，同一現(xiàn)態(tài)的次態(tài)應(yīng)盡可能分配相鄰的二進制代碼；)③輸出相同，現(xiàn)態(tài)相鄰。(即在每一種輸入取值下均具有相同輸出的現(xiàn)態(tài)應(yīng)盡可能分配相鄰的二進制代碼。)一般來說，上述3條原則在大多數(shù)情況下是有效的。但由于3條原則是分別實施的，因此，對于某些狀態(tài)表常常出現(xiàn)不能同時滿足3條原則的情況。此時，可按從①至③的優(yōu)先順序考慮，即把原則①放在首位。

此外，從電路實際工作狀態(tài)考慮，一般將初始狀態(tài)分配“0”狀態(tài)。第48頁，共56頁，2023年，2月20日，星期四三、舉例例對如下狀態(tài)表進行狀態(tài)編碼（設(shè)A為初始狀態(tài)）。現(xiàn)態(tài)次態(tài)/輸出x=0x=1AC/1B/0BA/0A/1CA/1D/1DD/1C/0

解

所示狀態(tài)表中，狀態(tài)數(shù)N=4，故狀態(tài)編碼的長度應(yīng)為m=2。即實現(xiàn)該狀態(tài)表的功能需要兩個觸發(fā)器。第49頁，共56頁，2023年，2月20日，星期四

根據(jù)相鄰法的編碼原則，4個狀態(tài)的相鄰關(guān)系如下：

根據(jù)原則①，狀態(tài)B和C應(yīng)分配相鄰的二進制代碼；根據(jù)原則②，狀態(tài)B和C、A和D、C和D應(yīng)分配相鄰的二進制代碼；根據(jù)原則③，狀態(tài)A和D應(yīng)分配相鄰的二進制代碼。綜合①~③可知，狀態(tài)分配時要求滿足B和C、A和D、C和D相鄰。在進行狀態(tài)分配時，為了使狀態(tài)之間的相鄰關(guān)系一目了然，通常將卡諾圖作為狀態(tài)分配的工具。

假定狀態(tài)變量用y2y1表示，