EDA技术8_状态机

1、 同步时序电路的设计方法同步时序电路的设计方法深圳大学信息工程学院本章提要 有限状态机FSM简介 FSM的分类：Moore机和Mealy机 FSM的VHDL实现同步系统设计原则 方法：所有输入到触发器，寄存器和计数器等部件的时钟，必须是由系统时钟直接驱动的。 结果：所有的状态变化均在时钟的有效沿（rising or falling edges)发生。 优势：所有的开关暂态，开关噪声和其他干扰均发生在时钟脉冲间，对系统性能没有影响。*系统的最大时钟频率由最长路径的最大延迟决定系统的最大时钟频率由最长路径的最大延迟决定深圳大学信息工程学院同步时序电路的构成示意图深圳大学信息工程学院有限状态机的状态

2、转移图图形表示：状态、转移、条件和逻辑开关6 FSMFSM是为时序电路设计而创建的特殊模型技术，是为时序电路设计而创建的特殊模型技术，在针对在针对任务顺序非常明确任务顺序非常明确的电路（如交通灯控制器）是非常的电路（如交通灯控制器）是非常实用实用。 理论上，任何时序电路都可以建立理论上，任何时序电路都可以建立FSMFSM模型，但并不总模型，但并不总是一种高效的方法。是一种高效的方法。如果一味地追求使用如果一味地追求使用FSMFSM来设计时来设计时序电路，可能会导致代码冗长和容易出错序电路，可能会导致代码冗长和容易出错。例如，任。例如，任务简单的寄存器就不必使用务简单的寄存器就不必使用FSMFS

3、M方式实现。又例如，方式实现。又例如，虽虽然任务与顺序很明确，但任务数目太多或者性能要求然任务与顺序很明确，但任务数目太多或者性能要求较高时，较高时，也不宜用也不宜用FSMFSM方式实现。方式实现。 状态机的设计包含两个主要过程，状态机的设计包含两个主要过程，一是状态机的建模，一是状态机的建模，二是状态机的编码。二是状态机的编码。有限状态机有限状态机(Finite State Machine,FSM)(Finite State Machine,FSM)7组合逻辑电路时序逻辑电路clkrstoutputinputpr_statenx_state状态机的组成状态机的组成: :如图。如图。状态机的种

4、类状态机的种类： MealyMealy型：当前状态、当前输入相关型：当前状态、当前输入相关 Moore Moore型：仅当前状态相关型：仅当前状态相关VHDLVHDL代码结构：代码结构： 时序逻辑部分：时序逻辑部分：processprocess内部内部 组合逻辑部分：组合逻辑部分： 在使用在使用FSMFSM方式设计方式设计VHDLVHDL代码时，通常代码时，通常会会在结构体的开始部分插入一个用户自在结构体的开始部分插入一个用户自定义的枚举数据类型定义的枚举数据类型，其中，其中包含所有可包含所有可能出现的电路状态能出现的电路状态。8设计风格设计风格#1#1一种结构清晰、易于实现的一种结构清晰、易

5、于实现的FSMFSM设计风格设计风格：FSMFSM中的时序逻辑部分和组合逻辑部分中的时序逻辑部分和组合逻辑部分分别独立设分别独立设计计；定义一个枚举数据类型，内部包含所有定义一个枚举数据类型，内部包含所有FSMFSM需要的需要的状态；状态；9组合逻辑电路时序逻辑电路clkrstoutputinputpr_statenx_stateFSMFSM中中时序逻辑部分时序逻辑部分的设计特点：的设计特点：确定的输入确定的输入/ /输出端口输出端口典型的模板可供使用典型的模板可供使用-lower section-process (clock, reset)begin if (reset = 1) then

6、pr_state = state0; elsif (clockevent and clock=1) then pr_state /多个条件转移分支 if (input=.) then output = ; nx_state if (input=.) then output = ; nx_state=state2; else .; end if; . end case;end process;11设计风格设计风格#1#1的状态机模板的状态机模板 library ieee;use ieee.std_logic_1164.all;entity is port (input: in ; reset,

7、clock: in std_logic; output: out );end ;architecture of is type state is (state0, state1, state2, state3, .); signal pr_state, nx_state: state;begin-lower section-process (clock, reset)begin if (reset = 1) then pr_state = state0; elsif (clockevent and clock=1) then pr_state if (input=.) then output

