邏輯電路設(shè)計

1、邏輯電路設(shè)計第1頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三 設(shè)計的一般過程： 1. 建立給定問題的邏輯描述 這一步的關(guān)鍵是弄清楚電路的輸入和輸出，建立輸入和輸出之間的邏輯關(guān)系，得到描述給定問題的邏輯表達(dá)式。求邏輯表達(dá)式有兩種常用方法，即真值表法和分析法。 2. 求出邏輯函數(shù)的最簡表達(dá)式 為了使邏輯電路中包含的邏輯門最少且連線最少，要對邏輯表達(dá)式進(jìn)行化簡，求出描述設(shè)計問題的最簡表達(dá)式 。 3. 選擇邏輯門類型并將邏輯函數(shù)變換成相應(yīng)形式 根據(jù)簡化后的邏輯表達(dá)式及問題的具體要求，選擇合適的邏輯門，并將邏輯表達(dá)式變換成與所選邏輯門對應(yīng)的形式。 4. 畫出邏輯電路圖 根據(jù)實(shí)際問題的難易程

2、度和設(shè)計者熟練程度，有時可跳過其中的某些步驟。設(shè)計過程可視具體情況靈活掌握。第2頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三1.2 設(shè)計舉例 解 分析: “多數(shù)表決電路”是按照少數(shù)服從多數(shù)的原則對某項(xiàng)決議進(jìn)行表決，確定是否通過。 令 邏輯變量A、B、C - 分別代表參加表決的3個成員，并約定邏輯變量取值為0表示反對，取值為1表示贊成；邏輯函數(shù) F- 表示表決結(jié)果。F取值為0表示決議被否定，F(xiàn)取值為1表示決議通過。按照少數(shù)服從多數(shù)的原則可知，函數(shù)和變量的關(guān)系是：當(dāng)3個變量A、B、C中有2個或2個以上取值為1時，函數(shù)F的值為1，其他情況下函數(shù)F的值為0。 例 設(shè)計一個三變量“多數(shù)表決

3、電路”。第3頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三 建立給定問題的邏輯描述 假定采用 “真值表法”，可作出真值表如下表所示。 0 0 0 00 0 1 00 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 1ABC F由真值表可寫出函數(shù)F的最小項(xiàng)表達(dá)式為 F(A,B,C) = m (3,5,6,7)第4頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三 求出邏輯函數(shù)的最簡表達(dá)式作出函數(shù)F(A,B,C) = m (3,5,6,7)的卡諾圖如下圖所示。用卡諾圖化簡后得到函數(shù)的最簡“與-或”表達(dá)式為 選擇邏輯門類型并進(jìn)行邏輯函數(shù)變換假定采用與

4、非門構(gòu)成實(shí)現(xiàn)給定功能的電路，則應(yīng)將上述表達(dá)式變換成“與非-與非”表達(dá)式。即第5頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三 畫出邏輯電路圖由函數(shù)的“與非-與非”表達(dá)式，可畫出實(shí)現(xiàn)給定功能的邏輯電路圖如下圖所示。本例采用的是“真值表法”，真值表法的優(yōu)點(diǎn)是規(guī)整、清晰；缺點(diǎn)是不方便，尤其當(dāng)變量較多時十分麻煩。第6頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三2 同步時序邏輯電路的設(shè)計 同步時序邏輯電路的設(shè)計是指根據(jù)特定的邏輯要求，設(shè)計出能實(shí)現(xiàn)其邏輯功能的時序邏輯電路。顯然， 設(shè)計是分析的逆過程，即： 同步時序邏輯電路設(shè)計追求的目標(biāo)是，使用盡可能少的觸發(fā)器和邏輯門實(shí)現(xiàn)預(yù)定的邏

5、輯要求！邏輯電路邏輯功能分析設(shè)計第7頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三2狀態(tài)化簡，求得最小化狀態(tài)表； 設(shè)計的一般步驟如下：1形成原始狀態(tài)圖和原始狀態(tài)表； 3狀態(tài)編碼，得到二進(jìn)制狀態(tài)表； 4選定觸發(fā)器的類型，并求出激勵函數(shù)和輸出函數(shù)最簡表達(dá)式； 5畫出邏輯電路圖。原始狀態(tài)圖是對設(shè)計要求最原始的抽象,根據(jù)邏輯問題的文字描述理解電路的輸入、輸出及狀態(tài)轉(zhuǎn)移關(guān)系，進(jì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ù)字標(biāo)注

