1、同步時(shí)序電路設(shè)計(jì)根底 同步時(shí)序邏輯電路的設(shè)計(jì)過程就是分析的逆過程，同步時(shí)序邏輯電路的設(shè)計(jì)過程就是分析的逆過程，也就是根據(jù)特定的邏輯要求，設(shè)計(jì)出能實(shí)現(xiàn)其邏輯也就是根據(jù)特定的邏輯要求，設(shè)計(jì)出能實(shí)現(xiàn)其邏輯功能的時(shí)序邏輯電路。設(shè)計(jì)追求的目的是運(yùn)用盡能功能的時(shí)序邏輯電路。設(shè)計(jì)追求的目的是運(yùn)用盡能夠少的觸發(fā)器和邏輯門實(shí)現(xiàn)給定的邏輯要求。夠少的觸發(fā)器和邏輯門實(shí)現(xiàn)給定的邏輯要求。 同步時(shí)序電路設(shè)計(jì)的普通步驟如下同步時(shí)序電路設(shè)計(jì)的普通步驟如下: (1) 建立原始形狀表。建立原始形狀表。 根據(jù)對(duì)時(shí)序電路的普通文字描畫闡明電路的輸根據(jù)對(duì)時(shí)序電路的普通文字描畫闡明電路的輸入、輸出及形狀的關(guān)系，進(jìn)而構(gòu)成形狀圖和形狀表。

2、入、輸出及形狀的關(guān)系，進(jìn)而構(gòu)成形狀圖和形狀表。由于開場得到的形狀圖和形狀表是對(duì)邏輯問題最原由于開場得到的形狀圖和形狀表是對(duì)邏輯問題最原始的籠統(tǒng)，其中能夠包含多余的形狀，所以稱為原始的籠統(tǒng)，其中能夠包含多余的形狀，所以稱為原始形狀圖和原始形狀表。始形狀圖和原始形狀表。(2) 形狀化簡。形狀化簡。 對(duì)原始形狀表進(jìn)展形狀化簡，消去多余的形狀，對(duì)原始形狀表進(jìn)展形狀化簡，消去多余的形狀，求得最小化形狀表。求得最小化形狀表。(3) 形狀分配形狀分配(或稱形狀編碼或稱形狀編碼)。 把形狀表中用字母或數(shù)字標(biāo)注的每個(gè)形狀用二把形狀表中用字母或數(shù)字標(biāo)注的每個(gè)形狀用二進(jìn)制代碼表示。進(jìn)制代碼表示。(4) 選擇觸發(fā)器類

3、型選擇觸發(fā)器類型(如如D或或JK觸發(fā)器觸發(fā)器)。 通常在開場設(shè)計(jì)時(shí)，曾經(jīng)初步選擇了觸發(fā)器。通常在開場設(shè)計(jì)時(shí)，曾經(jīng)初步選擇了觸發(fā)器。這一步是最后確定適宜的觸發(fā)器的類型。同一形這一步是最后確定適宜的觸發(fā)器的類型。同一形狀表選用不同類型的觸發(fā)器，得到的電路復(fù)雜程狀表選用不同類型的觸發(fā)器，得到的電路復(fù)雜程度也不同。度也不同。(5) 確定鼓勵(lì)函數(shù)和輸出函數(shù)表達(dá)式。確定鼓勵(lì)函數(shù)和輸出函數(shù)表達(dá)式。 根據(jù)選定的觸發(fā)器類型，列出鼓勵(lì)函數(shù)表，并根據(jù)選定的觸發(fā)器類型，列出鼓勵(lì)函數(shù)表，并求出鼓勵(lì)函數(shù)和輸出函數(shù)的最簡表達(dá)式。求出鼓勵(lì)函數(shù)和輸出函數(shù)的最簡表達(dá)式。(6) 畫出邏輯電路圖。畫出邏輯電路圖。 上述各步驟中，第一

4、步是最重要的。這一步要完成從文字描畫到邏輯符號(hào)的轉(zhuǎn)換，一旦完成了這步轉(zhuǎn)換，下面的步驟就可以用較為完善的設(shè)計(jì)方法進(jìn)展設(shè)計(jì)。 以上是普通同步時(shí)序電路的設(shè)計(jì)步驟。對(duì)于一些典型的或選用MSI芯片的電路設(shè)計(jì)，由于形狀數(shù)、形狀編碼和觸發(fā)器類型已給定，設(shè)計(jì)步驟可以簡化。實(shí)踐設(shè)計(jì)中可以根據(jù)詳細(xì)問題靈敏掌握。同步時(shí)序電路設(shè)計(jì)步驟建立原始形狀表 建立原始形狀表是同步時(shí)序電路設(shè)計(jì)中最重要的一建立原始形狀表是同步時(shí)序電路設(shè)計(jì)中最重要的一步。普通應(yīng)思索如下幾個(gè)方面：步。普通應(yīng)思索如下幾個(gè)方面： 1.確定電路模型。確定電路模型。 同步時(shí)序電路有同步時(shí)序電路有Mealy型和型和Moore型兩種模型，型兩種模型，不同模型構(gòu)造

5、對(duì)應(yīng)的電路構(gòu)造不同。不同模型構(gòu)造對(duì)應(yīng)的電路構(gòu)造不同。 2.設(shè)立初始形狀。設(shè)立初始形狀。 時(shí)序邏輯電路在輸入信號(hào)開場作用之前的形狀時(shí)序邏輯電路在輸入信號(hào)開場作用之前的形狀稱為初始形狀。稱為初始形狀。 3.根據(jù)需求記憶的信息添加新的形狀。根據(jù)需求記憶的信息添加新的形狀。 從初始形狀出發(fā)，逐個(gè)添加和完善，直到每個(gè)形從初始形狀出發(fā)，逐個(gè)添加和完善，直到每個(gè)形狀下各種輸入取值均已思索而沒有新的形狀出現(xiàn)為狀下各種輸入取值均已思索而沒有新的形狀出現(xiàn)為止。止。 4.確定各時(shí)辰電路的輸出。確定各時(shí)辰電路的輸出。例例1 1 例例1. 1. 某模某模5 5加加1 1和加和加2 2計(jì)數(shù)器有一個(gè)輸入計(jì)數(shù)器有一個(gè)輸入x

6、x和一個(gè)輸出和一個(gè)輸出Z Z。輸入。輸入x x為加為加1 1、加、加2 2控制信控制信號(hào)，當(dāng)號(hào)，當(dāng)x=0 x=0時(shí)，計(jì)數(shù)器在時(shí)鐘脈沖作用下時(shí)，計(jì)數(shù)器在時(shí)鐘脈沖作用下進(jìn)展加進(jìn)展加1 1計(jì)數(shù)；當(dāng)計(jì)數(shù)；當(dāng)x=1x=1時(shí)，計(jì)數(shù)器在時(shí)鐘時(shí)，計(jì)數(shù)器在時(shí)鐘脈沖作用下進(jìn)展加脈沖作用下進(jìn)展加2 2計(jì)數(shù)。當(dāng)電路計(jì)滿計(jì)數(shù)。當(dāng)電路計(jì)滿5 5個(gè)形狀后，輸出個(gè)形狀后，輸出Z Z產(chǎn)生一個(gè)產(chǎn)生一個(gè)1 1信號(hào)作為進(jìn)信號(hào)作為進(jìn)位輸出，平常位輸出，平常Z Z輸出為輸出為0 0。試建立該計(jì)數(shù)。試建立該計(jì)數(shù)器的器的MealyMealy型原始形狀圖和形狀表。型原始形狀圖和形狀表。 解解: : 該問題已指定電路模型為該問題已指定電路模型為

7、MealyMealy型，型，且輸入和形狀、輸出之間的關(guān)系也非常且輸入和形狀、輸出之間的關(guān)系也非常清楚，所以形狀圖的建立很容易。清楚，所以形狀圖的建立很容易。 假設(shè)模假設(shè)模5 5計(jì)數(shù)器的計(jì)數(shù)器的5 5個(gè)形狀分別用個(gè)形狀分別用A A、B B、C C、D D、E E表示，其中表示，其中A A為初始形狀。根據(jù)題意為初始形狀。根據(jù)題意可作出原始形狀圖如右圖所示，相應(yīng)的可作出原始形狀圖如右圖所示，相應(yīng)的原始形狀表如右表所示。原始形狀表如右表所示。 輸入輸入狀態(tài)狀態(tài)X=0 X=1AB/0C/0BC/0D/0CD/0E/0DE/0A/1EA/1B/0例例2 2例例2. 2. 某序列檢測器有一個(gè)輸入端某序列檢測

