本文選題：粒計(jì)算 + 組合邏輯優(yōu)化　； 參考：《太原理工大學(xué)》2017年碩士論文

【摘要】：組合邏輯優(yōu)化是數(shù)字邏輯電路中一項(xiàng)重要的研究?jī)?nèi)容。真值表是組合邏輯電路中一種常見的表現(xiàn)形式,同時(shí)也是組合邏輯優(yōu)化技術(shù)的橋梁。傳統(tǒng)的組合邏輯優(yōu)化方法有公式法、圖形法、列表法以及這些方法的改進(jìn)算法,但這些傳統(tǒng)算法都存在一定程度上的缺陷。粒計(jì)算是一個(gè)集理論、方法、技術(shù)和工具為一體的數(shù)學(xué)模型,它可以更好地幫助人類解決復(fù)雜的問題。雖然粒計(jì)算僅有短短幾十年的發(fā)展,但是粒計(jì)算理論已被廣泛運(yùn)用于社會(huì)生活的各個(gè)領(lǐng)域中,例如,人工智能(AI)、數(shù)據(jù)挖掘與分析、機(jī)器學(xué)習(xí)等。隨著粒計(jì)算研究的不斷深入及其理論的逐漸成熟,我們嘗試把粒計(jì)算理論運(yùn)用于組合邏輯電路優(yōu)化中,并且得到了新的高效算法。本文主要采用了粒計(jì)算的思想進(jìn)行數(shù)字邏輯電路的優(yōu)化,把粒計(jì)算與組合邏輯優(yōu)化相結(jié)合,使真值表的約簡(jiǎn)過程轉(zhuǎn)化為規(guī)則提取的過程,并提出了兩種新的算法。這兩種算法分別適用于多輸入多輸出(MIMO)的真值表和多輸入單輸出(MISO)的不完備真值表。首先,本文構(gòu)建了一種基于粒矩陣的等價(jià)關(guān)系模型,在該模型中分別定義了等價(jià)矩陣和等價(jià)關(guān)系矩陣,提出了基于等價(jià)關(guān)系的多輸出真值表約簡(jiǎn)算法。本文通過挖掘等價(jià)關(guān)系矩陣中的隱含信息,獲取最簡(jiǎn)邏輯規(guī)則。另外,通過定義啟發(fā)式算子加快了算法的收斂速度。本文以七段數(shù)碼管為實(shí)例對(duì)算法步驟進(jìn)行了詳細(xì)的描述,隨后對(duì)算法的復(fù)雜度進(jìn)行分析,并通過理論分析證明了所提出算法的有效性。其次,構(gòu)建了一種基于粒矩陣的相容關(guān)系模型,并定義了不完備真值表的表現(xiàn)形式。在不完備真值表的基礎(chǔ)上,分別定義了相容矩陣和相容關(guān)系矩陣,針對(duì)數(shù)字邏輯電路中的任意邏輯表達(dá)式,提出了基于相容關(guān)系的邏輯表達(dá)式化簡(jiǎn)算法。本文根據(jù)相容關(guān)系矩陣中元素之間的關(guān)系,快速地獲取不完備真值表中的最簡(jiǎn)邏輯規(guī)則。另外,通過設(shè)置算法的終止條件,提高了算法的運(yùn)行效率。隨后,分析了算法的復(fù)雜度,并通過實(shí)例說明與理論分析,驗(yàn)證了算法的正確性。最后,本文設(shè)計(jì)了一個(gè)基于粒計(jì)算的邏輯信息系統(tǒng)的約簡(jiǎn)平臺(tái),此平臺(tái)可以運(yùn)行本文提出的兩種算法和傳統(tǒng)的Q-M真值表約簡(jiǎn)算法。本文提出的兩種算法不僅解決了傳統(tǒng)算法中計(jì)算過程冗長(zhǎng)復(fù)雜的問題,使得化簡(jiǎn)過程更加的簡(jiǎn)潔明了,還克服了傳統(tǒng)算法在大規(guī)模數(shù)據(jù)中的不適用性,更好地解決了大規(guī)模邏輯電路的優(yōu)化問題。
[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.
【學(xué)位授予單位】：太原理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TN791

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 陳澤華;馬賀;;基于粒矩陣的多輸入多輸出真值表快速并行約簡(jiǎn)算法[J];電子與信息學(xué)報(bào);2015年05期

2 陳澤華;曹長(zhǎng)青;謝剛;;基于粒矩陣的多變量真值表快速約簡(jiǎn)算法[J];模式識(shí)別與人工智能;2013年08期

3 張清華;王國胤;劉顯全;;基于最大粒的規(guī)則獲取算法[J];模式識(shí)別與人工智能;2012年03期

4 苗奪謙;徐菲菲;姚一豫;魏萊;;粒計(jì)算的集合論描述[J];計(jì)算機(jī)學(xué)報(bào);2012年02期

5 張清華;周玉蘭;滕海濤;;基于粒計(jì)算的認(rèn)知模型[J];重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年04期

6 錢進(jìn);孟祥萍;劉大有;葉飛躍;;一種基于粗糙集理論的最簡(jiǎn)決策規(guī)則挖掘算法[J];控制與決策;2007年12期

7 李元振;潘全科;李俊青;;基于蟻群算法的邏輯函數(shù)化簡(jiǎn)[J];計(jì)算機(jī)工程與設(shè)計(jì);2007年12期

8 ;Three Perspectives of Granular Computing[J];南昌工程學(xué)院學(xué)報(bào);2006年02期

9 張義清;管致錦;李洵;;邏輯函數(shù)的粗糙集表達(dá)及最小化方法[J];黑龍江大學(xué)自然科學(xué)學(xué)報(bào);2006年02期

10 杜偉林;苗奪謙;李道國;張年琴;;概念格與粒度劃分的相關(guān)性分析[J];計(jì)算機(jī)科學(xué);2005年12期

，

本文編號(hào)：2052499