状态机及其VHDL设计.doc

第7章　状态机及其VHDL设计
内容提要：有限状态机（Finite State Machine，简称FSM）是一类很重要的时序电路，是许多数字系统的核心部件，也是实时系统设计中的一种数学模型，是一种重要的、易于建立的、应用比较广泛的、以描述控制特性为主的建模方法，它可以应用于从系统分析到设计的所有阶段。有限状态机的优点在于简单易用，状态间的关系清晰直观。建立有限状态机主要有两种方法：“状态转移图”和“状态转移表”。标准状态机通常可分为Moore和Mealy两种类型。本章主要介绍了基于VHDL的常见有限状态机的类型、结构、功能及表达方法，重点是如何有效地设计与实现。
学习要求：了解状态机的基本结构、功能和分类，掌握有限状态机的一般设计思路与方法、状态机编码方案的恰当选取、Moore和Mealy状态机的本质区别及设计实现。
关 键 词：状态机(State Machine)，Moore，Mealy，VHDL设计(VHDL Design)
7.1 状态机的基本结构和功能
7.2　一般状态机的VHDL设计
7.2.1 状态机的一般组成
7.2.2 状态机的编码方案
7.3　摩尔状态机的VHDL设计
7.4　米立状态机的VHDL设计
7.1 状态机的基本结构和功能
状态机的基本结构如图7.1所示。除了输人信号、输出信号外，状态机还包含一组寄存器记忆状态机的内部状态。状态机寄存器的下一个状态及输出，不仅同输入信号有关，而且还与寄存器的当前状态有关，状态机可以认为是组合逻辑和寄存器逻辑的特殊组合。它包括两个主要部分：即组合逻辑部分和寄存器。组合逻辑部分又可分为状态译码器和输出译码器，状态译码器确定状态机的下一个状态，即确定状态机的激励方程，输出译码器确定状态机的输出，即确定状态机的输出方程。寄存器用于存储状态机的内部状态。
输出

输入

状态
译码器

状态
寄存器

状态

图7.1　状态机的基本结构

状态机的基本操作有两种：
1．状态机的内部状态转换。
状态机经历一系列状态，下一状态由状态译码器根据当前状态和输入条件决定。
2．产生输出信号序列。
输出信号由输出译码器根据当前状态和输入条件确定。
用输入信号决定下一状态也称为“转移”。除了转移之外，复杂的状态机还具有重复和历程功能。从一个状态转移到另一状态称为控制定序，而决定下一状态所需的逻辑称为转移函数。
在产生输出的过程中，根据是否使用输入信号可以确定状态机的类型。两种典型的状态机是米立（Mealy）状态机和摩尔（Moore）状态机。摩尔状态机的输出只是当前状态的函数，而米立状态机的输出一般是当前状态和输入信号的函数。对于这两类状态机，控制定序都取决于当前状态和输入信号。大多数实用的状态机都是同步的时序电路，由时钟信号触发进行状态的转换。时钟信号同所有的边沿触发的状态寄存器和输出寄存器相连，使状态的改变发生在时钟的上升或下降沿。

在数字系统中．那些输出取决于过去的输入和当前的输入的部分都可以作为有限状态机。有限状态机的全部“历史”都反映在当前状态上。当给FSM一个新的输入时，它就会产生一个输出。输出由当前状态和输入共同决定，同时FSM也会转移到下一个新状态，也是随着FSM的当前状态和输入而定。FSM中，其内部状态存放在寄存器中，下一状态的值由状态译码器中的一个组合逻辑——转移函数产生，状态机的输出由另一个组合逻辑——输出函数产生。
建立有限状态机主要有两种方法：状态转移图（状态图）和状态转移表（状态表）。它们是等价的，相互之间可以转换。
状态转移图　如图7.2所示，图中每个椭圆表示状态机的一个状态，而箭头表示状态之间的一个转换，引起转换的输入信号及当前输出表示在转换箭头上。
摩尔状态机和米立状态机的表示方法不同，摩尔状态机的状态译码输出写在状态圈内，米立状态机的状态译码输出写在箭头旁，如图7.3所示。
输入/出

输入/出

输入/出

输入/出

输入/出

输入/出

状态A

状态B

状态C

