不完全規(guī)定函數(shù)的啟發(fā)式ESOP最小化算法

卜登立

(1. 井岡山大學(xué) 電子與信息工程學(xué)院, 江西 吉安 343009；2. 流域生態(tài)與地理環(huán)境監(jiān)測國家測繪地理信息局重點實驗室, 江西 吉安 343009)

0 引 言

RM(Reed-Muller)邏輯是基于“與-異或”的邏輯表示， 和基于“與-或”的布爾邏輯相比， 其在算術(shù)、 通信、 校驗電路等方面具有面積優(yōu)勢[1]， 并且能夠?qū)崿F(xiàn)具有通用測試集的可測試性電路設(shè)計[2]， 近年來在信息安全領(lǐng)域的電路設(shè)計中也得到了應(yīng)用[3]， 因此RM邏輯受到了越來越廣泛的關(guān)注.

積之異或和(Exclusive-or Sum of Products, ESOP)是最一般化的混合極性RM邏輯表示， 它對變量的出現(xiàn)形式?jīng)]有任何限制， 相對于其他形式的RM邏輯， 其能夠獲得更為精簡的表示， 更有助于降低電路實現(xiàn)開銷， 因此被作為一種邏輯模型應(yīng)用于納電子電路設(shè)計中[4]， 通過對ESOP進行優(yōu)化實現(xiàn)相應(yīng)電路的優(yōu)化. 另外， 由于其能夠較為直接地映射到可逆電路中， 因此ESOP表示模型被廣泛應(yīng)用于可逆電路綜合[5-6]， 即先由exorcism算法[7]產(chǎn)生ESOP覆蓋， 然后再將乘積項映射到可逆門網(wǎng)絡(luò).

降低ESOP的復(fù)雜度， 有助于降低使用ESOP作為邏輯模型電路的面積[4]， 也有助于降低采用ESOP表示模型進行綜合所得可逆電路的量子成本[6]， 因此ESOP最小化成為電路綜合中一個非常重要的步驟. 當(dāng)前也有一些ESOP最小化的研究工作， 如文獻[4]結(jié)合極性轉(zhuǎn)換和局部變換啟發(fā)式地優(yōu)化ESOP邏輯， 文獻[8]通過細(xì)分立方體進行ESOP的精確最小化， 文獻[9]提出了通過檢查ESOP多項式包含乘積項數(shù)的上限和下限對搜索空間進行剪枝的精確ESOP最小化算法， 以及廣泛應(yīng)用于可逆電路綜合中生成ESOP覆蓋的exorcism算法[7]. 這些方法和算法均假設(shè)函數(shù)是完全規(guī)定函數(shù)， 然而當(dāng)前的電路設(shè)計方法常常不滿足這個假設(shè)， 為降低設(shè)計成本經(jīng)常需要重用事先設(shè)計好的電路模塊， 這導(dǎo)致很多函數(shù)是包含大量外部無關(guān)項的不完全規(guī)定函數(shù)[10]. 對于不完全規(guī)定函數(shù)， 如果恰當(dāng)?shù)貙o關(guān)項進行賦值， 能夠進一步降低其ESOP的復(fù)雜度[11]， 從而降低電路開銷. 由于ESOP具有指數(shù)級的優(yōu)化空間， 再加上不完全規(guī)定函數(shù)ESOP的優(yōu)化空間隨無關(guān)最小項數(shù)量的增加呈指數(shù)級增長， 使得不完全規(guī)定函數(shù)的精確ESOP最小化算法時間效率非常低. 如文獻[11]算法在進行輸入變量數(shù)為6的不完全規(guī)定函數(shù)的ESOP最小化時就需要若干個小時， 導(dǎo)致其實用性較差， 并且無法應(yīng)用于輸入數(shù)較多的不完全規(guī)定函數(shù). 文獻[12]給出了一種不完全規(guī)定函數(shù)的MPRM(Mixed polarity RM)展開式最小化算法. MPRM展開式可以看作是ESOP邏輯的一種特例， 與MPRM展開式相比， ESOP邏輯有可能獲得更為精簡的表示. 因此有必要研究不完全規(guī)定函數(shù)的啟發(fā)式ESOP最小化算法， 并將其適用于具有較多輸入數(shù)的不完全規(guī)定函數(shù).

