數位電路/最佳化
< 數位電路
雖然設計良好的狀態機具有明確的行為，但可以有多種方法來實現相同的行為。考慮以下兩種有限狀態機。
一般來說，我們希望找到具有最少狀態的有限狀態機實現，因此需要最少的資源，無論是 ROM 裝置的大小還是 FPGA 中的 LE。
蘊涵圖是簡化有限狀態機的常用方法。它的工作原理是找到具有相同轉換的那些狀態。它是一種適合用手快速計算的圖形方法。
首先，讓我們考慮一個大小為 N×N 的網格，其中 N 是狀態數。每個單元格代表一對狀態。由於這是一個無序對，單元格 (i, j) 等效於 (j,i)，因此可以省略（綠色方塊）。此外，狀態當然等效於自身（藍色方塊）。然後，我們可以消除右上角三角形和對角線。對於七狀態機，我們將有以下蘊涵圖輪廓
注意，每個方向都有 N−1 個方塊，並且在任何單元格中，M<N。
為了開始最佳化有限狀態機，我們需要一個狀態轉換表。對於這個例子，我們將以實現以下內容的有限狀態機為例
| 當前狀態 | 下一狀態 | 輸出 | ||
|---|---|---|---|---|
| 輸入 X | 輸入 X | |||
| 0 | 1 | 0 | 1 | |
| 0 | 7 | 2 | 0 | 0 |
| 1 | 7 | 5 | 0 | 0 |
| 2 | 7 | 0 | 1 | 0 |
| 3 | 0 | 7 | 1 | 0 |
| 4 | 3 | 6 | 0 | 0 |
| 5 | 3 | 1 | 1 | 0 |
| 6 | 3 | 4 | 1 | 0 |
| 7 | 4 | 3 | 1 | 0 |
- 繪製蘊涵圖。您為每種可能的州組合都有一個單元格。目標是消除所有非等效的狀態對。透過在單元格中“標記”十字來表示消除。一旦所有非等效狀態都被移除，所有剩餘的狀態對都必須是等效的。
- 第一步是遍歷蘊涵圖中的每個單元格。對於每個單元格，參考狀態轉換表中的兩個狀態，並檢視每個輸入的輸出。
- 如果輸出不同，則在單元格中放置一個十字。檢視每個輸入的輸出 - 它們必須相同。如果狀態具有不同的輸出，則它們不可能是等效的。
- 如果輸出相同，則狀態可能是等效的 - 如果下一狀態也相同，則會發生這種情況。在單元格中，寫下由該單元格表示的兩個狀態的下一狀態。例如，如果單元格 (2,5)
- 對於輸入 X=0：狀態 2 → 7，狀態 5 → 3。
- 對於輸入 X=1：狀態 2 → 0，狀態 5 → 1。
- 因此，我們在單元格 (2,5) 的頂部寫“7−3”，在底部寫“0−1”。我們正在為每個輸出寫入下一狀態對。下面的圖 1 顯示了此階段結束時蘊涵圖。
- 下一步是再次遍歷圖表。這次我們檢視每個未標記單元格中列出的狀態對。分別考慮每個下一狀態對。如果表示下一狀態對的單元格已被標記，則也標記當前狀態（您可能需要反轉狀態的順序）。如果任何下一狀態對不等效，則當前狀態也不等效。如果單元格包含條目“i−i”，則忽略它，因為狀態必須等效於自身。例如
- 對於輸入 0：狀態 3 → 0，狀態 5 → 3。
- 對於輸入 1：狀態 3 → 7，狀態 5 → 1。
- 現在，狀態 0 和 3 不等效（呼叫 (0,3) 已被標記）。現在，如果下一狀態不等效，則當前狀態也不等效。因此，我們標記 (3,5)。圖 2 顯示了第一次通過後的結果，新標記以紅色顯示。
- 重複步驟 3，直到檢查所有未標記的單元格，並且無法標記任何單元格。在本例中，這種情況已經發生。
- 現在，搜尋每個未標記的單元格 (i, j)。寫下方程“i = j”。如果您已經將其中一項放入方程中，而沒有另一項，則將其新增到該方程中。在本例中
- 0=1=4
- 2=5=6
- 3=7
- 我們現在已經將狀態機減少到更少的州（從八個減少到三個）。
| 圖 1 | 圖 2 |
|---|---|
|
|
我們可以使用每個方程中只使用一個（等效）狀態來編寫新的狀態轉換表 - 我們將選擇 0、2 和 3。您選擇哪個並不重要，並且您可以在之後重新編號，但在這裡我們不打算這樣做。
| 當前狀態 | 下一狀態 | 輸出 | ||
|---|---|---|---|---|
| 輸入 X | 輸入 X | |||
| 0 | 1 | 0 | 1 | |
| 0 | 3 | 2 | 0 | 0 |
| 2 | 3 | 0 | 1 | 0 |
| 3 | 0 | 3 | 1 | 0 |
