Lecture5有限狀態(tài)機ppt課件

1、有限形狀機有限形狀機Finite State MachineFinite State Machine例：計數(shù)器設(shè)計例：計數(shù)器設(shè)計 設(shè)計一電路，包含基設(shè)計一電路，包含基4計數(shù)器，和譯碼輸出模塊。計數(shù)器，和譯碼輸出模塊。計數(shù)器的輸出計數(shù)器的輸出(Present_value)從從0到到3循環(huán)；循環(huán)；當(dāng)計數(shù)值為當(dāng)計數(shù)值為2時，譯碼輸出時，譯碼輸出(DataOut)為為“1，否那么輸出否那么輸出“0。Regs1ClkPresent_valueQ(n)Next_valueQ(n+1) 譯碼譯碼DataOutZ(n)00/001/010/111/0Regs1ClkPresent_valueQ(n)Next_

2、valueQ(n+1) 譯碼譯碼DataOutZ(n)00/001/010/111/0擴展一個輸入端擴展一個輸入端din，當(dāng)當(dāng)din = 1時計數(shù)器遞時計數(shù)器遞增計數(shù)；當(dāng)增計數(shù)；當(dāng)din = 0時時計數(shù)器遞減計數(shù)。計數(shù)器遞減計數(shù)。dinDin=1Din = 1Din = 1Din = 1Din = 0Din = 0Din = 0Din = 0Regs/-1ClkPresent_valueQ(n)Next_valueQ(n+1) 譯碼譯碼DataOutZ(n)再將計數(shù)器修正成一再將計數(shù)器修正成一個形狀轉(zhuǎn)換器，形狀個形狀轉(zhuǎn)換器，形狀為為S0, S1, S2, S3。每個形狀的取值根據(jù)每個形狀的取值

3、根據(jù)詳細(xì)情況而定。比如詳細(xì)情況而定。比如S0 = 00, S1 = 11, S3 = 01, S4 = 10。din00/001/010/111/0Din=1Din = 1Din = 1Din = 1Din = 0Din = 0Din = 0Din = 0Regs/-1ClkPresent_valueQ(n)Next_valueQ(n+1) 譯碼譯碼DataOutZ(n)再將計數(shù)器修正成一再將計數(shù)器修正成一個形狀轉(zhuǎn)換器，形狀個形狀轉(zhuǎn)換器，形狀為為S0, S1, S2, S3。每個形狀的取值根據(jù)每個形狀的取值根據(jù)詳細(xì)情況而定。比如詳細(xì)情況而定。比如S0 = 00, S1 = 11, S3 = 0

4、1, S4 = 10。dinS0/0S1/0S2/1S3/0Din=1Din = 1Din = 1Din = 1Din = 0Din = 0Din = 0Din = 0Regs/-1ClkPresent_valueQ(n)Next_valueQ(n+1) 譯碼譯碼DataOutZ(n)如今我們得到了一個比較通用如今我們得到了一個比較通用的時序電路，這種電路統(tǒng)稱為的時序電路，這種電路統(tǒng)稱為形狀機形狀機(State Machine)。dinS0/0S1/0S2/1S3/0Din=1Din = 1Din = 1Din = 1Din = 0Din = 0Din = 0Din = 0Regs/-1Clk

5、Present_valueQ(n)Next_valueQ(n+1) 譯碼譯碼DataOutZ(n)有限形狀機概述有限形狀機概述數(shù)字系統(tǒng)控制部分的每一個控制態(tài)可以看數(shù)字系統(tǒng)控制部分的每一個控制態(tài)可以看作一種形狀，與每一個控制態(tài)相關(guān)的轉(zhuǎn)換作一種形狀，與每一個控制態(tài)相關(guān)的轉(zhuǎn)換條件指定了當(dāng)前形狀的下一個形狀和輸出。條件指定了當(dāng)前形狀的下一個形狀和輸出。根據(jù)有限形狀機的輸出與當(dāng)前形狀與當(dāng)前根據(jù)有限形狀機的輸出與當(dāng)前形狀與當(dāng)前輸入的關(guān)系，可以分成輸入的關(guān)系，可以分成Moore型和型和Mealy型兩種類型的有限形狀機。型兩種類型的有限形狀機。 Moore形狀機和形狀機和Mealy形狀機形狀機Moore形狀機