8、器有一個(gè)輸入端x x和一個(gè)輸出端和一個(gè)輸出端Z Z。輸入端。輸入端x x輸入一串隨機(jī)的二進(jìn)制代碼，當(dāng)輸入序列中出現(xiàn)輸入一串隨機(jī)的二進(jìn)制代碼，當(dāng)輸入序列中出現(xiàn)011011時(shí)，時(shí)，輸出輸出Z Z產(chǎn)生一個(gè)產(chǎn)生一個(gè)1 1輸出，平常輸出，平常Z Z輸出輸出0 0。典型輸入、輸出序列。典型輸入、輸出序列如下。如下。 輸入輸入x x： l 0 1 0 1 1 1 0 0 1 1 l 0 1 0 1 1 1 0 0 1 1 0 0 輸出輸出Z Z：0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 01 0 試作出該序列檢測器的原始形狀圖和原始形狀表。試作出該序列檢測器的原始形

9、狀圖和原始形狀表。 解解 假定用假定用MealyMealy型同步時(shí)序邏輯電路實(shí)現(xiàn)該序列檢測器型同步時(shí)序邏輯電路實(shí)現(xiàn)該序列檢測器的邏輯功能，那么原始形狀圖的建立過程如下。的邏輯功能，那么原始形狀圖的建立過程如下。 設(shè)電路的初始形狀為設(shè)電路的初始形狀為A A。當(dāng)處在初始形狀下電路輸入為。當(dāng)處在初始形狀下電路輸入為0 0時(shí)，輸出時(shí)，輸出Z Z為為0 0，由于輸入，由于輸入0 0是序列是序列011011中的第一個(gè)信號(hào)，中的第一個(gè)信號(hào)，所以應(yīng)該用一個(gè)形狀將它記住，假定用形狀所以應(yīng)該用一個(gè)形狀將它記住，假定用形狀B B記住收到了第記住收到了第一個(gè)一個(gè)0 0，那么在形狀，那么在形狀A(yù) A輸入輸入0 0時(shí)應(yīng)轉(zhuǎn)

10、向形狀時(shí)應(yīng)轉(zhuǎn)向形狀B B；當(dāng)處在初始形；當(dāng)處在初始形狀狀A(yù) A電路輸入為電路輸入為1 1時(shí)，輸出時(shí)，輸出Z Z為為0 0，由于輸入，由于輸入1 1不是序列不是序列011011的第一個(gè)信號(hào)，故不需求記住，可令其停留在形狀的第一個(gè)信號(hào)，故不需求記住，可令其停留在形狀A(yù) A。該轉(zhuǎn)。該轉(zhuǎn)換關(guān)系如圖換關(guān)系如圖(a)(a)所示。所示。 當(dāng)電路處于形狀當(dāng)電路處于形狀B時(shí)，假設(shè)輸入時(shí)，假設(shè)輸入x為為0，那么它不是序列，那么它不是序列“011的第二的第二個(gè)信號(hào)，但仍可作為序列中的第一個(gè)信號(hào)，但仍可作為序列中的第一個(gè)信號(hào)，故可令電路輸出為個(gè)信號(hào)，故可令電路輸出為0，停，停留在形狀留在形狀B；假設(shè)輸入；假設(shè)輸入x為

11、為1，那么，那么意味著收到了序列意味著收到了序列“011的前面兩的前面兩位位01，可用一個(gè)新的形狀，可用一個(gè)新的形狀C將它記將它記住，故此時(shí)電路輸出為住，故此時(shí)電路輸出為0，轉(zhuǎn)向形，轉(zhuǎn)向形狀狀C。部分形狀圖如圖。部分形狀圖如圖(b)所示。所示。 當(dāng)電路處于形狀當(dāng)電路處于形狀C時(shí)，假設(shè)輸入時(shí)，假設(shè)輸入x為為0，那么收到的延續(xù)，那么收到的延續(xù)3位代碼為位代碼為010，不是關(guān)懷的序列不是關(guān)懷的序列011，但此時(shí)輸入，但此時(shí)輸入的的0依然可以作為序列的第一個(gè)信依然可以作為序列的第一個(gè)信號(hào)，故此時(shí)應(yīng)輸出號(hào)，故此時(shí)應(yīng)輸出0，轉(zhuǎn)向形狀，轉(zhuǎn)向形狀B；假設(shè)輸入假設(shè)輸入x為為1，那么表示收到了序，那么表示收到了序

12、列列011，可用一個(gè)新的形狀，可用一個(gè)新的形狀D記住，記住，此時(shí)應(yīng)輸出此時(shí)應(yīng)輸出1，轉(zhuǎn)向形狀，轉(zhuǎn)向形狀D。部分形。部分形狀圖如圖狀圖如圖(c)所示。所示。當(dāng)電路處于形狀當(dāng)電路處于形狀D時(shí)，假設(shè)輸入時(shí)，假設(shè)輸入x為為0，那么應(yīng)輸出那么應(yīng)輸出0，轉(zhuǎn)向形狀，轉(zhuǎn)向形狀B；假設(shè)輸入；假設(shè)輸入x為為l，那么應(yīng)輸出那么應(yīng)輸出0，轉(zhuǎn)向形狀，轉(zhuǎn)向形狀A(yù)。至此，得到。至此，得到了該序列檢測器完好的了該序列檢測器完好的Mealy型形狀圖，型形狀圖，如圖如圖(d)所示。相應(yīng)的原始形狀表如右所所示。相應(yīng)的原始形狀表如右所示。示。 從上述建立原始形狀圖的過程可知，實(shí)從上述建立原始形狀圖的過程可知，實(shí)現(xiàn)一個(gè)序列檢測器的功能

13、所需求的形狀數(shù)現(xiàn)一個(gè)序列檢測器的功能所需求的形狀數(shù)與要識(shí)別的序列長度相關(guān)，序列越長，需與要識(shí)別的序列長度相關(guān)，序列越長，需求記憶的代碼位數(shù)越多，形狀數(shù)也就越多。求記憶的代碼位數(shù)越多，形狀數(shù)也就越多。實(shí)踐上在建立序列檢測器的原始形狀圖時(shí)，實(shí)踐上在建立序列檢測器的原始形狀圖時(shí)，可以先根據(jù)序列中要記憶的信息設(shè)立好每可以先根據(jù)序列中要記憶的信息設(shè)立好每一個(gè)形狀，并建立起當(dāng)輸入信號(hào)正好按指一個(gè)形狀，并建立起當(dāng)輸入信號(hào)正好按指定序列變化時(shí)各形狀的相互關(guān)系；然后再定序列變化時(shí)各形狀的相互關(guān)系；然后再確定每個(gè)形狀下輸入出現(xiàn)不同取值時(shí)的輸確定每個(gè)形狀下輸入出現(xiàn)不同取值時(shí)的輸出和形狀轉(zhuǎn)移方向，即可得到一個(gè)完好的出

14、和形狀轉(zhuǎn)移方向，即可得到一個(gè)完好的形狀圖。形狀圖。 輸入輸入狀態(tài)狀態(tài)X=0 X=1AB/0 A/0BB/0 C/0CB/0 D/1DB/0 A/0例例3 3例例3.3.假設(shè)用假設(shè)用MooreMoore型同步時(shí)序電路實(shí)現(xiàn)上例型同步時(shí)序電路實(shí)現(xiàn)上例“011011序列檢測器，那么電路輸出完全取決序列檢測器，那么電路輸出完全取決于形狀，而與輸入無直接關(guān)系。在作形狀圖于形狀，而與輸入無直接關(guān)系。在作形狀圖時(shí)，應(yīng)將輸出標(biāo)志在代表各形狀的圓圈內(nèi)。時(shí)，應(yīng)將輸出標(biāo)志在代表各形狀的圓圈內(nèi)。 假定電路初始形狀為假定電路初始形狀為A A，并用形狀，并用形狀B B、C C、D D分別表示收到了輸入分別表示收到了輸入X

