基于粒分辨矩阵与乐观概念的组合逻辑电路优化算法研究

作     者：闫心怡 

作者单位：太原理工大学 

学位级别：硕士

导师姓名：陈泽华

授予年度：2020年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 080902[工学-电路与系统] 0809[工学-电子科学与技术（可授工学、理学学位）] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：粒计算 等价关系 形式概念分析 电路优化 最简逻辑函数表达式 

摘      要：作为逻辑电路分析与设计中的一项重要内容,组合逻辑电路优化的主要研究内容之一是对描述逻辑电路的真值表或逻辑函数表达式进行化简。工业中常常采用电子设计自动化工具对逻辑电路进行优化,但是随着大数据时代的到来,电路集成度更高,规模更大,组合逻辑电路的优化算法也面临着新的机遇和挑战。随着计算能力不断增强,知识工程方法不断发展,本文尝试采用粒计算理论与形式概念分析理论来解决组合数字逻辑电路中的优化问题。本文在课题组前期工作基础上,利用粒分辨矩阵和乐观概念将真值表化简转化为信息系统的规则提取问题。主要独创性工作包括:首先,在等价关系和传统分辨矩阵的基础上,构造粒分辨矩阵,通过分辨逻辑输出的“0和“1进行真值表化简。粒分辨矩阵有别于传统的分辨矩阵,其既不对称也不是方阵,但却包含了利用最少的等价类识别所有输出为“1的所有信息。在寻找规则的过程中引用启发式信息的概念,加快算法的收敛性。最终设计了基于粒分辨矩阵的逻辑电路优化算法。并证明了该算法与传统卡诺图化简方法的等价性。其次将真值表看作逻辑信息系统,直接从等价类角度定义逻辑信息系统生成的乐观概念,在不同的粒度空间下生成乐观概念,并根据乐观概念与真值表中输出属性的关系获取真值表中的最简规则。通过实例来展示以上两种算法的具体计算过程,通过理论分析证明了该算法的正确性。本文提出的两种真值表约简算法,拓展了粒计算理论与形式概念分析理论的研究领域和应用范围,并在一定程度上丰富了逻辑电路优化中的优化问题求解方法,研究成果可以推广到SAT问题求解与命题逻辑的证明中。