针对状态机的综合优化策略

有限状态机及其设计技术是数字系统设计中的重要组成部分，是实现高效率、高可靠性逻辑控制的重要途径。大部分数字系统都可以划分为控制单元和数据单元两个组成部分。通常，控制单元的主体是一个状态机，它接收外部信号以及数据单元产生的状态信息，产生控制信号序列。状态机性能的好坏对系统性能有较大的影响。良好的状态机的实现不仅与状态机的设计有关，而且与采用的综合策略密切相关，不同的综合策略对最终实现的状态机的性能有很大的影响。

Synopsys公司的DC （Design Compiler，设计编译程序）提供了针对状态机的综合优化策略，这个过程既可以完全自动进行，也可以手工进行。本文论述了两种综合策略的实现。

　　1　状态机的基础描述

从数学的角度看，有限状态机可以表示为一个五元组M = （I， O， S，δ，λ） 。其中： I和O 分别表示输入、输出量; S 为状态向量;δ为次态方程（δ： S ×I） ;λ为输出方程（λ： S ×I） 。

从实际状态机的实现角度出发，根据输出方程，有限状态机可以分为3类：

a） 输出是状态向量和输入的函数———Mealy型状态机（λ： S ×I →O ） ;

b） 输出仅是状态向量的函数———Moore 型状态机（λ： S →O ） ;

c） 输出等于状态向量———状态输出型状态机（λ： S = O ） 。

在实际中最常用的状态机是Mealy型和Moore型状态机。

从电路的角度看，有限状态机是由触发器、寄存器和组合逻辑组合成的系统，图1展示了有限状态机的一般结构：一组保存状态向量的触发器，产生次状态和输出的组合逻辑。

图1　有限状态机一般结构

1.1　状态表

为了采用DC的有限状态机优化策略，必须首先把原始的状态机转换为用DC状态表描述的格式，这种转换可以自动完成，也可以手动完成。Synopsys的状态表提供了一种简单的、独立于工艺的有限状态机描述方式。下面是一个状态表的例子

# State table body

Input PresentNextOutput

Value State State Values

0 RESET RESET 00

1 RESET STATE1 01

0 STATE1 RESET 10

1 STATE1 STATE1 11

# Preferred state encoding

.encoding

RESET 2#00

STATE1 2#01

状态表的主体由行组成，每一行描述状态机的一个特定的状态转换。每行有4列：输入值，当前态，次态，输出值。有的输入可以引发状态转换，有的则不会。从状态表可以很容易看出状态机的转换行为。状态表还可以包含一个可选的部分，用于给出首选的状态编码，这些状态编码可以以十进制、二进制或者十六进制给出。

例子中的状态表包括： 1个输入; 2个状态，即RESET和STATE1; 4种输出，即RESET和STATE1分别编码为0 和1。RESET态只在输入为1 时转换到STATE1态，输出变为01，而STATE1态只在输入为0时转换到RESET态，输出变为10。

例子中所有可能的输入输出和状态组合都被用到了，如果状态机用到的状态少于可用的编码，便可以创建只包含所需要使用的状态转换的状态表，其他未指明的状态则按不关心态处理。

1.2　状态向量

状态向量是描述状态机的元素之一，是通过触发器实例名称的有序列表来指定的。指定的触发器存储了有序的位模式，这些位模式定义了有限状态机在任何给定时刻的当前状态。一个特定的触发器位模式与一个状态相对应。例如， ff1、ff2、ff3是触发器的实例名称，则列表{ ff1 ff2 ff3}定义了一个3位的状态向量，这个状态向量可以表示不多于8个状态的有限状态机。

1.3　状态编码

状态编码是描述状态机的另一个元素。有限状态机的状态编码用符号定义了状态机的所有合法状态的位编码。编码确定哪些状态向量的位模式代表合法状态，哪些位模式可以当作不关心态。不关心态提高了工具达到好的优化结果的可能性。大多数以HDL （硬件描述语言）或状态表给出的设计，DC可以直接从代码中提取出状态编码。在工具不能得到状态编码时要使用命令set_fsm_encoding来手动建立状态编码。对于以其他形式给出的设计，必须使用命令set_fsm_encoding手工建立状态编码。

1.4　编码风格

DC在优化中可以使用one2hot （单状态） 、二进制、格雷码和自动编码4种类型中的一种来分派状态机的状态。不同的编码风格可以导致具有很大差异的优化结果。

One2hot风格编码使用与状态机状态数相等的位来编码状态，每一个状态的编码只有1位是1，其余各位都是0，所以这种编码方式需要与状态数相等数目的触发器。这种编码方式简化了组合逻辑，可以获得最快的速度，但同时会大大增加设计的面积。二进制和格雷码编码方式