Verilog课件8.ppt

VIII - Working with Sequential Logic ? Copyright 2004, Gaetano Borriello and Randy H. Katz 有限状态机的分析 状态最简化 最少的状态需要最少的状态位 最少的位需要最少的逻辑方程 状态最简化方法 行匹配法 蕴含表方法 状态分配策略 顺序编码 随机编码 单点编码 面向输出的编码 启发式编码 有限状态机的划分 例：简单的自动售货机 自动售货机在收到15美分之后就会给出一件商品，这台机器具有能够接收5美分和1角硬币的单个投币口，每次投入一枚硬币，其中机械传感器用来指示插入投币口是5美分还是1角，控制器的输出导致一件商品交到顾客手中 两个假设简化设计： 不找零 在每次使用前，机器都会复位 例：简单的自动售货机 2、有限状态机抽象表达 列出最终能给出商品的输入顺序: 3个5美分：N，N，N 2个5美分，再1角：N，N，D 1角，5分：D，N 5分，1角：N，D 2个1角：D，D 画状态图: 输入: N, D, reset, clk 输出商品: open 假设: 假设信号N和D从来不会同时为真 省略了自环 N=D=0 (no coin) 只将open信号为真时列出 例：简单的自动售货机 3、状态最简化： 状态S4～S8具有等价，可合并成一个状态 每个状态表示接受到钱的数量 例：简单的自动售货机 4、进行状态分配 4个状态，采用2位状态编码： 0￠（00）、 5￠（01）、 10￠（10）、 15￠（11） 简单的自动售货机(verilog) module autosell (clk, reset, D, N,open); input clk, reset, D,N; output open; parameter cell0= 2b00，cell5 = 2b01, cell10= 2b10, cell15 = 2b11; reg [2:1] state; reg [2:1] next_state; always @(posedge clk) if (reset) state = cell0; else state = next_state; always @(N or D or state) case (state) cell0:  begin if (N) next_state = cell5; else if (D) next_state = cell10; else next_state = cell0; end 例：简单的自动售货机 逻辑电路 例：简单的自动售货机 单点编码 状态简化的等价状态 等价状态:设Si、Sj为两个原始状态，当它们满足以下条件时等效。 对于所有的输入组合 ① 输出相同 ② 它们的次态属于下列情况之一 A．次态相同。Si、Sj的次态均为Sk B．次态交错或为各自的现态。 交错：Si的次态为Sj，Sj 的次态为Si 。 为各自的现态：或Si的次态为Si，Sj的次态为Sj 。 等效类：由若干等效状态构成的集合。等效类中任意两个状态均等效。若存在关系，(S1，S2 )，(S2，S3 ) → (S1，S3 )，则 S1、S2、S3 属于同一等效类。 记作 (S1，S2 )，(S2，S3 ) → | S1、S2、S3 |。 最大等效类：一个等效类不是其他等效类的子集，则该等效类为最大等效类。 状态化简方法 行匹配法：一种良好的人工推导方法，但并不是总能得到最简状态表 蕴含表法：容易用软件实现，并确实能找到可能的最优解 可同时应用这两种方法： 行匹配法能快速化简，减少状态数目。接下来用蕴含表法，由于只针对更少的状态，因此能迅速找到行匹配法遗漏的等价状态 行匹配算法概述 算法概述（由状态转换表开始对状态进行化简） 1. 对状态进行分组，每组中的状态具有相同的输出 2. 检查转换表，查看各组中的状态是否对于所有的输入组合都进入等价的次态，若等价可将它们合并成一个状态，并重新命名。 3.然后将所有的状态转换过程都指向这些新状态 4.重复以上过程，直到再也没有状态可以合并 行匹配法例子 仅通过观察状态表就能判断状态等效 行匹配法化简例子 4比特序列检查器 初始状态图 该状态机具有单一输入X和输出Z，如果每次接收的4比特输入为0110或1010中的一个，则输出为1。状态机每次接收４比特输入后回到复位状态。 假设用米利型机实现： 　　只有在之前的４比特输入匹配指定串中的任意一个，输出才为１ 　　状态机只在每４位比特一组输入后才决定是否输出１ 状态表和行匹配法 状态表：每个状态对应一行，每列对应不同的输入组合的次态和输出 行匹