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

Formal Concept Analysis Based Parallel Reduction Algorithm for MIMO Truth Table

作　　者：陈泽华[1] 闫继雄 柴晶[1] 

机构地区：[1]太原理工大学信息工程学院,太原030024

出　　处：《电子与信息学报》2017年第9期2259-2265,共7页Journal of Electronics & Information Technology

基　　金：国家自然科学基金(61402319;61403273);山西省自然科学基金(2014021022-4)~~

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

关 键 词：数字逻辑电路 真值表约简 形式概念分析 规则提取 

分 类 号：TP331[自动化与计算机技术—计算机系统结构] TP181[自动化与计算机技术—计算机科学与技术]