基于粒矩阵的多输入多输出真值表快速并行约简算法

陈泽华马 贺

（太原理工大学信息工程学院 太原 030024）

基于粒矩阵的多输入多输出真值表快速并行约简算法

陈泽华*马 贺

（太原理工大学信息工程学院 太原 030024）

真值表是表征逻辑输入与输出之间因果关系的重要工具，真值表约简在数字逻辑电路的分析与设计中具有重要意义。该文将真值表看作逻辑信息系统，将真值表约简转化为逻辑信息系统的最简规则获取。采用粒计算分层粒化的思想，在不同粒度下，利用粒矩阵的知识表示形式、粒矩阵中的启发式知识以及粒矩阵运算，设计了多输入多输出真值表快速并行约简算法。以发光二极管七段数字显示器为例进行了算法说明，通过数学证明和算法复杂性分析证明了算法的正确性和有效性。

数字逻辑电路；真值表；粒度；粒矩阵；并行约简；粒计算

1 引言

真值表约简在数字逻辑电路分析与设计中具有重要作用。经典方法有卡诺图法、公式法、Q-M及其改进算法以及立方体算法等［17］-。当输入变量增大时，前3种方法算法复杂度比较高，不利于程序实现，而且不能对多个输出进行并行处理。立方体算法［2］相对简单，可以处理多输出，本质依然依靠逻辑代数运算规律。目前，真值表约简算法被内嵌在国外的电子设计自动化软件中，工程师们不再需要自行设计约简算法。因此，国内外对真值表的约简问题研究成果仍然停留在十几年前。

粒计算［8］求解复杂问题的思想和方法受到关注，基于粒计算的信息系统知识处理方法得到快速发展［915］-。……