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

有效

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

1.一種異或-多數(shù)邏輯圖中的反相器數(shù)量優(yōu)化方法，其特征在于包括以下步驟：

步驟①：計(jì)算出XMG中反相器初始總數(shù)C₁；

步驟②：對(duì)于XMG中任一結(jié)點(diǎn)q，根據(jù)該結(jié)點(diǎn)的輸入連接線的條數(shù)M判斷該結(jié)點(diǎn)的類型，如果M＝3，則判斷該結(jié)點(diǎn)為多數(shù)邏輯結(jié)點(diǎn)；如果M＝2，則判斷該結(jié)點(diǎn)為異或邏輯結(jié)點(diǎn)；

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

對(duì)于多數(shù)邏輯結(jié)點(diǎn)，滿足如下反相器傳輸規(guī)則(1)或(2)或(3)：

對(duì)于異或邏輯結(jié)點(diǎn)，滿足如下反相器傳輸規(guī)則(4)或(5)：

式(1)～(3)中，“”表示多數(shù)邏輯運(yùn)算，x、y、z表示任一多數(shù)邏輯結(jié)點(diǎn)的三個(gè)輸入，x、y、z上的橫線表示該多數(shù)邏輯結(jié)點(diǎn)的輸入連接線上有反相器，“＝”表示等式左右兩個(gè)多數(shù)邏輯結(jié)點(diǎn)的邏輯功能一致；式(4)～(5)中，表示異或邏輯運(yùn)算，m、n表任一異或邏輯結(jié)點(diǎn)的兩個(gè)輸入，m、n上的橫線表示該異或邏輯結(jié)點(diǎn)的輸入連接線上有反相器；

針對(duì)任一多數(shù)邏輯結(jié)點(diǎn)，記A₁為該多數(shù)邏輯結(jié)點(diǎn)的輸入連接線和輸出連接線上的所有反相器的數(shù)量，B₁為該多數(shù)邏輯結(jié)點(diǎn)的輸入連接線和輸出連接線上沒有反相器的連接線的數(shù)量，記S₁為該多數(shù)邏輯結(jié)點(diǎn)的savings值：

S₁＝A₁-B₁?(6)

針對(duì)任一異或邏輯結(jié)點(diǎn)，記A₂為該異或邏輯結(jié)點(diǎn)的輸入連接線和輸出連接線上的所有反相器的數(shù)量，B₂為該異或邏輯結(jié)點(diǎn)的輸入連接線和輸出連接線上沒有反相器的連接線的數(shù)量，C為修正參數(shù)，記S₂為該異或邏輯結(jié)點(diǎn)的savings值：

S₂＝A₂-B₂+C?(7)

S₂的計(jì)算分三種情況：

1)當(dāng)該異或邏輯結(jié)點(diǎn)的輸入連接線上沒有反相器時(shí)，C＝-1，則S₂＝A₂-B₂-1；

2)當(dāng)該異或邏輯結(jié)點(diǎn)的輸入連接線上只有一個(gè)反相器時(shí)，C＝1，則S₂＝A₂-B₂+1；

3)當(dāng)該異或邏輯結(jié)點(diǎn)的輸入連接線上有兩個(gè)反相器時(shí)，對(duì)于該異或邏輯結(jié)點(diǎn)的所有輸出連接線，若存在反相器的輸出連接線數(shù)量小于或等于沒有反相器的輸出連接線數(shù)量，則直接令S₂＝2；否則按照公式(7)計(jì)算，此時(shí)令C＝1，則S₂＝A₂-B₂+1；

計(jì)算出savings值S₁或者S₂后，如果S₁為正數(shù)，則在XMG中執(zhí)行反相器傳輸規(guī)則(1)或(2)或(3)，轉(zhuǎn)至步驟⑤；如果S₂為正數(shù)，則在XMG中執(zhí)行反相器傳輸規(guī)則(4)或(5)，轉(zhuǎn)至步驟⑤；如果S₁或者S₂為負(fù)數(shù)，則執(zhí)行步驟④；

步驟④：定義結(jié)點(diǎn)集合Q由結(jié)點(diǎn)q及與q的輸出連接線相連接的所有結(jié)點(diǎn)組成，判斷集合Q中所有結(jié)點(diǎn)執(zhí)行反相器傳輸規(guī)則前后所引起的反相器數(shù)量的改進(jìn)值，記為savings_two_level；針對(duì)集合Q中的每個(gè)結(jié)點(diǎn)，分別按照步驟②判斷結(jié)點(diǎn)的類型，并分別按照結(jié)點(diǎn)的類型調(diào)用式(6)或式(7)計(jì)算savings值，則savings_two_level為集合Q中所有結(jié)點(diǎn)的savings值之總和；如果savings_two_level為正數(shù)，則分別對(duì)集合Q中所有結(jié)點(diǎn)在XMG中按照結(jié)點(diǎn)的類型執(zhí)行相應(yīng)的反相器傳輸規(guī)則，否則執(zhí)行步驟⑤；

步驟⑤：遍歷XMG中下一個(gè)結(jié)點(diǎn)，重復(fù)步驟②～④，直到將XMG中所有結(jié)點(diǎn)遍歷一遍為止，完成對(duì)XMG中反相器數(shù)量的第一遍優(yōu)化；

步驟⑥：完成對(duì)XMG中反相器數(shù)量的第一遍優(yōu)化后，計(jì)算當(dāng)前XMG中反相器總數(shù)C₂，比較當(dāng)前XMG中反相器總數(shù)C₂與執(zhí)行步驟②～⑤之前的XMG中反相器初始總數(shù)C₁，如果C₂＝C₁，則說明第一遍優(yōu)化已得到XMG中反相器數(shù)量的最優(yōu)結(jié)果，優(yōu)化結(jié)束；如果C₂﹤C₁，則以該當(dāng)前XMG中反相器總數(shù)C₂作為第二遍優(yōu)化前XMG中反相器初始總數(shù)，再次執(zhí)行步驟②～⑤進(jìn)行第二遍優(yōu)化，如此循環(huán)進(jìn)行第i遍優(yōu)化，i為等于或大于2的正整數(shù)，直至第i遍優(yōu)化后XMG中反相器總數(shù)與第i遍優(yōu)化前XMG中反相器初始總數(shù)相等，則說明已得到XMG中反相器數(shù)量的最優(yōu)結(jié)果，優(yōu)化結(jié)束。