本文采用不完全規(guī)定函數(shù)的立方體表示， 提出一種邊實施無關(guān)項賦值邊進行化簡的啟發(fā)式ESOP最小化算法. 該算法根據(jù)立方體間的鄰近關(guān)系， 采用前瞻策略在RM域動態(tài)實施無關(guān)項賦值， 并結(jié)合Exorlink運算[7]和回溯策略進行ESOP最小化. 最后， 使用一組MCNC(Microelectronic Center of North China)不完全規(guī)定函數(shù)對所提算法進行了驗證.

1 理論基礎(chǔ)

1.1 不完全規(guī)定函數(shù)及其ESOP邏輯

定義 1 不完全規(guī)定函數(shù)g∶{0,1}n→{0,1,-}， 函數(shù)輸出值為“1”的最小項集合為ON集， 輸出值為“0”的最小項集合為OFF集， 輸出值為“-”的最小項為無關(guān)(don’t care, DC)項， 所有無關(guān)項構(gòu)成DC集.

根據(jù)定義1， 可將不完全規(guī)定函數(shù)g所有的最小項劃分為3個集合F,D和R， 分別表示該函數(shù)的ON集、 DC集和OFF集，F(xiàn)∩D=?，F(xiàn)∩R=?，D∩R=?.

對于無關(guān)項的賦值沒有進行規(guī)定， 可以取0也可以取1， 不會影響函數(shù)g的邏輯功能[13]. 可根據(jù)需要將無關(guān)項賦值為0或者1， 從而形成不完全規(guī)定函數(shù)的不同實現(xiàn).

定義 2 假設(shè)集合H?D， 即H為DC集的子集， 通過將H中的無關(guān)項賦值為1， 將差集DH中的無關(guān)項賦值為0， 那么由ON集Fy=F∪H和OFF集Ry=R∪(DH)構(gòu)成的完全規(guī)定布爾函數(shù)y是函數(shù)g的一個實現(xiàn)， 記作g→y.

對于由定義2得到的完全規(guī)定布爾函數(shù)y， 由于其ON集Fy=F∪H， 因此可將y分解為2個布爾函數(shù)y=f+h， 函數(shù)f和函數(shù)h的ON集分別為F和H.

定義 3 假設(shè)完全規(guī)定函數(shù)f的ESOP為fe， 那么f與fe功能等價， 記作f?fe.

對于輸入變量數(shù)為n的布爾函數(shù)f， 其ESOP邏輯可以表示為

定理 1 假設(shè)函數(shù)f的ESOP為fe， 函數(shù)h的ESOP為he， 函數(shù)y=f+h的ESOP為ye， 那么有fe⊕he?ye， g→fe⊕he， 即fe⊕he為不完全規(guī)定函數(shù)g的ESOP.

證明 根據(jù)定義2可知集合H是將集合D一個子集中的所有無關(guān)項均賦值為1的結(jié)果， 由于F∩D=?， 故F∩H=?， 因此y=f+h=f⊕h. 由于f?fe， h?he， 因此y=f⊕h?fe⊕he， 而y?ye， 故fe⊕he?ye. 又因為g→y， 所以g→fe⊕he.

根據(jù)定義2， 當(dāng)H=?， 即將不完全規(guī)定函數(shù)g的集合D中所有無關(guān)項均賦值0， 此時完全規(guī)定函數(shù)y的ON集Fy=F，OFF集Ry=R∪D. 將這種特殊情況下所得到的完全規(guī)定布爾函數(shù)記為y0， 由定理1可以得到如下推論.

推論 1 假設(shè)完全規(guī)定布爾函數(shù)y0的ESOP為y0,e， 那么g→y0,e.

本文根據(jù)定義2, 3和定理1所描述的函數(shù)之間的邏輯關(guān)系， 啟發(fā)式地確定集合H， 得到函數(shù)y， 然后對y進行ESOP最小化， 從而得到不完全規(guī)定函數(shù)g的近優(yōu)ESOP, 目的是希望通過無關(guān)項賦值來降低ESOP的復(fù)雜度.

1.2 立方體表示

對于n-輸入/m-輸出的多輸出布爾函數(shù)， 可以使用立方體表示乘積項. 采用位置標(biāo)記法的立方體表示為

c=[ci,co],