状态D

状态E

状态B
01

状态A
00

I/01

状态A

状态B

图7.2 状态转移图

图7.3　摩尔和米立状态机

如果能够写出FSM的状态转移图，就可以使用VHDL的状态机语句对它进行描述。
状态转移表　形式如表7.1所示。表中的行列出了全部可能的输入信号组合和内部状态以及相应的次状态和输出，因此状态表规定了状态机的转换函数和输出函数。然而，状态表不适合具有大量输入的系统，因为随着输入的增加其状态数和系统的复杂性会显著增加。
表7.1 状态转移表
现态
输入
次态
输出
S0-Sn
I0-Im
S0-Sn
Q0-QP

状态转移图、状态转移表这两种有限状态机的建立方法是等价的，都描述了同一硬件结构，它们可以相互转换，但各有优缺点，分别适合于不同场合。
7.2　一般状态机的VHDL设计
7.2.1 状态机的一般组成
用VHDL设计有限状态机方法有多种，但最一般和最常用的状态机设计通常包括说明部分，主控时序部分，主控组合部分和辅助进程部分。
1) 说明部分
说明部分中使用TYPE语句定义新的数据类型，此数据类型为枚举型，其元素通常都用状态机的状态名来定义。状态变量定义为信号，便于信息传递，并将状态变量的数据类型定义为含有既定状态元素的新定义的数据类型。说明部分一般放在结构体的ARCHITECTURE和BEGIN之间。
2) 主控时序进程
是指负责状态机运转和在时钟驱动正负现状态机转换的进程。状态机随外部时钟信号以同步方式工作，当时钟的有效跳变到来时，时序进程将代表次态的信号next_state中的内容送入现态信号current_state中，而next_state中的内容完全由其他进程根据实际情况而定，此进程中往往也包括一些清零或置位的控制信号。
3) 主控组合进程
根据外部输入的控制信号（包括来自外部的和状态机内容的非主控进程的信号）或（和）当前状态值确定下一状态next_state的取值内容，以及对外或对内部其他进程输出控制信号的内容。
4) 辅助进程
用于配合状态机工作的组合、时序进程或配合状态机工作的其他时序进程。
在一般状态机的设计过程中，为了能获得可综合的，高效的VHDL状态机描述，建议使用枚举类数据类型来定义状态机的状态，并使用多进程方式来描述状态机的内部逻辑。例如可使用两个进程来描述，—个进程描述时序逻辑，包括状态寄存器的工作和寄存器状态的输出，另一个进程描述组合逻辑，包括进程间状态值的传递逻辑以及状态转换值的输出。必要时还可以引入第三个进程完成其它的逻辑功能。
下例描述的状态机由两个主控进程构成，其中进程REG为主控时序进程，COM为主控组合进程。
[例7.1]
LIBRARY IEEE;
USE IEEE.STD_LOGIC_1164.ALL;
ENTITY s_machine IS
PORT (clk, reset: IN STD_LOGIC;
State_inputs: IN STD_LOGIC_VECTOR(0 TO 1);
comb_outputs: OUT STD_LOGIC_VECTOR(0 TO 1));
END ENTITY s_machine;

ARCHITECTURE behv OF s_machine IS
TYPE states IS (st0,st1,st2,st3);--定义states为枚举型数据类型
SIGNAL current_state, next_state : states;
BEGIN

REG: PROCESS (reset, clk) --时序逻辑进程
BEGIN

IF reset='1' THEN　　　--异步复位
Current_state<=st0;
ELSIF clk='1' AND clk'EVENT THEN
current_state<=next_state;
--当检测到时钟上升沿时转换至下一状态
END IF;
END PROCESS;
--由信号current_state将当前状态值带出此进程，进入进程COM

