正規式布爾函數NPN 等價匹配算法

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

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

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

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

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

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

1 基本概念與問題陳述

1.1 基本概念

1.2 正規式

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

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

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

2 基于正規式的布爾匹配算法

2.1 布爾函數NP 變換中變量的屬性

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

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

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

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

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

2.2 本文使用的正規式

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

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

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

2.3 加快匹配的關鍵方法

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

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

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

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

加快匹配的關鍵方法為：

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

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

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

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

② 在文獻[1,7]的算法中使用“已解決”的變量來計算“未解決”變量的高階特征值，以期“未解決”變量能夠獲得不同的高階特征值而變為“已解決”。

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

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

例1：布爾函數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}又是獨立變量類。因此產生兩組G1={x1,x3,x4}，G2={x0,x2}，根據上述“已解決”的判斷，這里G1和G2都 “已解決”，獲得排序 {x1,x3,x4,x0,x2}，直接得到正規式F(X)=x0x3+x0x3+x0x2+x0x2。

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

2.4 匹配算法

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

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

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

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

3 實驗結果

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

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

表1 MCNC 標準庫電路NPN 等價匹配結果

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

表2 隨機生成電路NPN 等價匹配結果

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

4 結 束 語

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