2011-10-26 6
什么是有限状态机？ 什么是有限状态机？
- 有限状态机是由寄存器组和组合逻辑构成的 硬件时序电路； 硬件时序电路； 其状态（即由寄存器组的1 - 其状态（即由寄存器组的1和0的组合状态所 构成的有限个状态）只能在同一 同一时钟跳变沿 构成的有限个状态）只能在同一时钟跳变沿 的 情况下才能从一个状态转向另一个状态； 情况下才能从一个状态转向另一个状态； 究竟转向哪一状态不但取决于各个输入值， - 究竟转向哪一状态不但取决于各个输入值， 还取决于当前状态。 还取决于当前状态。 状态机可用于产生在时钟跳变沿时刻开关的 - 状态机可用于产生在时钟跳变沿时刻开关的 复杂的控制逻辑，是数字逻辑的控制核心。 复杂的控制逻辑，是数字逻辑的控制核心。
2011-10-26 19
如何写好状态机
评判FSM的标准 （1）FSM要安全，稳定性要高 （2）FSM速度快，满足设计的频率要求 （3）FSM面积小，满足设计的面积要求 （4）FSM设计要清晰易懂、易维护
2011-10-26
20
简单的状态机设计举例
状态转移图表示 RTL级可综合的 RTL级可综合的 Verilog 模块表示
26
表示方法之二
HDL模型来表示同一个有限状态 模型来表示同一个有限状态， 我们还可以用另一个 Verilog HDL模型来表示同一个有限状态， 见下例。 用可综合的Verilog模块设计用独热码one Verilog模块设计用独热码onecode表示状态 见下例 。 （ 用可综合的 Verilog 模块设计用独热码 one-hot code 表示状态 的状态机） 的状态机）
2011-10-26 10
带流水线输出的 Mealy 状态机
下一个状态 = F(当前状态，输入信号)； F(当前状态 输入信号) 当前状态， G(当前状态，输入信号) 输出信号 = G(当前状态，输入信号)； 当前状态
输入
下一状态 激励信号 状态 寄存器 的逻辑 F
clk 输入
当前状态
输出 逻辑 G
//定义状态变量参数值 //定义状态变量参数值
always @(posedge Clock) if (!Reset) //定义复位后的初始状态和输出值 begin //定义复位后的 state <= Idle; K2<=0; K1<=0; 2011-10-26 end
2011-10-26 18
4) 选定触发器的类型并求出状态方程、驱动方程和输 出方程。 5) 按照方程得出逻辑图 用Verilog HDL来描述有限状态机，可以充分发挥 硬件描述语言的抽象建模能力，使用always块语句 和case（if）等条件语句及赋值语句即可方便实现。 具体的逻辑化简及逻辑电路到触发器映射均可由计 算机自动完成。
2011-10-26 12
状态机的基本要素
5.1 状态机介绍 构成： 构成： 1）状态（present state 状态（ next state） state） 2）输入（input） 输入（input） 3）输出（output） 输出（output）
状态机的基本描述方式
状态转移图：用来描述系统状态和变迁情况的有
第5章 状态机
状态机是一种思想方法
2011-10-26
1
2011-10-26
2
为什么要设计有限状态机？ 为什么要设计有限状态机？
如果能严格以时钟跳变沿为前提，按排好时序，来 操作逻辑系统中每一个开关Si，则系统中数据的流 动和处理会按同一时钟节拍有序地进行，可以控制 冒险和竞争现象对逻辑运算的破坏，时延问题就能 有效地加以解决。
Clear
A/K2=1
2011-10-26
图3.4
状态转移图
22
有限状态机的Verilog 有限状态机的Verilog描述 Verilog描述
1. 2. 3. 4. 5. 6. 7.
8.
定义模块名和输入输出端口； 定义模块名和输入输出端口； 定义输入、输出变量或寄存器； 定义输入、输出变量或寄存器； 定义时钟和复位信号； 定义时钟和复位信号； 定义状态变量和状态寄存器； 定义状态变量和状态寄存器； 用时钟沿触发的always块表示状态转移过程 块表示状态转移过程； 用时钟沿触发的always块表示状态转移过程； 在复位信号有效时给状态寄存器赋初始值； 在复位信号有效时给状态寄存器赋初始值； 描述状态的转换过程：符合条件， 描述状态的转换过程：符合条件，从一个状态到 另外一个状态，否则留在原状态； 另外一个状态，否则留在原状态； 验证状态转移的正确性，必须完整和全面。 验证状态转移的正确性，必须完整和全面。
2011-10-26 16
2) 状态化简
如果在状态转换图中出现这样两个状态， 它们在相同的输入下转换到同一状态去，并 得到一样的输出，则称它们为等价状态。显 然等价状态是重复的，可以合并为一个。电 路的状态数越少，存储电路也就越简单。状 态化简的目的就在于将等价状态尽可能地合 并，以得到最简的状态转换图。
向图。（用于设计规划阶段定义逻辑功能，也可用 于分析状态机代码时用。EDA工具支持状态转移图 HDL 作为逻辑设计的输入，可自动翻译成HDL语言代 码。）
状态转移列表：用表的形式将当前状态与下一状
态都表示出来。是数字逻辑电路常用的设计方法， 用于对状态化简。在FPGA设计中，不经常使用。 HDL语言描述状态机：就是应用语言的方式设计。
2011-10-26 4
为什么要设计有限状态机？ 为什么要设计有限状态机？
10ns
clock t S1 S2 S3 t S4 t Sn
2011-10-26
开 关 t t
t
5
为什么要设计有限状态机？
有了以上电路，我们就不难设计出复杂的控制序列 来操纵数字系统的控制开关阵列。能达到以上要求 的电路就是时序和组合电路互相结合的产物：同步 有限状态机和由状态和时钟共同控制的开关逻辑阵 列。 我们只要掌握有限状态机的基本设计方法，加上 对基本电路的掌握，再加上对数据处理的过程的细 致了解，我们就可以避免由于逻辑器件和布线延迟 产生的冒险竞争现象所造成的破坏，设计出符合要 求的复杂数字逻辑系统。
24
表示方法之一（续） 表示方法之一（ else case (state) Idle: Idle: begin if (A)
else end Start: Start: begin if (!A) else end
2011-10-26
begin Start; state <= Start; <=0 K1<=0; end Idle; state <= Idle;
state <= Stop; Stop; state <= Start; Start;
25
表示方法之一（续） 表示方法之一（
Stop: //符合条件进入新状态 符合条件进入新状态， Stop: begin //符合条件进入新状态，否则留在原状态 if (A) begin Clear; state <= Clear; K2<= 1; end Stop; else state <= Stop; end Clear: Clear: begin if (!A) begin Idle; state <= Idle; <=0 <=1 K2<=0; K1<=1; end Clear; else state <= Clear; end endcase endmodule 2011-10-26
输出
时钟信号clk 时钟信号clk
图2. 2011-10-26 时钟同步的状态机结构 (Moor状态机) 9
Moore有限状态机
Moore状态机的输出只与有限状态自动机的当前状 态有关，与输入信号的当前值无关。 Moore有限状 态机在时钟CLOCK脉冲的有效边沿后的有限个门延 后，输出达到稳定值。即使在一个时钟周期内输入 信号发生变化,输出也会在一个完整的时钟周期内保 持稳定值而不变。输入对输出的影响要到下一个时 钟周期才能反映出来。 Moore有限状态机最重要的特点就是将输入与输出 信号隔离开来。
2011-10-26 17
状态分配
状态分配又称状态编码。通常有很多编码 方法，编码方案选择得当，设计的电路可以简 单，反之，选得不好，则设计的电路就会复杂 许多。实际设计时，需综合考虑电路复杂度与 电路性能之间的折衷，在触发器资源丰富的 FPGA或ASIC设计中采用独热编码（one-hotcoding）既可以使电路性能得到保证又可充分 利用其触发器数量多的优势。
输出流 水线寄 存器 clk 输入
输出
时钟信号clk 时钟信号clk
2011-10-26 图3 带流水线输出的Mealy 状态机 11
Mealy和moore型状态机的主要区别
状态机一般分为三种类型： Moore型状态机：下一状态只由当前状态决定，即 次态=f(现状，输入)，输出=f（现状）； Mealy型状态机：下一状态不但与当前状态有关， 还与当前输入值有关，即次态=f(现状，输入)，输出 =f（现状，输入）； 混合型状态机。 Moore型与Mealy型两种状态机的不同点在于， Moore型状态机的输出信号是直接由状态寄存器译 码得到，而Mealy型状态机则是以现时的输入信号 结合即将变成次态的现态，编码成输出信号。
2011-10-26
21
有限状态机的图形表示
图形表示：状态、转移、条件和逻辑开关 图形表示：状态、转移、
A/K1=0 Start !Reset /K2=0 K1=0 Idle !Reset /K2=0 K1=0 Stop !Reset /K2=0 K1=0 !A
（!Reset |!A ）/ K2=0 K1=1
利用同步有限状态机就能产生复杂的以时钟跳变 沿为前提的同步时序逻辑，并提供操作逻辑系统的 开关阵列所需要的复杂控制时序（具有信号互锁和 先后次序等要求的）。