第七章有限状态机的设计

第7章

有限状态机的设计主要内容状态机的概述

概念、优点、分类MOORE（摩尔）型状态机MEALY（米利）型状态机状态编码非法状态一、什么是状态机？先看一个例子—设计一个六进制约翰逊计数器什么叫做约翰逊计数器？

一般的二进制计数器或十进制计数器,由于在每次计数时常有不止一位触发器翻转,以至于发生竞争冒险现象,造成误译动作.为了消除这种干扰，采用每次仅有一位触发器反转的计数器，称为约翰逊计数器一、什么是状态机？（续1）libraryieee;useieee.std_logic_1164.all;entityjh_cntis port(clk,reset:instd_logic; q:outstd_logic_vector(3downto0));end;architectureoneofjh_cntis typestateis(s0,s1,s2,s3,s4,s5); signalcurrent_state,next_state:state;beginreg:process(clk,reset)begin ifreset='1'thencurrent_state<=s0; elsifclk'eventandclk='1'then current_state<=next_state; endif;endprocess;自定义数据类型state，枚举类型主控时序进程在时钟驱动下，负责状态转换，但是不负责下一状态的具体状态取值一、什么是状态机？（续2）com:process(current_state)begin casecurrent_stateis whens0=>q<="0000";next_state<=s1; whens1=>q<="0001";next_state<=s2; whens2=>q<="0011";next_state<=s3; whens3=>q<="0111";next_state<=s4; whens4=>q<="0110";next_state<=s5; whens5=>q<="0100";next_state<=s0; endcase;endprocess;end;主控组合进程纯组合电路，决定每一状态下的输出和下一状态的具体取值一、什么是状态机？（续3）就理论而言，任何一个时序模型的电路系统都可以归结为一个状态机。把该电路系统分为有限个状态。在任意时刻，只能处于有限状态中的一个，在接受到一个输入事件时，状态机产生一个输出，同时伴随着状态的转移。有限状态机（FSM，FiniteStateMachine）是一种基本的、简单的、重要的形式化技术。是数字逻辑的另一种表示方法与一种设计思想。VHDL程序设计的FSM有如下优点：设计方案相对固定，程序层次分明，结构清晰，特别是可以定义为符号化枚举类型的状态，使VHDL综合器对状态机具有很大的优化功能。

容易构成性能良好的同步时序模块，容易消除电路中的毛刺现象。由纯硬件组成，工作方式是根据控制信号按照预先设定的状态进行顺序运行，使其运行速度和可靠性较好。

二、状态机的分类按照不同的分类方法有不同类型的状态机按状态机的信号输出方式分MOORE型状态机MEALY型状态机输出由当前状态所决定输出由当前状态和输入共同决定二、状态机的分类（续1）按结构分单进程状态机（一段式）多进程状态机（两段式、三段式）主控时序进程主控组合进程决定下一状态的具体取值每一个状态的输出二、状态机的分类（续2）按状态的表达方式上分符号化状态机以文字符号代表每一个状态，在实际电路中是以二进制组合来表示，由综合器根据优化情况来确定编码确定状态编码的状态机在定义状态时，就人为的将状态的编码确定下来，可以采用的编码形式有：状态位直接输出型编码、顺序码、格雷码、一位热码等例：CONSTANTs0:std_logic_vector(1downtown0)：=“00”；CONSTANTs1:std_logic_vector(1downtown0)：=“01”；CONSTANTs2:std_logic_vector(1downtown0)：=“10”；二、状态机的分类（续3）按时钟分同步输出状态机由时钟信号控制异步输出状态机没有经过时钟而直接输出一般情况下，速度快于同步状态机，仅仅档状态机的性能要求高时，才选择三、MOORE型状态机输出仅和状态有关，因此状态机的输出信号就写在表示状态的圆圈之中。状态转移图例1：实现下图所示状态机设计三、MOORE型状态机（续1）entityd2mooreisport(clk,a,reset:instd_logic;q:outstd_logic_vector(3downto0));end;p0:process(reset,clk)beginifreset='1'thencurrent_state<=st0;elsifclk'eventandclk='1'thencurrent_state<=next_state;endif;endprocess;p1:process(current_state)begincasecurrent_stateiswhenst0=>q<="0000";whenst1=>q<="1001";whenst2=>q<="1100";whenst3=>q<="1111";endcase;endprocess;时钟上升沿到来时，完成状态转移决定每一状态下的输出三、MOORE型状态机（续2）p2:process(current_state,a)begincasecurrent_stateiswhenst0=>ifa='1'thennext_state<=st1;elsenext_state<=st0;endif;whenst1=>ifa='0'thennext_state<=st2;elsenext_state<=st1;endif;whenst2=>ifa='1'thennext_state<=st3;elsenext_state<=st2;endif;whenst3=>ifa='0'thennext_state<=st0;elsenext_state<=st3;endif;endcase;endprocess;end;决定下一状态的具体取值三段式、MOORE型状态机返回三、MOORE型状态机（续3）由软件自动生成状态转移图TOOLS—NETLISTVIEWERS三、MOORE型状态机（续4）三、MOORE型状态机（续5）波形仿真结果异步复位三、MOORE型状态机（续6）architectureoneofd1mooreistypestypeis(st0,st1,st2,st3);signalstate:stype;beginp0:process(reset,clk)beginifreset='1'thenstate<=st0;elsifclk'eventandclk='1'thencasestateiswhenst0=>q<="0000";ifa='1'thenstate<=st1;elsestate<=st0;endif;whenst1=>q<="1001";ifa='0'thenstate<=st2;elsestate<=st1;endif;whenst2=>q<="1100";ifa='1'thenstate<=st3;elsestate<=st2;endif;whenst2=>q<="1100";ifa='1'thenstate<=st3;elsestate<=st2;endif;whenst3=>q<="1111";ifa='0'thenstate<=st0;elsestate<=st3;endif;endcase;endif;endprocess;end;返回返回1三、MOORE型状态机（续7）单进程MOORE状态机多进程MOORE状态机next_state<=st1current_state<=st1q<=“1001”q<=“0000”state<=st1;示例示例三、MOORE型状态机（续8）单进程MOORE状态机多进程MOORE状态机毛刺三、MOORE型状态机（续9）总结单进程状态机的特点输出端得到的信号值要比多进程晚一个时钟周期能够减少输出信号波形的毛刺现象四、MEALY型状态机例2：实现下图所示状态机设计输出由当前状态和输入信号决定，所以输出信号写在箭头转移处四、MEALY型状态机（续1）architectureoneofd2mealyis typestypeis(st0,st1,st2,st3); signalstate:stype;beginreg:process(reset,clk)begin ifreset='1'thenstate<=st0; elsifclk'eventandclk='1'then casestateis whenst0=>ifa='1'thenstate<=st1;endif; whenst1=>ifa='0'thenstate<=st2;endif; whenst2=>ifa='1'thenstate<=st3;endif; whenst3=>ifa='0'thenstate<=st0;endif; endcase; endif;endprocess;在时钟信号控制下，决定下一状态四、MEALY型状态机（续2）com:process(state,a)begin casestateis whenst0=>ifa='1'thenq<="1001"; elseq<="0000";endif; whenst1=>ifa='0'thenq<="1100"; elseq<="1001";endif; whenst2=>ifa='1'thenq<="1111";elseq<="1100";endif; whenst3=>ifa='0'thenq<="0000";elseq<="1111";endif; endcase;endprocess;end;根据状态和输入信号控制输出输出信号q由当前状态和输入信号共同决定，与时钟无关返回四、MEALY型状态机（续3）MEALY型状态机MOORE型状态机示例示例四、MEALY型状态机（续4）总结MEALY型状态机和MOORE型状态机的特点状态转化输出信号与时钟信号的关系MOOREMEALY由输入决定由输入决定由当前状态决定由当前状态和输入决定与时钟信号同步不依赖于时钟，只要输入变化，输出能够立即变化Moore和mealy状态机