式中： 輸入部分ci=[c0,c1,…,cn-1]； 輸出部分co=[cn,cn+1,…,cn+m-1].cj∈{0,1,-}， 對于ci， 分別表示相應(yīng)變量xj以反變量形式、 原變量形式出現(xiàn)以及不出現(xiàn)在乘積項中； 對于co， 則表示ci對應(yīng)的乘積項分別為函數(shù)第j-n(n≤j≤n+m-1)個輸出的OFF, ON和DC乘積項. 對于ci， 如果cj∈{0,1}， 則稱cj為立方體中的一個文字(literal).

假設(shè)n≤j≤n+m-1， 如果?j,cj=0， 則記作co=0.

定義 4 對于立方體c， 如果?j(n≤j≤n+m-1)， 有cj∈{0,1}， 則稱之為完全規(guī)定立方體， 如果co=0則稱之為OFF立方體， 如果完全規(guī)定立方體c的co≠0則稱之為ON立方體； 如果?j(n≤j≤n+m-1)， 有cj∈{0,-}， 且?j,cj=-， 則稱之為DC立方體.

根據(jù)定義4， 不完全規(guī)定函數(shù)的ON集F由所有ON立方體構(gòu)成， OFF集R則由所有OFF立方體構(gòu)成， DC集則由所有DC立方體構(gòu)成， 并且F∩D=?，F(xiàn)∩R=?，D∩R=?.

對于一個表示多輸出函數(shù)的立方體集合C， 如果?c∈C均為完全規(guī)定立方體， 那么該函數(shù)為完全規(guī)定函數(shù). 如果?c∈C為DC立方體， 那么該函數(shù)為不完全規(guī)定函數(shù).

定義 5 對于兩個完全規(guī)定的立方體a和b，ao∧bo=[an∧bn,…,an+m-1∧bn+m-1]， 其中“∧”表示邏輯與， 由于此時aj,bj∈{0,1}(n≤j≤n+m-1)， 因此“∧”的運算規(guī)則為0∧0=0， 0∧1=0， 1∧1=1.

當(dāng)且僅當(dāng)?j(n≤j≤n+m-1)，aj=bj時，ao=bo. 而立方體a和b間的距離定義為

1.3 Exorlink運算

立方體變換是將滿足某種關(guān)系的一組立方體在不改變其邏輯含義的前提下進行組合變形， 經(jīng)常被用來實現(xiàn)函數(shù)的化簡[4]. Exorlink運算[7]是立方體變換的擴展， 根據(jù)立方體間的鄰近關(guān)系， 依次與相鄰的立方體進行連接， 從而減少乘積項數(shù)或文字?jǐn)?shù). 距離為1或2立方體間的Exorlink運算根據(jù)式(1)所示的規(guī)則進行.

(1)

由式(1)可知， 如果D(a,b)=1且aj,bj≠-， 實施a和b之間的Exorlink運算可以減少乘積項數(shù)， 也可以看作將b和a歸并， 并使a中的文字?jǐn)?shù)減少1. 如果D(a,b)=2， 雖然實施a和b之間的Exorlink運算不能減少乘積項數(shù)， 但如果條件

Ca,b=(ao∧bo≠?)∧(aj≠bj)∧

(ak≠bk)∧(aj,ak,bj,bk≠-)

2 不完全規(guī)定函數(shù)的ESOP最小化

本文采用立方體表示法， 使用exorcism算法中的Exorlink運算并結(jié)合前瞻策略與回溯策略進行不完全規(guī)定函數(shù)的ESOP最小化. 先由不完全規(guī)定函數(shù)的ON集F借助exorcism算法得到ESOP覆蓋(立方體集合)G； 然后采用前瞻策略啟發(fā)式地實施無關(guān)項賦值， 確定集合H， 并得到其ESOP覆蓋He； 再借助Exorlink運算對G∪He進行ESOP最小化， 并對不能降低ESOP復(fù)雜度的無關(guān)項賦值采用回溯策略進行回溯.

2.1 啟發(fā)式無關(guān)項賦值