15、X送來的送來的0 0、0101、011011。顯然，根據(jù)題意，僅當(dāng)處于形狀顯然，根據(jù)題意，僅當(dāng)處于形狀D D時(shí)電路輸出時(shí)電路輸出為為1 1，其他形狀下輸出均為，其他形狀下輸出均為0 0。當(dāng)形狀從初始。當(dāng)形狀從初始開場，輸入端開場，輸入端X X正好依次輸入正好依次輸入0 0、1 1、1 1時(shí)，那時(shí)，那么形狀從么形狀從A A轉(zhuǎn)到轉(zhuǎn)到B B、B B轉(zhuǎn)到轉(zhuǎn)到C C、C C轉(zhuǎn)到轉(zhuǎn)到D D。據(jù)此可。據(jù)此可得到部分形狀圖如右圖得到部分形狀圖如右圖(a)(a)所示。然后，思索所示。然后，思索到到A A形狀下輸入為形狀下輸入為1 1時(shí)，它不是指定序列中的時(shí)，它不是指定序列中的第一位信號(hào)，不用記憶，可令形狀停留在

16、第一位信號(hào)，不用記憶，可令形狀停留在A A；B B形狀下輸入為形狀下輸入為0 0時(shí)，它不是指定序列的第二時(shí)，它不是指定序列的第二位，但可作為指定序列的第一位，故可令其位，但可作為指定序列的第一位，故可令其停留在停留在B B；C C形狀下輸入為形狀下輸入為0 0時(shí)，不是指定序列時(shí)，不是指定序列的第三位的第三位, ,但同樣可作為第一位但同樣可作為第一位, ,故令其轉(zhuǎn)向故令其轉(zhuǎn)向形狀形狀B B；D D形狀下輸入形狀下輸入0 0時(shí)，同樣應(yīng)轉(zhuǎn)向時(shí)，同樣應(yīng)轉(zhuǎn)向B B，而，而輸入為輸入為1 1時(shí)，那么應(yīng)令其進(jìn)入形狀時(shí)，那么應(yīng)令其進(jìn)入形狀A(yù) A。得到完。得到完好的好的MooreMoore型原始形狀圖如右圖型原

17、始形狀圖如右圖(b)(b)所示。所示。1000Z輸出輸出ABDDBCCBBABAX=1X=0現(xiàn)態(tài)現(xiàn)態(tài)次態(tài)次態(tài)例例4 例例4. 某同步時(shí)序電路用于檢測串行輸入的某同步時(shí)序電路用于檢測串行輸入的8421碼，其輸入的碼，其輸入的順序是先低位后高位，當(dāng)出現(xiàn)非法數(shù)字順序是先低位后高位，當(dāng)出現(xiàn)非法數(shù)字(即輸入即輸入1010，1011，1100，1101，1110，1111)時(shí)，電路的輸出為時(shí)，電路的輸出為1。試作出該時(shí)序。試作出該時(shí)序電路的電路的Mealy型模型形狀圖和形狀表。型模型形狀圖和形狀表。 解：根據(jù)題意，電路有一個(gè)輸入和一個(gè)輸出。設(shè)輸入解：根據(jù)題意，電路有一個(gè)輸入和一個(gè)輸出。設(shè)輸入x用來接用來接

18、納納8421碼，輸出碼，輸出Z用來指示在輸入端出現(xiàn)了非法數(shù)字。用來指示在輸入端出現(xiàn)了非法數(shù)字。 假定起始形狀為假定起始形狀為A，當(dāng)?shù)谝晃惠斎氪a到來時(shí)，有兩，當(dāng)?shù)谝晃惠斎氪a到來時(shí)，有兩種能夠的情況，即種能夠的情況，即1和和0，故需用兩個(gè)形狀，故需用兩個(gè)形狀B和和C來表示這兩種來表示這兩種能夠；從形狀能夠；從形狀B和和C出發(fā)，當(dāng)出發(fā)，當(dāng)x輸入的第二位代碼到來時(shí)，又輸入的第二位代碼到來時(shí)，又各有兩種能夠的情況，分別用形狀各有兩種能夠的情況，分別用形狀D，E，F(xiàn)，G表示；從形表示；從形狀狀D，E，F(xiàn)，G出發(fā)，當(dāng)出發(fā)，當(dāng)x輸入的第三位代碼到來時(shí)，同樣，輸入的第三位代碼到來時(shí)，同樣，各有兩種能夠，共有

19、各有兩種能夠，共有8種不同的情況，分別用形狀種不同的情況，分別用形狀H，I，J，K，L，M，N，P表示。當(dāng)表示。當(dāng)x輸入的第四位代碼到來時(shí)，即一輸入的第四位代碼到來時(shí)，即一組組8421碼全部被接納。對(duì)輸入的碼全部被接納。對(duì)輸入的8421碼進(jìn)展判別，假設(shè)出現(xiàn)碼進(jìn)展判別，假設(shè)出現(xiàn)非法數(shù)字，電路的輸出為非法數(shù)字，電路的輸出為1，否那么為，否那么為0，并前往到起始形狀，并前往到起始形狀A(yù)。根據(jù)以上分析，可以得到如下的形狀圖：。根據(jù)以上分析，可以得到如下的形狀圖： 從形狀圖可以看出，由于串行輸入是先低位后高位，從形狀圖可以看出，由于串行輸入是先低位后高位，因此，判別輸入的因此，判別輸入的8421碼能否為

20、非法數(shù)字時(shí)，應(yīng)從碼能否為非法數(shù)字時(shí)，應(yīng)從低位到高位查看各位輸入值。待低位到高位查看各位輸入值。待4位代碼檢測完后，位代碼檢測完后，那么應(yīng)轉(zhuǎn)向初始形狀那么應(yīng)轉(zhuǎn)向初始形狀A(yù)，以便檢查下一組代碼。，以便檢查下一組代碼。ABDCEFGHIJKLMNP0/01/00/00/00/00/00/00/00/00/00/00/00/00/00/00/01/01/01/01/01/01/01/01/01/11/11/11/11/11/1 將形狀圖轉(zhuǎn)換成形狀表，那么如下表所示：將形狀圖轉(zhuǎn)換成形狀表，那么如下表所示：現(xiàn)態(tài)現(xiàn)態(tài) 次態(tài)次態(tài)/輸出輸出 現(xiàn)態(tài)現(xiàn)態(tài) 次態(tài)次態(tài)/輸出輸出 x=0 x=1 x=0 x=1 A B/

21、0 C/0 B D/0 E/0 I A/0 A/1 C F/0 G/0 J A/0 A/1 D H/0 I/0 K A/0 A/1 E J/0 K/0 L A/0 A/0 F L/0 M/0 M A/0 A/1 G N/0 P/0 N A/0 A/1 H A/0 A/0 P A/0 A/1 上述各例所建立的原始形狀圖和原始形狀表上述各例所建立的原始形狀圖和原始形狀表中，對(duì)于所設(shè)立的每一個(gè)形狀，在不同輸入取值中，對(duì)于所設(shè)立的每一個(gè)形狀，在不同輸入取值下都有確定的次態(tài)和輸出。通常將這類形狀圖和下都有確定的次態(tài)和輸出。通常將這類形狀圖和形狀表稱為完全確定形狀圖和形狀表，由它們所形狀表稱為完全確定形狀

22、圖和形狀表，由它們所描畫的電路稱為完全確定電路。實(shí)踐運(yùn)用中，根描畫的電路稱為完全確定電路。實(shí)踐運(yùn)用中，根據(jù)某些設(shè)計(jì)要求建立的原始形狀圖和原始形狀表據(jù)某些設(shè)計(jì)要求建立的原始形狀圖和原始形狀表中往往存在不確定的次態(tài)或輸出，即存在某些形中往往存在不確定的次態(tài)或輸出，即存在某些形狀，它們?cè)谀承┹斎肴≈迪碌拇螒B(tài)或輸出是隨意狀，它們?cè)谀承┹斎肴≈迪碌拇螒B(tài)或輸出是隨意的。這種形狀圖和形狀表被稱為不完全確定形狀的。這種形狀圖和形狀表被稱為不完全確定形狀圖和形狀表，所描畫的電路稱為不完全確定電路。圖和形狀表，所描畫的電路稱為不完全確定電路。例例5 5 例例5. 5. 設(shè)計(jì)一個(gè)用于引爆控制的同步時(shí)序電路，該電設(shè)計(jì)

