下载掌阅APP，畅读海量书库
立即打开
在数字系统中，有限状态机（Finite State Machine,FSM）有着非常重要的应用。只有掌握了FSM的原理和实现方法，才能够说真正掌握了数字世界的本质。
图2.66给出了有限状态机的模型。有限状态机分为摩尔（Moore）状态机和米勒（Mealy）状态机。摩尔状态机的输出只和当前状态有关；而米勒状态机的输出不但和当前的状态有关，而且和当前的输入有关。
图2.66 有限状态机的模型
对于最简单的FSM模型来说，可以不出现输出逻辑，即可以将当前状态作为输出变量直接输出。
从宏观上来说，有限状态机由组合逻辑电路和时序逻辑电路共同组成。其中：
（1）组合逻辑电路构成下状态转移逻辑和输出逻辑，下状态转移逻辑控制数据流的方向，输出逻辑用于驱动输出每个状态所对应的输出变量。
（2）时序逻辑电路构成状态寄存器，状态寄存器是状态机中的记忆（存储）电路。
图2.67给出了一个具体的有限状态机模型，图中：
（1）下标PS表示当前的状态（Previous State, PS）。
（2）下标NS表示下一个状态（Next State, NS）。
从构成要素上来说，该状态机模型包含：
（1）输入逻辑变量的集合。在该模型中，输入逻辑变量的集合为｛I 0 ,I 1 ｝。
（2）状态集合。因为A PS ,A NS =0／1, B PS ,B NS =0／1, C PS ,C NS =0／1。所以
该状态机模型最多可以有8个状态，每个状态是状态集合｛000,001,010,011,100,101, 110,111｝中任意编码的组合。
（3）状态转移函数。用来控制下状态转移逻辑，下状态转移逻辑表示为当前状态和当前输入逻辑变量的函数，对于该模型来说：
图2.67 一个具体的有限状态机模型
C NS =f 3 （A PS B PS C PS ,I 0 ,I 1 ）
（4）输出变量集合。在该模型中，输出变量的集合为｛Y 0 ,Y 1 ,Y 2 ,Y 3 ｝。
（5）输出函数。用来确定当前状态下各输出变量的驱动电平，即输出变量可以表示为当前状态和当前输入逻辑变量的函数。对于该模型来说：
下面以图2.68所示的状态图为例，详细介绍有限状态机的实现过程。
图2.68 FSM的状态图描述
状态图是有限状态机最直观和最直接的表示方法。图2.68中：
（1）每个圆圈表示一个状态，圆圈内的二进制数表示该状态的编码组合。
（2）两个圆圈之间带箭头的连线表示从一个状态转移到另一个状态。连线上方为状态转移的条件。
（3）每个状态旁给出了当前状态下的输出变量。
从状态图中可以很直观地知道有限状态机的状态集合、输入变量和输出变量，因此只要从状态图中得到具体的状态转移函数和输出函数就可以实现有限状态机。
图2.68所示有限状态机模型的描述如下。
1）状态集合
该状态机包含4个状态，4个状态分别编码为00,01,11,10。其中：
① 状态变量A NS B NS ⊆｛00,01,10,11｝；
② 状态变量A PS B PS ⊆｛00,01,10,11｝。
2）输入变量
该状态机包含3个输入变量，即x, y, z。
3）系统的状态迁移和在各个状态下的输出描述
（1）当复位系统时，系统处于状态“00”。该状态下，驱动逻辑输出变量RED为低，驱动逻辑输出变量GRN为高。当输入变量x=0时，系统一直处于状态“00”；当逻辑输入变量x=1时，系统迁移到状态“01”。
（2）当系统处于状态“01”时，驱动逻辑输出变量RED为低，由输入变量x驱动逻辑输出变量GRN。当输入变量x=0,y=0,z=0时，系统一直处于状态“01”；当输入变量x=1或者y=1时，系统迁移到状态“00”；当输入变量x=0,y=0,z=1时，系统迁移到状态“11”。
（3）当系统处于状态“11”时，驱动逻辑输出变量RED为低，由逻辑输入变量x和y共同驱动逻辑输出变量GRN，即GRN=x·y。当输入变量x=0,y=0,z=0时，系统一直处于状态“11”；当输入变量x=1或者z=1时，系统迁移到状态“00”；当输入变量x=0,y=1, z=0时，系统迁移到状态“10”。
（4）当系统处于状态“10”时，驱动逻辑输出变量RED为高，驱动逻辑输出变量GRN为低。在该状态下，系统无条件迁移到状态“00”。
图2.69（a）和图2.69（b）分别给出了下状态编码B NS 和A NS 的卡诺图映射。下面举例说明卡诺图的推导过程。当A PS B PS =00时，表示当前的状态是“00”。要想B NS 为1，则A NS B NS 允许的编码组合为“01”或者“11”，即下一个状态是“01”或者“11”。但是，从图2.68可以看出，只存在从状态“00”到状态“01”的变化，而不存在从状态“00”到状态“11”的变化。此外，从图2.68可以看出，从状态“00”到状态“01”的转移条件是输入变量x=1，即y和z可以是全部任意组合的情况，包括“00”，“01”、“10”和“11”。所以，在图2.69（a）中，在第一行（A PS B PS =00）输入变量zyx取值分别为001、011、111和101的列下填入“1”，该行的其他列都填入“0”。
以此类推，完成图2.69下状态编码B NS 和A NS 的卡诺图映射。
状态转移函数的逻辑表达式可表示为
图2.70（a）和图2.70（b）分别给出了输出变量GRN和RED的卡诺图映射。下面举例说明卡诺图的推导过程。当A PS B PS =00时，GRN=1，与x、y、z的输入无关。
图2.69 状态转移函数的卡诺图映射
图2.70 输出变量的卡诺图映射
输出函数可用下面的逻辑表达式表示：
图2.71给出了图2.68所示状态机模型的具体实现电路。
本节将使用前面介绍的FSM实现方法设计一个三位八进制计数器。
三位八进制计数器可以从000计数到111。图2.72给出了三位八进制计数器的状态图描述。
图2.71 图2.68所示状态机模型的实现电路
图2.72 三位八进制计数器的状态图描述
在时钟的每个上升沿到来时，计数器从一个状态转移到另一个状态，计数器的输出从000递增到111，然后返回000。由于在该设计中状态编码反映了输出逻辑变量的变化规律，所以将状态编码作为逻辑变量输出。
如表2.28所示，3个触发器的输出Q 2 、Q 1 、Q 0 表示当前的状态。由下状态转移逻辑输出的状态编码组合D 2 、D 1 和D 0 确定下一个状态。
表2.28 三位计数器状态转移关系
注 ：D触发器任意时刻的输入包含下一个计数值，因此在下一个时钟上升沿，这个值就锁存到Q，计数器的值将递增1。
如图2.73所示，通过化简卡诺图，得到状态转移逻辑的表达式为
图2.74给出了使用基本逻辑门和D触发器芯片所构建的三位八进制计数器，图2.75给出了对该电路执行SPICE瞬态分析的结果，从分析结果可知该设计的正确性。
注 ：读者进入本书配套提供例子的＼eda_verilog＼counter_3b.ms14路径下，用Multisim 14工具打开该设计，执行SPICE瞬态仿真，观察仿真结果。
图2.73 状态编码的卡诺图映射
图2.74 使用基本逻辑门和D触发器芯片所构建的三位八进制计数器
图2.75 对图2.74所示的电路执行SPICE瞬态分析的结果
思考与练习2-16： 如图2.76所示，为下面的状态图分配状态编码，并说明编码规则。
图2.76 需要编码的状态图
思考与练习2-17： 如图2.77所示，设计实现该状态图的FSM。
图2.77 状态图描述
思考与练习2-18： 如图2.78所示，设计实现该计数功能的计数器。
图2.78 计数器的状态图描述
思考与练习2-19： 将上题的计数值显示在共阳／共阴极七段数码管上。