已知DC立方體c和ESOP覆蓋G中的立方體a， 采用前瞻策略的啟發(fā)式無關(guān)項賦值是根據(jù)“實施c和a間的Exorlink運算對ESOP復(fù)雜度所產(chǎn)生影響”的先驗知識來決定是否將c作為ON立方體(即將c中的無關(guān)項賦值為1)加入到G. 如果D(a,c)=1且aj,bj≠-， 根據(jù)式(1)可知， 實施a和c間的Exorlink運算， 可以將c和a歸并， 并使立方體a中的文字?jǐn)?shù)減少1， 能夠降低ESOP的復(fù)雜度， 因此將c作為ON立方體加入到G， 并實施c和a間的Exorlink運算， 以便在降低ESOP復(fù)雜度的同時也為后續(xù)的無關(guān)項賦值產(chǎn)生距離為1的立方體. 由于G在無關(guān)項賦值過程中是動態(tài)變化的， 因此無關(guān)項賦值是動態(tài)實施的.

為區(qū)分DC立方體與G中的非DC立方體， 對立方體a設(shè)置DC標(biāo)志wa， 如果wa=1表明a是DC立方體， 如果wa=0則表明a是非DC立方體.

算法1所示的lookahead判斷將DC立方體c作為ON立方體加入到G對降低ESOP復(fù)雜度是否有幫助， 如果確定有幫助或者可能有幫助則返回非0值， 否則返回0值. 算法1體現(xiàn)了本文的前瞻策略.

算法 1lookahead(s,c,G,D)

1)t←0;

2) for eacha∈Gandwa=0 andao∧co≠0{

3) if (s=1 andD(a,c)=2 andCa,c=true) {

4)t←t+1;

5) } else if(D(a,c)=1) {∥假設(shè)al≠cl(0≤l≤n-1)

6) ifao=co{

7) if (al≠- andcl≠-) return 2;

8) else if (s=1) return 3;}

9)} else if (D(a,c)=0) {

10) if (ao=co) {

11)G←G{a},D←D{c};

12) return 1; }

13) else return 2; } }

14) if (s=1 andt>1) return 3;

15) return 0.

算法lookahead搜索ESOP覆蓋G中是否存在與不相交DC集D(D中的立方體兩兩不相交)中的立方體c滿足所指定條件的立方體， 如果存在則返回非0值. 其中G←G{a}表示從集合G中刪除立方體a，D←D{c}也有類似的含義.

參數(shù)s控制搜索的行為， 如果s=0， 則僅判斷將無關(guān)項賦值為1是否能夠確定降低ESOP的復(fù)雜度， 如步驟7)和步驟9)～13). 對于步驟7)， 由于D(a,c)=1,ao=co,al≠-且cl≠-， 根據(jù)式(1)可知將c作為ON立方體加入到G并實施a和c間的Exorlink運算能夠減少a中的文字?jǐn)?shù). 在步驟9)～13)中， 如果D(a,c)=0且ao=co， 則說明將c作為ON立方體加入到G并實施a和c間的Exorlink運算可使ESOP減少一個立方體(立方體a被消除)； 如果ao≠co， 由于步驟2)中限定了ao∧co≠0， 因此實施a和c間的Exorlink運算能夠使ao中的1數(shù)減少， 從而可以減少函數(shù)某些輸出所包含的乘積項數(shù).

如果s=1， 則還需判斷將c作為ON立方體加入到G是否有降低ESOP復(fù)雜度的可能， 如步驟8)和步驟14). 對于步驟8)， 盡管D(a,c)=1且ao=co， 但是當(dāng)al=-或cl=-時， 將c作為ON立方體并實施a和c間的Exorlink運算僅能夠使立方體a中輸入變量xl的出現(xiàn)形式發(fā)生變化(例如當(dāng)al=1,cl=-時， 實施a和c間的Exorlink運算將使al=0，xl的出現(xiàn)形式由正極性變?yōu)樨?fù)極性)， 雖不能確定降低ESOP的復(fù)雜度， 但是有可能使覆蓋G中立方體間的距離發(fā)生變化， 在進行后續(xù)的ESOP化簡時， 有可能降低ESOP的復(fù)雜度. 對于步驟14)， 其中的t由步驟3)和步驟4)決定. 步驟3)表明立方體a和c間的距離為2且條件Ca,c為真， 將c作為ON立方體并實施a和c間的Exorlink運算雖然能夠使立方體a和c中的文字?jǐn)?shù)均減少1， 但由于立方體c的加入?yún)s使ESOP增加了一個立方體. 由于立方體a文字?jǐn)?shù)的減少和立方體c的加入， 將使覆蓋G中立方體間的距離發(fā)生變化， 從而在進行后續(xù)的ESOP化簡時， 也有可能降低ESOP的復(fù)雜度， 因此如果在覆蓋G中存在著多個與立方體c間滿足距離為2且條件Ca,c為真的立方體時返回非0值.