23、一個(gè)用于引爆控制的同步時(shí)序電路，該電路有一個(gè)輸入端路有一個(gè)輸入端x x和一個(gè)輸出端和一個(gè)輸出端Z Z。平常輸入。平常輸入x x一直為一直為0 0，一旦需求引爆，那么從，一旦需求引爆，那么從x x延續(xù)輸入延續(xù)輸入4 4個(gè)個(gè)1 1信號(hào)信號(hào)( (不被不被0 0延續(xù)延續(xù)) )，電路收到第四個(gè)，電路收到第四個(gè)1 1后在輸出端后在輸出端Z Z產(chǎn)生一個(gè)產(chǎn)生一個(gè)1 1信信號(hào)點(diǎn)火引爆，該電路連同引爆安裝一同被炸毀。試號(hào)點(diǎn)火引爆，該電路連同引爆安裝一同被炸毀。試建立該電路的建立該電路的MealyMealy型形狀圖和形狀表。型形狀圖和形狀表。 解解: : 該電路實(shí)踐上是一個(gè)用于特殊場所的該電路實(shí)踐上是一個(gè)用于特殊場

24、所的“11111111序列檢測器。它與普通序列檢測器有兩點(diǎn)不同。序列檢測器。它與普通序列檢測器有兩點(diǎn)不同。一是輸入帶有約束條件，即一旦輸入出現(xiàn)一是輸入帶有約束條件，即一旦輸入出現(xiàn)1 1，那么一，那么一定是不被定是不被0 0延續(xù)的延續(xù)延續(xù)的延續(xù)4 4個(gè)個(gè)l l；二是收到；二是收到4 4個(gè)個(gè)1 1后產(chǎn)生的后產(chǎn)生的引爆信號(hào)，同時(shí)使電路自毀，故此時(shí)不再存在次態(tài)引爆信號(hào)，同時(shí)使電路自毀，故此時(shí)不再存在次態(tài)問題。問題。 設(shè)形狀設(shè)形狀A(yù)表示電路初始形狀，形狀表示電路初始形狀，形狀B表示收到了表示收到了第一個(gè)第一個(gè)1輸入，形狀輸入，形狀C表示收到了延續(xù)表示收到了延續(xù)2個(gè)個(gè)1輸入，形輸入，形狀狀D表示收到了延續(xù)

25、表示收到了延續(xù)3個(gè)個(gè)1輸入。根據(jù)題意，輸入。根據(jù)題意，A形狀下形狀下x為為1時(shí)，輸出為時(shí)，輸出為0轉(zhuǎn)向形狀轉(zhuǎn)向形狀B；B形狀下形狀下x為為1時(shí)，輸出時(shí)，輸出為為0轉(zhuǎn)向形狀轉(zhuǎn)向形狀C；C形狀下形狀下x為為1時(shí)，輸出為時(shí)，輸出為0轉(zhuǎn)向形狀轉(zhuǎn)向形狀D；而；而D形狀下形狀下x為為1時(shí)，輸出為時(shí)，輸出為1，次態(tài)隨意，次態(tài)隨意(實(shí)踐上實(shí)踐上已不存在次態(tài)已不存在次態(tài))。其次，。其次，A形狀下形狀下x為為0時(shí)，可令輸出時(shí)，可令輸出為為0，停留在形狀，停留在形狀A(yù)，而，而B、C、D這這3個(gè)形狀下由于個(gè)形狀下由于x不會(huì)為不會(huì)為0，故可令輸出和次態(tài)作為無關(guān)處置。據(jù)此，故可令輸出和次態(tài)作為無關(guān)處置。據(jù)此，可得到該電路

26、的可得到該電路的Mealy型原始形狀圖如以下圖所示，型原始形狀圖如以下圖所示，原始形狀表如下表所示。圖表中用原始形狀表如下表所示。圖表中用“d表示不確定表示不確定次態(tài)或不確定輸出。次態(tài)或不確定輸出。 在時(shí)序電路設(shè)計(jì)中，利用不完全確定形狀表中不在時(shí)序電路設(shè)計(jì)中，利用不完全確定形狀表中不確定次態(tài)和不確定輸出的隨意性，通常可使設(shè)計(jì)確定次態(tài)和不確定輸出的隨意性，通常可使設(shè)計(jì)方案變得更簡單。這一點(diǎn)和組合電路設(shè)計(jì)中利用方案變得更簡單。這一點(diǎn)和組合電路設(shè)計(jì)中利用函數(shù)包含的無關(guān)最小項(xiàng)簡化電路構(gòu)造是類似的，函數(shù)包含的無關(guān)最小項(xiàng)簡化電路構(gòu)造是類似的，只不過在處置上要復(fù)雜一些。只不過在處置上要復(fù)雜一些。 輸入輸入狀

27、態(tài)狀態(tài)X=0 X=1AA/0B/0Bd/dC/0Cd/dD/0Dd/dd/1形狀化簡形狀化簡 在建立原始形狀圖和原始形狀表時(shí)，主要思索的是如何明晰、在建立原始形狀圖和原始形狀表時(shí)，主要思索的是如何明晰、正確地反映設(shè)計(jì)要求，而沒有刻意追求如何使圖、表中包含正確地反映設(shè)計(jì)要求，而沒有刻意追求如何使圖、表中包含的形狀數(shù)目到達(dá)最少。因此，在構(gòu)造的形狀圖和形狀表中往的形狀數(shù)目到達(dá)最少。因此，在構(gòu)造的形狀圖和形狀表中往往存在多余形狀。但在設(shè)計(jì)詳細(xì)電路時(shí)，形狀數(shù)目的多少將往存在多余形狀。但在設(shè)計(jì)詳細(xì)電路時(shí)，形狀數(shù)目的多少將直接決議電路中所需觸發(fā)器數(shù)目的多少。所以，為了降低電直接決議電路中所需觸發(fā)器數(shù)目的多少

28、。所以，為了降低電路的復(fù)雜性和電路本錢，應(yīng)盡能夠地使描畫設(shè)計(jì)要求的形狀路的復(fù)雜性和電路本錢，應(yīng)盡能夠地使描畫設(shè)計(jì)要求的形狀表中包含的形狀數(shù)到達(dá)最少。表中包含的形狀數(shù)到達(dá)最少。 所謂形狀化簡，就是采用某種化簡技術(shù)從原始形狀表中消去所謂形狀化簡，就是采用某種化簡技術(shù)從原始形狀表中消去多余形狀，得到一個(gè)既能正確地描畫給定的邏輯功能，又能多余形狀，得到一個(gè)既能正確地描畫給定的邏輯功能，又能使所包含的形狀數(shù)目到達(dá)最少的形狀表，通常稱這種形狀表使所包含的形狀數(shù)目到達(dá)最少的形狀表，通常稱這種形狀表為最小化形狀表。為最小化形狀表。 形狀化簡的方法很多，最常用的一種方法是隱含表法。在利形狀化簡的方法很多，最常用

29、的一種方法是隱含表法。在利用隱含表進(jìn)展化簡時(shí)，對(duì)于完全給定原始形狀表和不完全給用隱含表進(jìn)展化簡時(shí)，對(duì)于完全給定原始形狀表和不完全給定原始形狀表援用了不同的概念，并且處置過程有所不同。定原始形狀表援用了不同的概念，并且處置過程有所不同。下面分別進(jìn)展討論。下面分別進(jìn)展討論。1完全確定形狀表的化簡完全確定形狀表的化簡完全確定形狀表的化簡是建立在形狀等效這個(gè)概念的完全確定形狀表的化簡是建立在形狀等效這個(gè)概念的根底之上的。為此，在討論化簡方法之前，先引見化根底之上的。為此，在討論化簡方法之前，先引見化簡時(shí)涉及的幾個(gè)概念。簡時(shí)涉及的幾個(gè)概念。(1)等效形狀和等效類等效形狀和等效類等效形狀：假設(shè)形狀等效形狀