COM: PROCESS(current_state, state_Inputs) --组合逻辑进程
BEGIN
CASE current_state IS -- 确定当前状态的状态值
WHEN st0 =>comb_outputs <= "00"; --初始状态译码输出"00"
IF state_inputs="00" THEN
--根据外部的状态控制输入"00"
next_state<=st0;
--在下一时钟后，进程REG的状态将维持为st0
ELSE
nextstate<=st1;
--否则，在下一时钟后，进程REG的状态将为st1
END IF;
WHEN st1=> comb_outputs<="01";
--对应状态st1的译码输出"01"
IF state_inputs="00" THEN
--根据外部的状态控制输人"00"
next_state<=st1;
--在下一时钟后，进程REG的状态将维持为st1
ELSE
next_state<=st2;
-- 否则，在下一时钟后，进程REG的状态将为st2
END IF;
WHEN st2=> comb_outputs<="10"; --以下依次类推
IF state_inputs="11" THEN
next_state<=st2;
ELSE
next_state<=st3;
END IF;
WHEN st3=>comb_outputs<="11";
IF state_inputs="11" THEN
next_state<=st3;
ELSE
next_state<=st0;
END IF;
END CASE;
END PROCESS;
END ARCHITECTURE behv;
图7.4为上述状态机的工作时序图。reset为异步复位信号，低电平有效，而clk为上升沿有效。如在第3个脉冲上升沿到来时current_state=“st0”，state_inputs＝“01”，输出comb_outputs=“01”。第4个脉冲上升沿到来时current_state=“st1”，state_inputs＝“00”，输出comb_outputs=“01”。综合后的RTL图如图7.5所示。

图7.4 例7.1状态机的工作时序图

图7.5　例7.1状态机的RTL图

一般来说，程序的不同进程间是并行运行的，但由于敏感信号设置的不同和电路的延迟，在时序上进程间的动作是有先后的。如对上例中的状态转换行为来说，有进程REG和COM，它们的敏感信号表分别为（reset,clk）和（current_state,state_inputs），在clk上升沿到来时，进程REG将首先运行，完成状态转换的赋值操作。如果外部控制信号state_inputs不变，只有当来自进程REG的信号current_state改变时，进程COM才开始动作，并将根据current_state和state_inputs的值来决定下一有效时钟沿到来后，进程REG的状态转换方向。这个状态机的两位组合逻辑输出comb_outputs是对当前状态的译码。我们可以通过这个输出值来了解状态机内部的运行情况，同时还可以利用外部控制信号state_inputs任意改变状态机的状态变化模式。
注意：在上例中，有两个信号起到了互反馈的作用，完成了两个进程间的信息传递的功能，这两个信号分别是current_state〔进程REG－>进程COM)和next_state(进程COM－>进程REG)。
在VHDL中可以有两种方式来创建反馈机制：即使用信号的方式和使用变量的方式。通常倾向于使用信号的方式（如例7.1）。一般而言，在进程中使用变量传递数据，然后使用信号将数据带出进程。在设计过程中，如果希望输出的信号具有寄存器锁存功能，则需要为此输出写第3个进程，并把clk和reset信号放入敏感信号表中。但必须注意避免由于寄存器的引入而创建了不必要的异步反馈路径。根据VHDL综合器的规则，对于所有可能的输入条件，如果进程中的输出信号没有被明确的赋值时，此信号将自动被指定，即在未列出的条件下保持原值，这就意味着引入了寄存器。因此，我们在程序的综合过程中，应密切注意VHDL综合器给出的警告信息，并根据警告信息对程序作必要的修改。
一般来说，利用状态机进行设计有如下几个步骤：
(1) 分析设计要求，列出状态机的全部可能状态，并对每一个状态进行编码。
(2) 根据状态转移关系和输出函数画出状态转移图。
(3) 由状态转移图，用VHDL语句对状态机描述。
7.2.2 状态机的编码方案
在状态机的编码方案中，有两种重要的编码方法：二进制编码和一位热码(One—Hot)编码。