2.2 ESOP最小化算法

算法2所示的dc_min是不完全規(guī)定函數(shù)ESOP最小化算法的主體部分， 通過啟發(fā)式地實施無關(guān)項賦值， 將滿足條件的DC立方體通過無關(guān)項賦值作為ON立方體加入到ESOP覆蓋G后， 對G中距離為1的立方體實施Exorlink運算， 降低ESOP的復(fù)雜度， 并對覆蓋G使用Exorlink運算進行ESOP化簡， 對能夠降低ESOP復(fù)雜度的無關(guān)項賦值進行確認(rèn)， 對于那些不能有效降低ESOP復(fù)雜度的無關(guān)項賦值， 則采用回溯策略進行回溯.

算法 2dc_min(s,G,D)

1) do {

2)u←0;

3) for eachc∈D{

4)z←lookahead(s,c,G,D);

5) ifz≥2 {

6)G←G∪{c},D←D{c};

7)linkd1cubes(G); }

8)u←u+z;}

9) if(u>0)iterativelinks(G);

10) }until(u=0);

11) for eacha∈G{

12) if (wa=1) {

13)G←G{a},D←D∪{a};}}

在算法2中， 步驟7)的linkd1cubes對ESOP覆蓋G中距離為1的立方體a和b實施Exorlink運算， 如果a或b的DC標(biāo)志為1， 則將其DC標(biāo)志清零， 確認(rèn)無關(guān)項賦值. 步驟9)中的iterativelinks則采用Exorlink運算迭代地對ESOP覆蓋G進行化簡， 直至進行Exorlink運算無法降低ESOP覆蓋G的復(fù)雜度為止[7]， 如果G中DC標(biāo)志為1的立方體能夠減少立方體數(shù)或文字?jǐn)?shù)， 則將其DC標(biāo)志清零， 確認(rèn)無關(guān)項賦值. 步驟11)～13)是算法dc_min中的無關(guān)項賦值回溯策略， 即將覆蓋G中DC標(biāo)志為1的立方體刪除， 并將之重新添加至DC覆蓋D， 因為通過無關(guān)項賦值將這些立方體作為ON立方體不能降低ESOP的復(fù)雜度.

由算法1和算法2可以看出， 本文將無關(guān)項賦值結(jié)合到了ESOP的化簡過程中， 因此無關(guān)項賦值是在RM域內(nèi)實施的， 并且實現(xiàn)了邊實施無關(guān)項賦值邊進行ESOP化簡. 下面給出不完全規(guī)定函數(shù)的啟發(fā)式ESOP最小化算法.

算法 3 啟發(fā)式ESOP最小化算法

1) 解析邏輯網(wǎng)表, 得到其ON集F和DC集D;

2) 對D實施不相交銳積運算, 使其成為不相交覆蓋;

3) 將集合F作為輸入, 使用GenerateInitialEsopCover得到初始ESOP覆蓋G;

4) 使用exorcism算法中的ReduceEsopCover對G進行化簡;

5)dc_min(0,G,D);

6)dc_min(1,G,D);dc_min(0,G,D);

7) 算法結(jié)束, 覆蓋G為不完全規(guī)定函數(shù)g的近優(yōu)ESOP覆蓋.

由于算法3的步驟2)中通過不相交銳積運算使D成為不相交覆蓋(D中的立方體兩兩不相交)， 因此D也可以視為ESOP覆蓋D. 步驟3)中的GenerateInitialEsopCover使用exorcism算法[7]中的ESOP初始覆蓋生成方法獲得ESOP初始覆蓋， 步驟4)則使用exorcism算法中的ReduceEsopCover[7]對G進行化簡. 步驟5)和步驟6)動態(tài)獲得H， 并對G∪H進行ESOP化簡. 由于D是不相交覆蓋， 而H?D， 因此H也是不相交覆蓋， 也可視為ESOP覆蓋He， 根據(jù)1.1節(jié)的分析， 可知算法3結(jié)束時的G為不完全規(guī)定函數(shù)的ESOP覆蓋.

3 算法驗證及結(jié)果分析