30、：假設(shè)形狀Si和和Sj是完全確定形狀表中的是完全確定形狀表中的兩個(gè)形狀，假設(shè)對(duì)于一切能夠的輸入序列，分別從兩個(gè)形狀，假設(shè)對(duì)于一切能夠的輸入序列，分別從Si和和Sj出發(fā)，所得到的輸出呼應(yīng)序列完全一樣，那么形出發(fā)，所得到的輸出呼應(yīng)序列完全一樣，那么形狀狀Si和和Sj是等效的，記作是等效的，記作(Si，Sj)，或者說，形狀，或者說，形狀Si和和Sj是等效對(duì)。是等效對(duì)。 這里所說的一切能夠的輸入序列，是指輸入序列這里所說的一切能夠的輸入序列，是指輸入序列的長度和構(gòu)造是恣意的，它包含無窮多位，且有無窮的長度和構(gòu)造是恣意的，它包含無窮多位，且有無窮多種組合。假設(shè)企圖經(jīng)過檢測一切能夠輸入序列下的多種組合。假

31、設(shè)企圖經(jīng)過檢測一切能夠輸入序列下的輸出來確定兩個(gè)形狀能否等效，顯然是不現(xiàn)實(shí)的。現(xiàn)輸出來確定兩個(gè)形狀能否等效，顯然是不現(xiàn)實(shí)的。現(xiàn)實(shí)上，由于在構(gòu)成原始形狀表時(shí)，對(duì)每個(gè)形狀均思索實(shí)上，由于在構(gòu)成原始形狀表時(shí)，對(duì)每個(gè)形狀均思索了在一位輸入各種取值下的次態(tài)和輸出，因此，從整了在一位輸入各種取值下的次態(tài)和輸出，因此，從整體上講，原始形狀表曾經(jīng)反映了各形狀在恣意輸入序體上講，原始形狀表曾經(jīng)反映了各形狀在恣意輸入序列下的輸出。從而，可以根據(jù)形狀表上所列出的一位列下的輸出。從而，可以根據(jù)形狀表上所列出的一位輸入各種組合下的次態(tài)和輸出來判別某兩個(gè)形狀能否輸入各種組合下的次態(tài)和輸出來判別某兩個(gè)形狀能否等等效。假定效

32、。假定Si和和Sj是完全確定的原始形狀表中的兩個(gè)是完全確定的原始形狀表中的兩個(gè)現(xiàn)態(tài)，那么現(xiàn)態(tài)，那么Si和和Sj等效的條件可歸納為在一位輸入等效的條件可歸納為在一位輸入的各種取值組合下滿足如下兩條。的各種取值組合下滿足如下兩條。 第一，它們的輸出一樣。第一，它們的輸出一樣。 第二，它們的次態(tài)屬于以下情況之一：第二，它們的次態(tài)屬于以下情況之一： a次態(tài)一樣；次態(tài)一樣； b次態(tài)交錯(cuò)或?yàn)楦髯缘默F(xiàn)態(tài)；次態(tài)交錯(cuò)或?yàn)楦髯缘默F(xiàn)態(tài)； c次態(tài)循環(huán)或?yàn)榈刃?duì)。次態(tài)循環(huán)或?yàn)榈刃?duì)。 這里，情況這里，情況b中所謂的次態(tài)交錯(cuò)，是指在某種輸中所謂的次態(tài)交錯(cuò)，是指在某種輸入取值下，入取值下，Si的次態(tài)為的次態(tài)為Sj，而，而S

33、j的次態(tài)為的次態(tài)為Si。而所。而所謂次態(tài)為各自的現(xiàn)態(tài)，即謂次態(tài)為各自的現(xiàn)態(tài)，即Si的次態(tài)仍為的次態(tài)仍為Si，Sj的次的次態(tài)仍為態(tài)仍為Sj。情況。情況c中的次態(tài)循環(huán)是指確定兩個(gè)形狀中的次態(tài)循環(huán)是指確定兩個(gè)形狀能否等效的關(guān)聯(lián)形狀對(duì)之間，其依賴關(guān)系構(gòu)成閉環(huán)。能否等效的關(guān)聯(lián)形狀對(duì)之間，其依賴關(guān)系構(gòu)成閉環(huán)。而兩個(gè)次態(tài)為形狀對(duì)循環(huán)體中的一個(gè)形狀對(duì)。而兩個(gè)次態(tài)為形狀對(duì)循環(huán)體中的一個(gè)形狀對(duì)。 例如，例如，S1和和S2在某種輸入取值下的次態(tài)是在某種輸入取值下的次態(tài)是S3和和S4，而，而S3和和S4在該種輸入取值下的次態(tài)又是在該種輸入取值下的次態(tài)又是S1和和S2，那么稱這種情況，那么稱這種情況為次態(tài)循環(huán)。而次態(tài)為

34、等效對(duì)是指為次態(tài)循環(huán)。而次態(tài)為等效對(duì)是指Si和和Sj的次態(tài)已被確以的次態(tài)已被確以為等效形狀。例如，為等效形狀。例如，S1的次態(tài)是的次態(tài)是S3，S2的次態(tài)是的次態(tài)是S4，雖然，雖然S3和和S4既不一樣，也不交錯(cuò)或循環(huán)，但假設(shè)以既不一樣，也不交錯(cuò)或循環(huán)，但假設(shè)以S3和和S4作為作為現(xiàn)態(tài)，在一位輸入的各種取值下，其輸出一樣且次態(tài)一樣現(xiàn)態(tài)，在一位輸入的各種取值下，其輸出一樣且次態(tài)一樣或交錯(cuò)或循環(huán)，即或交錯(cuò)或循環(huán)，即S3和和S4等效，那么，等效，那么，S1和和S2是等效的。是等效的。 等效形狀具有傳送性。即假設(shè)等效形狀具有傳送性。即假設(shè)S1和和S2等效，等效，S2和和S3等效，那么，一定有等效，那么，一

35、定有S1和和S3等效。記作等效。記作 (S1，S2)，(S2，S3)(S1，S3) 等效類：所謂等效類是指由假設(shè)干彼此等效的形狀構(gòu)成等效類：所謂等效類是指由假設(shè)干彼此等效的形狀構(gòu)成的集合。在一個(gè)等效類中的恣意兩個(gè)形狀都是等效的。根的集合。在一個(gè)等效類中的恣意兩個(gè)形狀都是等效的。根據(jù)等效形狀的傳送性，可以從等效對(duì)中尋覓出等效類。例據(jù)等效形狀的傳送性，可以從等效對(duì)中尋覓出等效類。例如，由如，由(S1，S2)和和(S2，S3)可以推出可以推出(S1，S3)，進(jìn)而可知，進(jìn)而可知S1、S2、S3屬于同一等效類，記作屬于同一等效類，記作 (S1，S2)，(S2，S3)S1，S2，S3 在等效關(guān)系中，等效對(duì)

36、是狹義的概念，它是對(duì)兩個(gè)形狀而言的，等效類卻是廣義的概念，兩個(gè)形狀或多個(gè)形狀均可以組成一個(gè)等效類，甚至一個(gè)形狀也可以稱為等效類，由于任何形狀和它的本身必然是等效的。最大等效類：所謂最大等效類，是指不被任何別的等效類所包含的等效類。這里所指的最大，并不是指包含的形狀最多，而是指它的獨(dú)立性，即使是一個(gè)形狀，只需它不被包含在別的等效類中，也是最大等效類。換句話說，假設(shè)一個(gè)等效類不是任何其他等效類的子集，那么該等效類稱為最大等效類。 利用上述判別形狀等效的條件及形狀等效的性質(zhì)，就可以進(jìn)展形狀簡化。 原始形狀表的化簡過程，就是尋覓最大等效類，然后將每個(gè)最大等效類中的一切形狀合并為一個(gè)新的形狀，從而得到最

37、小化形狀表的過程。簡化后的形狀數(shù)等于最大等效類的個(gè)數(shù)。(2)用隱含表進(jìn)展形狀化簡用隱含表進(jìn)展形狀化簡 用隱含表法進(jìn)展形狀化簡的普通步驟如下。用隱含表法進(jìn)展形狀化簡的普通步驟如下。作隱含表。隱含表是一個(gè)直角三角形階梯網(wǎng)格，橫向作隱含表。隱含表是一個(gè)直角三角形階梯網(wǎng)格，橫向和縱向格數(shù)一樣，等于原始形狀表中的形狀數(shù)減和縱向格數(shù)一樣，等于原始形狀表中的形狀數(shù)減1。隱。隱含表中的方格是用形狀稱號(hào)來標(biāo)注的，即橫向從左到含表中的方格是用形狀稱號(hào)來標(biāo)注的，即橫向從左到右按原始形狀表中的形狀順序依次標(biāo)上第一個(gè)形狀至右按原始形狀表中的形狀順序依次標(biāo)上第一個(gè)形狀至倒數(shù)第二個(gè)形狀的形狀稱號(hào)，而縱向自上到下依次標(biāo)倒數(shù)第

