張菊玲，郭文強，楊曉梅，朱義鑫，楊國武

(1. 新疆財經(jīng)大學信息管理學院 烏魯木齊 830012；2. 電子科技大學計算機科學與工程學院 成都 611731；3. 電子科技大學大數(shù)據(jù)研究中心 成都 611731)

自十九世紀30 年代開始就有學者發(fā)現(xiàn)并意識到布爾匹配和布爾分類在開關電路中扮演著重要角色，人們開始從各個方面研究電路的設計與優(yōu)化[1-3]。布爾等價分類和等價匹配作為電路設計和電路優(yōu)化中的重要技術，逐漸被更多的學者研究[4-5]。

對布爾函數(shù)輸入或輸出的置換運算稱為P 操作，對輸入或輸出的非運算稱為N 操作。根據(jù)對布爾函數(shù)輸入和輸出執(zhí)行P 操作和N 操作的組合，可產(chǎn)生N 變換、P 變換、NP 變換和NPN 變換等，也由此形成了布爾函數(shù)的P 等價匹配、NP 等價匹配和NPN 等價匹配。其中NPN 等價匹配研究較多，第一個N 表示輸入非，P 表示輸入置換，第二個N 表示輸出非。給定一個n輸入布爾函數(shù)，其NPN 變換共有n!2n+1個，采用窮盡法進行匹配，其復雜度是O(n!2n+1)。因此，布爾函數(shù)的NPN 等價分類和匹配是NP 難問題。當前，NPN 等價分類中n的最大值是10[6]。

在數(shù)字電路的技術映射和工藝庫綁定中，布爾函數(shù)NPN 等價匹配是一個必要環(huán)節(jié)，其目的是為當前設計的電路找到一個最優(yōu)的替代電路[7]。現(xiàn)有的布爾函數(shù)NPN 等價匹配方法主要集中在成對比較法、基于正規(guī)式和基于SAT 的方法[8-12]。除此之外，還存在一些基于Walsh 譜特征和學習的方法[13-15]。

本文基于對香農(nóng)擴展定理代數(shù)余子式運算的研究發(fā)現(xiàn)：1)布爾函數(shù)的變量在NP 變換中其對稱性和獨立性不變；2)獨立變量具有相位不確定性；3)利用獨立變量區(qū)分其他變量的不可用性。利用這些特性首先能更早地判定兩個布爾函數(shù)的不等價性，其次能有效地減少匹配中產(chǎn)生的候選正規(guī)式分支數(shù)量，從而減少匹配算法的空間復雜度，提高匹配速度。

1 基本概念與問題陳述

1.1 基本概念

1.2 正規(guī)式

NPN 等價分類將n變量布爾函數(shù)劃分為多個等價類，每個等價類中的所有布爾函數(shù)相互是NPN等價的，即它們之間均可相互轉(zhuǎn)換。在上述等價類中選擇一個布爾函數(shù)作為該類的代表，該代表稱為正規(guī)式?；谡?guī)式的布爾匹配更多應用于工藝庫綁定。對某個電路函數(shù)f(X)進行工藝庫綁定，即在工藝庫中尋找合適的基元實現(xiàn)該電路，通過計算f(X)的正規(guī)式并使用哈希查找快速實現(xiàn)[1]。

令由m個NPN 等價布爾函數(shù)構成的等價類E={f0(X),f1(X),···,fm?1(X)}， 對?i,j∈{0,1,···,m?1}都有fi(X)?fj(X)， 從E中選擇一個布爾函數(shù)作為該等價類的正規(guī)式，記為F(X)。

基于正規(guī)式的布爾函數(shù)NPN 等價匹配可描述為：給定兩個布爾函數(shù)f(X)和g(X)，它們的正規(guī)式 分 別 為F(X)和G(X)， 若 有F(X)=G(X)，則 有f(X)?g(X)。

2 基于正規(guī)式的布爾匹配算法

2.1 布爾函數(shù)NP 變換中變量的屬性

根據(jù)對香農(nóng)分解代數(shù)余子式運算的研究，本文得出在布爾函數(shù)NP 等價變換中具有以下6 個屬性。

6) 布爾函數(shù)f(X)中 的獨立變量xi經(jīng)過NP 變換后，獨立性不變。

如有3 變量布爾函數(shù)f(X)=x1x2+x1x2，若有N 變換φ =(0,0,1) 和 P 變換π =(2，0，1)，f(X)中有獨立變量x0且 經(jīng)過變換x0變換為x2，f(T X)=x0x1+x0x1， 明顯f(T X)中 有獨立變量x2。