8、= ; nx_state if (input=.) then output = ; nx_state=state2; else .; end if; . end case;end process;end 两个进程两个进程并发执行并发执行12例例8.1 8.1 模模1010计数器计数器功能描述功能描述：状态转移图：状态转移图特点分析特点分析：摩尔型状态机：摩尔型状态机设计分析设计分析：状态较多，枚举很不方便，：状态较多，枚举很不方便，仅作为例子参考，不推荐实际应用。仅作为例子参考，不推荐实际应用。zero(0000)one(0001)two(0010)three(0011)four(0100)f

9、ive(0101)nine(1001)eight(1000)seven(0111)six(0110)rst13library ieee;use ieee.std_logic_1164.all;entity counter is port ( -无输入数据- rst, clk: in std_logic; count: out std_logic_vector(3 downto 0);end counter;architecture state_machine of counter is type state is (zero, one, two, three, four, five, six,

10、 seven, eight, nine); signal pr_state, nx_state: state;begin-lower section-process (clk, rst)begin if (rst = 1) then pr_state = zero; elsif (clkevent and clock=1) then pr_state count = “0000”; nx_state count = “0001”; nx_state count=“0010”; nx_state count=“1001”; nx_state=zero; end case;end process;

11、end state_machine;两个进程两个进程并发执行并发执行代码实现：代码实现：所需寄存器个数所需寄存器个数： 上限上限loglog2 210=410=414例例8.2 8.2 简单的简单的FSM#1FSM#1功能描述功能描述：FSMxabdclkrststateA(x=a)stateB(x=b)d=0d=0d=1d=1rst15entity simple_fsm is port ( a, b, c, d, rst, clk: in BIT; x: out BIT);end simple_fsm;architecture simple_fsm of simple_fsm is type

12、 state is (stateA, stateB); signal pr_state, nx_state: state;begin-lower section-process (clk, rst)begin if (rst = 1) then pr_state = stateA; elsif (clkevent and clock=1) then pr_state x =a; if (d=1) then nx_state=stateB; else nx_state x=b; if (d=1) then nx_state=stateA; else nx_state=stateB; end if

13、; end case;end process;end simple_fsm;代码实现：代码实现：所需寄存器个数所需寄存器个数： 1 1个，用于存储两个状态编码。个，用于存储两个状态编码。168.3 8.3 设计风格设计风格#2#2 在很多应用中（如波形整齐、流水线技术等），在很多应用中（如波形整齐、流水线技术等），需要同步的寄存器输出，即需先使用寄存器存储起需要同步的寄存器输出，即需先使用寄存器存储起来，然后在时钟边沿时才进行更新，如图来，然后在时钟边沿时才进行更新，如图b b：17设计风格设计风格#2#2的状态机模板的状态机模板使用辅助信号如使用辅助信号如temptemp library i

14、eee;use ieee.std_logic_1164.all;entity is port (input: in ; reset, clock: in std_logic; output: out );end ;architecture of is type state is (state0, state1, state2, state3, .); signal pr_state, nx_state: state; signal temp: ;begin-lower section-process (clock, reset)begin if (reset = 1) then pr_stat

15、e = state0; elsif (clockevent and clock=1) then output=temp; pr_state temp = ; if (condition) then nx_state temp = ; if (condition) then nx_state=state2; .; end if; . end case;end process;end temp信号将输出结信号将输出结果存储起来，只有果存储起来，只有当所需时钟边沿到当所需时钟边沿到来时才被赋值给输来时才被赋值给输出端口出端口18entity simple_fsm is port ( a, b, c,

16、 d, rst, clk: in BIT; x: out BIT);end simple_fsm;architecture simple_fsm of simple_fsm is type state is (stateA, stateB); signal pr_state, nx_state: state; signal temp: BIT;begin-lower section-process (clk, rst)begin if (rst = 1) then pr_state = stateA; elsif (clkevent and clock=1) then pr_state = n

17、x_state; x temp=a; if (d=1) then nx_state=stateB; else nx_state temp=b; if (d=1) then nx_state=stateA; else nx_state=stateB; end if; end case;end process;end simple_fsm;所需寄存器个数所需寄存器个数： 2 2个，一个用于存储两个个，一个用于存储两个状态编码，另一个用于存储同步输出结果。状态编码，另一个用于存储同步输出结果。例例8.38.3：用：用FSM#2FSM#2实现例实现例8.28.2： -同步输出同步输出198.4 8.4

18、 状态机的编码风格状态机的编码风格二进制码和独热码二进制码和独热码（1 1）状态机编码的概念）状态机编码的概念：在设计状态机时，需要对状态机在设计状态机时，需要对状态机的状态进行编码，从而决定需要使用的寄存器数目。的状态进行编码，从而决定需要使用的寄存器数目。（2 2）状态机编码的方式：）状态机编码的方式：二进制编码、一位热独码、两位二进制编码、一位热独码、两位独热码或其它编码方式，独热码或其它编码方式，默认的方式是二进制编码默认的方式是二进制编码。 例：例：8状态状态FSM的状态编码的状态编码20（3 3）不同的编码方式所需要的触发器数目和组合逻辑资源是）不同的编码方式所需要的触发器数目和组

19、合逻辑资源是不同的：不同的： 二进制编码：二进制编码：需要寄存器数目最少，但所需组合逻辑最需要寄存器数目最少，但所需组合逻辑最多，速度最慢；多，速度最慢；这些特性对于这些特性对于PALPAL和门阵列结构和门阵列结构是可以接是可以接受的。但是因为受的。但是因为FPGAFPGA具有许多触发器和较少的组合逻辑资具有许多触发器和较少的组合逻辑资源，高编码的状态变量会导致低的源，高编码的状态变量会导致低的FPGAFPGA速度和密度的实现速度和密度的实现效率。效率。一位独热编码（一位独热编码（One-Hot EncodingOne-Hot Encoding）：）：就是使每个状态占就是使每个状态占用状态寄存

20、器的一位。这种编码方法看起来好像很浪费资用状态寄存器的一位。这种编码方法看起来好像很浪费资源，例如，对于一位热独码编码来说，一个具有源，例如，对于一位热独码编码来说，一个具有1616个状态个状态的在限状态机需要的在限状态机需要1616个触发器，但如果使用二进制编码，个触发器，但如果使用二进制编码，则只需要则只需要4 4个触发器。但是，一位有效编码方法可以简化个触发器。但是，一位有效编码方法可以简化组合逻辑和逻辑之间的内部连接。一位热独码编码可以产组合逻辑和逻辑之间的内部连接。一位热独码编码可以产生较小的并且更快的有效状态机。这对于顺序逻辑资源比生较小的并且更快的有效状态机。这对于顺序逻辑资源比

21、组合逻辑资源更丰富的可编程组合逻辑资源更丰富的可编程ASICASIC来说，是比较有效的编来说，是比较有效的编码方式。特别是码方式。特别是对于对于FPGAFPGA结构来说，一位热独码编码是最结构来说，一位热独码编码是最好的状态编码方式好的状态编码方式。另外，。另外，One-hotOne-hot编码所需的编码所需的 组合逻辑组合逻辑最少最少, ,触发器最多触发器最多, ,工作时钟频率可以做到最高工作时钟频率可以做到最高。21双热码：介于二进制编码和独热编码之间，双热码：介于二进制编码和独热编码之间，每一次状态变每一次状态变化都会带来两个位的跳变，使用化都会带来两个位的跳变，使用n n个寄存器可以实

22、现对个寄存器可以实现对n(n-1)/2n(n-1)/2个状态进行编码个状态进行编码。 GrayGray码：码：就面积与速度的折中考虑来说是最好的选择就面积与速度的折中考虑来说是最好的选择, ,当当然然GrayGray码还有其他很多好的特性码还有其他很多好的特性, ,暂时不属于这次讨论的暂时不属于这次讨论的范畴。范畴。其他编码方式其他编码方式（4 4）状态机编码方式的选择状态机编码方式的选择：一般的综合工具对状态机进行：一般的综合工具对状态机进行综合时都可以让用户对这三种编码进行选择。对于大的基于综合时都可以让用户对这三种编码进行选择。对于大的基于FPGAFPGA的状态机的实现来说，一位有效编码

23、是最佳的方法。对的状态机的实现来说，一位有效编码是最佳的方法。对于较少状态的有限状态机（小于于较少状态的有限状态机（小于8 8个状态），二进制编码可能个状态），二进制编码可能更有效。更有效。为了提高状态机的设计性能，可以将大的状态机为了提高状态机的设计性能，可以将大的状态机（大于（大于3232个状态）分为几个小的状态机，每个状态机都使用个状态）分为几个小的状态机，每个状态机都使用合适的编码方式。合适的编码方式。主干路(major)次要马路(minor)传感器(sensor)常态：主干路绿灯，次要马路红灯变态：有小车在次要马路行使，主干路红灯，次要马路绿灯。灯变化时，计数器开始工作。记时完成，灯

24、恢复常态。 输入l次要马路的车，carl计数器完成记时，timed 输出l主干路灯l次要马路灯l启动计数器（start_timer)例例8.8.4 4：用：用FSMFSM实现交通灯控制实现交通灯控制交通灯控制器major=greenminor=redcarstart_timermajor=redminor=greentimedGR00112 态（G,R）状态框,包含输出:主干路灯G，次要路灯R判断框，条件：car,timed条件输出框，与输出信号在同一个周期里被置位（set)交通灯控制器交通灯控制器交通灯控制器交通灯控制器LIBRARY IEEE; USE IEEE.STD_LOGIC_116

