數(shù)字邏輯-時(shí)序電路：同步時(shí)序電路的化簡(jiǎn)

1課程代碼：00830040第九章

同步時(shí)序電路的化簡(jiǎn)(2)課程回顧—狀態(tài)等價(jià)性數(shù)字邏輯——時(shí)序電路（十一）

2定義1：完全確定的時(shí)序電路中狀態(tài)S1,

S2,…,

Sj被稱為等價(jià)的，當(dāng)且僅當(dāng)對(duì)于任意的輸入序列，將S1,

S2,

…,

Sj

中的任意狀態(tài)作為初始狀態(tài)，電路的輸出序列都是相同的。定義2：設(shè)Si和Sj

是完全確定時(shí)序電路的兩個(gè)狀態(tài)，

Sk和Sl

是在輸入Ip時(shí)Si和Sj的下一個(gè)狀態(tài)，Si和Sj是等價(jià)的當(dāng)且僅當(dāng)對(duì)于每一可能的Ip

滿足下列的條件：1.

Si和Sj

的輸出相同；2.

下一個(gè)狀態(tài)Sk和Sl是等價(jià)的。9.2

完全確定電路的狀態(tài)化簡(jiǎn)數(shù)字邏輯——時(shí)序電路（十一）

3三種方法1

觀察法2

劃分法3

蘊(yùn)含表法課程回顧：例1數(shù)字邏輯——時(shí)序電路（十一）

4Partition

blocksActionPartition

P0Output

for

x=0Output

for

x=1Partition

P1Next

state

for

x=0Next

state

for

x=1Partition

P2Next

state

for

x=0Next

state

for

x=1Partition

P3Next

state

for

x=0

Next

state

for

x=1

Partition

P4

=P3States

Band

Care

equivalent(ABCDE)1110000011Separate

(ABC)

and

(DE)Separate

(ABC)

and

(DE)(ABC)(DE)Separate

(A)

and

(BC)CCBBEEDEBA(A)(BC)(DE)Separate

(D)

and

(E)CBCBEEDEBA(A)(BC)(D) (E)CBCBEEDBEA(A)(BC)(D) (E)9.2.3蘊(yùn)涵表法C/1B/0C/1E/0B/1E/0D/0

B/1E/0 A/1X0 1BCDE缺第一個(gè)A B C D少最后一個(gè)BCDE蘊(yùn)涵表BEBC,BEVXXXXXXBABCDEABCD數(shù)字邏輯——時(shí)序電路（十一）

5EBEBC,BEVXXXXXXBAA B C DA B C D9.2.3

蘊(yùn)含表法數(shù)字邏輯——時(shí)序電路（十一）

6畫出空的蘊(yùn)涵表，蘊(yùn)含表的方格表示所有可能的狀態(tài)對(duì)。檢查蘊(yùn)涵表的每個(gè)方塊，當(dāng)對(duì)應(yīng)的兩狀態(tài)輸出不相同時(shí)，在該方塊內(nèi)打“X”。添完蘊(yùn)涵表:對(duì)于每一種輸入可能，將輸出相同的次態(tài)對(duì)添入對(duì)應(yīng)的蘊(yùn)涵單元內(nèi)。當(dāng)蘊(yùn)涵表單元的蘊(yùn)涵項(xiàng)等于相對(duì)應(yīng)的兩狀態(tài)或?yàn)橥粋€(gè)狀態(tài)時(shí)：打?qū)μ?hào)“V”；當(dāng)單元包含的所有蘊(yùn)涵對(duì)都變?yōu)椤癡”時(shí)，其對(duì)應(yīng)兩狀態(tài)位等價(jià)，對(duì)應(yīng)的單元可變?yōu)椤癡”。處理蘊(yùn)涵表，確定每個(gè)狀態(tài)對(duì)的等價(jià)性。當(dāng)蘊(yùn)涵單元包含的蘊(yùn)涵項(xiàng)有一個(gè)為“X”時(shí),則其對(duì)應(yīng)的狀態(tài)對(duì)不等價(jià)，該單元畫“X”.從蘊(yùn)涵表得到等價(jià)狀態(tài)對(duì)，導(dǎo)出等價(jià)劃分：沒有畫“X”的單元對(duì)應(yīng)的狀態(tài)對(duì)為等價(jià)對(duì).數(shù)字邏輯——時(shí)序電路（十一）

7例1(b)BCDEBCDA(a)01xA

BCDEC/1B/0C/1E/0B/1E/0D/0B/1E/0A/1(c)BCDEBCDA(d)BCDEBEBCBE

ABBCDA(e)BCDE-(BC)--PK=

(A)(BC)(D)(E)(f)BEBCBE

ABBC

DA8—時(shí)序電路（十一）

