基于粒计算的完全确定时序逻辑电路状态化简算法

GrC-based State Reduction Algorithm for Completely Specified Sequential Logic Circuit

状态化简是指通过一定算法消除时序逻辑电路中的冗余状态,进而降低电路复杂性、减少功耗和提高系统可靠性.完全确定时序逻辑电路指是指输出和次态不存在不确定状态的电路,其状态化简的本质是根据等价关系,寻找最大状态等价类的过程.本文将粒计算理论应用到传统的状态化简问题中,提出基于粒计算的状态化简算法.在定义输出矩阵和状态转移矩阵基础上,根据迭代原则,从粗粒度到细粒度,利用等价关系对论域元素持续进行分层粒化,直到分类不再改变得到所需的最大等价类(粒子).实验结果与分析表明,该算法准确有效.

State reduction refers to eliminate redundant states in the sequential logic circuit, which can help reduce the number of components, decrease the complexity and power cost of the circuit and improve system reliability. There are no uncertain states in the completely specified sequential logic circuit, and the key point for state reduction in such circuits is to find the maximal equivalence classes. By introducing Granular Computing （GrC） method, a CJrC-based state reduction algorithm was proposed in this paper. Output matrix and transfer matrix was defined first, then the equivalence relation is continuously applied to partition the elements in the universe from coarser granularity to finer granularity until the biggest equivalence classes （granule） are obtained. The experimental results and analysis show the accuracy and efficiency of the proposed algorithm.