数字电路/优化
< 数字电路
虽然设计良好的状态机具有明确的行为，但可以有多种方法来实现相同的行为。考虑以下两种有限状态机。
一般来说，我们希望找到具有最少状态的有限状态机实现，因此需要最少的资源，无论是 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 |
