[發明專利]一種基于中心概念的數字電路邏輯表達簡化方法

在審

• 申請號: 202010601566.5
• 申請日: 2020-06-28
• 公開（公告）號: CN111914499A
• 公開（公告）日: 2020-11-10
• 發明（設計）人: 陳澤華;溫馨;閆心怡;趙哲峰;柴晶
• 申請（專利權）人: 太原理工大學
• 主分類號: G06F30/327
• 分類號: G06F30/327;G06F30/32
• 代理公司: 太原高欣科創專利代理事務所(普通合伙) 14109
• 代理人: 冷錦超;鄧東東

本發明一種基于中心概念的數字電路邏輯表達簡化方法本方法，屬于邏輯電路優化技術領域；目的在于以提高決策邏輯表達式化簡的正確性和有效性；具體是通過將數據處理工具形式概念分析與數字邏輯電路優化應用相結合，對原數字邏輯電路真值表轉化為決策形式背景進行生成概念的同時進行邏輯優化；本方法所生成中心概念的內涵能夠直觀體現出該邏輯電路真值表邏輯輸入與邏輯輸出之間的關系；相較于其他方法來說具有較高的識別率且能夠對數字電路中的邏輯表達式實現有效化簡。

技術領域

本發明屬于邏輯電路優化技術領域，具體為一種基于中心概念的數字電路邏輯表達簡化方法。

背景技術

邏輯表達式的化簡問題在數字電路中具有重要的研究意義，為考慮到數字電路的設計以及成本問題，使得在保證原電路功能不變的基礎上，盡可能降低輸入電路中門電路的個數，讓電路更加簡潔、安全。隨著邏輯電路規模不斷加大，人工智能理論與方法的不斷發展，集成電路設計與生產國產自主化的進程推進，我國EDA技術的發展將迎來新的挑戰。相對于發展迅速的人工智能算法，邏輯優化方法相對發展較慢。此時，將邏輯優化問題轉化為知識發現問題，利用現有知識發現的理論和方法。

從數據分析角度進行處理，尋找新的方法有重要意義。傳統的邏輯表達式化簡方法有公式法、卡諾圖法、Q-M算法以及立方體法，傳統邏輯優化方法眾多，在此基礎上也涌現出相應的改進算法。在硬件電路迅速發展的態勢下，傳統的邏輯優化方法雖然在解決問題的思路上相對成熟，但在數字電路規模急劇增大時，傳統方法將面臨新的機遇和挑戰。

數據挖掘與知識工程在人工智能領域備受關注，作為數據挖掘中的重要研究內容，規則提取吸引了眾多學者的關注。其研究對象主要是信息系統，信息系統常用決策表來表示。在邏輯電路的分析與設計中，通常用真值表來表示邏輯輸入出之間的關系，真值表約簡對大規模邏輯電路的優化意義非凡。然而真值表可以看作特殊的決策，這將人工智能數據挖掘理論與數字邏輯電路優化聯系起來。

發明內容

本發明克服現有技術存在的不足，提供一種基于中心概念的數字電路邏輯表達簡化方法，通過將形式概念分析理論與數字邏輯電路優化應用進行結合，以提高決策邏輯表達式化簡的正確性和有效性。

本發明是通過如下技術方案實現的。

一種基于中心概念的數字電路邏輯表達簡化方法，包括以下步驟：

1)對數字邏輯電路真值表LIS＝(U，R，V，f)進行預處理，將其轉換成決策形式背景S＝(U，A，I，D，J)，記Z＝A∪D；

2)對于計算n＝1次的形式概念(z^↓，z^↓↑)，并將第一次求得的概念存入Concept集合中；

3)依次判斷第n層時的概念(X，B)，若d∈B，且X不包含于外延集合中；B為此概念的內涵，其中B中既包含決策屬性C又包含決策屬性d，其中此時為中心概念；

4)則Rules＝Rules∪{C→d}，Exten＝Exten∪X，同時對提取完規則的概念(X，B)進行標記并存入Del中；

5)對概念集Concept進行更新：Concept＝Concept-Del。

6)判斷Exten是否等于U：若相等，則轉至步驟9得到與原數字邏輯電路真值表等價的最簡決策規則；如不相等，則進行步驟7；

7)此時n＝n+1，對當前Concept中的所有概念按照公式(X₁，B₁)∧(X₂，B₂)＝(X₁∩X₂，(B₁∪B₂)^↓↑)進行兩兩相交邏輯運算，并記錄新產生的概念；