空间管理您的位置: EDA中国门户网站 » chenhongyi的个人空间 » 日志

状态机学习笔记

上一篇 / 下一篇 2007-04-11 23:57:37 / 天气: 晴朗 / 心情: 高兴

查看( 634 ) / 评论( 65 )

FSM (finite state machine)学习笔记

chenhongyi 4.11

1．为什么要使用状态机
利用VHDL设计的实用逻辑系统中，有许多是可以利用有限状态机的设计方案来描述和实现的。无论与基于VHDL的其它设计方案相比，还是与可完成相似功能的CPU相比较，状态机都有其难以超越的优越性，它主要表现在以下几方面：
a. 有限状态机克服了纯硬件数字系统顺序方式控制不灵活的缺点。状态机的工作方式是根据控制信号按照预先设定的状态进行顺序运行的，状态机是纯硬件数字系统中的顺序控制电路，因此状态机在其运行方式上类似于控制灵活和方便的CPU，而在运行速度和工作可靠性方面都优于CPU。
b. 由于状态机的结构模式相对简单，设计方案相对固定，特别是可以定义符号化枚举类型的状态，这一切都为VHDL综合器尽可能发挥其强大的优化功能提供了有利条件。而且，性能良好的综合器都具备许多可控或自动的专门用于优化状态面的功能。
c. 状态机容易构成性能良好的同步时序逻辑模块，这对于对付大规模逻辑电路设计中令人深感棘手的竞争冒险现象无疑是一个上佳的选择。为了消除电路中的毛刺现象，在状态机设计中有多种设计方案可供选择。
d. 与VHDL的其它描述方式相比，状态机的VHDL表述丰富多样、程序层次分明，结构清晰，易读易懂；在排错、修改和模块移植方面也有其独到的特点。
e. 在高速运算和控制方面，状态机更有其巨大的优势。由于在VHDL中，一个状态机可以由多个进程构成，一个结构体中可以包含多个状态机，而一个单独的状态机（或多个并行运行的状态机）以顺序方式所能完成的运算和控制方面的工作与一个CPU的功能类似。因此，一个设计实体的功能更类似于一个含有并行运行的多CPU的高性能微处理器的功能。
f. 尽管CPU和状态机都是按照时钟节拍以顺序时序方式工作的，但CPU是按照指令周期，以逐条执行指令的方式运行的；每执行一条指令，通常只能完成一项简单的操作，而一个指令周期须由多个机器周期构成，一个机器周期又由多个时钟节拍构成；相比之下，状态机状态变换周期只有一个时钟周期，而且，由于在每一状态中，状态机可以完成许多并行的运算和控制操作。一般由状态机构成的硬件系统比CPU所能完成同样功能的软件系统的工作速度要高出三至四个数量级。
g.就可靠性而言，状态机的优势也是十分明显的。CPU本身的结构特点与执行软件指令的工作方式决定了任何CPU都不可能获得圆满的容错保障。因此，用于要求高可靠性的特殊环境中的电子系统中，如果以CPU作为主控部件，应是一项错误的决策。然而，状态机系统就不同了，首先它是由纯硬件电路构成，不存在CPU运行软件过程中许多固有的缺陷；其次是由于状态机的设计中能使用各种完整的容错技术；再次是当状态机进入非法状态并从中跳出，进入正常状态所耗的时间十分短暂，通常只有2、3个周期，约数十个ns，尚不足以对系统的运行构成损害；而CPU通过复位方式从非法运行方式中恢复过来，耗时达数十ms，这对于高速高可靠系统显然是无法容忍的。
2.  有限状态机及其技术是实用数字系统设计中的重要组成部分，是实现高效率高可靠逻辑控制的重要途径。
      VHDL中的枚举数据类型是一种特殊的数据类型，它们是用文字符号来表示一组实际的二进制数。例如，状态机的每一状态在实际电路中是以一组触发器的当前二进制数位的组合来表示的，但设计者在状态机的设计中，为了更利于阅读、编译和VHDL综合器的优化，往往将表征每一状态的二进制数组用文字符号来代表，即所谓状态符号化。例如：

111.jpg
在这里，信号present_state和next_state的数据类型定义为states，它们的取值范围是可枚举的，即从st0~st5共六种，而这些状态代表六组惟一的进制数值。
在综合过程中，枚举类型文字元素的编码通常是自动设置的，综合器根据优化情况、优化控制的设置或设计者的特殊设定来确定名元素具体编码的二进制位数、数值及元素间编码顺序。一般情况下，编码顺序是默认的，如一般将第一个枚举量（最左边的量）编码为‘0’或‘0000’等，以后的依次加1。综合器在编码过程中自动将每一个枚举量元素转变成位矢量，位矢量的长度根据实际情况决定。如前例中用于表达6个状态的位适量长度可以为3，编码默认为：st0=“000”，st1=“001”，st2=“010”，st3=“011”，st4=“100”，st5=“101”。
一般地，编码方式也会因综合器及综合控制方式不同而不同，为了某些特殊的需要，编码顺序也可以人为设置。
用Type语句来定义符号化的枚举类型，并将状态机中的现态和次态的类型定义为相应的数据类型将有助于综合器对状态机设计程序的优化设计。