6、的每個狀態(tài)用二進(jìn)制代碼表示，以便和電路中觸發(fā)器的狀態(tài)一致。根據(jù)選定的觸發(fā)器類型，列出激勵函數(shù)真值表，并求出激勵函數(shù)和輸出函數(shù)的最簡表達(dá)式。其中，激勵函數(shù)是由二進(jìn)制狀態(tài)表和觸發(fā)器激勵表共同確定的。 以上步驟是就一般設(shè)計問題而言的。實(shí)際中設(shè)計者可以根據(jù)具體問題靈活掌握。當(dāng)設(shè)計方案中包含有冗余狀態(tài)時，必須對冗余狀態(tài)的處理結(jié)果加以討論，以確保電路邏輯功能的可靠實(shí)現(xiàn)。 第8頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三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)表。如果原始

7、狀態(tài)圖不能正確地反映設(shè)計要求，則依此設(shè)計出來的電路必然是錯誤的。因此，建立正確的原始狀態(tài)圖和狀態(tài)表是同步時序電路設(shè)計中最關(guān)鍵的一步。 原始狀態(tài)圖的形成是建立在對設(shè)計要求充分理解的基礎(chǔ)之上的，設(shè)計者必須對給定的問題進(jìn)行認(rèn)真、全面地分析，弄清楚電路輸出和輸入的關(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)，

8、然后從初始狀態(tài)出發(fā)考慮在各種輸入作用下的狀態(tài)轉(zhuǎn)移和輸出響應(yīng)。 第9頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三三、 根據(jù)需要記憶的信息增加新的狀態(tài) 同步時序電路中狀態(tài)數(shù)目的多少取決于需要記憶和區(qū)分的信息量。一般來說，若在某個狀態(tài)下出現(xiàn)的輸入信號能用已有狀態(tài)表示，則應(yīng)轉(zhuǎn)向已有狀態(tài)。僅當(dāng)某個狀態(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型電

9、路中應(yīng)指明從每一個狀態(tài)出發(fā)，在不同輸入作用下的輸出值。 在描述一個邏輯問題的原始狀態(tài)圖和原始狀態(tài)表中，狀態(tài)數(shù)目不一定能達(dá)到最少，這一點(diǎn)無關(guān)緊要，因?yàn)榭梢詫λ龠M(jìn)行狀態(tài)化簡。設(shè)計者應(yīng)把清晰、正確地描述設(shè)計要求放在第一位 。其次，由于在開始時往往不知道描述一個給定的邏輯問題需要多少狀態(tài)，因此，在原始狀態(tài)圖和狀態(tài)表中一般用字母或數(shù)字表示狀態(tài)。 第10頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三 例 某序列檢測器有一個輸入端x和一個輸出端Z。輸入端 x 輸入一串隨機(jī)的二進(jìn)制代碼，當(dāng)輸入序列中出現(xiàn)“011”時，輸出Z產(chǎn)生一個1輸出，平時Z輸出0 。典型輸入、輸出序列如下。輸入x:10101

10、1100110輸出Z:000001000010試作出該序列檢測器的原始狀態(tài)圖和原始狀態(tài)表。解1. 假定用Mealy型同步時序邏輯電路實(shí)現(xiàn)該序列檢測器的邏輯功能.設(shè): 狀態(tài)A-電路的初始狀態(tài)；狀態(tài)B-表示收到了序列“011”中的第一個信號“0”；狀態(tài)C-表示收到了序列“011”中的前面兩位“01” ；狀態(tài)D-表示收到了序列“011”。第11頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三 當(dāng)電路處在狀態(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，因?yàn)檩斎?不是序列011的第一個信號，故不需要記住。該轉(zhuǎn)換關(guān)系如圖所示。 當(dāng)電路處于狀態(tài)B

