基于粒计算的逻辑信息系统优化

发布时间：2018-06-22 10:12

本文选题：粒计算 + 组合逻辑优化　；参考：《太原理工大学》2017年硕士论文

【摘要】：组合逻辑优化是数字逻辑电路中一项重要的研究内容。真值表是组合逻辑电路中一种常见的表现形式,同时也是组合逻辑优化技术的桥梁。传统的组合逻辑优化方法有公式法、图形法、列表法以及这些方法的改进算法,但这些传统算法都存在一定程度上的缺陷。粒计算是一个集理论、方法、技术和工具为一体的数学模型,它可以更好地帮助人类解决复杂的问题。虽然粒计算仅有短短几十年的发展,但是粒计算理论已被广泛运用于社会生活的各个领域中,例如,人工智能(AI)、数据挖掘与分析、机器学习等。随着粒计算研究的不断深入及其理论的逐渐成熟,我们尝试把粒计算理论运用于组合逻辑电路优化中,并且得到了新的高效算法。本文主要采用了粒计算的思想进行数字逻辑电路的优化,把粒计算与组合逻辑优化相结合,使真值表的约简过程转化为规则提取的过程,并提出了两种新的算法。这两种算法分别适用于多输入多输出(MIMO)的真值表和多输入单输出(MISO)的不完备真值表。首先,本文构建了一种基于粒矩阵的等价关系模型,在该模型中分别定义了等价矩阵和等价关系矩阵,提出了基于等价关系的多输出真值表约简算法。本文通过挖掘等价关系矩阵中的隐含信息,获取最简逻辑规则。另外,通过定义启发式算子加快了算法的收敛速度。本文以七段数码管为实例对算法步骤进行了详细的描述,随后对算法的复杂度进行分析,并通过理论分析证明了所提出算法的有效性。其次,构建了一种基于粒矩阵的相容关系模型,并定义了不完备真值表的表现形式。在不完备真值表的基础上,分别定义了相容矩阵和相容关系矩阵,针对数字逻辑电路中的任意逻辑表达式,提出了基于相容关系的逻辑表达式化简算法。本文根据相容关系矩阵中元素之间的关系,快速地获取不完备真值表中的最简逻辑规则。另外,通过设置算法的终止条件,提高了算法的运行效率。随后,分析了算法的复杂度,并通过实例说明与理论分析,验证了算法的正确性。最后,本文设计了一个基于粒计算的逻辑信息系统的约简平台,此平台可以运行本文提出的两种算法和传统的Q-M真值表约简算法。本文提出的两种算法不仅解决了传统算法中计算过程冗长复杂的问题,使得化简过程更加的简洁明了,还克服了传统算法在大规模数据中的不适用性,更好地解决了大规模逻辑电路的优化问题。
[Abstract]:Combinatorial logic optimization is an important research content in digital logic circuits. Truth table is a common representation in combinatorial logic circuits, and it is also a bridge of combinatorial logic optimization technology. The traditional combinatorial logic optimization methods include the formula method, the graphic method, the list method and the improved algorithm of these methods, but these traditional algorithms all have some defects to some extent. Granular computing is a mathematical model that integrates theory, method, technology and tools. It can better help people solve complex problems. Although granular computing has been developed for only a few decades, it has been widely used in various fields of social life, such as artificial intelligence (AI), data mining and analysis, machine learning and so on. With the deepening of granular computing and the maturation of its theory, we try to apply it to combinatorial logic circuit optimization, and obtain a new efficient algorithm. In this paper, the idea of granular computing is used to optimize the digital logic circuit. Combining the granular computation with the combinational logic optimization, the reduction process of the truth table is transformed into the rule extraction process, and two new algorithms are proposed. These two algorithms are suitable for multiple input multiple output (MIMO) truth tables and multiple input single output (miso) incomplete truth tables respectively. Firstly, an equivalent relation model based on grain matrix is constructed. In the model, the equivalent matrix and the equivalent relation matrix are defined respectively, and an algorithm of multi-output truth table reduction based on equivalence relation is proposed. In this paper, the simplest logic rules are obtained by mining the implicit information in the equivalence relation matrix. In addition, heuristic operators are defined to speed up the convergence of the algorithm. In this paper, the algorithm steps are described in detail with a seven-segment digital tube as an example, then the complexity of the algorithm is analyzed, and the effectiveness of the proposed algorithm is proved by theoretical analysis. Secondly, a compatible relation model based on granular matrix is constructed, and the representation of incomplete truth table is defined. On the basis of incomplete truth table, the compatible matrix and compatible relation matrix are defined, and an algorithm for simplifying the logical expression based on compatible relation is proposed for any logic expression in digital logic circuit. In this paper, according to the relation between the elements in the compatible relation matrix, the simplest logic rules in the incomplete truth table are obtained quickly. In addition, the efficiency of the algorithm is improved by setting the termination condition of the algorithm. Then, the complexity of the algorithm is analyzed, and the correctness of the algorithm is verified by an example and theoretical analysis. Finally, a reduction platform of logic information system based on granular computing is designed, which can run the two algorithms proposed in this paper and the traditional Q-M truth-table reduction algorithm. The two algorithms proposed in this paper not only solve the complex problem of the computation process in the traditional algorithm, but also overcome the inapplicability of the traditional algorithm in large-scale data. The optimization problem of large scale logic circuits is better solved.
【学位授予单位】：太原理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TN791

【参考文献】