充分條件：根據(jù)屬性1)、屬性2)和屬性6)可知，若兩個布爾函數(shù)f(X)和g(X)是NP 等價的，那么這兩個布爾函數(shù)的變量具有相同的對稱變量結(jié)構和獨立變量結(jié)構。

因此，可通過上述充分條件先比較兩個布爾函數(shù)變量的結(jié)構，盡早確定不等價情況。

2.2 本文使用的正規(guī)式

文獻[1]提出了基于高階通用特征的匹配算法，0～n階特征構成高階通用特征向量，且NP 等價類中具有最大特征向量的布爾函數(shù)作為正規(guī)式，證明了每個布爾函數(shù)具有唯一的由0～n階特征值組成的特征向量Vf=(0階特征,1階特征,···,n階特征)，其中0 階特征1 個，m階 特征有Cnm個。利用特征向量計算正規(guī)式：按照0 階特征、1 階特征、···、n階特征順序計算布爾函數(shù)的通用特征，每計算完一次特征后，根據(jù)特征值的大小對變量進行排序，從而找出在某個或某幾個排序下使特征向量值最大的情況，最后所得排序就是一個能將布爾函數(shù)轉(zhuǎn)換為對應正規(guī)式的NP 變換，再根據(jù)該NP 變換計算出相應的正規(guī)式。

在文獻[1]的基礎上，文獻[7]提出了DC(difference and cofactor)特征向量增加了布爾差分特征，這樣能夠更加快速地找到布爾函數(shù)所在等價類中具有最大DC 特征向量的正規(guī)式。

本文將延續(xù)使用DC 特征向量[7]，利用NP 變換時變量變換前后對稱性與獨立性不變的屬性，獨立變量的屬性3)、4)、5)和6)，加快正規(guī)式的計算，從而提高布爾函數(shù)NPN 等價匹配速度。

2.3 加快匹配的關鍵方法

本文將布爾函數(shù)的變量分為3 類：獨立變量、對稱變量和非對稱變量。在計算布爾函數(shù)正規(guī)式的過程中，根據(jù)變量的類型和DC 特征值進行分組。具有相同DC 特征值的變量為一組，每組根據(jù)變量類型分為獨立變量類、對稱變量類和非對稱變量類。當所有的組都是“已解決”狀態(tài)，產(chǎn)生一個候選NP 變換。上述3 類變量所在組處于“已解決”狀態(tài)需滿足的條件為：

1) 非對稱變量，變量相位確定且所在組就一個非對稱變量；

2) 對稱變量，變量相位確定且所在組只有一個對稱類，無其他對稱類和非對稱變量；

3) 獨立變量，因獨立變量的布爾差分特征值為0，即使有其他對稱變量與其具有相同的通用特征值，但布爾差分特征值一定不同，直接標記“已解決”。

加快匹配的關鍵方法為：

1) 給定兩個布爾函數(shù)f(X)和g(X)，首先計算他們的0 階特征、1 階DC 特征，判斷所有變量的對稱性和獨立性，并根據(jù)以上結(jié)果對兩個布爾函數(shù)的變量進行分組。

2) 根據(jù)上面的計算結(jié)果，比較兩個布爾函數(shù)的變量是否具有相同的結(jié)構，即相同的0 階特征、1 階DC 特征、對稱變量結(jié)構和獨立變量結(jié)構。如果f(X)和g(X)/g(X)具有相同結(jié)構再分別計算它們的正 規(guī) 式F(X)和G(X)， 若 等 式F(X)=G(X)成 立，則NPN 等價，否則不等價。

3) 分別利用本文所提出的獨立變量所具有的屬性3)、屬性4)和屬性5)，能更好地減少計算正規(guī)式過程中的搜索空間，具體步驟為：

① 在計算特征值的過程中獨立變量的相位始終無法確定。若布爾函數(shù)具有獨立變量，必有一個對稱類且只有獨立變量。在計算候選正規(guī)式的過程中一定會產(chǎn)生兩個分支[1,7]，分別嘗試同相對稱和反相對稱，所需探測的正規(guī)NP 變換數(shù)增加1 倍。本文直接將獨立變量標記為正相且“已解決”。

② 在文獻[1,7]的算法中使用“已解決”的變量來計算“未解決”變量的高階特征值，以期“未解決”變量能夠獲得不同的高階特征值而變?yōu)椤耙呀鉀Q”。

③ 同樣，參考文獻[1,7]的算法，利用獨立變量去解決其他“未解決”的變量，以期用獨立變量對“未解決”變量計算高階特征值，從而使這些“未解決”的變量得以“解決”。

