基于形式概念分析的多输入多输出真值表并行约简算法

陈泽华; 闫继雄; 柴晶

doi:10.11999/JEIT170023

基于形式概念分析的多输入多输出真值表并行约简算法

doi: 10.11999/JEIT170023

基金项目:

国家自然科学基金(61402319, 61403273)，山西省自然科学基金(2014021022-4)

计量
- 文章访问数: 1363
- HTML全文浏览量: 169
- PDF下载量: 222
- 被引次数: 0
出版历程
- 收稿日期: 2017-01-09
- 修回日期: 2017-05-25
- 刊出日期: 2017-09-19

Formal Concept Analysis Based Parallel Reduction Algorithm for MIMO Truth Table

Funds:

The National Natural Science Foundation of China (61402319, 61403273), The Natural Science Foundation of Shanxi Province (2014021022-4)

摘要

摘要: 真值表约简是数字逻辑电路分析与设计的关键问题之一，形式概念分析(Formal Concept Analysis, FCA)是一种从形式背景进行数据分析和规则提取的工具。该文将多输入多输出(Multiple-Input Multiple-Output, MIMO)真值表转化为决策形式背景，将真值表的约简问题转化为决策形式背景的最简规则提取过程，提出一种基于FCA的MIMO真值表并行约简算法。通过理论证明、实例演示和算法的复杂性分析，说明了新算法的正确性、有效性和快速性。
- 数字逻辑电路 /
- 真值表约简 /
- 形式概念分析 /
- 规则提取
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.
- Digital logic circuit /
- Truth table reduction /
- Formal Concept Analysis (FCA) /
- Rule extraction

HTML全文

参考文献(32)

YAN Shi. Fundamentals of Digital Electronics[M]. Beijing: 5th Edition, Higher Education Press, 2006: 29-54.

阎石. 数字电子技术基础[M], 第5版, 北京: 高等教育出版社, 2006: 29-54.

刘宝琴. 数字电路与系统[M], 第2版, 北京: 清华大学出版社, 2007: 39-56.

LIU Baoqin. Digital Circuits and Systems[M]. 2nd Edition, Beijing: Tsinghua University Press, 2007: 39-56.

QUINE W V. The problem of simplifying truth functions[J]. American Mathematical Monthly, 1952, 59(8): 521-531. doi: 10.2307/2308219.

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.

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.

黄均鼐, 赵文庆. 自动逻辑综合[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.

边计年, 薛宏熙, 苏明, 等. 数字系统设计自动化[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.

陈泽华, 曹长青, 谢刚. 基于粒矩阵的多变量真值表快速约简算法[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.

陈泽华, 马贺. 基于粒矩阵的多输入多输出真值表快速并行约简算法[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.

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.

CHEIN Michel. Algorithme de recherche des sous-matrices premires d'une matrice[J]. Bulletin Mathmatique de la Socit des Sciences Mathmatiques de la Rpublique Socialiste de Roumanie, 1969, 13(1): 21-25.

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.

何苗, 石慧, 魏玲. 基于包含度理论的概念格构造方法研究[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.

魏玲, 祁建军, 张文修. 决策形式背景的概念格属性约简[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.

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.

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.

李金海, 梅长林, 张红英, 等. 基于遗传算法的决策形式背景的属性约简方法及其在决策分析中的应用[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.

翟岩慧, 李德玉, 曲开社. 决策蕴涵规范基[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.

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.

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.

田宏, 王绍斐. 概念格的批处理构造算法[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.

施引文献

资源附件(0)

访问统计