基于形式概念分析的多輸入多輸出真值表并行約簡算法

陳澤華; 閆繼雄; 柴晶

doi:10.11999/JEIT170023

基于形式概念分析的多輸入多輸出真值表并行約簡算法

doi: 10.11999/JEIT170023

基金項目:

國家自然科學(xué)基金(61402319, 61403273)，山西省自然科學(xué)基金(2014021022-4)

計量
- 文章訪問數(shù): 1376
- HTML全文瀏覽量: 175
- PDF下載量: 222
- 被引次數(shù): 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)

摘要

摘要: 真值表約簡是數(shù)字邏輯電路分析與設(shè)計的關(guān)鍵問題之一，形式概念分析(Formal Concept Analysis, FCA)是一種從形式背景進行數(shù)據(jù)分析和規(guī)則提取的工具。該文將多輸入多輸出(Multiple-Input Multiple-Output, MIMO)真值表轉(zhuǎn)化為決策形式背景，將真值表的約簡問題轉(zhuǎn)化為決策形式背景的最簡規(guī)則提取過程，提出一種基于FCA的MIMO真值表并行約簡算法。通過理論證明、實例演示和算法的復(fù)雜性分析，說明了新算法的正確性、有效性和快速性。
- 數(shù)字邏輯電路 /
- 真值表約簡 /
- 形式概念分析 /
- 規(guī)則提取
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.

閻石. 數(shù)字電子技術(shù)基礎(chǔ)[M], 第5版, 北京: 高等教育出版社, 2006: 29-54.

劉寶琴. 數(shù)字電路與系統(tǒng)[M], 第2版, 北京: 清華大學(xué)出版社, 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]. 復(fù)旦學(xué)報(自然科學(xué)版), 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.

邊計年, 薛宏熙, 蘇明, 等. 數(shù)字系統(tǒng)設(shè)計自動化[M]. 第2版，北京: 清華大學(xué)出版社, 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]. 電子與信息學(xué)報, 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.

何苗, 石慧, 魏玲. 基于包含度理論的概念格構(gòu)造方法研究[J]. 西北大學(xué)學(xué)報: (自然科學(xué)版), 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]. 中國科學(xué)(E輯:信息科學(xué)), 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.

李金海, 梅長林, 張紅英, 等. 基于遺傳算法的決策形式背景的屬性約簡方法及其在決策分析中的應(yīng)用[J]. 小型微型計算機系統(tǒng), 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.

翟巖慧, 李德玉, 曲開社. 決策蘊涵規(guī)范基[J]. 電子學(xué)報, 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.

田宏, 王紹斐. 概念格的批處理構(gòu)造算法[J]. 大連交通大學(xué)學(xué)報, 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.

相關(guān)文章

施引文獻

資源附件(0)

訪問統(tǒng)計