6、的輸出只與當(dāng)前形狀有關(guān)形狀機的輸出只與當(dāng)前形狀有關(guān)次態(tài)次態(tài)邏輯邏輯狀狀 態(tài)態(tài)存放器存放器輸出輸出邏輯邏輯輸入輸入次態(tài)次態(tài)現(xiàn)態(tài)現(xiàn)態(tài)輸出輸出時鐘時鐘復(fù)位復(fù)位Moore形狀機和形狀機和Mealy形狀機形狀機Mealy形狀機的輸出與當(dāng)前形狀機及形狀機的輸出與當(dāng)前形狀機及當(dāng)前輸入信號有關(guān)當(dāng)前輸入信號有關(guān)次態(tài)次態(tài)邏輯邏輯狀狀 態(tài)態(tài)存放器存放器輸出輸出邏輯邏輯輸入輸入次態(tài)次態(tài)現(xiàn)態(tài)現(xiàn)態(tài)輸出輸出時鐘時鐘復(fù)位復(fù)位形狀機的表示方法形狀機的表示方法形狀轉(zhuǎn)換表形狀轉(zhuǎn)換表算法流程圖算法流程圖形狀轉(zhuǎn)換圖形狀轉(zhuǎn)換圖這是最流行的這是最流行的表示方法表示方法形狀轉(zhuǎn)換圖形狀轉(zhuǎn)換圖形狀形狀1形狀形狀4形狀形狀2形狀形狀3入入/ /出

7、出入入入入入入/ /出出/ /出出/ /出出Moore條件控條件控制定序制定序直接控直接控制定序制定序形狀轉(zhuǎn)換圖形狀轉(zhuǎn)換圖形狀形狀1形狀形狀4形狀形狀2形狀形狀3入入/出出入入/出出入入/出出入入/出出/出出Mealy條件控條件控制定序制定序直接控直接控制定序制定序用用VHDL描畫形狀機的組成描畫形狀機的組成一個用來描畫有限形狀機功能的一個用來描畫有限形狀機功能的VHDL言語程序中應(yīng)該包含以下幾個內(nèi)容：言語程序中應(yīng)該包含以下幾個內(nèi)容：(1)至少包括一個形狀信號，它們用來至少包括一個形狀信號，它們用來指定有限形狀機的形狀；指定有限形狀機的形狀；(2)形狀轉(zhuǎn)移指定和輸出指定，它們對形狀轉(zhuǎn)移指定和輸

8、出指定，它們對應(yīng)于控制單元中與每個控制步有關(guān)的應(yīng)于控制單元中與每個控制步有關(guān)的轉(zhuǎn)移條件；轉(zhuǎn)移條件；(3)時鐘信號，它普通是用來進展同步時鐘信號，它普通是用來進展同步的；的；(4)同步或異步復(fù)位信號。同步或異步復(fù)位信號。 形狀機的形狀機的VHDL描畫方式描畫方式(1)單進程描畫方式：單進程描畫方式就是指在單進程描畫方式：單進程描畫方式就是指在VHDL言語程序的構(gòu)造體中，運用一個進程語句言語程序的構(gòu)造體中，運用一個進程語句來描畫有限形狀機中的次態(tài)邏輯、形狀存放器和來描畫有限形狀機中的次態(tài)邏輯、形狀存放器和輸出邏輯。輸出邏輯。(2)雙進程描畫方式：一個進程語句用來描畫有限雙進程描畫方式：一個進程語句

9、用來描畫有限形狀機中次態(tài)邏輯、形狀存放器和輸出邏輯中的形狀機中次態(tài)邏輯、形狀存放器和輸出邏輯中的任何兩個；另外一個進程那么用來描畫有限形狀任何兩個；另外一個進程那么用來描畫有限形狀機剩余的功能。機剩余的功能。(3)三進程描畫方式：一個進程用來描畫有限形狀三進程描畫方式：一個進程用來描畫有限形狀機中的次態(tài)邏輯；一個進程用來描畫有限形狀機機中的次態(tài)邏輯；一個進程用來描畫有限形狀機中的形狀存放器；另外一個進程用來描畫有限形中的形狀存放器；另外一個進程用來描畫有限形狀機中的輸出邏輯。狀機中的輸出邏輯。形狀機的形狀機的VHDL描畫方式描畫方式描述方式描述方式進程描述功能進程描述功能三進程描述方式三進程描