利用屬性3)、4)或5)，本文對于獨立變量所在的組直接標記為“已解決”，針對具有獨立變量的布爾函數(shù)NPN 等價匹配，可降低空間復雜度50%。

例1：布爾函數(shù)f=x1x3+x1x3+x3x4+x3x4，計算一階DC 特征向量和對稱變量檢測，Vf={(10,10,0),(12,8,12),(10,10,0),(8,12,12),(8,12,12)}，對稱檢測得到兩個對稱類， {x1,x3,x4}和 {x0,x2}， 其中{x0,x2}又是獨立變量類。因此產(chǎn)生兩組G1={x1,x3,x4}，G2={x0,x2}，根據(jù)上述“已解決”的判斷，這里G1和G2都 “已解決”，獲得排序 {x1,x3,x4,x0,x2}，直接得到正規(guī)式F(X)=x0x3+x0x3+x0x2+x0x2。

例1 中如果不考慮本文方法，那么需要利用變量x1計 算x0和x2的二階特征，其目的是獲得這兩個變量的相位，結(jié)果一定是相位不確定，因此產(chǎn)生兩個排序{x1,x3,x4,x0,x2} 和{x1,x3,x4,x0,x2}。

2.4 匹配算法

本算法采用樹形結(jié)構存儲計算正規(guī)式過程中產(chǎn)生的候選正規(guī)式，利用樹的深度優(yōu)先搜索實現(xiàn)。當?shù)趍個組之前的所有組已經(jīng)解決且都無法解決后續(xù)尚未“解決”的組；同時，第m個組需要分為p種情況，這時都將產(chǎn)生p個分支。本文通過上述的關鍵方法減少分支數(shù)，以提高匹配速度。

函數(shù)Initial()用來計算布爾函數(shù)f和g的0 階特征、1 階DC 特征值、對稱性、獨立性、相位信息和初始分組信息，偽代碼如下。

函數(shù)Canonical()用來計算布爾函數(shù)的最大正規(guī)變換，偽代碼如下。

給定兩個n變量布爾函數(shù)f和g，算法先分別調(diào)用Initial()計算它們的初始特征向量和變量結(jié)構，如果變量結(jié)構相同再分別調(diào)用Canonical()函數(shù)計算它們兩個的正規(guī)變換，最后計算正規(guī)式F和G，如果F=G成立，那么布爾函數(shù)f和g是NPN 等價的。其中，當出現(xiàn) |f|=|g|=2n?1時，處理方法同文獻[1]。

3 實驗結(jié)果

基于MCNC 標準電路庫中電路和隨機生成電路的布爾函數(shù)，對本文提出的算法和文獻[1]中的基于高階通用特征的算法進行了測試、比較和驗證。測試環(huán)境配置為3.3 GHz CPU、8 GB RAM。

表1 為對MCNC 標準電路庫中電路的布爾函數(shù)NPN 等價匹配的實驗結(jié)果，表2 為隨機生成電路的布爾函數(shù)NPN 等價匹配的結(jié)果。兩表中的第1 列是變量個數(shù)，第2～3 列和4～5 列是本文和文獻[1]算法的匹配平均時間(AVG)和平均候選正規(guī)變換數(shù)(A.T)。

表1 MCNC 標準庫電路NPN 等價匹配結(jié)果

根據(jù)表1 中的實驗結(jié)果可以看出，本文算法對MCNC 標準電路庫中電路的布爾函數(shù)的匹配速度比文獻[1]提升了40.1%，搜索空間減少了42.1%。根據(jù)表2 可以看出本文算法對隨機電路的布爾函數(shù)匹配速度比文獻[1]提升了51%，搜索空間減少75.4%?？梢訬PN 等價匹配對隨機電路的布爾函數(shù)匹配速度提升更高，其原因是隨機產(chǎn)生電路的布爾函數(shù)中具有獨立變量的情況更多一些。

表2 隨機生成電路NPN 等價匹配結(jié)果

通過實驗可以看出，本文算法能夠大大減少計算正規(guī)式過程中的搜索空間，并大幅提高了布爾函數(shù)匹配速度。

4 結(jié) 束 語

本文通過對布爾函數(shù)香農(nóng)分解代數(shù)余子式運算的研究，得出6 個有利于布爾匹配的屬性。利用這些屬性提出了更有效的基于正規(guī)式的NPN 布爾匹配算法，有效減少了算法的搜索空間和提高了布爾函數(shù)NPN 等價匹配的速度。該算法能夠更好地應用到電路設計和優(yōu)化中去，具有一定的應用價值。如何解決布爾函數(shù)在最壞情況下的NPN 等價匹配難題，是下一步的研究難點。