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

摘要

真值表约简是数字逻辑电路分析与设计的关键问题之一,形式概念分析(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.