Abstract:Truth table reduction is one of the key problems in the analysis and design of digital logic circuits, FCA (Formal Concept Analysis) is a tool for data analysis and rule extraction from formal contexts. In this paper, MIMO (Multiple-Input Multiple-Output) truth table is transformed into formal decision context, thus the reduction problem of truth table is transformed into the simplest rule extraction process of formal decision context. Then, a parallel reduction algorithm for MIMO truth table based on FCA is proposed. The correctness, efficiency and rapidity of the new algorithm are illustrated by the theoretical proof, example demonstration and complexity analysis of the proposed algorithm.
YAN Shi. Fundamentals of Digital Electronics[M]. Beijing: 5th Edition, Higher Education Press, 2006: 29-54.
[2]
刘宝琴. 数字电路与系统[M], 第2版, 北京: 清华大学出版社, 2007: 39-56.
LIU Baoqin. Digital Circuits and Systems[M]. 2nd Edition, Beijing: Tsinghua University Press, 2007: 39-56.
[3]
QUINE W V. The problem of simplifying truth functions[J]. American Mathematical Monthly, 1952, 59(8): 521-531. doi: 10.2307/2308219.
[4]
DUSA A and THIEM A. Enhancing the minimization of boolean and multivalue output functions With QMC[J]. The Journal of Mathematical Sociology, 2015, 39(2): 92-108. doi: 10.1080/0022250X.2014.897949.
[5]
HUANG Xinjie, WU Ning, and ZHANG Xiaoqiang. Quine- McCluskey repair technique for evolutionary design of combinational logic circuits[J]. Lecture Notes in Engineering & Computer Science, 2015, 2216(1): 674-678.
CHEN Zehua, CAO Changqing, and XIE Gang. Granular matrix based rapid reduction algorithm for multivariable truth table[J]. Pattern Recognition and Artificial Intelligence, 2013, 26(8): 745-750. doi: 10.3969/j.issn.1003-6059.2013.08. 006.
CHEN Zehua and MA He. Granular matrix based rapid parallel reduction algorithm for MIMO truth table[J]. Journal of Electronics & Information Technology, 2015, 37(5): 1260-1265. doi: 10.11999/JEIT141129.
[10]
WILLE R. Restructuring Lattice Theory: An Approach Based on Hierarchies of Concepts[M]. Springer Netherlands, 1982: 445-470. doi: 10.1007/978-94-009-7798-3_15.
[11]
CHEIN Michel. Algorithme de recherche des sous-matrices premières d'une matrice[J]. Bulletin Mathématique de la Société des Sciences Mathématiques de la République Socialiste de Roumanie, 1969, 13(1): 21-25.
[12]
GANTER B. Two basic algorithms in concept analysis[C]. International Conference on Formal Concept Analysis, Springer-Verlag, Agadir, Morocco, 2010: 312-340. doi: 10.1007/978-3-642-11928-6_22.
HE Miao, SHI Hui, and WEI Ling. Concept lattice construction based on inclusion degree[J]. Journal of Northwest University (Natural Science Edition), 2014, 44(1): 6-10.
WEI Ling, QI Jianjun, and ZHANG Wenxiu. Attribute reduction theory of concept lattice based on decision formal contexts[J]. Science in China (Series F:Information Sciences), 2008, 51(7): 910-923.
[15]
LI Jinhai, MEI Changlin, KUMAR Cherukuri-Aswani, et al. On rule acquisition in decision formal contexts[J]. International Journal of Machine Learning and Cybernetics, 2013, 4(6): 721-731. doi: 10.1007/s13042-013-0150-z.
[16]
SHAO Mingwen, LEUNG Yee, and WU Weizhi. Rule acquisition and complexity reduction in formal decision contexts[J]. International Journal of Approximate Reasoning, 2014, 55(1): 259-274. doi: 10.1016/j.ijar.2013.04.011.
LI Jinhai, MEI Changlin, ZHANG Hongying, et al. Attribute reduction method for formal decision contexts based on genetic algorithm and its application to decision-making analysis[J]. Journal of Chinese Mini-Micro Computer Systems, 2015, 36(8): 1803-1808.
ZHAI Yanhui, LI Deyu, and QU Kaishe. Canonical basis for decision implications[J]. Acta Electronica Sinica, 2015, 43(1): 18-23. doi: 10.3969/j.issn.0372-2112.2015.01.004.
[19]
KANG Xiangping and MIAO Duoqian. A study on information granularity in formal concept analysis based on concept-bases[J]. Knowledge-Based Systems, 2016, 105: 147-159. doi: 10.1016/j.knosys.2016.05.005.
[20]
LI Jinhai, MEI Changlin, and LÜ Yuejin. Knowledge reduction in decision formal contexts[J]. Knowledge-Based Systems, 2011, 24(5): 709-715. doi: 10.1016/j.knosys.2011.02. 011.
TIAN Hong and WANG Shaofei. Batch processing algorithm for concept lattice[J]. Journal of Dalian Jiaotong University, 2011, 32(3): 72-75. doi: 10.3969/j.issn.1673-9590.2011.03.017.