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