38、二個(gè)形狀的形狀稱號(hào)，而縱向自上到下依次標(biāo)上第二個(gè)形狀至最后一個(gè)形狀的稱號(hào)。表中每個(gè)方格上第二個(gè)形狀至最后一個(gè)形狀的稱號(hào)。表中每個(gè)方格代表一個(gè)形狀對(duì)。代表一個(gè)形狀對(duì)。尋覓等效對(duì)。利用隱含表尋覓形狀表中的全部等效對(duì)尋覓等效對(duì)。利用隱含表尋覓形狀表中的全部等效對(duì)普通要進(jìn)展兩輪比較，首先進(jìn)展順序比較，然后進(jìn)展普通要進(jìn)展兩輪比較，首先進(jìn)展順序比較，然后進(jìn)展關(guān)聯(lián)比較。關(guān)聯(lián)比較。 所謂順序比較是按照隱含表中從上至下、從左至右的所謂順序比較是按照隱含表中從上至下、從左至右的順序，對(duì)照原始形狀表依次對(duì)一切形狀對(duì)進(jìn)展逐一檢順序，對(duì)照原始形狀表依次對(duì)一切形狀對(duì)進(jìn)展逐一檢查和比較，并將檢查結(jié)果以簡單明了的方式標(biāo)注在隱

39、查和比較，并將檢查結(jié)果以簡單明了的方式標(biāo)注在隱含表中的相應(yīng)方格內(nèi)。每個(gè)形狀對(duì)的比較結(jié)果有含表中的相應(yīng)方格內(nèi)。每個(gè)形狀對(duì)的比較結(jié)果有3種情種情況，一是明確是等效的，在相應(yīng)方格內(nèi)填上況，一是明確是等效的，在相應(yīng)方格內(nèi)填上“；二；二是明確是不等效的，在相應(yīng)方格內(nèi)填上是明確是不等效的，在相應(yīng)方格內(nèi)填上“；三是與；三是與其他形狀對(duì)相關(guān)，有待于進(jìn)一步檢查的，在相應(yīng)方格其他形狀對(duì)相關(guān)，有待于進(jìn)一步檢查的，在相應(yīng)方格內(nèi)填上相關(guān)的形狀對(duì)。內(nèi)填上相關(guān)的形狀對(duì)。 所謂關(guān)聯(lián)比較是指對(duì)那些在順序比較時(shí)髦未確定能否等效的形狀對(duì)作進(jìn)一步檢查。 關(guān)聯(lián)比較時(shí)，首先要確定隱含表中待檢查的那些次態(tài)對(duì)能否等效，并由此確定原形狀對(duì)能否

40、等效。假設(shè)隱含表中某方格內(nèi)有一個(gè)次態(tài)對(duì)不等效，那么該方格所對(duì)應(yīng)的兩個(gè)形狀就不等效，于是在相應(yīng)方格中添加標(biāo)志“。假設(shè)方格內(nèi)的次態(tài)對(duì)均為等效形狀對(duì)，那么與該方格對(duì)應(yīng)的形狀為等效形狀，該方格不添加任何標(biāo)志。這種判別有時(shí)要反復(fù)多次，直到判別出形狀對(duì)等效或不等效為止。求出最大等效類。在找出原始形狀表中的一切等效對(duì)之后，可利用等效形狀的傳送性，求出各最大等效類。確定各最大等效類時(shí)應(yīng)留意兩點(diǎn)：一是各最大等效類之間不應(yīng)出現(xiàn)一樣形狀，由于假設(shè)兩個(gè)等效類之間有一樣形狀，那么根據(jù)等效的傳送性可令其合為一個(gè)等效類；二是原始形狀表中的每一個(gè)形狀都必需屬于某一個(gè)最大等效類，換句話說，各最大等效類所包含的形狀之和必需覆蓋原

41、始形狀表中的全部形狀，否那么，化簡后的形狀表不能描畫原始形狀表所描畫的功能。下面舉例闡明化簡過程。下面舉例闡明化簡過程。例例. 化簡所示原始形狀表。化簡所示原始形狀表。解解 該表為具有該表為具有7個(gè)形狀的原始形狀個(gè)形狀的原始形狀表。用隱含表法化簡如下。表。用隱含表法化簡如下。作隱含表。根據(jù)畫隱含表的規(guī)那作隱含表。根據(jù)畫隱含表的規(guī)那么，可得到與給定形狀表對(duì)應(yīng)的隱么，可得到與給定形狀表對(duì)應(yīng)的隱含表框架如下圖。由于原始形狀表含表框架如下圖。由于原始形狀表中有中有A-G共共7個(gè)形狀，所以隱含表的個(gè)形狀，所以隱含表的橫向和縱向各有橫向和縱向各有6個(gè)方格。縱向從個(gè)方格。縱向從上到下依次為上到下依次為B-G

42、，橫向從左到右，橫向從左到右依次為依次為AF。表中每個(gè)方格代表一。表中每個(gè)方格代表一個(gè)形狀對(duì)，如左上角的方格代表形個(gè)形狀對(duì)，如左上角的方格代表形狀對(duì)狀對(duì)A和和B，右下角的方格代表形狀，右下角的方格代表形狀對(duì)對(duì)F和和G。BCDEFGA B C D E F隱含表格式隱含表格式作出最小化形狀表。根據(jù)求出的最大等效類，將每作出最小化形狀表。根據(jù)求出的最大等效類，將每個(gè)最大等效類中的全部形狀合并為一個(gè)形狀，即可得個(gè)最大等效類中的全部形狀合并為一個(gè)形狀，即可得到和原始形狀表等價(jià)的最小化形狀表。到和原始形狀表等價(jià)的最小化形狀表。尋覓等效對(duì)。首先進(jìn)展順序比較，根據(jù)等效形狀的判別規(guī)范，尋覓等效對(duì)。首先進(jìn)展順序比

43、較，根據(jù)等效形狀的判別規(guī)范，依次檢查每個(gè)形狀對(duì)，可得到順序比較結(jié)果如以下圖所示。依次檢查每個(gè)形狀對(duì)，可得到順序比較結(jié)果如以下圖所示。例如，形狀表中例如，形狀表中C和和F滿足形狀等效條件，所以，在隱含表的相滿足形狀等效條件，所以，在隱含表的相應(yīng)方格內(nèi)填入應(yīng)方格內(nèi)填入“；形狀；形狀A(yù)和和C不滿足等效條件，故在隱含表的不滿足等效條件，故在隱含表的相應(yīng)方格內(nèi)填入相應(yīng)方格內(nèi)填入“；形狀；形狀A(yù)和和E雖然滿足輸出一樣這個(gè)條件，雖然滿足輸出一樣這個(gè)條件，但它們的次態(tài)在但它們的次態(tài)在x=1時(shí)為時(shí)為B和和E，由于當(dāng)前尚不能確定，由于當(dāng)前尚不能確定B和和E能否能否等效，因此，將等效，因此，將BE填人相應(yīng)方格中。填

44、人相應(yīng)方格中。 輸入輸入狀態(tài)狀態(tài)X=0 X=1AC/0B/1BF/0A/1CF/0G/0DD/1E/0EC/0E/1FC/0G/0GC/1D/0BCFC D EBEAECFF G CDDEA B C D E F根據(jù)輸出根據(jù)輸出,7個(gè)個(gè)形狀分成形狀分成3組：組：C，F(xiàn)A，B，ED，G組內(nèi)形狀才有組內(nèi)形狀才有能夠等效。能夠等效。經(jīng)過順序比較后，還有經(jīng)過順序比較后，還有A和和B，A和和E，B和和E以及以及D和和C共共4個(gè)形狀對(duì)個(gè)形狀對(duì)尚未確定能否等效。故應(yīng)接著進(jìn)展尚未確定能否等效。故應(yīng)接著進(jìn)展關(guān)聯(lián)比較，其結(jié)果如右圖所示。關(guān)聯(lián)比較，其結(jié)果如右圖所示。 例如，在圖中，形狀例如，在圖中，形狀A(yù)、B對(duì)應(yīng)對(duì)應(yīng)

