有限状态机初步 2014

1、1VHDL有限状态机有限状态机FSM初步初步2状态机状态机 概念：概念： 是一类十分重要的时序电路是一类十分重要的时序电路 许多数字电路的核心部件许多数字电路的核心部件 结构：结构： 组合逻辑部分（状态译码器和输出译码器）组合逻辑部分（状态译码器和输出译码器） 时序逻辑部分（寄存器）时序逻辑部分（寄存器）3 状态机是纯硬件数字系统中的状态机是纯硬件数字系统中的顺序控制电路顺序控制电路，其运，其运行方式上类似于控制灵活和方便的行方式上类似于控制灵活和方便的CPU，而在运行速而在运行速度和工作可靠性方面都优于度和工作可靠性方面都优于CPU。 状态机结构模式相对简单，设计方案相对固定状态机结构模式相

2、对简单，设计方案相对固定。状状态机的态机的VHDL表述丰富多样，程序层次分明，结构清晰，表述丰富多样，程序层次分明，结构清晰，易读易懂；在排错、修改和模块移植方面也有其独到易读易懂；在排错、修改和模块移植方面也有其独到之点。之点。 在高速运算和控制方面，状态机具有巨大的优势。在高速运算和控制方面，状态机具有巨大的优势。在在VHDL中中,一个状态机可以有多个进程构成一个状态机可以有多个进程构成,一个结构体中可以包一个结构体中可以包含多个状态机含多个状态机,而一个单独的状态机而一个单独的状态机(或多个并行运行的状态机或多个并行运行的状态机)以以顺序方式所能完成的运算和控制方面的工作与一个顺序方式所

3、能完成的运算和控制方面的工作与一个CPU的功能类的功能类似。因此，一个设计实体的功能便类似于一个含有并行运行的多似。因此，一个设计实体的功能便类似于一个含有并行运行的多CPU的高性能微处理器的功能。的高性能微处理器的功能。 就运行速度而言就运行速度而言: 状态机的状态变换周期只有一个时钟周期，而在每状态机的状态变换周期只有一个时钟周期，而在每一个状态中，状态机可以完成许多并行的运算和控制操一个状态中，状态机可以完成许多并行的运算和控制操作，所以，一个完整的控制程序，即使用多个并行状态作，所以，一个完整的控制程序，即使用多个并行状态机构成，其状态数也是十分有限的。一般由状态机构成机构成，其状态数

4、也是十分有限的。一般由状态机构成的硬件系统比的硬件系统比CPU所能完成同样功能的软件系统的工作所能完成同样功能的软件系统的工作速度要高出速度要高出三到五个数量级三到五个数量级。 就可靠性而言就可靠性而言: 由于由于CPU本身的结构特点与执行软件指令的工作方式决定了本身的结构特点与执行软件指令的工作方式决定了CPU不能获得圆满的容错保障不能获得圆满的容错保障，这已是不争的事实。而状态机，这已是不争的事实。而状态机系统不同，系统不同，首先首先由于它是纯硬件电路构成，不存在由于它是纯硬件电路构成，不存在CPU运行软件过运行软件过程中许多固有的缺陷；程中许多固有的缺陷；其次其次是由于状态机设计中能使用

5、各种完整的是由于状态机设计中能使用各种完整的容错技术；容错技术；第三第三是状态机从非法状态跳出进入正常状态的耗时十分是状态机从非法状态跳出进入正常状态的耗时十分短暂，通常只有短暂，通常只有2、3个时钟周期，约几十个个时钟周期，约几十个ns，不足于对系统运行不足于对系统运行构成损坏，而构成损坏，而CPU则是通过复位方式从非法运行方式中恢复过来，则是通过复位方式从非法运行方式中恢复过来，耗时达几十耗时达几十ms，这对于高速高可靠系统显然是无法容忍的。这对于高速高可靠系统显然是无法容忍的。为什么要使用状态机？为什么要使用状态机？4状态机的结构状态机的结构状态译状态译码器码器状态寄存器状态寄存器(当前

6、状态当前状态)输输出出译译码码器器输入输入信号输出信号输出状态输出状态输出5状态机状态机-各部分的功能各部分的功能 状态译码器状态译码器 确定状态机的下一个状态确定状态机的下一个状态 输出译码器输出译码器 确定状态机输出确定状态机输出 状态寄存器状态寄存器 存储状态机的内部状态存储状态机的内部状态6状态机的基本操作状态机的基本操作 状态的转换：状态的转换： 下一个状态由译码器根据下一个状态由译码器根据当前状态当前状态和和输入条输入条件件决定。决定。 输出信号的产生：输出信号的产生： 输出信号由译码器根据输出信号由译码器根据当前状态当前状态和和输入条件输入条件决定。决定。7状态机的时序种类状态机

