Lecture5有限状态机ppt课件

1、有限形状机有限形状机Finite State MachineFinite State Machine例：计数器设计例：计数器设计 设计一电路，包含基设计一电路，包含基4计数器，和译码输出模块。计数器，和译码输出模块。计数器的输出计数器的输出(Present_value)从从0到到3循环；循环；当计数值为当计数值为2时，译码输出时，译码输出(DataOut)为为“1，否那么输出否那么输出“0。Regs1ClkPresent_valueQ(n)Next_valueQ(n+1) 译码译码DataOutZ(n)00/001/010/111/0Regs1ClkPresent_valueQ(n)Next_

2、valueQ(n+1) 译码译码DataOutZ(n)00/001/010/111/0扩展一个输入端扩展一个输入端din，当当din = 1时计数器递时计数器递增计数；当增计数；当din = 0时时计数器递减计数。计数器递减计数。dinDin=1Din = 1Din = 1Din = 1Din = 0Din = 0Din = 0Din = 0Regs/-1ClkPresent_valueQ(n)Next_valueQ(n+1) 译码译码DataOutZ(n)再将计数器修正成一再将计数器修正成一个形状转换器，形状个形状转换器，形状为为S0, S1, S2, S3。每个形状的取值根据每个形状的取值

3、根据详细情况而定。比如详细情况而定。比如S0 = 00, S1 = 11, S3 = 01, S4 = 10。din00/001/010/111/0Din=1Din = 1Din = 1Din = 1Din = 0Din = 0Din = 0Din = 0Regs/-1ClkPresent_valueQ(n)Next_valueQ(n+1) 译码译码DataOutZ(n)再将计数器修正成一再将计数器修正成一个形状转换器，形状个形状转换器，形状为为S0, S1, S2, S3。每个形状的取值根据每个形状的取值根据详细情况而定。比如详细情况而定。比如S0 = 00, S1 = 11, S3 = 0

4、1, S4 = 10。dinS0/0S1/0S2/1S3/0Din=1Din = 1Din = 1Din = 1Din = 0Din = 0Din = 0Din = 0Regs/-1ClkPresent_valueQ(n)Next_valueQ(n+1) 译码译码DataOutZ(n)如今我们得到了一个比较通用如今我们得到了一个比较通用的时序电路，这种电路统称为的时序电路，这种电路统称为形状机形状机(State Machine)。dinS0/0S1/0S2/1S3/0Din=1Din = 1Din = 1Din = 1Din = 0Din = 0Din = 0Din = 0Regs/-1Clk

5、Present_valueQ(n)Next_valueQ(n+1) 译码译码DataOutZ(n)有限形状机概述有限形状机概述数字系统控制部分的每一个控制态可以看数字系统控制部分的每一个控制态可以看作一种形状，与每一个控制态相关的转换作一种形状，与每一个控制态相关的转换条件指定了当前形状的下一个形状和输出。条件指定了当前形状的下一个形状和输出。根据有限形状机的输出与当前形状与当前根据有限形状机的输出与当前形状与当前输入的关系，可以分成输入的关系，可以分成Moore型和型和Mealy型两种类型的有限形状机。型两种类型的有限形状机。 Moore形状机和形状机和Mealy形状机形状机Moore形状机

6、的输出只与当前形状有关形状机的输出只与当前形状有关次态次态逻辑逻辑状状 态态存放器存放器输出输出逻辑逻辑输入输入次态次态现态现态输出输出时钟时钟复位复位Moore形状机和形状机和Mealy形状机形状机Mealy形状机的输出与当前形状机及形状机的输出与当前形状机及当前输入信号有关当前输入信号有关次态次态逻辑逻辑状状 态态存放器存放器输出输出逻辑逻辑输入输入次态次态现态现态输出输出时钟时钟复位复位形状机的表示方法形状机的表示方法形状转换表形状转换表算法流程图算法流程图形状转换图形状转换图这是最流行的这是最流行的表示方法表示方法形状转换图形状转换图形状形状1形状形状4形状形状2形状形状3入入/ /出