11、輸入x為0時，盡管它不是序列011的第二個信號，但仍可作為序列中的第一個信號，故可令電路輸出為0，停留在狀態(tài)B；若輸入x為1，則意味著收到了序列011的前面兩位01，可令電路輸出0轉(zhuǎn)向狀態(tài)C。如圖所示。 第12頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三 當(dāng)電路處于狀態(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。如圖所示。 當(dāng)電路處于狀態(tài)D輸入x為0時，應(yīng)輸出0轉(zhuǎn)向狀態(tài)B；若輸入x為1，則應(yīng)輸出0，轉(zhuǎn)向狀

12、態(tài)A。 至此，得到了該序列檢測器完整的Mealy型狀態(tài)圖，如圖 (d)所示。相應(yīng)的原始狀態(tài)表如表所示。 第13頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三可畫出狀態(tài)圖如下：相應(yīng)狀態(tài)表如下：第14頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三2假定用Moore型同步時序邏輯電路實(shí)現(xiàn)該序列檢測器的邏輯功能.由于電路輸出完全取決于狀態(tài) ，而與輸入無直接聯(lián)系。在作狀態(tài)圖時，應(yīng)將輸出標(biāo)記在代表各狀態(tài)的圓圈內(nèi)。設(shè)電路初始狀態(tài)為A，并用狀態(tài)B、C、D分別表示收到了輸入x送來的0、01、011。顯然，根據(jù)題意，僅當(dāng)處于狀態(tài)D時電路輸出為1，其他狀態(tài)下輸出均為0。第15頁，共56頁，2

13、022年，5月20日，19點(diǎn)51分，星期三 當(dāng)從初始狀態(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)令其進(jìn)入狀態(tài)A。完整的Moore型原始狀態(tài)圖如圖右圖所示。 1第16頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三構(gòu)造Moo

14、re型原始狀態(tài)圖如下：相應(yīng)的原始狀態(tài)表如下表所示。1第17頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三例設(shè)計一個用于引爆控制的同步時序電路，該電路有一個輸入端x和一個輸出端Z。平時輸入x始終為0，一旦需要引爆，則從 x 連續(xù)輸入4個1信號(不被0間斷)，電路收到第四個1后在輸出端Z產(chǎn)生一個1信號點(diǎn)火引爆，該電路連同引爆裝置一起被炸毀。試建立該電路的Mealy型狀態(tài)圖和狀態(tài)表。（該問題的實(shí)際意義？-施工的安全性?。┙夥治?該電路實(shí)際上是一個用于特殊場所的“1111”序列檢測器。它與一般序列檢測器有兩點(diǎn)不同：1.輸入帶有約束條件，即一旦輸入出現(xiàn)1，則一定是不被0間斷的連續(xù)4個1；2.

15、收到4個1后，輸出產(chǎn)生的引爆信號使電路自毀，故此時不再存在次態(tài)問題。第18頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三設(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頁，2022年，5月20日，19點(diǎn)51分，星期三注意:在時序電路設(shè)計中，狀態(tài)化簡時利用不完全確定狀態(tài)表中不確定次態(tài)和不確定輸出的隨意性，通?？墒乖O(shè)計方案變得更簡單。這一點(diǎn)類似包含無關(guān)最小項(xiàng)的組合電路設(shè)計，只不過在處理

16、上要復(fù)雜一些。第20頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三2.2狀態(tài)化簡什么叫狀態(tài)化簡？ 所謂狀態(tài)化簡，是指采用某種化簡技術(shù)從原始狀態(tài)表中消去多余狀態(tài)，得到一個既能正確地描述給定的邏輯功能，又能使所包含的狀態(tài)數(shù)目達(dá)到最少的狀態(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 2 m-1方法：常用方法有觀察法、輸出分類法、隱含表法等。下面討論最常用的一種方法-隱含表法。在利用隱含表進(jìn)行化簡時，對于完全給定原始狀態(tài)表和不完全給定原始狀態(tài)表引用了不同的概念，并且

17、處理過程有所不同。 第21頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三一、 完全確定狀態(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 為等效對。請注意掌握三點(diǎn)：定義、判斷方法和性質(zhì)。第22頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三 判斷方法若狀態(tài)Si和Sj 是完全確定的原始狀態(tài)表中的兩個現(xiàn)態(tài)，則Si和Sj 等效的條件可歸納為在一位輸入的各種取值組合下滿足如下兩條：第一，輸出相同；

18、第二，次態(tài)屬于下列情況之一：a.次態(tài)相同；b.次態(tài)交錯或?yàn)楦髯缘默F(xiàn)態(tài)；c.次態(tài)循環(huán)或?yàn)榈刃?。?3頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三 性質(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)，進(jìn)而可知S1、S2、S3屬于同一等效類，記作 S1，S2，S3，即(S1，S2) ，(S2，S3) S1，S2，S3第24頁，共56頁，2022

19、年，5月20日，19點(diǎn)51分，星期三(3) 最大等效類所謂最大等效類，是指不被任何別的等效類所包含的等效類。注意： 這里所指的最大，并不是指包含的狀態(tài)最多，而是指它的獨(dú)立性，即使是一個狀態(tài)，只要它不被包含在別的等效類中，也是最大等效類。換而言之，如果一個等效類不是任何其他等效類的子集， 則該等效類稱為最大等效類。完全給定原始狀態(tài)表的化簡過程，就是尋找出表中的所有最大等效類，然后將每個最大等效類中的狀態(tài)合并為一個新的狀態(tài)，從而得到最小化狀態(tài)表。簡化后的狀態(tài)數(shù)等于最大等效類的個數(shù)！第25頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三2狀態(tài)化簡(1)隱含表化簡法的一般步驟 作隱含表隱含表

20、是一個直角三角形階梯網(wǎng)格，橫向和縱向格數(shù)相同，即等于原始狀態(tài)表中的狀態(tài)數(shù)減1。隱含表中的方格是用狀態(tài)名稱來標(biāo)注的，即橫向從左到右按原始狀態(tài)表中的狀態(tài)順序依次標(biāo)上第一個狀態(tài)至倒數(shù)第二個狀態(tài)的狀態(tài)名稱，而縱向自上到下依次標(biāo)上第二個狀態(tài)至最后一個狀態(tài)的名稱。表中每個方格代表一個狀態(tài)對。作隱含表 找等效對 求最大等效類 狀態(tài)合并作最簡狀態(tài)表12345第26頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三順序比較：按照隱含表中從上至下、從左至右的順序，對照原始狀態(tài)表依次對所有“狀態(tài)對”進(jìn)行逐一檢查和比較，并將檢查結(jié)果標(biāo)注在隱含表中的相應(yīng)方格內(nèi)。比較結(jié)果標(biāo)注如下：等效 - 在相應(yīng)方格內(nèi)填上“”；

21、不等效- 在相應(yīng)方格內(nèi)填上“”； 與其他狀態(tài)對相關(guān) - 在相應(yīng)方格內(nèi)填上相關(guān)的狀態(tài)對。關(guān)聯(lián)比較：指對那些在順序比較時尚未確定是否等效的狀態(tài)對作進(jìn)一步檢查。直到判別出狀態(tài)對等效或不等效為止。 尋找等效對 利用隱含表尋找狀態(tài)表中的全部等效對一般需要進(jìn)行兩輪比較，首先進(jìn)行順序比較，然后進(jìn)行關(guān)聯(lián)比較。 第27頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三 關(guān)聯(lián)比較時，首先要確定隱含表中待檢查的那些次態(tài)對是否等效，并由此確定原狀態(tài)對是否等效。如果隱含表中某方格內(nèi)有一個次態(tài)對不等效，則該方格所對應(yīng)的兩個狀態(tài)就不等效，并在相應(yīng)方格中增加標(biāo)志/。若方格內(nèi)的次態(tài)對均為等效狀態(tài)對，則與該方格對應(yīng)的狀態(tài)

22、為等效狀態(tài)，該方格不增加任何標(biāo)志。這種判別有時要反復(fù)多次，直到判別出狀態(tài)對等效或不等效為止。第28頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三求出最大等效類在找出原始狀態(tài)表中的所有等效對之后，可利用等效狀態(tài)的傳遞性，求出各最大等效類。狀態(tài)合并，作出最小化狀態(tài)表將每個最大等效類中的全部狀態(tài)合并為一個狀態(tài)，即可得到和原始狀態(tài)表等價的最小化狀態(tài)表。確定各最大等效類時應(yīng)注意兩點(diǎn)： 各最大等效類之間不應(yīng)出現(xiàn)相同狀態(tài)，因?yàn)槿魞蓚€等效類之間有相同狀態(tài)，則根據(jù)等效的傳遞性可令其合為一個等效類； 原始狀態(tài)表中的每一個狀態(tài)都必須屬于某一個最大等效類，換句話說，各最大等效類所包含的狀態(tài)之和必須覆蓋原始

23、狀態(tài)表中的全部狀態(tài)，否則，化簡后的狀態(tài)表不能描述原始狀態(tài)表所描述的功能。第29頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三(2)化簡舉例例化簡下表所示原始狀態(tài)表。解 作隱含表給定原始狀態(tài)表具有7個狀態(tài)，根據(jù)畫隱含表的規(guī)則，可畫出隱含表框架如下。第30頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三 尋找等效對根據(jù)等效狀態(tài)的判斷標(biāo)準(zhǔn)，依次檢查每個狀態(tài)對，可得到順序比較結(jié)果如圖 (a)所示。關(guān)聯(lián)比較的結(jié)果如圖 (b)所示。 圖(a) 圖(b)第31頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三由判斷結(jié)果可知，原始狀態(tài)表中的7個狀態(tài)共有四個等效對：(A，B)，(A

24、，E)， (B，E)，(C，F(xiàn))。第32頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三狀態(tài)合并，作出最小化狀態(tài)表令A(yù),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頁，2022年，5月20日，19點(diǎn)51分，星期三二、不完全確定狀態(tài)表的化簡 不完全確定狀態(tài)表中存在不確定的次態(tài)或輸出，這些不確定的狀態(tài)和輸出對于狀態(tài)化簡是有利的，關(guān)鍵是必須恰當(dāng)處理，以確?；喦昂鬆顟B(tài)表的邏輯功能不變。為此，引入出了

25、一個新的概念-相容狀態(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頁，2022年，5月20日，19點(diǎn)51分，星期三 相容狀態(tài)的判斷

26、假定狀態(tài)Si和Sj是不完全確定狀態(tài)表中的兩個現(xiàn)態(tài)，狀態(tài)Si和Sj相容的條件可歸納為在一位輸入的各種取值組合下滿足如下兩條。 第一，它們的輸出完全相同，或者其中的一個(或兩個)輸出不確定。 第二，它們的次態(tài)屬于下列情況之一： a.次態(tài)相同； b.次態(tài)交錯或?yàn)楦髯缘默F(xiàn)態(tài)； c.次態(tài)循環(huán)或?yàn)橄嗳輰Γ?d.其中的一個(或兩個)為不確定狀態(tài)。 注意! 相容狀態(tài)不具有傳遞性。這是因?yàn)榕袛鄡蓚€狀態(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=0 x=1ABCDA/0A/0A/0B

27、/1D/dD/0D/1d/1第35頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三(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頁，2022年，5月20日，19點(diǎn)51分，星期三2 .不完全確定狀態(tài)表的化簡 (1) 化簡步驟

28、 一般步驟如下： 作隱含表，尋找相容狀態(tài)對。 利用隱含表尋找相容對的過程與化簡完全確定狀態(tài)表時尋找等效對的過程是相同的，僅僅是狀態(tài)相容與狀態(tài)等效的標(biāo)準(zhǔn)有所不同而已。即在順序比較完成后，可利用已建立的隱含表繼續(xù)進(jìn)行關(guān)聯(lián)比較，直至判斷出所有狀態(tài)對相容或不相容為止，便可列出原始狀態(tài)表中的全部相容對。 利用狀態(tài)合并圖，求出最大相容類。 狀態(tài)合并圖：狀態(tài)合并圖是求最大相容類工具。它將狀態(tài)表的所有狀態(tài)以點(diǎn)的形式均勻地繪在圓周上，然后把所有相容對用線段連接起來。若某些頂點(diǎn)任意兩點(diǎn)之間都有連線，則其頂點(diǎn)狀態(tài)的集合構(gòu)成一個最大相容類。第37頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三 圖(a)、(

29、b)、(c)分別表示包含3個、4個和5個狀態(tài)的最大相容類狀態(tài)合并圖。 第38頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三 利用閉覆蓋表，求最小閉覆蓋。 最小閉覆蓋 - 是從最大相容類(或相容類)中選出一個相容類的集合，該相容類集合滿足以下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)鍵，就是尋找一個最小閉覆蓋。 閉覆

30、蓋表：所謂閉覆蓋表是指反映閉合和覆蓋這兩個性質(zhì)的表格，該表反映相容類集合對狀態(tài)的覆蓋情況和相容類的閉合關(guān)系。表的左邊自上而下列出所選相容類，表的中間覆蓋部分列出各相容類對原始狀態(tài)表中狀態(tài)的覆蓋情況，表的右邊閉合部分列出各相容類在一位輸入各種取值組合下的次態(tài)組合。（注意，這里所說的相容類包括最大相容類和它們的子類。） 作出最小化狀態(tài)表。 將最小閉覆蓋中的每個相容類用一個新的狀態(tài)符號表示，再將其代入原始狀態(tài)表中，即可得到與原始狀態(tài)表功能相同的最小化狀態(tài)表。第39頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三例 化簡下表所示的原始狀態(tài)表。 解 表中所示是一個具有5個狀態(tài)的原始狀態(tài)表，表中

31、存在不確定的次態(tài)和輸出，因此，屬于不完全確定狀態(tài)表。作隱含表，尋找相容狀態(tài)對。 作出隱含表，并根據(jù)相容狀態(tài)的判斷標(biāo)準(zhǔn)對各狀態(tài)對進(jìn)行順序比較和關(guān)聯(lián)比較后的結(jié)果如圖所示。第40頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三 作狀態(tài)合并圖，找出最大相容類。 根據(jù)相容狀態(tài)對可作出狀態(tài)合并圖如圖5.25所示。從狀態(tài)合并圖得到最大相容類為A,B,D、A,C,D、A,C,E。 由隱含表中的標(biāo)注可知，該狀態(tài)表中的相容狀態(tài)對有：(A,B)、(A，C)、(A，D)、(A，E)、(B，D)、(C，D)、(C，E)。第41頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三 作閉覆蓋表，求最小閉覆蓋

32、。 由得到的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頁，2022年，5月20日，19點(diǎn)51分，星期三 作出最小化狀態(tài)表。 假定最小閉覆蓋中的相容類A,B,D用狀態(tài)a表示，相容類A,C,E用狀態(tài)b表示，將其代入表所示原始狀態(tài)表中，可得到最小化狀態(tài)表

33、如表所示。 注意：在填寫最小化狀態(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=0 x=1ab/1a/0ba/0b/1 值得指出的是，在化簡不完全給定狀態(tài)表時，構(gòu)成最小閉覆蓋的相容類并不一定是最大相容類。例如，本例中選最大相容類A,B,D和相容類C,E作為最小閉覆蓋，可得到相同的結(jié)果。在某些情況下，如果僅僅從最大相容類中去選擇最小閉覆蓋，則合并后的狀態(tài)表不一定是最簡的。而如果在滿足最小覆蓋的前提下，在最大相容類和非

34、最大相容類之間作恰當(dāng)?shù)倪x擇，卻能得到最簡的狀態(tài)表。 第43頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三2.3 狀態(tài)編碼狀態(tài)編碼：是指給最小化狀態(tài)表中用字母或數(shù)字表示的狀態(tài)，指定一個二進(jìn)制代碼，形成二進(jìn)制狀態(tài)表。狀態(tài)編碼也稱狀態(tài)分配，或者狀態(tài)賦值。 一般情況下，采用的狀態(tài)編碼方案不同，所得到的輸出函數(shù)和激勵函數(shù)的表達(dá)式也不同，從而設(shè)計出來的電路其復(fù)雜程度也不同。 狀態(tài)編碼的任務(wù)是：確定狀態(tài)編碼的長度(即二進(jìn)制代碼的位數(shù)，或者說所需觸發(fā)器個數(shù))；尋找一種最佳的或接近最佳的狀態(tài)分配方案。以便使所設(shè)計的時序電路最簡單。第44頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三一、確

35、定二進(jìn)制代碼的位數(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)分配時,二進(jìn)制代碼的位數(shù)應(yīng)為 m = 3?；蛘哒f狀態(tài)變量個數(shù)為3。二、確定狀態(tài)分配方案狀態(tài)與代碼之間的對應(yīng)關(guān)系可以有許多種。一般說來，用m 位二進(jìn)制代碼的2m種組合來對N個狀態(tài)進(jìn)行分配時，可能出現(xiàn)的狀態(tài)分配方案數(shù)Ks為例如，當(dāng) N = 4, m= 2時，K S = 24。第45頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三例如，當(dāng) N = 4, m = 2 時，KS = 24。隨著狀態(tài)數(shù)目的增加，分配方案的數(shù)目急劇增加。

36、如何從眾多的分配方案中尋找出一種最佳方案，使所設(shè)計的電路最簡單，是一件十分困難的事情。而且，分配方案的好壞還與所采用的觸發(fā)器類型相關(guān)，即一種分配方案對某種觸發(fā)器是最佳的，但對另一種觸發(fā)器則不一定是最佳的。因此，狀態(tài)分配是一個比較復(fù)雜的問題。盡管做了大量研究工作，但從理論上講，尋求最佳狀態(tài)編碼的問題尚未完全解決。在實(shí)際工作中，工程技術(shù)人員通常按照一定的原則、憑借設(shè)計的經(jīng)驗(yàn)去尋找相對最佳的編碼方案。第46頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三一種常用方法稱為相鄰分配法。相鄰分配法的基本思想是：在選擇狀態(tài)編碼時，盡可能使激勵函數(shù)和輸出函數(shù)在卡諾圖上的“1”方格處在相鄰位置，從而有

37、利于激勵函數(shù)和輸出函數(shù)的化簡。第47頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三相鄰分配法的狀態(tài)編碼原則如下： 次態(tài)相同，現(xiàn)態(tài)相鄰。(即在相同輸入條件下，具有相同次態(tài)的現(xiàn)態(tài)應(yīng)盡可能分配相鄰的二進(jìn)制代碼；) 同一現(xiàn)態(tài)，次態(tài)相鄰。(即在相鄰輸入條件下，同一現(xiàn)態(tài)的次態(tài)應(yīng)盡可能分配相鄰的二進(jìn)制代碼；) 輸出相同，現(xiàn)態(tài)相鄰。(即在每一種輸入取值下均具有相同輸出的現(xiàn)態(tài)應(yīng)盡可能分配相鄰的二進(jìn)制代碼。)一般來說，上述3條原則在大多數(shù)情況下是有效的。但由于3條原則是分別實(shí)施的， 因此，對于某些狀態(tài)表常常出現(xiàn)不能同時滿足3條原則的情況。此時，可按從至的優(yōu)先順序考慮，即把原則放在首位。此外，從電路實(shí)際

38、工作狀態(tài)考慮，一般將初始狀態(tài)分配“0”狀態(tài)。第48頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三三、舉例例對如下狀態(tài)表進(jìn)行狀態(tài)編碼（設(shè)A為初始狀態(tài)）。 現(xiàn)態(tài) 次態(tài)/輸出 x=0 x=1 A C/1 B/0 B A/0 A/1 C A/1 D/1 D D/1 C/0解所示狀態(tài)表中，狀態(tài)數(shù)N = 4，故狀態(tài)編碼的長度應(yīng)為 m=2。即實(shí)現(xiàn)該狀態(tài)表的功能需要兩個觸發(fā)器。第49頁，共56頁，2022年，5月20日，19點(diǎn)51分，星期三根據(jù)相鄰法的編碼原則，4個狀態(tài)的相鄰關(guān)系如下：根據(jù)原則，狀態(tài)B和C應(yīng)分配相鄰的二進(jìn)制代碼；根據(jù)原則，狀態(tài)B和C、A和D、C和D應(yīng)分配相鄰的二進(jìn)制代碼；根據(jù)原則，狀態(tài)A和D應(yīng)分配相鄰的二進(jìn)制代碼。綜合可知，狀態(tài)分配時要求滿足B和C、A和D、C和D相鄰。在進(jìn)行狀