文中算法采用C語言實現(xiàn)， 并在Linux操作系統(tǒng)下使用gcc編譯器進行編譯. 在配置為Intel Core i3-2350M CPU 6GB RAM的個人計算機上對12個不同規(guī)模的MCNC不完全規(guī)定函數(shù)進行ESOP最小化， 并分別與exorcsim算法[7]的結(jié)果以及文獻[12]算法的結(jié)果進行比較， 其中文獻[12]算法也采用C語言實現(xiàn).

分別使用exorcism算法和算法3對不完全規(guī)定函數(shù)進行ESOP最小化， 并統(tǒng)計算法結(jié)果ESOP的立方體數(shù)和文字?jǐn)?shù)， 結(jié)果如表 1 所示. 其中的“I/O”表示函數(shù)的“輸入/輸出數(shù)”， “改進”是指相對于exorcism算法的結(jié)果， 算法3結(jié)果的立方體數(shù)以及文字?jǐn)?shù)分別減少的百分比. 在使用exorcism算法進行ESOP最小化時， 采用了“-q 2”選項.

表 1 與exorcism算法結(jié)果比較

由表 1 可以看出， 與exorcism算法的結(jié)果相比， 對于絕大多數(shù)不完全規(guī)定函數(shù)， 算法3均能減少其ESOP的立方體數(shù)和文字?jǐn)?shù)， 最大分別減少了10.53%和14.49%(函數(shù)fout)， 有2個函數(shù)(dk48和mark1)， 盡管不能減少立方體數(shù)， 但卻能夠減少文字?jǐn)?shù). 從總體角度看， 對于這些不完全規(guī)定函數(shù)， 本文算法3使其ESOP的立方體數(shù)減少了4.15%， 文字?jǐn)?shù)減少了4.86%， 這驗證了本文算法的有效性.

由于文獻[12]算法是針對單輸出函數(shù)進行最小化， 為與之進行比較， 在對不完全規(guī)定的多輸出函數(shù)進行ESOP最小化時， 將多輸出函數(shù)視為多個單輸出函數(shù)分別進行最小化， 然后分別統(tǒng)計各個單輸出函數(shù)ESOP結(jié)果的立方體數(shù)之和(總立方體數(shù))以及文字?jǐn)?shù)之和(總文字?jǐn)?shù))， 結(jié)果如表 2 所示.

表 2 與文獻[12]算法結(jié)果比較

由表 2 可以看出， 與文獻[12]算法相比， 在將多輸出函數(shù)視為多個單輸出函數(shù)進行ESOP最小化時， 本文算法3能夠有效減少其ESOP的總立方體數(shù)和總文字?jǐn)?shù). 從表2最后一行的總體角度看， 與文獻[12]算法相比， 對于這些不完全規(guī)定函數(shù)， 本文算法3使其ESOP的立方體數(shù)減少了44.37%， 文字?jǐn)?shù)減少了48.46%， 這進一步驗證了本文算法的有效性. 從時間角度看， 雖然對輸入數(shù)小于20的函數(shù)， 文獻[12]算法具有較高的時間效率， 但是對于輸入數(shù)大于或等于20的函數(shù)(bcd和mark1)而言， 本文算法具有更高的時間效率， 特別是對于函數(shù)bcd. 相對于文獻[12]算法， 本文算法所需時間降低了3個數(shù)量級之多， 這說明本文算法對于輸入數(shù)較多的不完全規(guī)定函數(shù)具有更好適用性.

綜上所述， 本文算法能夠減少不完全規(guī)定函數(shù)ESOP的立方體數(shù)以及文字?jǐn)?shù)， 能夠適用于輸入數(shù)較多的不完全規(guī)定函數(shù)， 既適用于單輸出函數(shù)， 也適用于多輸出函數(shù).

4 結(jié) 論