7、出入入入入入入/ /出出/ /出出/ /出出Moore条件控条件控制定序制定序直接控直接控制定序制定序形状转换图形状转换图形状形状1形状形状4形状形状2形状形状3入入/出出入入/出出入入/出出入入/出出/出出Mealy条件控条件控制定序制定序直接控直接控制定序制定序用用VHDL描画形状机的组成描画形状机的组成一个用来描画有限形状机功能的一个用来描画有限形状机功能的VHDL言语程序中应该包含以下几个内容：言语程序中应该包含以下几个内容：(1)至少包括一个形状信号，它们用来至少包括一个形状信号，它们用来指定有限形状机的形状；指定有限形状机的形状；(2)形状转移指定和输出指定，它们对形状转移指定和输

8、出指定，它们对应于控制单元中与每个控制步有关的应于控制单元中与每个控制步有关的转移条件；转移条件；(3)时钟信号，它普通是用来进展同步时钟信号，它普通是用来进展同步的；的；(4)同步或异步复位信号。同步或异步复位信号。 形状机的形状机的VHDL描画方式描画方式(1)单进程描画方式：单进程描画方式就是指在单进程描画方式：单进程描画方式就是指在VHDL言语程序的构造体中，运用一个进程语句言语程序的构造体中，运用一个进程语句来描画有限形状机中的次态逻辑、形状存放器和来描画有限形状机中的次态逻辑、形状存放器和输出逻辑。输出逻辑。(2)双进程描画方式：一个进程语句用来描画有限双进程描画方式：一个进程语句

9、用来描画有限形状机中次态逻辑、形状存放器和输出逻辑中的形状机中次态逻辑、形状存放器和输出逻辑中的任何两个；另外一个进程那么用来描画有限形状任何两个；另外一个进程那么用来描画有限形状机剩余的功能。机剩余的功能。(3)三进程描画方式：一个进程用来描画有限形状三进程描画方式：一个进程用来描画有限形状机中的次态逻辑；一个进程用来描画有限形状机机中的次态逻辑；一个进程用来描画有限形状机中的形状存放器；另外一个进程用来描画有限形中的形状存放器；另外一个进程用来描画有限形状机中的输出逻辑。状机中的输出逻辑。形状机的形状机的VHDL描画方式描画方式描述方式描述方式进程描述功能进程描述功能三进程描述方式三进程描

10、述方式进程进程1：描述次态逻辑：描述次态逻辑进程进程2：描述状态寄存器：描述状态寄存器进程进程3：描述输出逻辑：描述输出逻辑双进程描双进程描述方式述方式 形式形式1 进程进程1：描述次态逻辑、状态寄存器：描述次态逻辑、状态寄存器进程进程2：描述输出逻辑：描述输出逻辑形式形式2 进程进程1：描述状态寄存器、输出逻辑：描述状态寄存器、输出逻辑进程进程2：描述次态逻辑：描述次态逻辑形式形式3 进程进程1：描述次态逻辑、输出逻辑：描述次态逻辑、输出逻辑进程进程2：描述状态寄存器：描述状态寄存器单进程描述方式单进程描述方式进程进程1：描述次态逻辑、状态寄存器和：描述次态逻辑、状态寄存器和输出逻辑输出逻辑

11、存储控制器存储控制器idledecisionreadwritereadyread_writereadyreadyreadyreadyreadyread_write 设计一个存储控制器，设计一个存储控制器，它的详细要求为它的详细要求为:(1)存存储控制器可以根据微处储控制器可以根据微处置器的读周期或者写周置器的读周期或者写周期，分别对存储器输出期，分别对存储器输出写使能信号写使能信号we和读使能和读使能信号信号oe；(2)存储控制存储控制器的输入信号有器的输入信号有3个个:微微处置器的预备就绪信号处置器的预备就绪信号ready、微处置器的读、微处置器的读写信号写信号read_write和和时钟信

12、号时钟信号clk。 存储控制器存储控制器列出当前形状和输出值的关系列出当前形状和输出值的关系状态状态输出输出OEWEidle00decision00write01read10建立形状转换表，列出次态和转换条件建立形状转换表，列出次态和转换条件当前状态当前状态次态次态转换条件转换条件idledecisionready=1decisionwritew_r=0readw_r=1writeidleready=1writeready=0readidleready=1readready=0利用利用VHDLVHDL言语进展形状机描画言语进展形状机描画一切形状均可以表达为一切形状均可以表达为CASE-CASE

