|
|
|
| Formal Concept Analysis Based Parallel Reduction Algorithm for MIMO Truth Table |
| CHEN Zehua YAN Jixiong CHAI Jing |
| (College of Information Engineering, Taiyuan University of Technology, Taiyuan 030024, China) |
|
|
|
|
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.
|
|
Received: 09 January 2017
Published: 27 June 2017
|
|
|
| Fund:The National Natural Science Foundation of China (61402319, 61403273), The Natural Science Foundation of Shanxi Province (2014021022-4) |
|
Corresponding Authors:
CHEN Zehua
E-mail: zehuachen@163.com
|
|
|
|
| [1] |
阎石. 数字电子技术基础[M], 第5版, 北京: 高等教育出版社, 2006: 29-54.
|
|
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.
|
| [6] |
黄均鼐, 赵文庆. 自动逻辑综合[J]. 复旦学报(自然科学版), 1984, 23(2): 233-237.
|
|
HUANG Junnai and ZHAO Wenqing. Automatic logic synthesis[J]. Journal of Fudan University (Natural Science), 1984, 23(2): 233-237.
|
| [7] |
边计年, 薛宏熙, 苏明, 等. 数字系统设计自动化[M]. 第2版，北京: 清华大学出版社, 2005: 221-226.
|
|
BIAN Jinian, XUE Hongxi, SU Ming, et al. Design Automation for Digital Systems[M]. 2nd Edition, Beijing: Tsinghua University Press, 2005: 221-226.
|
| [8] |
陈泽华, 曹长青, 谢刚. 基于粒矩阵的多变量真值表快速约简算法[J]. 模式识别与人工智能, 2013, 26(8): 745-750. doi: 10.3969/j.issn.1003-6059.2013.08.006.
|
|
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.
|
| [9] |
陈泽华, 马贺. 基于粒矩阵的多输入多输出真值表快速并行约简算法[J]. 电子与信息学报, 2015, 37(5): 1260-1265. doi: 10.11999/JEIT141129.
|
|
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.
|
| [13] |
何苗, 石慧, 魏玲. 基于包含度理论的概念格构造方法研究[J]. 西北大学学报: (自然科学版), 2014, 44(1): 6-10.
|
|
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.
|
| [14] |
魏玲, 祁建军, 张文修. 决策形式背景的概念格属性约简[J]. 中国科学(E辑:信息科学), 2008, 38(2): 195-208.
|
|
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.
|
| [17] |
李金海, 梅长林, 张红英, 等. 基于遗传算法的决策形式背景的属性约简方法及其在决策分析中的应用[J]. 小型微型计算机系统, 2015, 36(8): 1803-1808.
|
|
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.
|
| [18] |
翟岩慧, 李德玉, 曲开社. 决策蕴涵规范基[J]. 电子学报, 2015, 43(1): 18-23. doi: 10.3969/j.issn.0372-2112.2015.01.004.
|
|
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.
|
| [21] |
田宏, 王绍斐. 概念格的批处理构造算法[J]. 大连交通大学学报, 2011, 32(3): 72-75. doi: 10.3969/j.issn.1673-9590.2011. 03.017.
|
|
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.
|
|
|
|