ESOP因其緊湊的表示形式在可測試性電路設(shè)計、 納電子電路設(shè)計與優(yōu)化以及可逆電路綜合中得到了較為廣泛的應(yīng)用. 對于不完全規(guī)定函數(shù)， 合理的無關(guān)項賦值有助于降低ESOP的復(fù)雜度， 從而有利于降低采用ESOP作為模型所實現(xiàn)電路的開銷. ESOP最小化問題本身就具有指數(shù)級的復(fù)雜度， 并且不完全規(guī)定函數(shù)ESOP的優(yōu)化空間又隨著無關(guān)最小項的增加呈指數(shù)級增長， 需要研究不完全規(guī)定函數(shù)的啟發(fā)式ESOP最小化算法. 本文根據(jù)不完全規(guī)定函數(shù)與其完全規(guī)定函數(shù)實現(xiàn)之間的邏輯關(guān)系以及立方體間的鄰近關(guān)系， 提出了一種在RM域邊實施無關(guān)項賦值邊進行ESOP化簡的不完全規(guī)定函數(shù)ESOP最小化算法. 使用不完全規(guī)定函數(shù)對所提算法進行驗證的結(jié)果表明， 所提算法能夠減少不完全規(guī)定函數(shù)ESOP的立方體數(shù)和文字?jǐn)?shù)， 并且適用于輸入數(shù)較多的不完全規(guī)定函數(shù).

[1]卜登立, 江建慧. 基于對偶邏輯的混合極性RM電路極性轉(zhuǎn)換和優(yōu)化方法[J]. 電子學(xué)報, 2015, 43(1): 79-85. Bu Dengli, Jiang Jianhui. Dual logic based polarity conversion and optimization of mixed polarity RM circuits[J]. Acta Electronica Sinica, 2015, 43(1)： 79-85. (in Chinese)

[2]Rahaman H, Das D K, Bhattacharya B B. Testable design of AND-EXOR logic networks with universal test sets[J]. Computers and Electrical Engineering, 2009, 35(5)： 644-658.

[3]Monteiro C, Takahashi Y, Sekine T. Low-power secure S-box circuit using charge-sharing symmetric adiabatic logic for advanced encryption standard hardware design[J]. IET Circuits, Devices & Systems, 2015, 9(5)： 362-369.

[4]卜登立. 快速啟發(fā)式ESOP電路面積優(yōu)化算法[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2015, 27(11)： 2161-2168. Bu Dengli. Fast heuristic area optimization algorithm for ESOP circuits[J]. Journal of Computer-Aided Design & Computer Graphics, 2015, 27(11)： 2161-2168. (in Chinese)

[5]Shafaei A, Saeedi M, Pedram M. Cofactor sharing for reversible logic synthesis[J]. ACM Journal on Emerging Technologies in Computing Systems, 2014, 11(2)： 1-21.

[6]Datta K, Gokhale A, Sengupta I, et al. An ESOP-based reversible circuit synthesis flow using simulated annealing[J]. Applied Computation and Security Systems, 2015, 305： 131-144.

[7]Mishchenko A, Perkowski M. Fast heuristic minimization of exclusive-sums-of-products[C]. Proceedings of the 5th Reed-Muller Workshop, Mississippi, 2001： 241-249.

[8]張巧文, 汪鵬君, 胡江. 基于分層超立方體的精確ESOP最小化[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2016, 28(1)： 172-179. Zhang Qiaowen, Wang Pengjun, Hu Jiang. Exact minimization of ESOP expressions based on hierarchical hypercube[J]. Journal of Computer-Aided Design & Computer Graphics, 2016, 28(1)： 172-179. (in Chinese)[9]Hirayama T, Nishitani Y. Exact minimization of AND-EXOR expressions of practical benchmark functions[J]. Journal of Circuits, Systems, and Computers, 2009, 18(3)： 465-486.

[10]Chang K H, Bertacco V, Markov I L, et al. Logic synthesis and circuit customization using extensive external don’t-cares[J]. ACM Transactions on Design Automation of Electronic Systems, 2010, 15(3)： 1-26.

[11]Sampson M, Kalathas M, Voudouris D, et al. Exact ESOP expression for incompletely specified functions[J]. Integration, the VLSI Journal, 2012, 45(2)： 197-204.

[12]汪迪生, 汪鵬君. 包含無關(guān)項的MPRM展開式最小化算法[J]. 浙江大學(xué)學(xué)報(理學(xué)版), 2014, 41(1)： 38-42. Wang Disheng, Wang Pengjun. Algorithm about minimization of MPRM expansions including don’t care terms[J]. Journal of Zhejiang University(Science Edition), 2014, 41(1)： 38-42. (in Chinese)

[13]Brand D, Bergamaschi R A, Stok L. Don’t cares in synthesis： theoretical pitfalls and practical solutions[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1998, 17(4)： 285-304.