3．一般有限状态机的设计

在有限状态机的设计中，需要有三个不可缺少的设计要素，首先需要在状态存储中存储这些状态，其次需要有下一个状态的逻辑关系，另外还需要有输出信号的逻辑关系。状态机的设计包含两个主要过程，一是状态机的建模，二是状态机的编码。
W&orn[0L@Z0

3.1 有限状态机的建模EDA中国门户网站JJmb {0jE

有限状态机通常使用CASE语句来建模，一般的模型由两个进程组成，一个进程用来实现顺序逻辑电路，另一个进程用来实现组合逻辑电路，如果需要的话，还可以使用更多的进程。通常，状态机制状态信息储存在一个信号中。CASE语句的多个分支包含了每个状态的行为。不同数量的进程对于程序的仿真和综合具有不同的影响。EDA中国门户网站LK4m:iFE4p|o

a 结构和可读性。因为VHDL模型的组合逻辑单元和存储单元为两个不同的结构单元，如果它们被分开建模，即它们的VHDL代码放置在两个进程中，则VHDL代码的结构和可读性都比较好。但是，设计者可能只关心状态机的状态变化，这些变化可以从模型的外部观察到，设计中，一个进程描述就已经足够实现这个目标了。但是从程序的可读性来说，这并不是最好的。EDA中国门户网站+e/TY,dhM

b 仿真。仿真来说，两个进程的结构更加有助于错误的定位。因为通过仿真，可以访问下一个状态的信号波形，从而很容易确定错误发生的位置（发生在那个进程中）。
1f7E~!v ~ \T1M0

c 综合。仿真算法是基于启发式实现的。如果使用两个进程描述有限状态机，其结构更接近硬件结构，因此仿真工具易于产生更好的仿真结果。

总之，使用两个进程来描述有限状态机是比较好的结构，程序结构清晰，可读性好，程序的仿真和综合特性也比较好。

3.2 有限状态机的编码
(} x9U,W%`7wU3X0

有限状态机的编码对于其能否在FPGA中高效实现是一个关键。用于产生状态机逻辑的传统方法会产生高编码的状态变量。具有高编码状态变量的状态机需要一个最少数量的触发器和较多的组合逻辑。这些特性对于PAL和门阵列结构是可以接受的。但是因为FPGA具有许多触发器和较少的组合逻辑资源，高编码的状态变量会导致低的FPGA速度和密度的实现效率。EDA中国门户网站+O3[wPF|7L;x5s

利用一位热独编码（One-Hot Encoding）可以创建更有效地在FPGA结构中实现的有限状态机。每个状态可以使用一个触发器来创建状态机，并且可以降低组合逻辑的密度。对于大的基于FPGA的状态机的实现来说，一位有效编码是最佳的方法。对于较少状态的有限状态机（小于8个状态），二进制编码可能更有效，为了提高状态机的设计性能，可以将大的状态机（大于32个状态）分为几个小的状态机，每个状态机都使用合适的编码方式。EDA中国门户网站%Rk Y6_Vh7l#i
3.3分类EDA中国门户网站wn8_%Q7i(o

用VHDL设计的状态机有多种形式，从状态机的信号输出方式上分：有Mealy型和Moore型两种；从结构上分：单进程状态机和多进程状态机；从状态表达方式上分有符号化状态机和确定状态编码的状态机；从编码方式上分有顺序编码状态机、一位热独码编码状态机或其它编码方式状态机。
SdYm U8nY0

一位独热编码就是使每个状态占用状态寄存器的一位。这种编码方法看起来好像很浪费资源，例如，对于一位热独码编码来说，一个具有16个状态的在限状态机需要16个触发器，但如果使用二进制编码，则只需要4个触发器。但是，一位有效编码方法可以简化组合逻辑和逻辑之间的内部连接。一位热独码编码可以产生较小的并且更快的有效状态机。这对于顺序逻辑资源比组合逻辑资源更丰富的可编程ASIC来说，是比较有效的编码方式。特别是对于FPGA结构来说，一位热独码编码是最好的状态编码方式。
$v5H?L8M0

3.4定义编码方式的语法格式EDA中国门户网站ge*m'es}P

大多数综合工具都为有限状态机的编码提供了一个设置。通过该设置，用户可以选择一种编码方式。可以通过设置的编码方式有：一位热独码编码、二进制编码、格雷编码、顺序编码等。
(L*^3HFU:`)u;G r!W0

例如定义二进制编码的状态矢量的语句和定义一位热独码编码语句为：
A]Ei ?}~J0EDA中国门户网站8kv"a,L'_Zm
2.jpg
3kV1`2?yje0

3.5初始化状态机

当实现状态建模时，特别是使用一位有效编码方式时，用户应该初始化有限状态机，这样可以确保有限状态机开始工作时处于一个确定的状态。通常初始化有限状态机在实现顺序逻辑的进程中进行，例如下面的进程语句：
\2W}Ia5UY&v2@u0 EDA中国门户网站9L1| I j8x_Slu
EDA中国门户网站fI"v/Yfc
3.jpg