例2(c)BCDE(AD)(BE)(CF)----數(shù)字邏輯—PK

=

(AD)(BE)(CF)(G)(H)BEBCD(b)A(a)01xA

BCDEFGHADADCFCHBGFGEFGHE/0D/0A/1F/0C/0A/1B/0A/0D/1C/0C/0D/1H/1G/1C/1B/1例3BCDE(AF)(BC)(BH)(CH)----BCD(b)A(a)x1x2ABCDEFGHF數(shù)字邏輯——時(shí)序電路（十一）

9GEFGH00 01

11

10D/0D/0F/0A/0C/1D/0E/1F/0C/1D/0E/1A/0D/0B/0A/0F/0C/1F/0E/1A/0D/0D/0A/0F/0G/0G/0A/0A/0B/1D/0E/1A/0Note:(BC)(BH)(CH)=

(BCH)PK=

(AF)(BCH)(D)(E)(G)(c)AFBDAFDFAFDF

BDDGAFBGAFDGAFBCAFBCBCDF三種方法的比較數(shù)字邏輯——時(shí)序電路（十一）

10觀察法：直觀，功能不強(qiáng)。劃分法：功能強(qiáng)，可編程性不太強(qiáng)。蘊(yùn)含表法：功能強(qiáng)，可編程性強(qiáng)，步驟繁瑣，所用時(shí)間多。9.3

非完全確定狀態(tài)機(jī)的化簡(jiǎn)B/1 E/0B/1 E/0F/0 C/0B/1 A/1D/0 C/1D/0 C/1X0 1X0 1B/- E/0B/1 E/-F/0 C/0B/1 A/1D/0 C/-D/- C/1X0 1B’/1D’/0D’/0B’/0A’/1A’/1C’/0

B’/1A’B’C’D’(AB)(C)(D)(EF)數(shù)字邏輯——時(shí)序電路（十一）

11另一個(gè)結(jié)果X01X01AB/-E/0AB/0E/0BB/1E/-BB/1E/1CF/0C/0CF/0C/0DB/1A/1DB/1A/1ED/0C/-ED/0C/0FD/-C/1FD/1C/1X0 1A’B’B’/0 A’/0B’/1 A’/1(ACE)(BDF)數(shù)字邏輯——時(shí)序電路（十一）

129.3.1

狀態(tài)相容性數(shù)字邏輯——時(shí)序電路（十一）

13次態(tài)或者輸出不是對(duì)如任何狀態(tài)都是確定的?？蓱?yīng)用輸入序列(Applicable

inputsequences): 在非完全確定的時(shí)序電路中，一個(gè)輸入序列對(duì)于狀態(tài)

Si

是可應(yīng)用的，當(dāng)且僅當(dāng)電路的初始狀態(tài)是Si

，在輸入序列的作用下，除了最后一個(gè)可能的輸入外所有的次態(tài)都是確定的。定義1：相容狀態(tài)(Compatible

states)：兩個(gè)狀態(tài)

Si

和

Sj

是相容的當(dāng)且僅當(dāng)對(duì)于所有可能的可應(yīng)用輸入序列，每個(gè)狀態(tài)的輸出序列中確定的輸出是相同的。定義2：相容狀態(tài)(Compatible

states)：兩個(gè)狀態(tài)

Si

和

Sj

是相容的當(dāng)且僅當(dāng)滿足下列的條件，對(duì)于每一種可能的輸入

IpSi

and

Sj

的確定輸出是相容的。如果次態(tài)Sk

和

Sl

是確定的，

Sk

和

Sl

是相容的。不相容狀態(tài)(Incompatible

states)：兩個(gè)狀態(tài)被稱為不相容的，如果它們不是相容狀態(tài)。相容關(guān)系數(shù)字邏輯——時(shí)序電路（十一）

14相容關(guān)系：設(shè)R是集合S上定義的關(guān)系(Relation)，R是相容的當(dāng)且僅當(dāng)R是自反的(reflexive)、對(duì)稱的(symmetric)

。一個(gè)集合的相容關(guān)系可以將集合劃分(partition)為不相交的(disjoint)相容類。例：設(shè)S

={A,B,C,D,E}和關(guān)系

RR={A,A),(B,B),(C,C),(D,D),(E,E),(A,B),(B,A),(A,C),(C,A),(A,D),(D,A),(A,E),(E,A),(B,D),(D,B),(C,D),(D,C),(C,E),(E,C)}相容類為：(AB)(AC)(AD)(AE)(BD)(CD)(CE)(ABD)(ACD)(ACE)不相容類為

(BC)(BE)(DE)利用蘊(yùn)含表尋找相容關(guān)系對(duì)最大相容類需要通過(guò)歸并圖(merger

diagram)最大相容和不相容類數(shù)字邏輯——時(shí)序電路（十一）