在二进制编码的状态机中，状态位(B)与状态(S)的数目之间的关系为B=log2S，如两位状态位就有00，01，10，11四个不同状态，它们在不同的控制信号下可以进行状态转换，但如果各触发器又没有准确地同时改变其输出值，那么在状态01变到10时则会出现暂时的11或00状态输出，这类险象可能使整个系统造成不可预测的结果。这时，采用格雷码二进制编码是特别有益，在该编码方案中，每次仅一个状态位的值发生变化。
一位热码编码就是用n个触发器来实现n个状态的编码方式，状态机中的每一个状态都由其中一个触发器的状态来表示。如4个状态的状态机需4个触发器，同一时间仅一个状态位处于逻辑1电平，四个状态分别为：0001、0010、0100、1000。
在实际应用中，根据状态机的复杂程度、所使用的器件系列和从非法状态退出所需的条件来选择最适合的编码方案，使之能确保高效的性能和资源的利用。
对复杂的状态机，二进制编码需用的触发器的数目比一位热码编码的少。如100个状态的状态机按二进制编码仅用7个触发器就可以实现，而一位热码编码则要求100个触发器。另一方面，虽然一位热码编码要求用较多的触发器，但逻辑上通常相对简单些。在二进制编码的状态机中，控制从一个状态转换到另一个状态的逻辑与所有7个状态位以及状态机的输入均有关。这类逻辑通常要求到状态位输入的函数是多输入变量的。然而，在一热恋位编码的状态机中，到状态位的输入常常是其它状态位的简单函数。
站在器件结构的角度，不同结构支持其确定的编码类型。MAX+plus II编译程序对所采用的器件系列自动地选择最合适的编码方法（除非在设计文件中规定了具体的编码方案）。例如，FLEX 7000器件系列是寄存器增强型（Register-intensive），以这类器件为对象的状态机最好选用一位热码编码方案来实现。由于一位热码编码的状态机降低了送到每一个状态位的逻辑电路的复杂程度，因而可提高用FLEX 7000器件实现的状态机的性能。MAX 5000和MAX 7000器件系列最适合二进制状态机编码方案。这两类器件都能够利用共享和并联的扩展乘积项有效地实现复杂的逻辑函数。因此，在这两类器件小，可以容纳复杂的组合逻辑函数而不会浪费资源或损失性能。
另外，在选择编码方案时，必须考虑状态机可能进入的潜在的非法状态的数目。如果违反了状态位触发器的建立或保持时间，又没有定义所有可能出现的状态，则你的设计会终止在非法状态上。MAX+plus II设计进入方法允许你定义非法状态和规定你的状态机如何从非法状态中退出。例如，用二进制编码实现一个14个状态的状态机需4个状态位。这将有16个可能的状态，故该状态机仅有两个可能的状态是非法状态。然而一位热码编码的状态机通常有更多的潜在的非法状态。14个状态的一位热码编码的状态机需要14个状态。一位热码编码的状态机的非法状态数目由方程式（2n－n）确定，其中n为状态机的状态个数。因此，一位热码编码的14位状态共有16370个可能的非法状态。然而，只要设计中不违反状态位触发器的建立和保持时间，状态机将不会进入非法状态。

7.3　摩尔状态机的VHDL设计
摩尔有限状态机输出只与当前状态有关，与输入信号的当前值无关，是严格的现态函数。在时钟脉冲的有效边沿作用后的有限个门延后，输出达到稳定值。即使在时钟周期内输入信号发生变化，输出也会保持稳定不变。从时序上看，Moore状态机属于同步输出状态机。Moore有限状态机最重要的特点就是将输入与输出信号隔离开来。例7.2就是一个典型的Moore型状态机实例。
状态机的状态图如图7.6所示。
0

0

1

1

S1
0001

S4
1000

S2
0010

S3
0100

图7.6　Moore状态机的状态图

[例7.2]
LIBRARY ieee;
USE ieee.std_logic_1164.ALL;
USE ieee.std_logic_unsigned.ALL;
ENTITY moore IS
PORT ( clk, datain, reset : IN std_logic;
dataout : OUT std_logic_vector (3 DOWNTO 0));
END ENTITY moore;

ARCHITECTURE arc OF moore IS
TYPE state_type IS (s1, s2, s3, s4);
SIGNAL state: state_type;
BEGIN
state_process: PROCESS (clk, reset) --时序逻辑进程
BEGIN
IF reset='1' THEN --异步复位
state<=s1;
ELSIF clk'event and clk='1' THEN
--当检测到时钟上升沿时执行CASE语句
CASE state IS
WHEN S1=>IF datain='1' THEN
state<=s2;
END IF;
WHEN s2=>IF datain='0' THEN
state<=s3;
END IF;
WHEN s3=>IF datain='1' THEN
state <=s4;
END IF;
WHEN s4=>IF datain='0' THEN
state <=s1;
END IF;
END CASE;
END IF;
END PROCESS; --由信号state将当前状态值带出此进程，进入进程output_p