25、4.ALL;USE IEEE.NUMERIC_STD.ALL; ENTITY traffic_light_ctrl IS PORT( clk : IN STD_LOGIC; car : IN STD_LOGIC; timed : IN STD_LOGIC; major_green : OUT STD_LOGIC; manir_gree : OUT STD_LOGIC; start_timer : OUT STD_LOGIC );END traffic_light_ctrl;交通灯控制器ARCHITECTURE rtl OF traffic_light_ctrl IS TYPE state_ty

26、pe IS (G,R); SIGNAL p_state, n_state : state_type; BEGIN交通灯控制器 seq_proc : PROCESS (clk) IS BEGIN IF RISING_EDGE (clk) THEN p_state = n_state; END IF; END PROCESS seq_proc;交通灯控制器 comb_proc : PROCESS (car, timed, p_state) BEGIN start_timer major_green = 1; minor_green = 0; IF (car = 1) THEN start_time

27、r = 1; n_state = R; ELSE n_state major_green = 0; minor_green = 1; IF (timed = 1) THEN n_state = G; ELSE n_state = R; END IF; END CASE; END PROCESS comb_proc; END rtl;同步有限状态机种类 Moore 和Mealy 机lMoore机仅输出当前状态的函数lMealy机输出的是当前状态和输入的函数深圳大学信息工程学院Mealy 状态机下一个状态 = F(当前状态，输入信号)； 输出信号 = G(当前状态，输入信号)；深圳大学信息工程学院