45、的方格中次態(tài)對(duì)為的方格中次態(tài)對(duì)為CF，而形狀，而形狀C、F對(duì)應(yīng)的方格標(biāo)有對(duì)應(yīng)的方格標(biāo)有“號(hào)，闡明形號(hào)，闡明形狀狀C和和F等效，由此可判別出形狀等效，由此可判別出形狀A(yù)和和B等效。等效。 檢查形狀檢查形狀A(yù)、E的次態(tài)對(duì)，出的次態(tài)對(duì)，出現(xiàn)如下循環(huán)關(guān)系：現(xiàn)如下循環(huán)關(guān)系： 知形狀知形狀C和和F是等效的，而形是等效的，而形狀狀BE又與形狀又與形狀A(yù)B構(gòu)成循環(huán)，所以，構(gòu)成循環(huán)，所以，形狀形狀A(yù)和和E是等效形狀對(duì)，是等效形狀對(duì)，B和和E也也是等效形狀對(duì)。是等效形狀對(duì)。BCFC D EBEAECFF G CDDEA B C D E FAEBECF BCFC D EBEAECFF G CDDEA B C D E

46、 F 形狀D、G對(duì)應(yīng)的方格中含有CD和DE，而形狀C、D對(duì)應(yīng)的方格已標(biāo)以“X號(hào)，這闡明形狀C和D不等效。因此，可以判別形狀D和G不等效，它所對(duì)應(yīng)的方格應(yīng)添加記號(hào)“。 由隱含表可知，原始形狀表中的7個(gè)形狀共有四個(gè)等效對(duì)：(A，B)，(A，E)，(B，E)，(C，F(xiàn))。求出最大等效類。由所得到的四個(gè)等效對(duì)可知，等效對(duì)(A，B)，(A，E)，(B，E)構(gòu)成一個(gè)最大等效類A，B，E。 等效對(duì)(C，F(xiàn))不包含在任何其他等效類中，所以，它也是一個(gè)最大等效類。其次，形狀D和G不和任何其他形狀等效，故它們各自構(gòu)成一個(gè)最大等效類。由此可見，原始形狀表中的7個(gè)形狀共構(gòu)成四個(gè)最大等效類，分別表示如下：A，B，E，C

47、，F(xiàn)，D，G。作出最小化形狀表。將最大等效類作出最小化形狀表。將最大等效類A，B，E、C，F(xiàn)、D、G分別用新的字母分別用新的字母a、b、c、d表示，并表示，并代入原表形狀表中，即可得到化簡后的最小化形狀代入原表形狀表中，即可得到化簡后的最小化形狀表如下表所示。表如下表所示。 輸入輸入狀態(tài)狀態(tài)X=0X=1ab/0a/1bb/0d/0cc/1a/0db/1c/0不完全確定形狀表的化簡 在討論構(gòu)成原始形狀表時(shí)曾經(jīng)看到，根據(jù)實(shí)踐問題所構(gòu)成的在討論構(gòu)成原始形狀表時(shí)曾經(jīng)看到，根據(jù)實(shí)踐問題所構(gòu)成的原始形狀表除完全確定形狀表之外，還存在另一類不完全確原始形狀表除完全確定形狀表之外，還存在另一類不完全確定形狀表

48、。在這類形狀表中存在不確定的次態(tài)或輸出。無疑，定形狀表。在這類形狀表中存在不確定的次態(tài)或輸出。無疑，這些不確定的形狀和輸出對(duì)于形狀化簡將是有利的，關(guān)鍵是這些不確定的形狀和輸出對(duì)于形狀化簡將是有利的，關(guān)鍵是必需適當(dāng)處置，以確保化簡前后形狀表的邏輯功能不變。為必需適當(dāng)處置，以確保化簡前后形狀表的邏輯功能不變。為此，提出了一個(gè)新的概念此，提出了一個(gè)新的概念相容形狀。不完全確定形狀表相容形狀。不完全確定形狀表的化簡是建立在相容形狀根底上的。的化簡是建立在相容形狀根底上的。 (1)相容形狀和相容類相容形狀和相容類 相容形狀。假定形狀相容形狀。假定形狀Si和和Sj是不完全確定形狀表中的兩是不完全確定形狀表

49、中的兩個(gè)形狀，假設(shè)對(duì)于一切的有效輸入序列，分別從形狀個(gè)形狀，假設(shè)對(duì)于一切的有效輸入序列，分別從形狀Si和和Sj出發(fā)，所得到的輸出呼應(yīng)序列出發(fā)，所得到的輸出呼應(yīng)序列(除不確定的那些位之外除不確定的那些位之外)是完是完全一樣的，那么，形狀全一樣的，那么，形狀Si和和Sj是相容的，或者說形狀是相容的，或者說形狀Si和和Sj是相容對(duì)，記作是相容對(duì)，記作(Si，Sj)。 從形狀表中的形狀從形狀表中的形狀S出發(fā)，假設(shè)給定某輸入序列所得出發(fā)，假設(shè)給定某輸入序列所得到的形狀呼應(yīng)序列除最后一個(gè)次態(tài)外，其他次態(tài)都是確定的，到的形狀呼應(yīng)序列除最后一個(gè)次態(tài)外，其他次態(tài)都是確定的，那么這個(gè)輸入序列對(duì)形狀那么這個(gè)輸入序列

50、對(duì)形狀S是有效的。一切的有效輸入序列，是有效的。一切的有效輸入序列，是指有效輸入序列的長度和構(gòu)造是恣意的。是指有效輸入序列的長度和構(gòu)造是恣意的。在不完全確定形狀表中，判別兩個(gè)形狀能否相容的根據(jù)是表中在不完全確定形狀表中，判別兩個(gè)形狀能否相容的根據(jù)是表中給出的次態(tài)和輸出。假定形狀給出的次態(tài)和輸出。假定形狀Si和和Sj是不完全確定形狀表中的是不完全確定形狀表中的兩個(gè)現(xiàn)態(tài)，那么，形狀兩個(gè)現(xiàn)態(tài)，那么，形狀Si和和Sj相容的條件，可歸納為在一位輸相容的條件，可歸納為在一位輸入的各種取值組合下滿足如下兩條。入的各種取值組合下滿足如下兩條。 第一，它們的輸出完全一樣，或者其中的一個(gè)第一，它們的輸出完全一樣，

51、或者其中的一個(gè)(或兩個(gè)或兩個(gè))輸出輸出不不 確定。確定。 第二，它們的次態(tài)屬于以下情況之一：第二，它們的次態(tài)屬于以下情況之一： a次態(tài)一樣；次態(tài)一樣； b次態(tài)交錯(cuò)或?yàn)楦髯缘默F(xiàn)態(tài)；次態(tài)交錯(cuò)或?yàn)楦髯缘默F(xiàn)態(tài)； c次態(tài)循環(huán)或?yàn)橄嗳輰?duì)；次態(tài)循環(huán)或?yàn)橄嗳輰?duì)； d其中的一個(gè)其中的一個(gè)(或兩個(gè)或兩個(gè))為不確定形狀。為不確定形狀。 必需指出，相容形狀不具有傳送性。即不能由必需指出，相容形狀不具有傳送性。即不能由S1和和S2相容、相容、S2和和S3相容，推出相容，推出S1和和S3也相容。這是由于判別兩個(gè)形狀能否也相容。這是由于判別兩個(gè)形狀能否相容時(shí)，對(duì)于不給定的輸出和不給定的次態(tài)可以隨意指定的緣相容時(shí)，對(duì)于不給定

52、的輸出和不給定的次態(tài)可以隨意指定的緣故。故。 相容類。相容類是由彼此相容的形狀構(gòu)成的集合。處于同一相容類中的一切形狀之間都是兩兩相容的。例如，假設(shè)有相容對(duì)(S1，S2)、(S2，S3)和(S1，S3)，那么可構(gòu)成相容類S1，S2，S3。 最大相容類。假設(shè)一個(gè)相容類不是任何其他相容類的子集，那么該相容類稱為最大相容類。由于相容形狀無傳送性，所以，同一原始形狀表的各最大相容類之間能夠存在一樣形狀，即同一形狀能夠出如今不同的最大相容類中。(2)不完全確定形狀表的化簡 不完全確定形狀表的化簡過程與完全確定形狀表的化簡過程類似，只是在某些環(huán)節(jié)的詳細(xì)處置上稍有不同。其普通步驟與方法如下。 作隱含表，尋覓相

