状态机与时序图.ppt

状态机与时序图1.认识状态机•对象：静态属性和动态行为•状态（state）：是指在对象的生命周期中满足某些条件、执行某些活动或等待某些事件的条件（condition）或状况（situation）•状态机图通过对类对象的生存周期建立模型来描述对象随时间变化的动态行为，也可以用来描述用例、协作和方法的动态行为，它是展示状态与状态转换的图•状态机是一个对象所有可能的生命历程的模型描述对象的一种方式1.认识状态机•状态的一大特性就是转化状态不是孤立的，换句话说，状态是变化的，是会互相转换的•状态转换是两个状态之间、两个活动之间或者一个活动和一个状态之间的关系可以从一个状态发出一个或多个状态转换，前提是转换要唯一从一个状态发出的转换不能具有相同的事件，除非事件中有多个条件•两个状态转换的原则：•1、转化本身的逻辑性￿- 并非所有的状态之间都可以任意转化；•2、转化的外界因素￿- 转化的时候需要一个外因1.认识状态机•玩家所扮演的小人，就存在三种状态：小人跑动(move)、小人站立静止(stand)、小人在空中坠落(falling)1.认识状态机•状态机图上的转换条件，即图中数字代表的意义：•1、移动出了挡板，从空中坠落：M->F•2、坠落途中掉在挡板上，站立: F->S•3、用户按左、右键，或者掉在了有“方向履带”的挡板上，小人跑动起来: S->M•4、用户停止按键并且小人站在非“方向履带”的挡板上，小人站立: M->S•注意:　S->F　和　F->M　是不成立的。

2.状态机的作用•描述直观形象、易读易懂•易构成性能良好的时序逻辑模块•结构简单、层次分明、易排错•运行模式类似CPU，易于进行顺序控制•高可靠性，非法状态可控制3.状态机的设计•有限状态机设计的一般步骤：•1)逻辑抽象，得出状态转换图•就是把给出的一个实际逻辑关系表示为时序逻辑函数，可以用状态转换表或状态转换图来描述这就需要：••分析给定的逻辑问题，确定输入变量、输出变量以及电路的状态数通常是取原因（或条件）作为输入变量，取结果作为输出变量••定义输入、输出逻辑状态，并将电路状态顺序编号••按照要求列出电路的状态转换表或画出状态转换图•这样，就把给定的逻辑问题抽象到一个时序逻辑函数了3.状态机的设计•2)状态化简•如果在状态转换图中出现这样两个状态，它们在相同的输入下转换到同一状态去，并得到一样的输出，则称它们为等价状态显然等价状态是重复的，可以合并为一个电路的状态数越少，存储电路也就越简单状态化简的目的就在于将等价状态尽可能地合并，以得到最简的状态转换图•3)状态分配•状态分配又称状态编码通常有很多编码方法，编码方案选择得当，设计的电路可以简单，反之，选得不好，则设计的电路就会复杂许多。

3.状态机的设计•4）状态机选型：￿Mealy型和Moore型•从输出时序上看，Mealy状态机的输出是当前状态和所有输入信号的函数，它的输出是在输入变化后立即发生的，不依赖时钟的同步Moore型状态机输出则仅为当前状态的函数，状态机的输入发生变化还必须与状态机的时钟同步•5）HDL代码描述三要素：•首先需要在状态存储中存储这些状态－－同步进程•其次需要有下一个状态的逻辑关系－－状态转化进程•另外还需要有输出信号的逻辑关系－－输出描述进程•常用case……when……when……others……语句3.状态机的设计•例1：设计用来检测二进制输入序列的检测电路，当输入序列中连续输入4位数码均为1时，电路输出为1，其它为0•第一步：建立原始状态图•首先根据设计要求，分析清楚电路的输入和输出，确定有多少种输入信息需要“记忆”，对每一种需“记忆”的输入信息规定一种状态来表示，根据输入的条件和输出要求确定各状态之间的关系，从而构成原始状态图•本例电路有一个输入端X，接收被检测的二进制序列串行输入；有一个输出端Z电路的工作与输入序列必须同步3.状态机的设计•根据检测要求，当输入的二进制序列连续输入4个1时，输出为1，其余情况输出为0。

所以该电路必须“记忆”3位连续输入序列，一共8种情况，即000、100、010、110、001、101、011、111只有当3位连续输入为111，第4位也输入1时，输出才为1将需“记忆”的8种情况分别用状态A、B、C、D、E、F、G、H来表示，每次输入信号二进制序列X仅0、1两种可能3.状态机的设计•第二步：状态简化•状态等价条件：在所有输入条件下，两个状态对应输出完全相同；在所有输入条件下，两个状态转移效果完全相同•状态等价有传递性：S1S2,S2S3,则S1S3•采用列表比较的方法进行状态化简：•寻找全部等价对•表呈直角形网络形式，称隐含表表中每一个小方格代表一个状态对根据等价条件将各列状态和各行状态一一进行比较，比较结果填入小方格中3.状态机的设计•原始状态图中，两个状态输出不同，则为不等价状态如H与A-G状态，方格中填入X•在任何输入条件下，输出值都相同，且在任何输入条件下所对应的下一个状态也相同，则为等价状态，如A－E等，方格中填入Y•在任何输入条件下，输出值都相同，但在有些输入条件下，下一状态不相同，如A-B等，则将这些不相同的下一状态对填入到相应的方格中3.状态机的设计•H状态与其它各状态均不等价，则凡是隐含条件中包含H状态的状态对均不可能等价。