28、Moor e状态机下一个状态 = F(当前状态，输入信号)输出信号 = G(当前状态)；算法状态机ASM 算法状态机（Algorithmic State Machine)l和软件的流程图相似，但包含隐含的时序信息l比状态图更容易让人理解电路的执行过程l常用来描述复杂的时序系统l用状态的变化来描述系统算法状态机ASM状态输出值YAJ01Z=1(a)状态框(b)判断框(c)条件输出框1011判断框深圳大学信息工程学院J01判断框表示状态变量对控制器工作的影响判断框表示状态变量对控制器工作的影响注意：判断框不占用时间注意：判断框不占用时间状态框深圳大学信息工程学院如果一个信号没有被赋值，则它在此状态

29、被置位，而在其如果一个信号没有被赋值，则它在此状态被置位，而在其它状态被复位。它状态被复位。一个状态框占用一个时钟脉冲周期一个状态框占用一个时钟脉冲周期条件输出框深圳大学信息工程学院条件框的入口必定与判断框的输出相连。条件框的入口必定与判断框的输出相连。注意：条件输出框的输出信号与它所属的状态框的输注意：条件输出框的输出信号与它所属的状态框的输出信号（包括判断框）在同一时钟周期内被置位。出信号（包括判断框）在同一时钟周期内被置位。深圳大学信息工程学院ASM图的综合 状态赋值 状态越多，可能的赋值数目随之增加状态越多，可能的赋值数目随之增加 如果状态表中有如果状态表中有m个状态个状态 ，则需要，

30、则需要n个触个触发器发器 One-hot编码，需要编码，需要m个触发器个触发器 l三个状态：三个状态：001，010，100l每次只有一个触发器被置位每次只有一个触发器被置位l次态逻辑可能比较简单次态逻辑可能比较简单l对于可编程的逻辑器件，对于可编程的逻辑器件，one-hot编码系统使用的的资源可能编码系统使用的的资源可能会比用最少数量触发器的系统使用少会比用最少数量触发器的系统使用少l检查系统故障相对容易些检查系统故障相对容易些nnm221ASM EXAMPLE1 序列检测器 检测输入X中是否含有101串 如果输入X中含有101时，那么当输入串101中最后一个1出现时，与此同步就有输出Z=1

