狀態轉移圖工具

輸入循序電路(狀態機)的狀態轉移表,即可繪製狀態轉移圖,並追蹤狀態與輸出如何隨輸入序列變化。可以從「連續 2 個 1 就輸出 1」「偵測 101」「二進位數除以 3 的餘數」等範例開始,一邊修改表格一邊確認動作。也會顯示狀態最小化的結果,找出功能相同的狀態並加以合併。

狀態轉移表

狀態轉移圖與動作

狀態最小化

從第一列的狀態開始。摩爾型在各時刻的輸出,顯示的是讀入輸入後所轉移到的狀態的輸出。圖中的紅色箭頭是所選時刻的轉移。

狀態轉移圖與狀態轉移表

含有正反器的循序電路,會把過去的輸入記成「狀態」,並由目前的狀態與輸入決定下一個狀態與輸出。把這種動作以圓圈表示狀態、以箭頭表示轉移畫成的圖,就是狀態轉移圖;整理成表格則是狀態轉移表。例如「連續 2 個 1 就輸出 1」的電路,以 3 個狀態記住剛才連續出現的 1 的個數(0 個、1 個、2 個以上)。來了 0 就回到最初的狀態,來了 1 就前進到下一個狀態。選擇範例並移動時刻的滑桿,就能確認每個輸入沿著哪一個箭頭轉移。

摩爾型與米利型

輸出只由目前狀態決定的稱為摩爾型(Moore),由狀態與輸入共同決定的稱為米利型(Mealy)。摩爾型把輸出寫在狀態的圓圈內,米利型則以「輸入/輸出」的形式寫在箭頭上。米利型在輸入改變時輸出會立即改變,常能以較少的狀態實現相同功能,但輸入的雜訊或變化會直接反映在輸出上。摩爾型的輸出配合時脈變化,較容易處理,雖然會延遲 1 個時脈,但較為安全。「偵測 101」的範例以米利型需要 3 個狀態,改成摩爾型則要多一個「已偵測到 101」的狀態,共 4 個狀態。

狀態最小化

對相同的輸入序列一定產生相同輸出序列的兩個狀態,不需要加以區分,可以合併為一個(等價狀態)。找法是:先把輸出相同的狀態放進同一組,再依「輸入 0 與輸入 1 的下一個狀態是否落在同一組」把組別細分,重複到分組不再改變為止。無法從初始狀態到達的狀態也可以刪除。狀態減少後,記住狀態所需的正反器數量,以及產生下一個狀態的邏輯電路都會變小。在「含多餘狀態的表」範例中,6 個狀態會減為 3 個狀態。

轉換成電路:狀態指定

要把狀態轉移表做成實際的電路,需替每個狀態指定一個二進位編碼(狀態指定)。狀態有 k 個時,正反器只需 log₂ k 無條件進位後的個數;3 個狀態需要 2 個。接著,建立由目前狀態的位元與輸入求出下一個狀態的位元與輸出的真值表,以卡諾圖等方法化簡後接到正反器的輸入。每個狀態使用 1 個正反器的獨熱編碼(one-hot),雖然正反器較多,但下一個狀態的邏輯較簡單,常用於 FPGA。

練習邏輯電路題目

下列哪一項是對序向電路的正確說明?

  1. A輸出由目前的輸入與所記憶的內部狀態決定
  2. B輸出僅由目前的輸入決定
  3. C只處理類比訊號
查看答案與解析

正確答案:A. 輸出由目前的輸入與所記憶的內部狀態決定

序向電路具有正反器等記憶元件,輸出不僅取決於目前的輸入,也取決於過去輸入的歷程(內部狀態)。計數器、暫存器、狀態機是其代表例,可用來建立自動販賣機投入金額管理等模型。輸出僅由目前輸入決定的電路是組合電路(加法器、解碼器等),實際的數位電路是將這兩者以時脈交替連接的結構。

輸出僅由目前狀態決定的序向電路(狀態機)類型是哪一個?

  1. A米利型
  2. B摩爾型
  3. C哈佛型
查看答案與解析

正確答案:B. 摩爾型

摩爾型的輸出僅由目前狀態決定,米利型的輸出則由狀態與輸入兩者決定。摩爾型的輸出只在時脈邊緣之後才改變,輸入的變化與突波不會直接傳到輸出,因此穩定,時序也容易預測,但對輸入的反應會慢1個時脈,且狀態數容易增加。米利型可減少狀態數並能立即回應輸入,但輸入的變化會直接傳到輸出。實際設計中會將兩者組合使用。

以HDL撰寫的狀態機(state machine)的基本架構,下列何者正確?

  1. A只有記憶狀態的記憶體,不使用邏輯電路
  2. B只有決定輸出的電路,不記憶狀態
  3. C記憶目前狀態的暫存器、決定下一個狀態的組合電路、決定輸出的組合電路
查看答案與解析

正確答案:C. 記憶目前狀態的暫存器、決定下一個狀態的組合電路、決定輸出的組合電路

狀態機將目前的狀態記憶在正反器的暫存器中,由目前的狀態與輸入以組合電路決定下一個狀態,並在時脈邊緣更新狀態。輸出則由目前的狀態(與輸入)以組合電路決定。通訊程序的控制、自動販賣機、紅綠燈的控制等,許多依程序動作的電路都是寫成狀態機。

在具有3個狀態的狀態機中,記憶狀態所需的正反器數量的組合,下列何者正確(二進位編碼/獨熱編碼)?

  1. A3個/2個
  2. B2個/3個
  3. C1個/3個
查看答案與解析

正確答案:B. 2個/3個

在二進位編碼中,狀態以二進位的編號表示,因此3個狀態只要00、01、10共2位元(2個正反器)就足夠。在獨熱編碼中,每個狀態使用1個正反器,所以是3個。二進位中會剩下未使用的11編碼,為了在因雜訊等原因進入該編碼時能回到正確的狀態,先以default決定去處會比較安全。

常見問題

摩爾型與米利型該用哪一種?

若希望輸出與時脈同步、保持穩定,適合摩爾型;若想減少狀態數,或希望對輸入立即反應,則適合米利型。考試中可依輸出是寫在圓圈內還是箭頭上,判斷所給的圖屬於哪一型。

時刻 0 的輸出是什麼?

摩爾型即使在尚未讀入任何輸入的時刻 0,也會輸出初始狀態的輸出。本工具的「輸出序列」只列出讀入輸入之後的輸出。米利型的輸出要有輸入才會決定,因此時刻 0 沒有輸出。

最多可以輸入幾個狀態?

最多 8 個。輸入只有 0 與 1 兩種。狀態名稱可自由設定,最多 6 個字元,也會反映在下一個狀態的選項中。

考試中會怎麼出題?

在日本的基本資訊技術士考試、應用資訊技術士考試等資訊類證照考試中,常見的題型是讀取狀態轉移圖或狀態轉移表,回答給定輸入序列後的最終狀態或輸出。輸入表格後逐一推進時刻,就能確認自己的追蹤是否正確。

相關術語

循序電路 正反器

相關計算工具

半導體、電子電路與資訊計算工具 →