13、-WHENWHEN构造中的一条语句。构造中的一条语句。形状的转移经过形状的转移经过if-then-elseif-then-else语句语句实现。实现。CASE present_state ISCASE present_state IS WHEN idle = WHEN idle = 输出量；输出量； IFIF ELSE ELSE END IF; END IF;有些形状的转换中，在条件满足时，有些形状的转换中，在条件满足时，转换到下一个形状，否那么坚持原来转换到下一个形状，否那么坚持原来的形状不变。这种情况对应着的形状不变。这种情况对应着IF-THEN-ELSE的两个分支。的两个分支。在这种情况

14、下，在这种情况下，ELSE分支并不是必需分支并不是必需的。但是短少的。但是短少ELSE分支，会导致额外分支，会导致额外的存储器。的存储器。形状转换形状转换形状描画的步骤：对每一个形状建立一项CASE语句的分支 WHEN 形状名 =确定输出变量经过IF-THEN-ELSE语句指定相应的次态。例case present_state is - CASE分支 when idle =oe=0;we=0; -确定输出变量if(ready = 1) then-确定次态next_state = decision;elsenext_state IF(ready = 1) THENnext_state = dec

15、ision;ELSEnext_state = idle;END IF;END CASE;END PROCESS nextstate_logic; 例：三进程描画方式例：三进程描画方式2 2state_register: PROCESS(clk)BEGIN IF(RISING_EDGE(clk) THEN present_state we = 0;oe we=0;oewe=0;oewe=1;oe=0; END CASE;END PROCESS output_logic 义务义务1 1：空调控制器：空调控制器S1S2S3thigh=0tlow=0thigh=0tlow=1thigh=1tlow=0

16、thigh=0tlow=1thigh=0tlow=0thigh=1tlow=0hot=0cool=0hot=0cool=1hot=1cool=0空调控制器形状转换图空调控制器形状转换图义务义务1 1：空调控制器：空调控制器S1S1：表示温度适中，不高也不低，对应着输入信号thigh和tlow均为低电平(无效)，空调器既不制冷也不制热，因此输出控制信号hot和cool都是低电平。S2S2：表示温度太低，对应着输入信号tlow为高电平，thigh为低电平，此时空调器应该任务在制热形状，相应的输出控制信号hot为高电平，cool无效。S3S3：表示温度太高，对应着输入信号thigh为高电平，tlow

17、为低电平，此时空调器应该任务在制冷形状，相应的输出控制信号cool为高电平，hot无效。义务义务1 1：空调控制器：空调控制器形状转换表形状转换表当前当前形状形状转换条件转换条件下一下一形状形状执行操作执行操作输出值输出值S1thigh=0&tlow=1thigh=1&tlow=0S2S3制热制热制冷制冷hot=1/cool=0hot=0/cool=1S2thigh=0&tlow=0thigh=1&tlow=0S1S3既不制冷也不制热既不制冷也不制热制冷制冷hot=0/cool=0hot=0/cool=1S3thigh=0&tlow=0thigh=0&a

18、mp;tlow=1S1S2既不制冷也不制热既不制冷也不制热制热制热hot=0/cool=0hot=1/cool=0形状机的运用设计形状机的运用设计例子：设计一个二进制序列检测器，当检测到例子：设计一个二进制序列检测器，当检测到10110序列时，就输出序列时，就输出1(一个时钟周期的脉冲一个时钟周期的脉冲)。其他情况下输出其他情况下输出0。 规定检测到一次之后，检测器复位到最初始的形规定检测到一次之后，检测器复位到最初始的形状，重新从头检测。如下所示：状，重新从头检测。如下所示：输入：输入：01101101101100输出：输出：00000001000001形状转换图设计形状转换图设计Moore

19、Moore10110S0/0S1/0S2/0S3/0S4/0S5/1Reset1100110100101011 0s1 s2s3s4 s5s0问题问题1：如何保证：如何保证形状机在初始时形形状机在初始时形状为状为s0？问题问题2：在形状机：在形状机跑飞，即脱离有效跑飞，即脱离有效形状形状(s0s5)时，时，如何使形状机能恢如何使形状机能恢复任务复任务Sx/0波形波形波形如以下波形如以下图所示图所示问题：假设需求问题：假设需求将输出脉冲往前将输出脉冲往前推一个时钟周期，推一个时钟周期，该如何修正设计？该如何修正设计？101101011 0s1 s2s3s4 s5s0输入输入时钟时钟输出输出当前形

20、状当前形状 发现当当前壮发现当当前壮态为态为s4，并且输，并且输入为入为0时，输出时，输出为为1。形状转换图设计形状转换图设计(Mealy)(Mealy)S0S1S2S3S4S5Reset100110100101sX/0/0/0/0/0/0/0/0/0/1/0/0101101011 0s1 s2s3s4 s5s0/00/1s0形状机的代码实现形状机的代码实现 形状定义形状定义 Architecture rtl of Syn isArchitecture rtl of Syn is - - 其他信号定义。其他信号定义。 Type SynFsmState is ( s0, s1, s2, s3,

21、s4, Type SynFsmState is ( s0, s1, s2, s3, s4, s5);s5); Signal SynCst, SynNst : SynFsmState;Signal SynCst, SynNst : SynFsmState; Begin Begin - - 构造体。构造体。 End rtl;End rtl;形状机的代码实现形状机的代码实现形状存放器进程描画形状存放器进程描画形状存放器输出译码下一状态译码当前形当前形状状输出输出下一形状下一形状输入输入时钟时钟clkclk形状存放器进程描画形状存放器进程描画Process( clk, Reset )Begin if(

22、 Reset = 1 ) then SynCst = S0; - 初始形状。初始形状。 elsif( clkevent and clk = 1 ) then SynCst when s1 = when s5 = End case;End process; if( din = 1 ) then SynNst = s1; else SynNst SynNst when s1 = when s5 = when others = End case;End process;MooreMealyDout = 0;Dout = 0;Dout = 0if( din = 1 ) then else end if

23、;, din )义务义务3 3：交通灯控制器：交通灯控制器模拟显示十字路口两个方向的交统统模拟显示十字路口两个方向的交统统行情况。两个方向均用红、黄、绿灯行情况。两个方向均用红、黄、绿灯指示实践形状。指示实践形状。 用用LEDLED同时显示两个方向形状的时间。同时显示两个方向形状的时间。时间计数方式为倒计数方式。技术参时间计数方式为倒计数方式。技术参数为绿数为绿( (红红)50)50秒、黄秒、黄( (红红)5)5秒、红秒、红( (绿绿)30)30秒和红秒和红( (黄黄)5)5秒。秒。方法：有限形状机方法：有限形状机当前状态当前状态下一状态下一状态东西灯东西灯南北灯南北灯S1S1S2S2G GR

