数字IC基础：状态化简与等价状态

相关阅读数字IC基础专栏https://blog.csdn.net/weixin_45791458/category_12365795.html?spm1001.2014.3001.5482如果时序机的两个状态对于所有可能的输入序列都具有相同的输出序列和相同的下一状态则称这两个状态是等价的。时序机的等价状态无法通过观察输出序列的异同对其加以区分合并等价状态也不会改变状态机的输入输出特性。通过识别合并等价状态也不会改变状态机的输入-输出特性。通过识别合并等价状态可以化简时序机的状态表与状态转移图并且在无需综合考虑电路功能的情况下减少硬件开销因为没必要对等价状态进行编码。一般而言对每一个有限状态机来说都会存在至少一个唯一的最简等效状态机。状态表如表1所示的状态机有两个等价状态S_4与S_5。在输入信号的作用下两个状态S_4和S_5具有相同的下一状态和输出。也就是说当状态机处于状态S_4并有输入序列作用时其输出与状态机处于S_5且在相同输入序列作用下时的输出是完全相同的。图1给出了该状态机的状态转移图并说明了状态S_4与状态S_5如何映射到相同的下一状态并且对所有的有效输入这两个等价状态都具有相同的输出。表1 等价状态S_4与S_5的下一状态表和输出表。用S_4代替S_5并将S_5所在行删除以此来化简该表下一状态输出输入输入当前状态0101S_0S_6S_300S_1S_1S_601S_2S_2S_5应使用S_4代替01S_3S_7S_301S_4S_7S_200S_5删除该行S_7S_200S_6S_0S_100S_7S_4S_300图1 等价状态的状态转移图如果时序机状态表中与两个状态有关的行是相同的则称这两个状态是等价的。删除一个等价状态外的其余全部等价状态并使受此影响的弧线重新指向保留的最后一个等级状态就会使状态转移图得到简化。但是需要注意当两个状态在状态表中相应的行不同时也不要轻易得出这两个状态不是等价状态的结论下一状态表中完全相同行的条件仅是其对应状态等价的充分条件而不是必要条件。因此仅仅比较状态表中的行并不是判别等价状态的充分方法还存在这种方法可能检测不到的其他等价状态。删除等价状态更一般的方法依赖于如下的等价递归定义如果两个状态对各输入值具有相同的输出并且对同样的输入值它们所转移到的下一状态也是相同或等价的则这两个状态是等价的。删除等价状态的步骤可归纳为1画出一个三角形的表格参见表2来表示不同状态的可能组合对2分析组合对状态的等价条件由原状态表已经知道S_4与S_5是等价的所以这里就不再考虑S_5了。再来看一个例子如果S_0与S_4转移到的下一状态是等价的并且它们对各个可能的输入所对应的输出也是相同的则认为S_0和S_4是等价状态。图1所示的状态表中S_0与S_4具有相同的输出但只有当S_6与S_7等价并且S_2与S_3等价这两个条件同时满足时S_0与S_4才是等价的。表2 表示可能等价状态对的表格S_1不可能S_2不可能S_6和S_4S_3不可能S_1和S_7、S_6和S_3S_2和S_7、S_4和S_3S_4S_6和S_7、S_3和S_2不可能不可能不可能S_6S_3和S_1不可能不可能不可能S_7和S_0、S_2和S_1S_7S_6和S_4不可能不可能不可能S_2和S_3S_0和S_4、S_1和S_3S_0S_1S_2S_3S_4S_6在表格的对应行列中列出了行列所对应的一对状态的等价条件。例如当状态机处于状态S_1时如果输入0或1其下一状态分别为S_1或S_6同样当状态机处于S_3时在上述相同输入的作用下它的下一状态分别为S_7与S_3。因此S_1与S_3等价的充要条件是S_1与S_7等价且S_6与S_3等价当然此时他们在相同输出时的输出要是一样的如果这个违反了就会被标记为不可能。在所有可能等价的状态中我们从表中可以发现S_1与S_3不等价因为S_1与S_7在表中被标记为不可能等价S_2与S_3也不等价因为S_2与S_7在表中被标记为不可能等价。在探讨S_7与S_0的等价关系时我们会遇到一些问题S_7与S_0等价要求S_6和S_4等价S_6和S_4等价要求S_7和S_0、S_2和S_1都等价而S_2和S_1等价又要求S_6和S_4等价我们会发现其中存在许多循环等价即A能证明BB能证明A这并不能判断A、B是否为真。但是我们的原则是无矛盾则接受。如果我们认为S_7与S_0、S_6和S_4、S_2和S_1分别等价且这并不会产生矛盾能逻辑自洽则就这么做因为这样能减少状态机的状态数。最后可以得到图2所示的简化状态转移图只包含了4个状态而非8个。图2 完全化简的状态转移图以上内容来源于《Verilog HDL高级数字设计》