15最大相容：不存在其他不在相容類中的狀態(tài)可以加入該相容類中。最大非相容類：不存在其他不在不相容類中的狀態(tài)可以加入該不相容類中。利用蘊(yùn)含表找出相容狀態(tài)對(duì)G (GH)F (GH)(FG)E (EG)(EH)(GH)(FG)E (FG)(EGH)D (DG)(FG)(EGH)C (CG)(CF)(CE)(CD)(DG)(FG)(EGH)C (CEG)(CDG)(CFG)(EGH)B (BC)(BG)(CEG)(CDG)(CFG)(EGH)A (AE)(AG)(AH)(BC)(BG)(CEG)(CDG)(CFG)(EGH)A (AEG)(AGH)(AEH)(BCG)(CEG)(CDG)(CFG)(EGH)A (AEGH)(BCG)(CDG)(CEG)(CFG)(c)G -F (FH)E (FH)(EF)D (FH)(EF)(DH)(DF)(DE)D (FH)(DH)(DEF)C (CH)(FH)(DH)(DEF)B (BH)(BF)(BE)(BD)(CH)(FH)(DH)(DEF)B (BH)(BDEF)(CH)(FH)(DH)B (BDEF)(CH)(BDFH)A (AB)(AC)(AD)(AF)(BDEF)(CH)(BDFH)A (ABDF)(AC)(BDEF)(CH)(BDFH)(d)BCDEBCD(b)AF數(shù)字邏輯——時(shí)序電路（十一）

16GEFGHACBGAEACBCACCGCE

ABACAGACADACBDDGAECDACADACCGAGEGCGAGCGDGAGCDADGHDECHCDAHCDDHADDG(a)01xABCDEFGHA/-C/1B/-A/-G/-E/0C/1C/-A/1C/-D/-A/-G/-G/-H/-D/-所用方法與完全確定電路一樣。(c)

最大相容類；(d)最大不相容類歸并圖(merger

diagram)BCA(c)A數(shù)字邏輯——時(shí)序電路（十一）

17BDCAECD(a)BBADE(b)CF(d)歸并圖(b)HBGCFA

DE(a)AHBG數(shù)字邏輯——時(shí)序電路（十一）

18CFDE9.3.2

最小化過(guò)程數(shù)字邏輯——時(shí)序電路（十一）

19選擇一組相容類滿足下列條件：完整性

Completeness：必須覆蓋原狀態(tài)機(jī)中所有的狀態(tài)。一致性

Consistency：相容類的封閉集合必須是封閉的；在所選擇的集合的每個(gè)相容類的次態(tài)，必須被這個(gè)集合的一些相容類包含。最小性

Minimality：使用數(shù)目最小的相容類。狀態(tài)數(shù)的邊界數(shù)字邏輯——時(shí)序電路（十一）

20設(shè)

U

是所求最小化電路中狀態(tài)數(shù)目的上界(upper

bound)。則

U

=

minimum(NSMC,

NSOC)，其中NSMC

=最大相容集合數(shù)。NSOC

=

原電路中的狀態(tài)數(shù)。設(shè)

L

be

是所求最小化電路中狀態(tài)數(shù)目的下界(lower

bound)則

L=maximum(NSMI1,NSMI2,…,NSMIi)其中

NSMIi

=

原電路的最大不相容類集合中第

i

組中的狀態(tài)數(shù)目。狀態(tài)化簡(jiǎn)算法數(shù)字邏輯——時(shí)序電路（十一）

21第1步

找出最大相容類第2步

找出最大不相容類第3步

找出所求狀態(tài)的上界和下界第4步

找出滿足完整性，一致性和最小性的的一組相容類。第5步

構(gòu)造最小化狀態(tài)表第4步所有的方法為試探法（trial

and

error）。22例1：x0 1x01(AEGH)AGHCDGA' A'/1C'/1(BCG)BGAEGB' B'/-A'/0(CDG)CGCEGC' B',

C',

D',

E'/1D'/0(CFG)DGAEGD' A'/1D'/0(CEG)AGCEGE' C'/-A'/0(a)(b)4

K

5(AEGH)(BCG)(CDG)(CEG)(CFG)數(shù)字邏輯——時(shí)序電路（十一）

例2：(d)AECDB(c)AECDB(b)BBCDAC數(shù)字邏輯——時(shí)序電路（十一）

23DEx01(a)ABCDEx01x01A/--/-C/1B/0D/0-/1-/-B/-A/0C/1(e)(ABD)(ACD)(ACE)ACADADBBC(f)A'B'B'/1A'/0A'/0B'/1ACAD

AD