Discernibility Matrix and Its Application in Logical Optimization

doi:10.3778/j.issn.1673-9418.2005006

Abstract

Abstract:

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.

Key words: truth table, rule discovery, discernibility matrix, minimal Boolean expression

摘要：

真值表的化简对于逻辑电路的分析与设计具有及其重要的意义。对真值表的化简问题进行研究，提出了一种利用分辨矩阵从真值表中获取最小布尔表达式的粒分辨矩阵方法，实现其在逻辑优化中的应用。首先，将真值表视为逻辑信息系统，将真值表的化简问题转化为逻辑信息系统的最简规则发现问题。然后，在传统分辨矩阵的基础上，利用等价关系模型构造粒分辨矩阵，找出可以组织成最小布尔表达式的信息粒，利用信息粒的析取合取运算获得逻辑信息系统的最小布尔表达式。为进一步加快算法的收敛速度，引入启发式信息的概念，给出了组织信息粒的判定法则，避免在最小布尔表达式的获取中出现冗余逻辑项，使得布尔逻辑表达式最简，同时提高最小布尔表达式的获取效率，解决大规模逻辑电路的优化问题。最后，给出了详细的算法，并通过实例和理论证明说明了该方法的正确性和有效性。

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

YAN Xinyi, WEN Xin, CHEN Zehua. Discernibility Matrix and Its Application in Logical Optimization[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(7): 1332-1338.

闫心怡, 温馨, 陈泽华. 分辨矩阵在逻辑优化中的应用[J]. 计算机科学与探索, 2021, 15(7): 1332-1338.

References

[1] YAN S. Fundamentals of digital electronics[M]. 5th ed. Beijing: Higher Education Press, 2006.
阎石. 数字电子技术基础[M]. 5版. 北京: 高等教育出版社, 2006.
[2] SKOWRON A, RAUSZER C. The discernibility matrices and functions in information systems[M]//SLOWINSKI R. Intelligent Decision Support-Handbook of Applications and Advances of the Rough Sets Theory. Berlin, Heidelberg: Springer, 1992.
[3] SKOWRON A. A synthesis of decision rules: applications of discernibility matrix[M]//LIN T Y, CERCONE N. Rough Sets and Data Mining Analysis of Imprecise Data. Hingham: Kluwer Academic Publishers, 1993.
[4] YIN L Z, YANG C H, WANG X L, et al. An incremental algorithm for attribute reduction based on labeled discerni-bility matrix[J]. Acta Automatica Sinica, 2014, 40(3): 397-404.
尹林子, 阳春华, 王晓丽, 等. 基于标记可辨识矩阵的增量式属性约简算法[J]. 自动化学报, 2014, 40(3): 397-404.
[5] QIAN W, SHU W, XIE Y, et al. Feature selection using com-pact discernibility matrix-based approach in dynamic incom-plete decision system[J]. Journal of Information Science & Engineering, 2015, 31(2): 509-527.
[6] WANG C Z, HE Q, CHEN D G, et al. A novel method for attribute reduction of covering decision systems[J]. Inform-ation Sciences, 2014, 254: 181-196.
[7] DAI J H. Rough set approach to incomplete numerical data[J]. Information Sciences, 2013, 241: 43-57.
[8] LIU G, LI L, YANG J, et al. Attribute reduction approaches for general relation decision systems[J]. Pattern Recognition Letters, 2015, 65(C): 81-87.
[9] LAZO-CORTéS M S, MARTíNEZ-TRINIDAD J F, CARRASCO-OCHOA J A, et al. A new algorithm for com-puting reducts based on the binary discernibility matrix[J]. Intelligent Data Analysis, 2016, 20(2): 317-337.
[10] LI H, LI D, ZHAI Y, et al. A novel attribute reduction app-roach for multi-label data based on rough set theory[J]. In-formation Sciences, 2016, 367: 827-847.
[11] GAO J, MA H, HAN Z D. Attribute reduction algorithm based on discernibility matrix with algebraic method[C]//Proceedings of the 2015 International Industrial Informatics and Computer Engineering Conference, Xi??an, Jan 10-11, 2015: 1-5.
[12] KONECNY J. On attribute reduction in concept lattices: methods based on discernibility matrix are outperformed by basic clarification and reduction[J]. Information Sciences, 2017, 415: 199-212.
[13] KONECNY J, KRAJCA P. On attribute reduction in concept lattices: experimental evaluation shows discernibility matrix based methods inefficient[J]. Information Sciences, 2018, 467: 431-445.
[14] KONECNY J, KRAJCA P. On attribute reduction in con-cept lattices: the polynomial time discernibility matrix-based method becomes the CR-method[J]. Information Sciences, 2019, 491: 48-62.
[15] CHEN Z H, MA H. Granular matrix based rapid parallel reduction algorithm for MIMO truth table[J]. Journal of Electronics and Information Technology, 2015, 37(5): 1260-1265.
陈泽华, 马贺. 基于粒矩阵的多输入多输出真值表快速并行约简算法[J]. 电子与信息学报, 2015, 37(5): 1260-1265.
[16] LI J H, HE J J, WU W Z. Optimization of class-attribute block in multi-granularity formal concept analysis[J]. Journal of Shandong University (Natural Science), 2020, 55(5): 1-12.
李金海, 贺建君, 吴伟志. 多粒度形式概念分析的类属性块优化[J]. 山东大学学报(理学版), 2020, 55(5): 1-12.
[17] SONG B, YAN J X, CHEN Z H. Rapid knowledge reduction of large scale truth table based on variable granularity[J].Computer Science, 2018, 45(7): 167-171.
宋波, 闫继雄, 陈泽华. 基于变粒度的大规模真值表快速知识约简[J]. 计算机科学, 2018, 45(7): 167-171.
[18] CHEN Z H, YAN J X, CHAI J. Formal concept analysis based parallel reduction algorithm for MIMO truth table[J]. Journal of Electronics and Information Technology, 2017, 39(9): 2259-2265.
陈泽华, 闫继雄, 柴晶. 基于形式概念分析的多输入多输出真值表并行约简算法[J]. 电子与信息学报, 2017, 39(9): 2259-2265.