从信号输出方式上分，有Moore和mealy状态机。

Moore状态机，输出仅为当前状态的函数；在输入发生变化时，虽然能确定下一个状态的去向，但还须等待下一个时钟到来，才能使状态发生变化时，以导致输出的变化。因此从时序上看属异步输出的状态机。

mealy状态机，输出是当前状态和所有输入信号的函数；在输入发生变化时，输出立即发生变化。从时序上看属同步输出的状态机。五、状态编码为了满足一些特殊需要，可直接将各状态用具体的二进制数进行定义，即状态机的直接编码。状态位直接输出型编码顺序编码格雷码（Gray）编码一位热码（one-hot）编码五、状态编码（续1）1、状态为直接输出型编码直接把状态机的状态编码作为输出信号（output=state），是状态机的一种特殊类型。例1：思考：此状态机属于什么类型？五、状态编码（续2）libraryieee;useieee.std_logic_1164.all;entitymoisport(clk,a,reset:instd_logic;q:outstd_logic_vector(1downto0));end;architectureoneofmoissignalstate:std_logic_vector(1downto0);constants0:std_logic_vector(1downto0):="00";constants1:std_logic_vector(1downto0):="10";constants2:std_logic_vector(1downto0):="11";constants3:std_logic_vector(1downto0):="01";begin状态编码五、状态编码（续3）process(clk,reset)beginifreset='1'thenstate<=s0;elsifclk'eventandclk='1'thencasestateiswhens0=>ifa='1'thenstate<=s1;endif;whens1=>ifa='0'thenstate<=s2;endif;whens2=>ifa='1'thenstate<=s3;endif;whens3=>ifa='0'thenstate<=s0;endif;endcase;endif;endprocess;q<=state;end;输入决定状态的转移输出=状态编码，状态决定输出五、状态编码（续4）2、其他编码方式顺序码、格雷码、一位热码顺序编码格雷码编码一位热码编码S0=“00”000001S1=“01”010010S2=“10”110100S3=“11”101000五、状态编码（续5）顺序编码使用触发器数量最少；剩余非法状态最少；增加了从一种状态向另一种状态转化的译码组合逻辑适用于组合逻辑资源相对丰富的CPLD器件格雷码编码当状态机改变状态时，状态向量中仅1位发生变化。一位热码编码使用触发器数量多，状态数等于触发器的数目简化了状态译码逻辑，提高了状态转化速度。适合含有较多时序逻辑资源的FPGA器件。六、非法状态处理非法状态：使用枚举类型或者直接指定状态编码的程序中，总是不可避免的出现大量剩余状态，即未定义的编码组合，这些状态在状态机的正常运行中是不需要出现的。合法状态与非法状态之和：m=2n如果状态机的实际状态数小于m，可以有四种选择：（1）、不做任何规定，让偶然性决定

结果：可能进入非法状态，出现短暂失控，或是完全无法摆脱非法状态而失去正常的功能。六、非法状态处理（续1）（2）、对每一个非法状态作出明确的状态转化指示状态顺序编码St0000St1