10、述方式進程進程1：描述次態(tài)邏輯：描述次態(tài)邏輯進程進程2：描述狀態(tài)寄存器：描述狀態(tài)寄存器進程進程3：描述輸出邏輯：描述輸出邏輯雙進程描雙進程描述方式述方式 形式形式1 進程進程1：描述次態(tài)邏輯、狀態(tài)寄存器：描述次態(tài)邏輯、狀態(tài)寄存器進程進程2：描述輸出邏輯：描述輸出邏輯形式形式2 進程進程1：描述狀態(tài)寄存器、輸出邏輯：描述狀態(tài)寄存器、輸出邏輯進程進程2：描述次態(tài)邏輯：描述次態(tài)邏輯形式形式3 進程進程1：描述次態(tài)邏輯、輸出邏輯：描述次態(tài)邏輯、輸出邏輯進程進程2：描述狀態(tài)寄存器：描述狀態(tài)寄存器單進程描述方式單進程描述方式進程進程1：描述次態(tài)邏輯、狀態(tài)寄存器和：描述次態(tài)邏輯、狀態(tài)寄存器和輸出邏輯輸出邏輯

11、存儲控制器存儲控制器idledecisionreadwritereadyread_writereadyreadyreadyreadyreadyread_write 設(shè)計一個存儲控制器，設(shè)計一個存儲控制器，它的詳細(xì)要求為它的詳細(xì)要求為:(1)存存儲控制器可以根據(jù)微處儲控制器可以根據(jù)微處置器的讀周期或者寫周置器的讀周期或者寫周期，分別對存儲器輸出期，分別對存儲器輸出寫使能信號寫使能信號we和讀使能和讀使能信號信號oe；(2)存儲控制存儲控制器的輸入信號有器的輸入信號有3個個:微微處置器的預(yù)備就緒信號處置器的預(yù)備就緒信號ready、微處置器的讀、微處置器的讀寫信號寫信號read_write和和時鐘信

12、號時鐘信號clk。 存儲控制器存儲控制器列出當(dāng)前形狀和輸出值的關(guān)系列出當(dāng)前形狀和輸出值的關(guān)系狀態(tài)狀態(tài)輸出輸出OEWEidle00decision00write01read10建立形狀轉(zhuǎn)換表，列出次態(tài)和轉(zhuǎn)換條件建立形狀轉(zhuǎn)換表，列出次態(tài)和轉(zhuǎn)換條件當(dāng)前狀態(tài)當(dāng)前狀態(tài)次態(tài)次態(tài)轉(zhuǎn)換條件轉(zhuǎn)換條件idledecisionready=1decisionwritew_r=0readw_r=1writeidleready=1writeready=0readidleready=1readready=0利用利用VHDLVHDL言語進展形狀機描畫言語進展形狀機描畫一切形狀均可以表達(dá)為一切形狀均可以表達(dá)為CASE-CASE

13、-WHENWHEN構(gòu)造中的一條語句。構(gòu)造中的一條語句。形狀的轉(zhuǎn)移經(jīng)過形狀的轉(zhuǎn)移經(jīng)過if-then-elseif-then-else語句語句實現(xiàn)。實現(xiàn)。CASE present_state ISCASE present_state IS WHEN idle = WHEN idle = 輸出量；輸出量； IFIF ELSE ELSE END IF; END IF;有些形狀的轉(zhuǎn)換中，在條件滿足時，有些形狀的轉(zhuǎn)換中，在條件滿足時，轉(zhuǎn)換到下一個形狀，否那么堅持原來轉(zhuǎn)換到下一個形狀，否那么堅持原來的形狀不變。這種情況對應(yīng)著的形狀不變。這種情況對應(yīng)著IF-THEN-ELSE的兩個分支。的兩個分支。在這種情況

14、下，在這種情況下，ELSE分支并不是必需分支并不是必需的。但是短少的。但是短少ELSE分支，會導(dǎo)致額外分支，會導(dǎo)致額外的存儲器。的存儲器。形狀轉(zhuǎn)換形狀轉(zhuǎn)換形狀描畫的步驟：對每一個形狀建立一項CASE語句的分支 WHEN 形狀名 =確定輸出變量經(jīng)過IF-THEN-ELSE語句指定相應(yīng)的次態(tài)。例case present_state is - CASE分支 when idle =oe=0;we=0; -確定輸出變量if(ready = 1) then-確定次態(tài)next_state = decision;elsenext_state IF(ready = 1) THENnext_state = dec

