[發(fā)明專利]一種異或-多數邏輯圖中的反相器數量優(yōu)化方法

有效

• 申請?zhí)枺?/td>: 201811414894.3
• 申請日: 2018-11-26
• 公開（公告）號: CN109639267B
• 公開（公告）日: 2023-04-07
• 發(fā)明（設計）人: 儲著飛;石磊;王倫耀;夏銀水
• 申請（專利權）人: 寧波大學
• 主分類號: H03K19/21
• 分類號: H03K19/21
• 代理公司: 寧波奧圣專利代理有限公司 33226
• 代理人: 謝瀟

本發(fā)明公開的異或?多數邏輯圖中的反相器數量優(yōu)化方法，首先計算XMG中反相器總數并判斷XMG中任意一個結點是多數邏輯結點還是異或邏輯結點，然后反復執(zhí)行優(yōu)化步驟，且一級優(yōu)化與二級優(yōu)化交替執(zhí)行，直到達到最優(yōu)的反相器數量為止。本發(fā)明不改變XMG的結構，降低了XMG中反相器的數量。本發(fā)明方法在基準電路中平均優(yōu)化17.3%，在應用到量子元胞自動機（QCA）中有2.1%的平均優(yōu)化。本發(fā)明方法能有效降低XMG中反相器的數量，為EDA設計減少成本，同時豐富邏輯綜合中反相器優(yōu)化的研究方法。本發(fā)明為異或?多數邏輯圖中的反相器數量的優(yōu)化提供了一種新思路，既提出了新的設計優(yōu)化方法，又降低了設計成本，對EDA的發(fā)展具有較強的現(xiàn)實意義和實踐意義。

技術領域

本發(fā)明涉及一種邏輯表達圖形的優(yōu)化方法，具體是一種異或-多數邏輯圖(XOR-Majority?Graphs,XMGs)中的反相器數量優(yōu)化方法。

背景技術

XMG(XOR-Majority?Graph)是由異或(XOR)、三輸入多數門(Majority-of-three)和反相器組成的邏輯表達圖形。在過去的幾十年里，邏輯綜合已經從異構邏輯表達轉向同構邏輯表達，這是因為同構邏輯表達具有統(tǒng)一的數據結構，易于操作并且使用較少的內存。為了對算術操作更好的支持和得到更緊湊的邏輯圖形表達，研究者在同構邏輯表達圖形MIG(Majority-Inverter?Graph)中引入了XOR操作，提出了異構邏輯表達圖形表示XMG。現(xiàn)如今，XMG已被廣泛應用于量子電路綜合、精確綜合等，對集成電路設計自動化的發(fā)展起到巨大的推動作用。

邏輯表達圖形直接對應著相應的電路實現(xiàn)，對于一些納米電路，實現(xiàn)反相器的成本遠高于多操作數運算符的物理實現(xiàn)，例如在量子細胞自動機(Quantum-dot?CellularAutomata,QCA)中，一個反相器由十三個細胞單元構成，比一個三輸入多數邏輯門所使用的細胞數要多一倍。因此，本發(fā)明提出一種異或-多數邏輯圖中的反相器數量優(yōu)化方法，通過改變反相器的分布，利用反相器傳輸規(guī)則減少XMG中反相器數量而不改變邏輯功能，從而得到優(yōu)化的納米電路設計。

發(fā)明內容

本發(fā)明所要解決的技術問題是，針對現(xiàn)有技術的不足，提供一種異或-多數邏輯圖中的反相器數量優(yōu)化方法，該方法首先計算XMG中反相器總數并判斷XMG中任意一個結點是多數邏輯結點(即Majority結點)還是異或邏輯結點(即XOR結點)，然后反復執(zhí)行優(yōu)化步驟，且一級優(yōu)化與二級優(yōu)化交替執(zhí)行，直到達到最優(yōu)的反相器數量為止。本發(fā)明優(yōu)化方法在整個優(yōu)化過程中，不改變XMG的結構，同時降低了XMG中反相器的數量。本發(fā)明方法能有效降低XMG中反相器的數量，為EDA設計減少成本，同時豐富邏輯綜合中反相器優(yōu)化的研究方法。

本發(fā)明解決上述技術問題所采用的技術方案為：一種異或-多數邏輯圖中的反相器數量優(yōu)化方法，包括以下步驟：

步驟①：計算出XMG中反相器初始總數C₁；

步驟②：對于XMG中任一結點q，根據該結點的輸入連接線的條數M判斷該結點的類型，如果M＝3，則判斷該結點為多數邏輯結點；如果M＝2，則判斷該結點為異或邏輯結點；

步驟③：判斷結點q執(zhí)行反相器傳輸規(guī)則前后所引起的反相器數量的改進值，記為savings；

對于多數邏輯結點，滿足如下反相器傳輸規(guī)則(1)或(2)或(3)：

對于異或邏輯結點，滿足如下反相器傳輸規(guī)則(4)或(5)：