7、的时序种类 同步时序状态机：同步时序状态机： 由时钟信号触发状态的转换和信号的输出由时钟信号触发状态的转换和信号的输出 异步时序状态机：异步时序状态机： 状态的转移和输出不与时钟信号同步状态的转移和输出不与时钟信号同步注意：注意：可综合的状态机设计要求使用同可综合的状态机设计要求使用同步状态机！步状态机！8状态机的基本组成状态机的基本组成 主控时序进程主控时序进程 主控组合进程主控组合进程 状态说明部分状态说明部分9主控时序进程主控时序进程： 所谓主控时序进程是指所谓主控时序进程是指负责状态机运转负责状态机运转 和和 在时钟驱动下负责状态在时钟驱动下负责状态转换的进程。转换的进程。 主控时序进

8、程主控时序进程 实际上是一个对工作时钟信号敏感的进程，可看作状态机实际上是一个对工作时钟信号敏感的进程，可看作状态机的的“驱动泵驱动泵”，而时钟，而时钟 clk 相当于这个相当于这个 “驱动泵驱动泵”中的驱动功率电源。中的驱动功率电源。resetPROCESSREGPROCESSCOMcurrent_statenext_stateclkS_inputS_outputFSM:一般状态机结构框图工作示意图一般状态机结构框图工作示意图主控时序主控时序进程进程主控组合主控组合进程进程10 主控组合进程通过信号主控组合进程通过信号current_state 中的状态值，进入相应的状中的状态值，进入相应的

9、状态，并在此状态中根据外部输入的信号如态，并在此状态中根据外部输入的信号如 S_input （指令），向外发（指令），向外发出控制信号如出控制信号如S_output ，同时确定下一状态的取向，即向，同时确定下一状态的取向，即向next_state中中赋入相应的状态值。此状态值通过赋入相应的状态值。此状态值通过next_state传给主控时序进程，直至传给主控时序进程，直至下一个时钟脉冲到来再进入再一次的状态转换周期。因此，主控组合下一个时钟脉冲到来再进入再一次的状态转换周期。因此，主控组合进程也称进程也称状态译码进程状态译码进程 。主控组合进程主控组合进程： 主控组合进程的任务主控组合进程的任

10、务 是根据外部输入的控制信号（包括来是根据外部输入的控制信号（包括来自状态机外部的信号和来自状态机内部其它非主控的组合和时序进自状态机外部的信号和来自状态机内部其它非主控的组合和时序进程的信号），及当前状态的状态值确定下一个状态的取向，即程的信号），及当前状态的状态值确定下一个状态的取向，即next_state 的取值内容，并确定对外输出或对内其它组合和时序进的取值内容，并确定对外输出或对内其它组合和时序进程输出控制信号的内容。程输出控制信号的内容。具体过程是具体过程是 ：resetPROCESSREGPROCESSCOMcurrent_statenext_stateclkS_inputS_o

11、utputFSM:一般状态机结构框图工作示意图一般状态机结构框图工作示意图11状态机的类型状态机的类型状态一状态一状态二状态二状态二状态二摩尔型摩尔型moore状态机状态机米勒型米勒型mealy状态机状态机状态一状态一输入输入12状态表状态表流程图流程图状态图状态图状态机的表达方式状态机的表达方式13状态表状态表14状态图状态图15状态图状态图 状态机的本质是对具有状态机的本质是对具有逻辑顺序逻辑顺序或或时序时序规律事件规律事件的一种描述方法。的一种描述方法。1617状态类型定义语句状态类型定义语句 TYPE 用户自定义数据类型用户自定义数据类型: 数据类型名数据类型名： 由设计者自定；由设计

