第2章-数字逻辑电路(第4讲)-2.4

数字逻辑基础主

讲：何宾

Email ：hebin@http://www.77cn.com.cn

2018.08LOGO

有限自动状态机

--重要性

在数字系统中，有限自动状态机（Finite State Machine,FSM ）有着非常重要的应用。只有掌握了FSM 的原理和实现方法，才能说真正的掌握了数字世界的本质。

有限自动状态机

--有限自动状态机原理

有限状态机分为摩尔（Moore ）状态机和米勒（Mealy ）状态机。

?摩尔状态机的输出只和当前状态有关；

?而米勒状态机的输出不但和当前的状态有关，而且和当前的输入有关。

有限自动状态机

--有限自动状态机原理

有限自动状态机

--有限自动状态机原理

有限自动状态机从宏观上来说，是由组合逻辑电路和时序逻辑电路共同组成的。其中：

?组合逻辑电路构成下状态转移逻辑和输出逻辑电路。下状态转移逻辑控制数据流的方向。

?时序逻辑电路构成状态寄存器。状态寄存器是状态机中的“记忆”（存储）电路。

有限自动状态机

--有限自动状态机原理

有限自动状态机

--有限自动状态机原理

状态机要素：

?输入逻辑变量的集合

在该模型中，输入逻辑变量集合为：{I0，I1}。?状态集合

}

1,0{,∈PS NS A A }

1,0{,∈PS NS B B }

1,0{,∈PS NS C C }

111,110,101,100,011,010,001,000{∈PS PS PS C B A }111,110,101,100,011,010,001,000{∈NS NS NS C B A ∵∴

有限自动状态机

--有限自动状态机原理

?状态转移函数

?用来控制下状态转移逻辑，状态转移可以表示为输入为当前的状态和当前的输入逻辑变量的函数，对于该模型：

)

,,(101I I C B A f A PS PS PS NS =)

,,(102I I C B A f B PS PS PS NS =),,(103I I C B A f C PS PS PS NS =

有限自动状态机

--有限自动状态机原理

?输出变量集合

?在该模型中，输出变量集合为{Y0,Y1,Y2,Y3}。

?输出函数

?用来确定在当前状态下，各个输出逻辑变量的值，即：输出可以表示为当前状态和当前输入逻辑变量的函数。对于该模型来说，输出函数可以表示如下：

)

,(110I C B A h Y PS PS PS =)

,(121I C B A h Y PS PS PS =)

,(132I C B A h Y PS PS PS =),(143I C B A h Y PS PS PS =

有限自动状态机

--状态图表示及实现

状态机的状态图表示状态图是有限状态机最直观和最直接的表示方法。图中：

?每个圆圈表示一个状态，圆圈内的二进制数的组合表示该状态的编码。

?两个圆圈之间的连线表示从一个状态转移到另一个状态。连线上方为状态转移条件。

?每个状态旁，给出了当前状态的输出变量。

有限自动状态机

--状态图表示及实现

有限自动状态机的状态图描述

有限自动状态机

--状态图表示及实现

该有限自动状态机模型描述如下：

?状态集合

?该状态机包含四个状态，四个状态分别编码为：00,01,11,10。其中：

?状态变量

?状态变量?输入变量

?该状态机中包含三个输入变量，即：x ，y ，z 。}11,10,01,00{B A NS NS ?}

11,10,01,00{B A PS PS ?

有限自动状态机

--状态图表示及实现

?系统的状态迁移和在各个状态下的输出描述为：

?当复位系统时，系统处于状态“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”。

有限自动状态机

--状态图表示及实现

推导状态转移函数

_________________z y x B y x B A x B A B PS PS PS PS PS NS ???+???+??=___

_____

z x B A z y x B A A PS PS PS PS NS ???+????=

有限自动状态机

--状态图表示及实现推导输出函数

y x B x A B A GRN PS PS PS PS ??+?+?=________

________

PS PS B A RED ?=