53、容形狀對(duì)。利用隱含表尋覓相容對(duì)的過程與化簡完全確定形狀表時(shí)尋覓等效對(duì)的過程是一樣的，僅僅是形狀相容與形狀等效的規(guī)范有所不同而已。即畫好隱含表后，首先依次判別每個(gè)形狀對(duì)的相容關(guān)系，并將判別結(jié)果標(biāo)注到隱含表中。假設(shè)某個(gè)形狀對(duì)相容，那么在相應(yīng)方格中填入“；假設(shè)某個(gè)形狀對(duì)是不相容的，那么在相應(yīng)方格中填入“；假設(shè)兩個(gè)形狀的輸出一樣(或者不確定)，而其次態(tài)尚不能直接確定能否相容，那么在相應(yīng)方格中填入與之相關(guān)的次態(tài)對(duì)。 在順序比較完成后，可利用已建立的隱含表繼續(xù)追蹤待確定的形狀，即進(jìn)展關(guān)聯(lián)比較。假設(shè)與之關(guān)聯(lián)的次態(tài)對(duì)都是相容的，那么原形狀對(duì)是相容的；只需某方格中填入的次態(tài)對(duì)中有一對(duì)不相容，那么該方格所對(duì)應(yīng)的形

54、狀對(duì)不相容，在該方格中填人標(biāo)志“。逐個(gè)檢查，直至判別出一切形狀對(duì)相容或不相容為止，即可列出原始形狀表中的全部相容對(duì)。 利用形狀合并圖，求出最大相容類。為了方便地找到最大相利用形狀合并圖，求出最大相容類。為了方便地找到最大相容類，可以借助于形狀合并圖。形狀合并圖是一種將不完全確容類，可以借助于形狀合并圖。形狀合并圖是一種將不完全確定形狀表的形狀，以定形狀表的形狀，以“點(diǎn)的方式均勻地繪在圓周上，然后把點(diǎn)的方式均勻地繪在圓周上，然后把一切相容對(duì)都用線段銜接起來而得到的圖。在這種圖中，圓周一切相容對(duì)都用線段銜接起來而得到的圖。在這種圖中，圓周上的點(diǎn)表示形狀，點(diǎn)與點(diǎn)之間的連線表示兩形狀之間的相容關(guān)上的點(diǎn)

55、表示形狀，點(diǎn)與點(diǎn)之間的連線表示兩形狀之間的相容關(guān)系，一切頂點(diǎn)之間都有連線的多邊形就構(gòu)成一個(gè)最大相容類。系，一切頂點(diǎn)之間都有連線的多邊形就構(gòu)成一個(gè)最大相容類。2個(gè)、個(gè)、3個(gè)、個(gè)、4個(gè)和個(gè)和5個(gè)形狀的最大相容類形狀合并圖如以下圖所個(gè)形狀的最大相容類形狀合并圖如以下圖所示：示：利用閉覆蓋表，求最小閉覆蓋。這一步與化簡完全確定形利用閉覆蓋表，求最小閉覆蓋。這一步與化簡完全確定形狀表差別較大。要想求出不完全給定形狀表的最小化形狀表，狀表差別較大。要想求出不完全給定形狀表的最小化形狀表，必需從最大相容類必需從最大相容類(或相容類或相容類)中選出一個(gè)相容類的集合，該相中選出一個(gè)相容類的集合，該相容類集合必需

56、滿足以下容類集合必需滿足以下3個(gè)條件。個(gè)條件。 S1S2 a覆蓋性，即所選相容類集合應(yīng)包含原始形狀表的全部形狀。 b. 最小性，即所選相容類集合中相容類個(gè)數(shù)應(yīng)最少。 c閉合性，即所選相容類集合中的任一相容類，在原始形狀表中任一輸入條件下產(chǎn)生的次態(tài)應(yīng)該屬于該集合中的某一個(gè)相容類。 同時(shí)具備最小、閉合和覆蓋3個(gè)條件的相容類(包括最大相容類)集合，稱為最小閉覆蓋。不完全確定形狀表的最簡化，就是尋覓一個(gè)最小閉覆蓋。 尋覓最小閉覆蓋要借助于閉覆蓋表。所謂閉覆蓋表是指反映閉合和覆蓋這兩個(gè)性質(zhì)的表，該表包括兩部分，一部分反映相容類集合的形狀覆蓋情況，另一部分反映相容類的閉合關(guān)系。閉覆蓋表的畫法是：在表的左邊

57、自上而以下出所選相容類，表的中間覆蓋部分從左到右列出全部形狀，表的右邊閉合部分列出各相容類在輸入各種取值組合下的次態(tài)組合。必需指出，這里所說的相容類包括最大相容類和它們的子類。 作出最小化形狀表。選出一個(gè)最小閉覆蓋之后，將最小閉覆作出最小化形狀表。選出一個(gè)最小閉覆蓋之后，將最小閉覆蓋中的每個(gè)相容類用一個(gè)新的形狀符號(hào)表示，再將其代入原始蓋中的每個(gè)相容類用一個(gè)新的形狀符號(hào)表示，再將其代入原始形狀表中，即可得到與原始形狀表功能一樣的最小化形狀表。形狀表中，即可得到與原始形狀表功能一樣的最小化形狀表。 下面舉例闡明不完全確定形狀表的化簡方法。下面舉例闡明不完全確定形狀表的化簡方法。 例例1化簡右面所示

58、的原始形狀表。化簡右面所示的原始形狀表。 解：解： 這是一個(gè)具有這是一個(gè)具有5個(gè)形狀的原個(gè)形狀的原 始形狀表，表中存在不確定的次態(tài)始形狀表，表中存在不確定的次態(tài) 和輸出，因此，是一個(gè)不完全確定和輸出，因此，是一個(gè)不完全確定 形狀表。用隱含表法化簡該形狀表形狀表。用隱含表法化簡該形狀表 的過程如下。的過程如下。 作隱含表，尋覓相容形狀對(duì)。作隱含表，尋覓相容形狀對(duì)。 作出隱含表，并根據(jù)相容形狀的判別規(guī)范對(duì)各形狀作出隱含表，并根據(jù)相容形狀的判別規(guī)范對(duì)各形狀 對(duì)進(jìn)展順序比較和關(guān)聯(lián)比較后的結(jié)果如下。對(duì)進(jìn)展順序比較和關(guān)聯(lián)比較后的結(jié)果如下。 輸入輸入狀態(tài)狀態(tài)X=0 X=1AA/dd/dBC/1B/0CD/0

59、d/1Dd/dB/dEA/0C/1 由隱含表中的標(biāo)注可知，該形狀表中的相容形狀對(duì)有：(A，B)、(A，C)、(A，D)、(A，E)、(B，D)、(C，D)、(C，E)。作形狀合并圖，找出最大相容類。 根據(jù)相容形狀對(duì)可作出形狀合并圖。從形狀合并圖得到最大相容類為A，B，D、A，C，D、A，C，E。作閉覆蓋表，求最小閉覆蓋。由得到的3個(gè)最大相容類，可作出其閉覆蓋表。 BACCADD E AD BCA B C D最大相容類最大相容類覆覆 蓋蓋閉閉 合合ABCD EX=0X=1ABDABDACBACDACDADBACEACEADC 由閉覆蓋表和選擇最小閉覆蓋的由閉覆蓋表和選擇最小閉覆蓋的3個(gè)條件個(gè)條件

60、(覆蓋、閉合、最小覆蓋、閉合、最小)可知，本例的最小閉覆蓋可由最大相容類可知，本例的最小閉覆蓋可由最大相容類A，B，D和和A，C，E組成。組成。 作出最小化形狀表。假定最小閉覆蓋中的相容類作出最小化形狀表。假定最小閉覆蓋中的相容類A，B，D用形狀用形狀a表示，相容類表示，相容類A，C，E用形狀用形狀b表示，將其代入原始形狀表中，可得到下面所示的最表示，將其代入原始形狀表中，可得到下面所示的最小化形狀表。小化形狀表。在填寫最小化形狀表中的輸出值時(shí)，假設(shè)原始形狀表在填寫最小化形狀表中的輸出值時(shí)，假設(shè)原始形狀表中的相應(yīng)輸出值有確定的和不確定的兩種類型，那么中的相應(yīng)輸出值有確定的和不確定的兩種類型，那