31、，且Z=1时电路不复位。X = 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 0Z = 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0Mealy机 VS Moore机Moore机需要更多的状态，不过更容易设计和调试机需要更多的状态，不过更容易设计和调试Moore机的输出不是在状态转移过程中产生的，而是完全由状态本身决定机的输出不是在状态转移过程中产生的，而是完全由状态本身决定Mealy机机Moore机s0Z=0X=1Z=1Z=0X=0Z=0X=1s1s2TTTFFF000110s0Z=0X=1Z=0X=0Z=0X=1s1s2TTTFFF000111Z=1X=1s3

32、T10ASM图的综合 序列检测器（Mealy)当前状态下一状态当前输出ZX=0 X=1X=0X=1S0S0S100S1S2S100S2S0S101ABABZX=0 X=1X=0X=1S0000100S1100100S2000101布尔量状态表One-hot vs. Binary state assignments0Z=0X=1Z=1Z=0X=0Z=0X=1s1s2TTTFFF000110ASM图的综合图的综合 序列检测器（序列检测器（Mealy)XAB010000011011XX1000XAB010001010111XX1001XAB010000010011XX1001B=XZ=X and A

33、ABZ输出由当前状态及输入决定A= (not X) and BASM图的综合 序列检测器（Mealy)次态逻辑次态逻辑寄存器寄存器输出逻辑输出逻辑B=XZ=X and AA=(not X) and BASM图的综合 序列检测器（Moore)当前状态下一状态当前输出ZX=0 X=1X=0X=1S0S0S100S1S2S100S2S0S300S3S2S111ABABZX=0 X=1S000010S110010S200110S310011布尔量状态表s0Z=0X=1Z=0X=0Z=0X=1s1s2TTTFFF000110Z=1X=1s3T11ASM图的综合图的综合 序列检测器（序列检测器（Moore

34、)XAB010000011010011110XAB010001010110011101XAB0000010100111B=XZ=A and BABZ输出由当前状态决定A=(A and not B and X ) or (B and not X)深圳大学信息工程学院ASM图的综合 序列检测器（Moore)次态逻辑次态逻辑寄存器寄存器输出逻辑输出逻辑A=A B X +B XB=XZ=ABFSM的VHDL实现 FSM中时序逻辑部分设计中时序逻辑部分设计 FSM中组合逻辑部分设计中组合逻辑部分设计 在比较复杂的状态机设计过程中，往往把状态的变化与在比较复杂的状态机设计过程中，往往把状态的变化与输出开关

35、的控制分成两部分来考虑。使用这种方法进行设计输出开关的控制分成两部分来考虑。使用这种方法进行设计时，时，FSM中的状态变化（时序逻辑部分）和开关控制（组合中的状态变化（时序逻辑部分）和开关控制（组合逻辑部分）分开独立设计。逻辑部分）分开独立设计。 FSM中时序逻辑部分设计 时序逻辑部分包含寄存器，clock和reset都与之相连，在process中实现，任何一种顺序描述语句都可以使用。51PROCESS ( reset, Clock ) BEGINIF (reset = 1 )THEN pre_state= state0 ; ELSIF (Clock event and clock=1) TH

36、EN pre_state IF (input=) THEN output = ; nx_state IF (input=) THEN output = ; nx_state IF (input=) THEN output = ; nx_state IF (input=) THEN output = ; nx_state = state3; ELSE END IF; END CASE;END PROCESS ; ASM图的VHDL描述 序列检测器LIBRARY IEEE; USE IEEE.STD_LOGIC_1164.ALL;USE IEEE.NUMERIC_STD.ALL; - sequen

37、tial detector- Mealy machineENTITY seq_detector IS PORT( clk : IN std_logic; i_X : IN std_logic; o_Z : OUT std_logic );END seq_detector;ASM图的VHDL描述 序列检测器ARCHITECTURE rtl OF seq_detector IS - binary state assignment type state_type is (s0, s1, s2); signal present_state, next_state : state_type := s0;

38、 - one-hot encoder - constant s0 : std_logic_vector (2 downto 0) := 001; - constant s1 : std_logic_vector (2 downto 0) := 010; - constant s2 : std_logic_vector (2 downto 0) := 100; -signal present_state, next_state : std_logic_vector (2 downto 0); - actual assignment - present_state = s0; BEGINProce

39、ss(clk)Begin if(clkevent and clk = 1) then present_state = next_state; endEnd process; comb_proc : process (next_state, i_X) is begin o_Z if i_X = 1 then next_state if i_X = 0 then next_state if i_X = 1 then next_state = s1; o_Z = 1; else next_state = s0; end if; end case; end process comb_proc; END rtl;ASM图的图的VHDL描述描