分辨矩阵在逻辑优化中的应用  

Discernibility Matrix and Its Application in Logical Optimization

作　　者：闫心怡 温馨 陈泽华 YAN Xinyi;WEN Xin;CHEN Zehua(College of Electrical and Power Engineering,Taiyuan University of Technology,Taiyuan 030024,China;College of Data Science,Taiyuan University of Technology,Taiyuan 030024,China)

机构地区：[1]太原理工大学电气与动力工程学院,太原030024 [2]太原理工大学大数据学院,太原030024

出　　处：《计算机科学与探索》2021年第7期1332-1338,共7页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金(61703299);国家重点研发计划(2018YFB1404500)。

摘　　要：真值表的化简对于逻辑电路的分析与设计具有及其重要的意义。对真值表的化简问题进行研究,提出了一种利用分辨矩阵从真值表中获取最小布尔表达式的粒分辨矩阵方法,实现其在逻辑优化中的应用。首先,将真值表视为逻辑信息系统,将真值表的化简问题转化为逻辑信息系统的最简规则发现问题。然后,在传统分辨矩阵的基础上,利用等价关系模型构造粒分辨矩阵,找出可以组织成最小布尔表达式的信息粒,利用信息粒的析取合取运算获得逻辑信息系统的最小布尔表达式。为进一步加快算法的收敛速度,引入启发式信息的概念,给出了组织信息粒的判定法则,避免在最小布尔表达式的获取中出现冗余逻辑项,使得布尔逻辑表达式最简,同时提高最小布尔表达式的获取效率,解决大规模逻辑电路的优化问题。最后,给出了详细的算法,并通过实例和理论证明说明了该方法的正确性和有效性。The simplification of truth table is of great significance to the analysis and design of logic circuits.In this paper,the simplification of truth table is studied,and a method of GDM(granular discernibility matrix)that uses discernibility matrix is proposed to obtain the minimum Boolean expression from truth table,and its application in logic optimization is realized.Firstly,the truth table is regarded as a logical information system and the simplification of truth table is transformed into the problem of finding the simplest rules of the logical information system.Then,based on the traditional discernibility matrix,the equivalent relation model is used to construct the GDM,the information granular that can be organized into the minimum Boolean expression is found,and the minimum Boolean expression of the logical information system is obtained by using the disjunctive and conjunction operation of the information granular.In order to accelerate the convergence speed of the algorithm,the heuristic information is introduced,and the decision rule of organizing information granular is given to avoid the occurrence of redundant logic items in the acquisition of the minimum Boolean expression,making Boolean logic expression simplest.The acquisition efficiency of the minimum Boolean expression is improved,and the problem of large-scale logic circuit optimization is solved.Finally,the algorithm is described in detail through an example,and its correctness is proven mathematically.Finally,a detailed algorithm is given,and the correctness and effectiveness of the method are demonstrated through examples and theoretical proofs.

关 键 词：真值表 规则发现 分辨矩阵 最小布尔表达式 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]