有限状态机设计.ppt

第6章 有限状态机设计,EDA 的控制单元 P189-208,第6章 有限状态机设计,一般有限状态机设计概述 Moore型有限状态机设计 Mealy型有限状态机设计 状态编码 非法状态处理,6.1 概 述,一、为什么要使用有限状态机，什么是状态机 二、有限状态机的分类及表示方法 三、有限状态机的设计举例,为什么要使用状态机,状态机：广义时序逻辑电路，按照预先设计的状态顺序运行。状态数有限，又称有限状态机（FSM，Finite State Machine）。 结构模式简单； 容易构成性能良好的同步时序逻辑模块； VHDL表述直观，程序结构清晰； 状态机设计的系统可靠性高。, 有限状态机克服了纯硬件数字系统顺序方式控制不灵活的缺点。,一、概述,6.1.1.2 状态机分类 输出方式： Moore（摩尔）输出仅是当前状态的函数； Mealy（米立）输出是当前状态和输入信号的函数； 结构分类： 单进程； 多进程； 状态表达方式： 顺序编码； 一位热码； 其它编码。,状态机的表示方法1,方法一：状态转换表,状态机的表示方法2,方法二：算法流程图,方法与软件程序的流程图类似,状态机的表示方法3,方法三：状态转换图,状态1,状态4,状态2,状态3,入,/出,入,入,入,/出,/出,/出,Moore,条件控制定序,直接控制定序,状态机的表示方法3,方法三：状态转换图,状态1,状态4,状态2,状态3,入,/出,入,入,入,/出,/出,/出,/出,Mealy,条件控制定序,直接控制定序,一、概述,6.1.3 状态机基本结构,状态 译码器,状态 寄存器,输 出 译 码 器,输入,反馈,输出,状态,组合逻辑,组合逻辑,时序逻辑,二、一般有限状态机的设计,6.2.1 一般有限状态机组成 说明部分； 时序进程； 组合进程； 辅助进程。,1. 说明部分,2. 时序进程,ARCHITECTURE . IS TYPE ST IS (s0，s1，s2，s3); SIGNAL current_state, next_state: ST; .,3.组合进程,在时钟信号的作用下，负责状态的转换。,4.辅助进程,根据输入信号和当前状态的取值（current_state）确定下一状态（next_state）的取值，确定输出或产生内部其它组合进程或时序进程所需的控制信号。,配合时序进程或组合进程工作的数据锁存器等进程。,有限状态机的程序构成,二、一般有限状态机的设计,6.2.1 一般有限状态机组成 组合进程：,注：状态译码器部分； 判别控制过程中的当前状态；（case - when） 决定进入下一个状态。 （if - then - else）,二、一般有限状态机的设计,6.2.1 一般有限状态机组成 辅助进程：,二、一般有限状态机的设计,【例 6-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 s_machine; ARCHITECTURE behave OF s_machine IS TYPE states IS (st0, st1, st2, st3); SIGNAL current_state, next_state: states; BEGIN REG: PROCESS (reset,clk) BEGIN IF reset = 1 THEN current_state = st0; ELSIF clk=1 AND clkEVENT THEN current_state = next_state; END IF; END PROCESS; COM: PROCESS(current_state, state_Inputs),BEGIN CASE current_state IS WHEN st0 = comb_outputs comb_outputs comb_outputs comb_outputs = “11”; IF state_inputs = “11“ THEN next_state = st3; ELSE next_state = st0; END IF; END case; END PROCESS; END behave;,课堂练习2,单稳态触发器设计 序列检测器设计,单稳态触发器,单稳态触发器在数字电路中一般用于定时（产生一定宽度的矩形波）、整形（把不规则的波形转换成宽度、幅度都相等的波形）以及延时（把输入信号延迟一定时间后输出）等。,（1）电路有一个稳态和一个暂稳态。 （2）在外来触发脉冲作用下，电路由稳态翻转到暂稳态。 （3）暂稳态是一个不能长久保持的状态，经过一段时间后，电路会自动返回到稳态。暂稳态的持续时间与触发脉冲无关，仅决定于电路本身的参数。,特点：,延迟与定时,整形,单稳态触发器的应用,二、一般有限状态机的设计,【例 6-2 】Moore状态机设计 Moore状态机的输出仅为当前状态的函数 Mealy状态机的输出是输入和当前状态的函数 在控制AD574模数转换器方面，FPGA要比 MCU8051快。,状态机控制电路设计思路： AD转换器工作时序-状态转换图-逻辑结构框图-VHDL代码,二、一般有限状态机的设计,【例 6-2 】Moore状态机设计 由FPGA控制AD574电路（三进程）,二、一般有限状态机的设计,【例 6-2 】Moore状态机设计 由FPGA控制AD574电路（三进程）,图6-4 AD574工作时序,二、一般有限状态机的设计,【例 6-2 】Moore状态机设计 由FPGA控制AD574电路,图6-5 AD574工作状态图,二、一般有限状态机的设计,【例 6-2 】Moore状态机设计 由FPGA控制AD574电路（三进程）,图6-6 采样状态机结构框图,LIBRARY IEEE; USE IEEE.STD_LOGIC_1164.ALL; ENTITY AD574 IS PORT ( d : IN STD_LOGIC_VECTOR(11 DOWNTO 0); clk,status : IN STD_LOGIC; -时钟CLK，状态信号STATUS lock0 : OUT STD_LOGIC; -内部锁存信号LOCK的测试信号 cs,a0,rc,k12x8 : OUT STD_LOGIC; -AD574控制信号 q : OUT STD_LOGIC_VECTOR(11 DOWNTO 0); -输出 END AD574; ARCHITECTURE behave OF AD574 IS TYPE states IS (st0, st1, st2, st3,st4); SIGNAL current_state, next_state: states :=st0 ; SIGNAL regl : STD_LOGIC_VECTOR(11 DOWNTO 0); SIGNAL lock : STD_LOGIC; BEGIN k12x8 = 1; lock0 = lock ; COM1: PROCESS(current_state, status) -决定转换状态的进程 接下页,BEGIN CASE current_state IS WHEN st0 = next_state next_state IF (STATUS=1) THEN next_state next_state next_state next_state CS CS CS CS CSCS=1; A0=1;RC=1;LOCK=0; -回初始态 END CASE ; END PROCESS COM2 ; REG: PROCESS (CLK) - 状态寄存器时序进程 接下页,BEGIN IF ( clkEVENT AND clk=1) THEN current_state = next_state; END IF; END PROCESS REG; LATCH1 : PROCESS (lock) - 数据锁存器进程 BEGIN IF lock=1 AND lockEVENT THEN regl = d ; END IF; END PROCESS ; q = regl; END behave;,2. Moore型有限状态机设,图：ADC0809工作时序,二、一般有限状态机的设计,【例 6-3 】Moore状态机设计 同步输出Moore型状态机,例1 两进程有限状态机,LIBRARY IEEE; USE IEEE.STD_LOGIC_1164.ALL; ENTITY MOORE2 IS PORT (DATAIN : IN STD_LOGIC_VECTOR(1 DOWNTO 0); CLK,RST : IN STD_LOGIC; Q : OUT STD_LOGIC_VECTOR(3 DOWNTO 0); END MOORE2; ARCHITECTURE behav OF MOORE2 IS TYPE ST_TYPE IS (ST0, ST1, ST2, ST3,ST4); SIGNAL current_state,next_state : ST_TYPE ; BEGIN shi_xu: process(clk,rst) begin,if rst=1 then current_state IF DATAIN =“10“ THEN next_state IF DATAIN =“11“ THEN next_state = ST2 ; ELSE next_state = ST1 ;END IF; Q = “0101“ ;,WHEN ST2 = IF DATAIN =“01“ THEN next_state IF DATAIN =“00“ THEN next_state IF DATAIN =“11“ THEN next_state next_state = ST0; END CASE; END PROCESS; END behav;,两进程有限状态机,图：单进程状态机工作时序,2. Moore型有限状态机设计,实例2：单进程Moore型有限状态机，特点是组合进程和时序进程在同一个进程中，输出引入了锁存器，且与时钟同步，避免了输出的竞争和冒险。缺点是输出晚了一个时钟周期。 LIBRARY IEEE; USE IEEE.STD_LOGIC_1164.ALL; ENTITY MOORE1 IS PORT (DATAIN : IN STD_LOGIC_VECTOR(1 DOWNTO 0); CLK,RST : IN STD_LOGIC; Q : OUT STD_LOGIC_VECTOR(3 DOWNTO 0); END MOORE1; ARCHITECTURE behav OF MOORE1 IS TYPE ST_TYPE IS (ST0, ST1, ST2, ST3,ST4); SIGNAL C_ST : ST_TYPE ; BEGIN,2. Moore型有限状态机设,PROCESS(CLK,RST) BEGIN IF RST =1 THEN C_ST IF DATAIN =“10“ THEN C_ST IF DATAIN =“11“ THEN C_ST IF DATAIN =“01“ THEN C_ST = ST3 ; ELSE C_ST = ST0 ;END IF; Q = “1100“ ;,2. Moore型有限状态机设,WHEN ST3 = IF DATAIN =“00“ THEN C_ST IF DATAIN =“11“ THEN C_ST C_ST = ST0; END CASE; END IF; END PROCESS; END behav;,2. Moore型有限状态机设,图：单进程状态机工作时序,3. Mealy型有限状态机设计,Mealy型有限状态机：输出不仅和当前的状态有关，还和外部输入信号有关。因此Mealy型时序电路的输出变化不必等待时钟的到来。和Moore型状态机相比，其输出变化要领先一个周期。 实例：本例进程COMREG是时序与组合混合型进程，进程COM1负责根据状态和输入信号给出不同的输出信号。 LIBRARY IEEE; USE IEEE.STD_LOGIC_1164.ALL; ENTITY MEALY1 IS PORT ( CLK ,DATAIN,RESET : IN STD_LOGIC; Q :OUT STD_LOGIC_VECTOR(4 DOWNTO 0); END MEALY1;,3. Mealy型有限状态机设计,ARCHITECTURE behav OF MEALY1 IS TYPE states IS (st0, st1, st2, st3,st4); SIGNAL STX : states ; BEGIN COMREG:PROCESS(CLK,RESET) BEGIN-决定转换状态的进程 IF RESET =1 THEN STX IF DATAIN = 1 THEN STX IF DATAIN = 0 THEN STX IF DATAIN = 1 THEN STX = st3; END IF;,3. Mealy型有限状态机设计,WHEN st3 = IF DATAIN = 0 THEN STX IF DATAIN = 1 THEN STX STX IF DATAIN = 1 THEN Q IF DATAIN = 0 THEN Q = “10111“ ; ELSE Q=“10100“ ; END IF ;,3. Mealy型有限状态机设计,WHEN st2 = IF DATAIN = 1 THEN Q IF DATAIN = 0 THEN Q IF DATAIN = 1 THEN Q Q=“00000“ ; END CASE ; END PROCESS COM1 ; END behav;,3. Mealy型有限状态机设计,图：本例状态机工作时序图,本例输出信号Q由组合电路直接产生，输出信号有毛刺，可能对后续电路产生影响，为解决这个问题，可对输出Q进行锁存后再输出。修改如下：,3. Mealy型有限状态机设计,修改COM1进程，对Q增加锁存器，以减少输出Q的毛刺。 COM1: PROCESS(STX,DATAIN,CLK) -输出控制信号的进程 VARIABLE Q2 : STD_LOGIC_VECTOR(4 DOWNTO 0); BEGIN CASE STX IS WHEN st0= IF DATAIN=1 THEN Q2 :=“10000“; ELSE Q2:=“01010“; END IF; WHEN st1= IF DATAIN=0 THEN Q2 :=“10111“; ELSE Q2:=“10100“; END IF; WHEN st2= IF DATAIN=1 THEN Q2 :=“10101“; ELSE Q2:=“10011“; END IF; WHEN st3= IF DATAIN=0 THEN Q2 :=“11011“; ELSE Q2:=“01001“; END IF; WHEN st4= IF DATAIN=1 THEN Q2 :=“11101“; ELSE Q2:=“01101“; END IF; WHEN OTHERS = Q2:=“00000“ ; END CASE ; IF CLKEVENT AND CLK = 1 THEN Q1=Q2; END IF; END PROCESS COM1 ; Q=Q1,状态机输出消除毛刺的方法,方法1，添加辅助进程对输出数据进行锁存 方法2，将双进程状态机改写为单进程状态机，其输出也是锁存过了，故能消除毛刺 方法3，使用状态位直接输出型状态机编码方式，其输出直接由当前状态输出，也没有毛刺,4.状态编码,一.状态编码原则 状态编码又称状态分配，通常有多种编码方法，编码方案选择得当，设计的电路可以简单，反之电路会占用过多的逻辑或速度降低。 主要介绍： 二进制编码 枚举型 格雷码 独热码 状态位直接输出型编码,二、进制编码 二进制编码和格雷码都是压缩状态编码。二进制编码的优点是使用的状态向量最少，但是从一个状态转移到相邻状态时，可能有多个比特位发生变化，瞬变次数多，易产生毛刺,两个状态之间会出现过渡状态。二进制编码的表示形式比较通用。 VHDL实例: Architecture one of example is constant st0 :std_logic_vector(1 downto 0):=“00“; constant st1 :std_logic_vector(1 downto 0):=“01“; constant st2 :std_logic_vector(1 downto 0):=“10“; constant st3 :std_logic_vector(1 downto 0):=“11“; Signal current_state,next_state : std_logic_vector(1 downto 0);,三、格雷码 格雷码在相邻状态的转化中，每次只有1个比特位发生变化，虽然减小了产生毛刺的可能，但不适用于有很多种状态跳转的情况。 如果状态机的所有状态是一个顺序序列，则可通过格雷码编码来消除毛刺，但对于时序逻辑状态机中的复杂分支，格雷码也不能达到消除毛刺的目的。,格雷码用法实例: Architecture behave of example is constant st0 :std_logic_vector(0 to 1):=“00“; constant st1 :std_logic_vector(0 to 1):=“01“; constant st2 :std_logic_vector(0 to 1):=“11“; constant st3 :std_logic_vector(0 to 1):=“10“; signal current_state,next_state :std_logic_vector(0 to 1);,四、独热（one hot）码 独热码是指对任意给定的状态，状态向量中只有一位为1，其余位都为0。N状态的状态机需要n个触发器 。这种状态机速度很快，当状态机的状态增加时，如果使用二进制码，那么状态机速度会明显下降。而采用独热码，虽然多用了触发器，但由于状态译码简单，节省和节化了组合逻辑电路。 注：实现基于FPGA的大型状态机通常用one-hot编码;对规模较 小的状态机少于8个状态二进制编码效率更高,One_hot编码实例: Architecture behave of example is constant st0:std_logic_vector(0 to 3):=“0001“; constant st1:std_logic_vector(0 to 3):=“0010“; constant st2:std_logic_vector(0 to 3):=“0100“; constant st3:std_logic_vector(0 to 3):=“1000“; signal current_state,next_state :std_logic_ vector(0 to 3);,五、枚举型 在设计中定义状态机的状态值为枚举数据类型,综合器一般把它表示为二进制数的序列. 实例: architecture behave of example is type states is(st0,st1,st2,st3); -定义states为枚举类型 signal present :states;,六、状态位直接输出型编码的设计举例,状态位直接输出型编码,每一位的编码值都赋予了实际的控制功能，即： CS = current_state（4） ； A0 = current_state（3） ； RC = current_state（2） ； LOCK = current_state（1） 。,【例6-7】 LIBRARY IEEE; USE IEEE.STD_LOGIC_1164.ALL; ENTITY AD574A IS PORT ( D : IN STD_LOGIC_VECTOR(11 DOWNTO 0); CLK ,STATUS : IN STD_LOGIC; OUT4 : OUT STD_LOGIC_VECTOR(3 DOWNTO 0); Q : OUT STD_LOGIC_VECTOR(11 DOWNTO 0) ); END AD574A; ARCHITECTURE behav OF AD574A IS SIGNAL current_state, next_state: STD_LOGIC_VECTOR(4 DOWNTO 0 ); CONSTANT st0 : STD_LOGIC_VECTOR(4 DOWNTO 0) := “11100“ ; CONSTANT st1 : STD_LOGIC_VECTOR(4 DOWNTO 0) := “00001“ ; CONSTANT st2 : STD_LOGIC_VECTOR(4 DOWNTO 0) := “00000“ ; CONSTANT st3 : STD_LOGIC_VECTOR(4 DOWNTO 0) := “00100“ ; CONSTANT st4 : STD_LOGIC_VECTOR(4 DOWNTO 0) := “00110“ ; SIGNAL REGL : STD_LOGIC_VECTOR(11 DOWNTO 0); SIGNAL LK : STD