output_p : PROCESS (state) --组合逻辑进程
BEGIN
CASE state IS -- 确定当前状态值
WHEN s1=>dataout<="0001"; --对应状态s1的数据输出为"0001"
WHEN s2=>dataout<="0010";
WHEN s3=>dataout<="0100";
WHEN s4=>dataout<="1000";
END CASE;
END PROCESS;
END ARCHITECTUR arc;

上例的VHDL描述中包含了两个进程：state_process和output_p，分别为时序逻辑进程和组合逻辑进程。图7.7是例7.2的工作时序图，由图可见，状态机在异步复位信号后state=s1，在第500ns有效上升时钟沿到来时，state=s1，datain=1，从而state由s1转换为s2，输出dataout0010，即使在500ns后的一个时钟周期内输入信号发生变化，输出也会维持稳定不变。综合后的结果见图7.8所示。

图7.7　Moore的工作时序图

图7.8　Moore的RTL图
7.4　米立状态机的VHDL设计
Mealy状态机的输出是现态和所有输入的函数，随输入变化而随时发生变化。从时序上看，Mealy状态机属于异步输出状态机，它不依赖于时钟，但Mealy状态机和Moore状态机的设计基本上相同。例7.2就是一个典型的Mealy型状态机实例。
状态机的状态图如图7.9所示。

1/0001

0/0001

0/0000

1/0001

0/1000

0/0010

1/0100

1/0001

S1

S4

S2

S3

图7.9　Moore状态机的状态图

例[7.3]
LIBRARY ieee;
USE ieee.std_logic_1164.ALL;
USE ieee.std_logic_unsigned.ALL;
ENTITY mealy IS
PORT ( clk, datain, reset : IN std_logic;
dataout : OUT std_logic_vector (3 DOWNTO 0));
END ENTITY mealy;

ARCHITECTURE arc OF mealy IS
TYPE state_type IS (s1, s2, s3, s4);
SIGNAL state : state_type;
BEGIN
state_process : PROCESS (clk, reset) --时序逻辑进程
BEGIN
IF reset='1' THEN --异步复位

state<=s1;
ELSIF clk'event and clk='1' THEN
--当检测到时钟上升沿时执行CASE语句
CASE state IS
WHEN S1=>IF datain='1' THEN
state<=s2;
END IF;
WHEN s2=>IF datain='0' THEN
state<=s3;
END IF;
WHEN s3=>IF datain='1' THEN
state <=s4;
END IF;
WHEN s4=>IF datain='0' THEN
state <=s1;
END IF;
END CASE;
END IF;
END PROCESS;

output_p : PROCESS (state) --组合逻辑进程
BEGIN
CASE state IS -- 确定当前状态值
WHEN s1=>
IF datain='1' THEN dataout<="0001";
ELSE dataout<="0000";
END IF;
WHEN s2=>
IF datain='0' THEN dataout<="0010";
ELSE dataout<="0001";
END IF;
WHEN s3=>
IF datain='1' THEN dataout<="0100";
ELSE dataout<="0001";
END IF;
WHEN s4=>
IF datain='0' THEN dataout<="1000";
ELSE dataout<="0001";
END IF;
END CASE;
END PROCESS;
END ARCHITECTURE arc;

上例的VHDL描述中包含了两个进程：state_process和output_p，分别为主控时序逻辑进程和组合逻辑进程。图7.10是例7.3的工作时序图，由图可见，状态机在异步复位信号来到时，datain=1，输出dataout=0001，在clk的有效上升沿来到前，datain发生了变化，由1－>0，输出dataout随即发生变化，由0000－>0001，反映了Mealy状态机属于异步输出状态机而它不依赖于时钟的鲜明特点。综合后的结果见图7.11所示。
Mealy状态机的VHDL结构要求至少有两个进程，或者是一个状态机进程加一个独立的并行贩值语句。

图7.10　Mealy的工作时序图

图7.11　Mealy的RTL图

（注：专业文档是经验性极强的领域，无法思考和涵盖全面，素材和资料部分来自网络，供参考。可复制、编制，期待你的好评与关注）