15、ision;ELSEnext_state = idle;END IF;END CASE;END PROCESS nextstate_logic; 例：三進程描畫方式例：三進程描畫方式2 2state_register: PROCESS(clk)BEGIN IF(RISING_EDGE(clk) THEN present_state we = 0;oe we=0;oewe=0;oewe=1;oe=0; END CASE;END PROCESS output_logic 義務(wù)義務(wù)1 1：空調(diào)控制器：空調(diào)控制器S1S2S3thigh=0tlow=0thigh=0tlow=1thigh=1tlow=0

16、thigh=0tlow=1thigh=0tlow=0thigh=1tlow=0hot=0cool=0hot=0cool=1hot=1cool=0空調(diào)控制器形狀轉(zhuǎn)換圖空調(diào)控制器形狀轉(zhuǎn)換圖義務(wù)義務(wù)1 1：空調(diào)控制器：空調(diào)控制器S1S1：表示溫度適中，不高也不低，對應(yīng)著輸入信號thigh和tlow均為低電平(無效)，空調(diào)器既不制冷也不制熱，因此輸出控制信號hot和cool都是低電平。S2S2：表示溫度太低，對應(yīng)著輸入信號tlow為高電平，thigh為低電平，此時空調(diào)器應(yīng)該任務(wù)在制熱形狀，相應(yīng)的輸出控制信號hot為高電平，cool無效。S3S3：表示溫度太高，對應(yīng)著輸入信號thigh為高電平，tlow

17、為低電平，此時空調(diào)器應(yīng)該任務(wù)在制冷形狀，相應(yīng)的輸出控制信號cool為高電平，hot無效。義務(wù)義務(wù)1 1：空調(diào)控制器：空調(diào)控制器形狀轉(zhuǎn)換表形狀轉(zhuǎn)換表當(dāng)前當(dāng)前形狀形狀轉(zhuǎn)換條件轉(zhuǎn)換條件下一下一形狀形狀執(zhí)行操作執(zhí)行操作輸出值輸出值S1thigh=0&tlow=1thigh=1&tlow=0S2S3制熱制熱制冷制冷hot=1/cool=0hot=0/cool=1S2thigh=0&tlow=0thigh=1&tlow=0S1S3既不制冷也不制熱既不制冷也不制熱制冷制冷hot=0/cool=0hot=0/cool=1S3thigh=0&tlow=0thigh=0&a

18、mp;tlow=1S1S2既不制冷也不制熱既不制冷也不制熱制熱制熱hot=0/cool=0hot=1/cool=0形狀機的運用設(shè)計形狀機的運用設(shè)計例子：設(shè)計一個二進制序列檢測器，當(dāng)檢測到例子：設(shè)計一個二進制序列檢測器，當(dāng)檢測到10110序列時，就輸出序列時，就輸出1(一個時鐘周期的脈沖一個時鐘周期的脈沖)。其他情況下輸出其他情況下輸出0。 規(guī)定檢測到一次之后，檢測器復(fù)位到最初始的形規(guī)定檢測到一次之后，檢測器復(fù)位到最初始的形狀，重新從頭檢測。如下所示：狀，重新從頭檢測。如下所示：輸入：輸入：01101101101100輸出：輸出：00000001000001形狀轉(zhuǎn)換圖設(shè)計形狀轉(zhuǎn)換圖設(shè)計Moore

19、Moore10110S0/0S1/0S2/0S3/0S4/0S5/1Reset1100110100101011 0s1 s2s3s4 s5s0問題問題1：如何保證：如何保證形狀機在初始時形形狀機在初始時形狀為狀為s0？問題問題2：在形狀機：在形狀機跑飛，即脫離有效跑飛，即脫離有效形狀形狀(s0s5)時，時，如何使形狀機能恢如何使形狀機能恢復(fù)任務(wù)復(fù)任務(wù)Sx/0波形波形波形如以下波形如以下圖所示圖所示問題：假設(shè)需求問題：假設(shè)需求將輸出脈沖往前將輸出脈沖往前推一個時鐘周期，推一個時鐘周期，該如何修正設(shè)計？該如何修正設(shè)計？101101011 0s1 s2s3s4 s5s0輸入輸入時鐘時鐘輸出輸出當(dāng)前形

20、狀當(dāng)前形狀 發(fā)現(xiàn)當(dāng)當(dāng)前壯發(fā)現(xiàn)當(dāng)當(dāng)前壯態(tài)為態(tài)為s4，并且輸，并且輸入為入為0時，輸出時，輸出為為1。形狀轉(zhuǎn)換圖設(shè)計形狀轉(zhuǎn)換圖設(shè)計(Mealy)(Mealy)S0S1S2S3S4S5Reset100110100101sX/0/0/0/0/0/0/0/0/0/1/0/0101101011 0s1 s2s3s4 s5s0/00/1s0形狀機的代碼實現(xiàn)形狀機的代碼實現(xiàn) 形狀定義形狀定義 Architecture rtl of Syn isArchitecture rtl of Syn is - - 其他信號定義。其他信號定義。 Type SynFsmState is ( s0, s1, s2, s3,

21、s4, Type SynFsmState is ( s0, s1, s2, s3, s4, s5);s5); Signal SynCst, SynNst : SynFsmState;Signal SynCst, SynNst : SynFsmState; Begin Begin - - 構(gòu)造體。構(gòu)造體。 End rtl;End rtl;形狀機的代碼實現(xiàn)形狀機的代碼實現(xiàn)形狀存放器進程描畫形狀存放器進程描畫形狀存放器輸出譯碼下一狀態(tài)譯碼當(dāng)前形當(dāng)前形狀狀輸出輸出下一形狀下一形狀輸入輸入時鐘時鐘clkclk形狀存放器進程描畫形狀存放器進程描畫Process( clk, Reset )Begin if(

22、 Reset = 1 ) then SynCst = S0; - 初始形狀。初始形狀。 elsif( clkevent and clk = 1 ) then SynCst when s1 = when s5 = End case;End process; if( din = 1 ) then SynNst = s1; else SynNst SynNst when s1 = when s5 = when others = End case;End process;MooreMealyDout = 0;Dout = 0;Dout = 0if( din = 1 ) then else end if

23、;, din )義務(wù)義務(wù)3 3：交通燈控制器：交通燈控制器模擬顯示十字路口兩個方向的交統(tǒng)統(tǒng)模擬顯示十字路口兩個方向的交統(tǒng)統(tǒng)行情況。兩個方向均用紅、黃、綠燈行情況。兩個方向均用紅、黃、綠燈指示實踐形狀。指示實踐形狀。 用用LEDLED同時顯示兩個方向形狀的時間。同時顯示兩個方向形狀的時間。時間計數(shù)方式為倒計數(shù)方式。技術(shù)參時間計數(shù)方式為倒計數(shù)方式。技術(shù)參數(shù)為綠數(shù)為綠( (紅紅)50)50秒、黃秒、黃( (紅紅)5)5秒、紅秒、紅( (綠綠)30)30秒和紅秒和紅( (黃黃)5)5秒。秒。方法：有限形狀機方法：有限形狀機當(dāng)前狀態(tài)當(dāng)前狀態(tài)下一狀態(tài)下一狀態(tài)東西燈東西燈南北燈南北燈S1S1S2S2G GR

