有限状态机的.ppt

状态分配策略 可能的策略 顺序编码 随机编码 单点编码 面向输出的编码 启发式编码 不能保证结果是最优的 – 另一个复杂的问题 VIII - Working with Sequential Logic ? Copyright 2004, Gaetano Borriello and Randy H. Katz * 顺序编码 简单的将符号状态名字替换成为规则的编码，设计者仅需要保证每个状态对应唯一的编码，以保证组合逻辑能够区分各个状态 VIII - Working with Sequential Logic ? Copyright 2004, Gaetano Borriello and Randy H. Katz * 单点编码 简单 容易编码、容易诊断和修改 小规模的逻辑函数 每个状态位对应方程中所含或项的数目和状态图中指向该状态的所有弧对应项的总数相同 适合于FPGA实现 大量的触发器可用 对大的状态机不实用 太多的状态需要太多的flip-flops 对大的有限状态机划分成小块可用单点编码 对单点编码进行一些改变 one-hot + all-0 VIII - Working with Sequential Logic ? Copyright 2004, Gaetano Borriello and Randy H. Katz * 用m位状态位编码m个状态，每个状态的单点编码只有在对应的位上为1，在其它位上均为0 随机编码 这是更简单的策略，随机选择可能的编码进行分配，它仅需要保证每个状态对应唯一的编码，以保证组合逻辑能够区分各个状态 VIII - Working with Sequential Logic ? Copyright 2004, Gaetano Borriello and Randy H. Katz * VIII - Working with Sequential Logic ? Copyright 2004, Gaetano Borriello and Randy H. Katz * 面向输出的编码 对于摩尔型，输出直接与状态位有关，但如果设计者直接实现摩尔型输出(即触发器的输出就是状态机的输出），则可以使用输出来区别状态 同步米利型输出也是通过触发器的输出直接实现，因此也可以这样用 对于整个状态机都使用面向输出的编码方式并不是很好的策略，明智的使用部分输出作为编码，也许能减少状态位的数量 启发式方法 该方法试图缩短相关状态间的布尔空间的距离。如状态Y用状态X转换而来，则它们的状态编码中的不同比特位应尽量少 状态图：类似于卡诺图，提供观察状态分配的相邻性的方法。 VIII - Working with Sequential Logic ? Copyright 2004, Gaetano Borriello and Randy H. Katz * 状态图中的方格按照状态位的二进制值进行索引，给出该编码的状态便放在图中对应的的方格里（最多能处理26个状态） 最少位变化启发式方法 目的是使所有状态间的转换中发生变化的位数最少 第二种分配方案： 分配S0，由于复位逻辑工作，通常将全0分配给起始状态 接下来分配S1、S2，将它们放在S0邻近位置 然后将S3放在S1、S2之间 最后将S4放在S3附近 VIII - Working with Sequential Logic ? Copyright 2004, Gaetano Borriello and Randy H. Katz * 基于次态和输入/输出的启发式方法 最高优先级：在给定的输入转换条件下，具有相同次态的状态应该在状态图中放到邻近的位置  中等优先级：具有相同现态的次态应放在状态图中邻近的位置  最低优先级：在给定输入的情况下，具有相同输出的状态应该放在状态中邻近的位置上 VIII - Working with Sequential Logic ? Copyright 2004, Gaetano Borriello and Randy H. Katz * I Q Q+ Oi a c ji b c k I Q Q+ Oi a b jk a c l I Q Q+ Oi a b ji c d j c = i * a + i * b b = i * ac = k * a j = i * a + i * cb = i * ad = i * c i / j i / k a b c a b c i / j k / l b d i / j a c i / j 例1：3比特序列检测器，当检测到010或110时输出为1 最高优先级：相同输入下具有同一次态的状态。S3’、S4’ 中等优先级：具有相同状态的