12、者自定； 数据类型定义：数据类型定义： 数组型数据类型数组型数据类型或或枚举型数据类型枚举型数据类型TYPE 数据类型名数据类型名 IS 数据类型定义；数据类型定义；TYPE 数据类型名数据类型名 IS 数据类型定义数据类型定义 OF 基本数据类型；基本数据类型；18状态类型定义语句状态类型定义语句 TYPE TYPE st1 IS ARRAY (0 TO 15) OF STD_LOGIC； TYPE week IS (sun，mon，tue，wed， thu，fri，sat)；例如：例如：ARCHITECTURE bhv OF cnt4 ISTYPE m_state IS (st0，st1，

13、st2，st3，st4，st5)； SIGNAL present_state，next_state ：m_state；BEGIN19状态机的说明部分状态机的说明部分 使用使用 TYPE 语句定义一个新的数据类型，一般为语句定义一个新的数据类型，一般为枚举枚举型型，其元素都用状态机的状态名来定义。说明部分一，其元素都用状态机的状态名来定义。说明部分一般放在般放在ARCHITECTURE 和和 BEGIN之间。例如：之间。例如：ARCHITECTURE IS TYPE states IS (S0, S1, S2, S3)； SIGNAL current_state, next_state : st

14、ates； BEGIN 2021library ieee;use ieee.std_logic_1164.all;entity traffic is port(clk:in std_logic; z:out std_logic_vector(5 downto 0); -ra,ya,ga,gb,yb,rbend traffic;architecture one of traffic is type state_type is ( s0,s1,s2,s3,s4,s5,s6,s7,s8,s9,10,s11,s12,s13,s14,s15,s16,s17,s18,s19, s20,s21,s22,s2

15、3,s24,s25,s26,s27,s28,s29,s30,s31,s32,s33,s34,s35,s36,s37, s38,s39,s40,s41,s42,s43,s44,s45,s46,s47,s48,s49,s50,s51,s52,s53,s54,s55, s56,s57,s58,s59,s60,s61,s62,s63,s64,s65,s66,s67,s68,s69,s70,s71,s72,s73, s74,s75,s76,s77,s78,s79,s80,s81,s82,s83,s84,s85,s86,s87,s88,s89）; signal state:state_type;begin

16、 process(clk) begin222324PROCESS(Clockin) BEGIN IF RISING_EDGE(Clockin) THEN IF Counter=48000000-1 THEN counter=0; Temp1=Not Temp1; ELSE Counter=Counter+1; END IF; END IF; IF falling_edge(clockin) THEN IF Counter=48000000/2 THEN Temp2=NOT Temp2; END IF; END IF; Clk=Temp1 XOR Temp2;END PROCESS ;分分频频器

17、器1Hz25 Architecture one of traffic is SIGNAL Counter:Integer RANGE 0 TO 48000000-1; SIGNAL Temp1,Temp2,clk:STD_LOGIC; Begin PROCESS(clockin) PROCESS(clk) PROCESS() 2627282930process(clk) variable a : std_logic_vector(3 downto 0);begin dig=11111110; if clkevent and clk=1 then if aled7sled7sled7sled7s

18、led7sled7sled7sled7sled7sled7s=10010000; end case; end process;31三进制计数器的状态图三进制计数器的状态图S2S0S1 / 1 / 0 / 0输入输入/输出输出32四进制计数器的状态图？四进制计数器的状态图？S3S1S2S4S0 / 0 / 0 / 0 / 1 / 033序列检测器序列检测器 序列检测器序列检测器就是将一个指定序列从数字就是将一个指定序列从数字码流中识别出来。码流中识别出来。 种类：种类： 有记忆功能的有记忆功能的 无记忆功能的无记忆功能的34序列检测器（序列检测器（111）的状态图）的状态图S2S0S1输入输入/

19、输出输出S3无记忆功能无记忆功能x / 01 / 011 / 0111 / 135序列检测器（序列检测器（111）的状态图）的状态图S2S0S1输入输入/输出输出S3有记忆功能有记忆功能x / 01 / 011 / 0111 / 136序列检测器（序列检测器（10010）的状态图的状态图S2S0S1输入输入/输出输出S3有记忆功能有记忆功能S4S537序列检测器（序列检测器（1110010）S0S1S7S2S3S6S5S41110010/10输入输入/输出输出38Moore型状态机型状态机-模模4计数器计数器LIBRARAY IEEE;USE IEEE.STD_LOGIC_1164.ALL;E

20、NTITY cnt4 ISPORT (clk :IN BIT; Q :OUT STD_LOGIC_VECTOR(1 DOWNTO 0);END cnt4;ARCHITECTURE bhv OF cnt4 IS TYPE state IS (s0，s1，s2，s3); -定义状态种类定义状态种类 SIGNAL current_state, next_state :state;39Moore型状态机型状态机-模模4计数器计数器BEGINreg: PROCESS（clk） -主控时序进程主控时序进程 BEGIN IF clkevent AND clk=1 THEN current_state q=“

21、00”;next_state q=“01”;next_state q=“10”;next_state q=“11”;next_state=s0; END CASE; END PROCESS; END ARCHITECTURE bhv; 41Mealy型有限状态机型有限状态机 Mealy 型机的型机的组合进程组合进程中的输出信号是中的输出信号是当前状态和当前输入的函数。当前状态和当前输入的函数。 与与Moore 型状态机相比，型状态机相比，Mealy 机的输机的输出变化要领先一个周期，即一旦输入信出变化要领先一个周期，即一旦输入信号或状态发生变化，输出信号即刻发生号或状态发生变化，输出信号即刻发

22、生变化。变化。42Mealy型状态机型状态机ENTITY demo2 ISPORT (clk，input，reset :IN STD_LOGIC; Q :OUT STD_LOGIC_VECTOR(3 DOWNTO 0);END demo2;ARCHITECTURE bhv OF demo2 ISTYPE state IS (s0，s1，s2，s3);SIGNAL current_state, next_state :state;BEGIN43Mealy型状态机型状态机reg:PROCESS（clk） BEGINIF reset=1 THEN current_state=s0； ELSIF cl

23、kevent AND clk=1 THENcurrent_state Q=“0000”； IF input =1THEN next_state=s1; ELSE next_state Q=“1001”； IF input =0THEN next_state=s2; ELSE next_state Q =“1100”； IF input =1THEN next_state=s3； ELSE next_state Q =“1111”； IF input =0THEN next_state =s0; ELSE next_state =s3； END IF； END CASE；END PROCESS；

24、END bhv；46Mealy型状态机型状态机47序列检测器的设计序列检测器的设计ENTITY test ISPORT （clk，x: IN STD_LOGIC； y: OUT STD_LOGIC）；）；END test；ARCHITECTURE bhv OF test ISTYPE state IS (s0，s1，s2，s3)；SIGNAL current_state, next_state :state；48BEGINreg：PROCESS（clk） BEGIN IF clkevent AND clk=1 THEN current_state IF x =0 THEN next_state

25、=s0； y=0;ELSE next_state=s1； y IF x =0 THEN next_state=s0；y=0 ELSE next_state=s2；y IF x =0 THEN next_state=s3；y=1; ELSE next_state=s2； y IF x =0 THEN next_state=s0；y=0; ELSE next_state=s1； y IF x =0 THEN next_state=s0； y=0; ELSE next_state=s1； y IF x =0 THEN next_state=s0；y=0 ELSE next_state=s2；y IF x =0 THEN next_state=s3；y=1; ELSE next_state=s2； y IF x =0 THEN next_state=s0；y=0; ELSE next_state=s1； y=0; END IF； .5.52硬件笔试题硬件笔试题 画状态机画状态机，接受，接受1，2，5分钱的卖报机，分钱的卖报机，每份报纸每份报纸5分钱。（分钱。（扬智电子扬智电子笔