24、 RS2S2S3S3Y YR RS3S3S4S4R RG GS4S4S1S1R RY Y形狀機形狀機采用雙進程描畫方式采用雙進程描畫方式次態(tài)邏輯和輸出邏輯放在一個進程中次態(tài)邏輯和輸出邏輯放在一個進程中實現(xiàn)，形狀存放器在另一個進程中實實現(xiàn)，形狀存放器在另一個進程中實現(xiàn)。現(xiàn)。從一個形狀轉(zhuǎn)換到另外一個形狀，需從一個形狀轉(zhuǎn)換到另外一個形狀，需求經(jīng)過一段時間，這段時間的終了將求經(jīng)過一段時間，這段時間的終了將導(dǎo)致次態(tài)變成現(xiàn)態(tài)；導(dǎo)致次態(tài)變成現(xiàn)態(tài)；關(guān)于計數(shù)器關(guān)于計數(shù)器設(shè)置東西、南北兩個計數(shù)器設(shè)置東西、南北兩個計數(shù)器計數(shù)器的初值在形狀轉(zhuǎn)換時設(shè)置計數(shù)器的初值在形狀轉(zhuǎn)換時設(shè)置計數(shù)器采用倒計數(shù)方式計數(shù)器采用倒計數(shù)方式計數(shù)終了計數(shù)終了(EOC)(EOC)信號將觸發(fā)形狀存放器信號將觸發(fā)形狀存放器進程的執(zhí)行進程的執(zhí)行計數(shù)的結(jié)果將被顯示出來。計數(shù)的結(jié)果將被顯示出來。形狀轉(zhuǎn)換的條件形狀轉(zhuǎn)換的條件計數(shù)器值為計數(shù)器值為0(0(使得使得EOC=1)EOC=1)由于有兩個計數(shù)器，因此有四由于有兩個計數(shù)器，因此有四( (三三) )種情種情況，分別對應(yīng)形狀轉(zhuǎn)換的情況。況，分別對應(yīng)形狀轉(zhuǎn)換的情況。程序組成程序組成構(gòu)造體有三個進程構(gòu)造體有三個進程形狀轉(zhuǎn)換和輸出形狀轉(zhuǎn)換和輸出形狀存放器形狀存放器計數(shù)器及譯碼計數(shù)器及譯碼計數(shù)器計數(shù)器形狀寄形狀寄存