面向数字逻辑电路分析与设计的粒计算理论与应用研究

The design of the large-scale digital integrated circuits is the focus of the development of national information industry and its theoretic foundation is digital logic circuits. The basic of digital logic circuits includes the analysis and design of combinational logic circuits and that of sequential logic circuits, in which the logic optimization is the key problem. In the process of analysis, the simplest logic relationship among the inputs and outputs of the system can be found by logic optimization; in the process of design, the reliability of the circuits and the power consumption of the system can be compromised by logic optimization. The nature of the optimization of combinational logic circuits is the simplification of the truth table and that of the sequential logic circuits is the simplification of the state transition table. With the dramatically increasing of the complexity of the circuits, the traditional logic optimization theory and methods are facing new challenges. Granular computing is an effective way to deal with large-scale and complicated problems. This project aims to establish a binary relation-based knowledge model which will explore the key problems of the basic theory of the digital logic circuits from the view of knowledge engineering. The project will transform the optimization of combinational logic circuits into the extraction of the minimal rule set of the knowledge system, and that of the sequential logic circuits into the extraction of the biggest equivalent classes, the biggest tolerant classes and the smallest cover of the knowledge system. Based on the theoretical exploration, the automatic optimization software will be developed. The project will have an important influence on deepening the research of the theory of granular computing and solving the key problems of the analysis and design in the digital logic circuits.

大规模数字集成电路设计是国家信息产业发展重点，它的理论基础是数字逻辑电路。数字逻辑电路的基础理论研究包括组合逻辑电路和时序逻辑电路的分析与设计，其中逻辑优化是关键。在分析阶段，通过逻辑优化寻找系统输入输出最简的逻辑关系；在设计阶段，通过逻辑优化提高电路可靠性、降低系统功耗。组合逻辑电路优化的本质是真值表化简，时序逻辑电路优化的本质是状态转移表化简。随着逻辑电路复杂性的不断提高，传统的逻辑优化理论和方法面临着新的挑战。粒计算是处理大规模、复杂问题的有效方法。本项目旨在建立粒计算的二元关系知识模型，从知识工程角度对数字逻辑电路基础理论中的关键问题进行研究，将组合逻辑电路的优化转化为提取知识系统的最简规则；将时序逻辑电路的优化转化为获取知识系统的最大等价类、最大相容类和最小闭覆盖。在理论研究基础上，开发逻辑优化软件。本项目对于深化粒计算理论研究，解决逻辑电路分析与设计中的关键问题具有重要意义。

随着逻辑电路集成度的不断提高,传统的逻辑优化理论和方法面临着新的挑战。粒计算是处理大规模、复杂不确定问题的有效方法。本项目通过深入研究粒计算理论,建立了一套完整的粒矩阵刻画的二元关系知识模型。在此基础上，建立了基于粒计算的数字逻辑电路优化的理论和方法。应用粒计算的二元关系（等价关系、相容关系）知识模型模型，从知识工程的角度，对数字逻辑电路分析与设计中的逻辑优化问题进行描述、分析、求解,解决了大规模数字逻辑电路优化的关键问题。在组合逻辑电路中：用粒计算的二元关系（等价关系、相容关系）知识模型描述真值表(含无关项)，采用分层粒化思想，在不同粒度空间通过统计方法、矩阵运算快速找到了系统输入输出之间最简单的逻辑关系，实现了组合逻辑电路中大规模真值表的快速化简。在时序逻辑电路电路中：用粒计算的二元关系（等价关系、相容关系）知识模型描述状态转移表(含无关项)，将完全确定状态转移表的化简，转化为利用粒矩阵求取最大等价类的过程；将不完全确定状态转移表的化简转化为利用粒矩阵求取最大相容类和最小闭覆盖的过程。最后通过算法分析、理论证明、实验验证，证明了其理论研究的正确性与算法的有效性，并开发了相应的软件包。本项目圆满完成了计划任务书中的内容，研究成果为大规模逻辑电路分的析与设计提供了有效解决方案。并为大规模数字逻辑电路的测试提供了研究思路和方法。