进一步化简如右图所示3.状态机的设计•D状态与其它状态均不等价，则隐含条件中包含D状态的状态对均不等价化简如右图所示•此时AC、AG、CE、EG等价的隐含条件均为AE和BF等价•故所有等价对为AC、AE、AG、BF、CE、CG、EG•其中ACEG等价，BF等价•由于AB不等价，最大等价类为：ACEG、BF、D、H3.状态机的设计•把（ACEG）合并为状态a，（BF)合并为状态b，（D）改写为d，（H）改写为h其简化后的状态图如右图所示3.状态机的设计•第三步：状态编码•一般有热独(ONE-HOT)编码和二进制编码•本例中，进行热独编码：a为0001，b为0010，c为0100，d为1000•第四步：状态机选型•从输出时序上看，Mealy状态机的输出是当前状态和所有输入信号的函数，它的输出是在输入变化后立即发生的，不依赖时钟的同步Moore型状态机输出则仅为当前状态的函数，状态机的输入发生变化还必须与状态机的时钟同步本例中采用Mealy型状态机￿3.状态机的设计•第五步：HDL代码描述•本例采用经典的三进程描述如下Type mystate is (a, b, d, h); Signal curren_state,next_state:mystate;•process (CLOCK, RESET) --同步进程￿•begin •if (RESET=‘1’) then curren_state￿<= a;--a为初始状态￿•elsif (CLOCK'event and CLOCK = '1') then •curren_state <= next_state; --现态￿<= 次态; •end if; •end process; 3.状态机的设计•process (curren_state, X) --状态转化进程￿•begin •case curren￿is •when￿a=> • if (X=‘0’) then • next_state <= a;• else next_state <= b; • end if; •when b =>￿• if(X=‘0’) then• next_state <= a;• else next_state <= d;• end if; when d=> • if (X=‘0’) then • next_state <= a;• else next_state <= h; • end if; •when h =>• if(X=‘0’) then• next_state <= a; • else next_state <= h;• end if;•when others => null;•end case; •end process; 3.状态机的设计•process(curren_state,X) --输出描述进程￿•begin •case curren_state￿•when h=> • if (X=‘1’) then • Z <= ‘1’; • else Z <= ‘0’;• end if; •when others => • Z <= ‘0’;•end case •end process; 4.时序图•时序图反应了模块的输入输出信号随时间变化的情况。

可以帮助理解模块的功能，直观的反应信号的变化及其相互关系•例1中的时序图如下所示：•只有X连续输入4个‘1’时，Z输出为‘1’，否则为‘0’4.时序图•时序图的问题：•要将模块的所有功能描述出来，时序图要把输入信号和输出信号的所有可能状态都反应出来，这样需要时序图的周期个数要尽可能的多些，输入信号的变化尽可能的多些•时序图一般用来辅助理解模块的功能，模块一般需要文字性或状态机的功能描述•时序图不便于HDL语言的描述5.时序图到状态机•时序图到状态机，一般要求时序图反应了所有输入和输出随时间的变化情况•然后分析输入和输出的关系，列出真值表，再根据真值表画出状态图•如例1中，根据其时序图，发现只有Ｘ连续4个周期为1时，Ｚ才是1，其它为0则按照第3节所述的方法进行状态机的设计•有一类特殊的时序图：读写时序图（接口时序图）•该类时序图反应了模块之间接口信号随时间变化情况，一般描述了模块之间读写的情况5.时序图到状态机•例2　异步静态RAM读时序5.时序图到状态机•异步静态RAM写时序5.时序图到状态机•从上面两张时序图中可以分析出，静态RAM的读写时序都分成三个部分：Setup、Strobe、Hold。

读写接口信号：EM_CS、EM_A、EM_D、EM_OE、EM_WE、EM_RW，随时间也有不同变化•这样可以把读写时序分成5个状态：Setup、Read、Write、Hold、Idle在Idle状态下，不读不写，EM_CS为无效Setup状态，EM_CS为有效，EM_RW分别为读写，EM_WE和EM_OE为无效Read状态，EM_OE有效，EM_WE无效Write状态，EM_WE有效，EM_OE无效Hold状态，￿EM_WE和EM_OE均无效•确定状态转移的条件，这里用到计数器，Setup和Hold均为2个clk；而Read和Write均为3个clk；从Idle到Setup，需要使EM_CS有效5.时序图到状态机•经上述分析，静态RAM读写时序状态机如下所示。