24、 RS2S2S3S3Y YR RS3S3S4S4R RG GS4S4S1S1R RY Y形状机形状机采用双进程描画方式采用双进程描画方式次态逻辑和输出逻辑放在一个进程中次态逻辑和输出逻辑放在一个进程中实现，形状存放器在另一个进程中实实现，形状存放器在另一个进程中实现。现。从一个形状转换到另外一个形状，需从一个形状转换到另外一个形状，需求经过一段时间，这段时间的终了将求经过一段时间，这段时间的终了将导致次态变成现态；导致次态变成现态；关于计数器关于计数器设置东西、南北两个计数器设置东西、南北两个计数器计数器的初值在形状转换时设置计数器的初值在形状转换时设置计数器采用倒计数方式计数器采用倒计数方式计数终了计数终了(EOC)(EOC)信号将触发形状存放器信号将触发形状存放器进程的执行进程的执行计数的结果将被显示出来。计数的结果将被显示出来。形状转换的条件形状转换的条件计数器值为计数器值为0(0(使得使得EOC=1)EOC=1)由于有两个计数器，因此有四由于有两个计数器，因此有四( (三三) )种情种情况，分别对应形状转换的情况。况，分别对应形状转换的情况。程序组成程序组成构造体有三个进程构造体有三个进程形状转换和输出形状转换和输出形状存放器形状存放器计数器及译码计数器及译码计数器计数器形状寄形状寄存