下列哪一項是對序向電路的正確說明?
- A輸出由目前的輸入與所記憶的內部狀態決定
- B輸出僅由目前的輸入決定
- C只處理類比訊號
輸入循序電路(狀態機)的狀態轉移表,即可繪製狀態轉移圖,並追蹤狀態與輸出如何隨輸入序列變化。可以從「連續 2 個 1 就輸出 1」「偵測 101」「二進位數除以 3 的餘數」等範例開始,一邊修改表格一邊確認動作。也會顯示狀態最小化的結果,找出功能相同的狀態並加以合併。
收藏與最近使用的工具只儲存在這個瀏覽器(localStorage)中。
從第一列的狀態開始。摩爾型在各時刻的輸出,顯示的是讀入輸入後所轉移到的狀態的輸出。圖中的紅色箭頭是所選時刻的轉移。
其他輸入維持目前的值,只讓選擇的輸入在目前值的 1/4 到 4 倍之間變化時的結果。紅點是目前的值。
含有正反器的循序電路,會把過去的輸入記成「狀態」,並由目前的狀態與輸入決定下一個狀態與輸出。把這種動作以圓圈表示狀態、以箭頭表示轉移畫成的圖,就是狀態轉移圖;整理成表格則是狀態轉移表。例如「連續 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。
若希望輸出與時脈同步、保持穩定,適合摩爾型;若想減少狀態數,或希望對輸入立即反應,則適合米利型。考試中可依輸出是寫在圓圈內還是箭頭上,判斷所給的圖屬於哪一型。
摩爾型即使在尚未讀入任何輸入的時刻 0,也會輸出初始狀態的輸出。本工具的「輸出序列」只列出讀入輸入之後的輸出。米利型的輸出要有輸入才會決定,因此時刻 0 沒有輸出。
最多 8 個。輸入只有 0 與 1 兩種。狀態名稱可自由設定,最多 6 個字元,也會反映在下一個狀態的選項中。
在日本的基本資訊技術士考試、應用資訊技術士考試等資訊類證照考試中,常見的題型是讀取狀態轉移圖或狀態轉移表,回答給定輸入序列後的最終狀態或輸出。輸入表格後逐一推進時刻,就能確認自己的追蹤是否正確。