基于字級表示的多輸出MPRM電路極性轉換算法

卜登立，朱 平

基于字級表示的多輸出MPRM電路極性轉換算法

卜登立1,2，朱 平1

(1. 井岡山大學電子與信息工程學院，江西 吉安 343009；2. 同濟大學電子與信息工程學院，上海 201804)

針對多輸出MPRM（Mixed-Polarity Reed-Muller）電路的極性轉換問題，提出了使用系數矩陣在字級表示多輸出布爾函數及其MPRM，并給出了一種極性轉換算法。實驗結果表明，與位級表示相比，所提出的基于字級表示的極性轉換算法可顯著縮短多輸出MPRM電路的極性轉換時間。

多輸出布爾函數；混合極性Reed-Muller電路；極性轉換；字級表示；系數矩陣

0 引言

布爾函數既可以在操作域使用基于AND/OR的形式表示，也可以在功能域使用基于AND/XOR的形式表示，前者常稱為布爾邏輯，后者常稱為RM(Reed-Muller)邏輯[1]。與布爾邏輯實現的電路相比，采用RM邏輯能夠減少邏輯門及其內部互聯的數量，并且可以減少最大路徑長度，因此，人們常用RM實現算術邏輯、通信系統和差錯校驗等電路[1-3]，并且使用RM邏輯實現的電路具有較好的可測性[4]，能夠降低測試復雜度。由于可逆電路和量子電路將XOR門作為基本的構建邏輯，因此RM邏輯在可逆電路和量子電路中也得到了廣泛的應用，并且量子電路的綜合方法已經開始使用RM邏輯形式[5]。

布爾函數有兩種常見的RM展開，固定極性RM(Fixed-Polarity RM，FPRM)展開和混合極性RM(Mixed-Polarity RM，MPRM)展開[1-3]。與FPRM相比，MPRM由于具有更大的極性空間，能夠得到更為簡化的表示形式，并且由于實際應用中多為多輸出電路，因此近年來多輸出MPRM電路得到了更多的關注[1, 3]。極性轉換是MPRM電路極性優(yōu)化過程中的一個重要步驟[1,3]，極性轉換速度的快慢將影響整個優(yōu)化過程的性能[3]，因此極性轉換方法成為RM電路研究領域一個較為重要的研究方向，如文獻[1]中的多輸出列表技術和文獻[3]中的系數矩陣變換極性轉換方法。但是當前的極性轉換方法主要是針對位級表示的多輸出布爾函數及其MPRM，而字級表示作為邏輯綜合領域中一種非常重要的方法與手段[6]，便于對多輸出電路進行整體操縱，從而滿足并行處理、模擬和驗證的要求[6]。近些年來矩陣表示在邏輯電路的設計、可靠性分析以及布爾網絡的控制等領域得到了廣泛的應用。如文獻[7,8]使用矩陣描述邏輯門和邏輯電路的概率行為以及確定性行為，通過矩陣運算來計算邏輯電路的信號可靠度，對邏輯電路的可靠性進行評估。文獻[6]和[9]使用矩陣的張量積來計算布爾差分，而布爾差分又被應用在電路可靠性分析[9]、測試、功耗估計等[6]領域。但這些應用或者是使用矩陣在位級表示布爾函數，或者是使用矩陣在操作域表示布爾函數。由于MPRM是在功能域表示布爾函數，因此有必要結合字級表示以及矩陣表示對多輸出MPRM電路進行研究。

本文采用系數矩陣在字級表示多輸出布爾函數及其MPRM，重點研究多輸出MPRM電路的極性轉換，給出了一種極性轉換算法，并通過實驗驗證了算法的有效性。

1 多輸出布爾函數及其MPRM的字級表示

式(1)所示的形式為多輸出布爾函數的位級表示，而字級表示則根據按位計數系統原理[6]，給每個輸出函數賦予一個權重，從而將多輸出函數表示為字級的算術表達式[6]，如式(2)所示。

例1一位全加器的位級表示如式(4)所示，其字級表示如式(5)所示。

2 多輸出MPRM電路極性轉換算法

采用字級表示后，可以很方便地對多輸出布爾函數進行整體極性轉換，從而得到不同極性值的MPRM電路。在得到多輸出MPRM電路的字級表示后，再根據每個輸出的位置進行屏蔽操作[6]即可得到其位級表示。本文采用文獻[3]中的系數矩陣變換方法對字級表示的多輸出布爾函數進行MPRM極性轉換。

算法1基于字級表示的多輸出MPRM極性轉換算法

else

end if

else

end if

end if

end while

下面舉例來說明字級表示時多輸出MPRM電路的極性轉換過程。

例2 一位全加器極性值為26的MPRM的字級表示如下式所示，

現使用算法1得到其極性值為5的MPRM。

圖1 的極性: 2à0

圖2 x1的極性: 2à1

結合式(7)，可得一位全加器極性值為5的MPRM的字級表示為：

3 實驗及結果分析

為驗證文中的算法1，并與采用位級表示的MPRM極性轉換方法比較，本文還設計了采用位級表示的系數矩陣變換MPRM極性轉換算法，稱之為算法2，2種算法均使用C++實現，并選取14個多輸出MCNC基準電路對2種算法進行測試。測試方法是對每個電路隨機生成200個不同的極性值，并按照生成的順序進行極性轉換，記錄每一次極性轉換所花費的時間，并統計200次極性轉換的平均時間。

算法測試的軟件環(huán)境為Windows XP Professional操作系統，硬件環(huán)境為Pentium IV 2.8GHz CPU 512MB RAM。表1給出了所采用的基準電路名稱、基準電路的輸入數、輸出數、200次極性轉換的平均時間、字級表示相對于位級表示極性轉換時間縮短的比例。

表1 MCNC基準電路測試結果

從表1中的結果可以看出，相對于位級表示，采用字級表示使得極性轉換的時間有較大程度的降低。由于矩陣本身的特性，在相同輸出的情況下，性能提升的程度隨輸入數的增加而增加；在相同輸入的情況下，性能提升的幅度隨著輸出數的增加而增大?？傮w來看，輸出數相對越多，則性能提升的幅度也相對越大，如電路misex3、table3和table5，其輸出數均大于10，因此性能提升超過了90%。14個電路的平均時間縮短了92%，從而驗證了文中所提出的基于字級表示的MPRM電路極性轉換算法的有效性。

4 結束語

由于采用RM邏輯實現的電路在面積和可測性方面的優(yōu)勢，使得RM邏輯在數字電路中得到了廣泛的應用，并且多輸出MPRM電路得到了較多的關注。本文使用系數矩陣在字級表示多輸出布爾函數及其MPRM，給出了基于字級表示的多輸出MPRM電路極性轉換算法。實驗結果驗證了所提出算法的有效性，相對于位級表示，使用字級表示可以顯著縮短多輸出MPRM電路極性轉換的時間。

[1] 李輝, 汪鵬君, 王振海. 混合極性列表技術及其在MPRM電路面積優(yōu)化中的應用[J]. 計算機輔助設計與圖形學學報, 2011, 23(3): 527-533.

[2] Tan E C, Yang H. Optimization of fixed-polarity Reed-Muller circuits using dual-polarity property[J]. Circuits, Systems, and Signal Processing, 2000, 19(6): 535-548.

[3] 卜登立, 江建慧. 使用系數矩陣變換極性轉換的MPRM電路面積優(yōu)化[J]. 計算機輔助設計與圖形學學報, 2013, 25(1): 126-135.

[4] 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.

[5] Drechsler R, Finder A, Wille R. Improving ESOP-based synthesis of reversible logic using evolutionary algorithms[J]. Lecture Notes in Computer Science, 2011, 6625:151-161.

[6] Yanushkevich S N, Miller D M, Shmerko V P, et al. Decision diagram techniques for micro- and nanoelectronic design handbook[M]. Boca Raton: CRC Press, 2006.

[7] Krishnaswamy S, Viamontes G F, Igor L. Markov, et al. Probabilistic Transfer Matrices in Symbolic Reliability Analysis of Logic Circuits[J]. ACM Transactions on Design Automation of Electronic Systems, 2008, 13(1): 8:1-8:35.

[8] 卜登立. 基于偽門故障模型的PTM可靠度評估方法[J]. 井岡山大學學報:自然科學版, 2012, 33(6): 56-60.

[9] Li H, Wang Y. Boolean derivative calculation with application to fault detection of combinational circuits via the semi-tensor product method[J]. Automatica, 2012, 48(4): 688-693.

WORD LEVEL REPRESENTATION BASED POLARITY CONVERSION ALGORITHM FOR MULTI-OUTPUT MPRM CIRCUITS

BU Deng-li1,2,ZHU Ping1

(1. School of Electronics and Information Engineering, Jinggangshan University, Ji’an Jiangxi 343009, China; 2. School of Electronics and Information Engineering, Tongji University, Shanghai 201804, China)

Word level representation of multi-output Boolean function and its mixed-polarity Reed-Muller (MPRM) using coefficient matrix is proposed for polarity conversion of multi-output MPRM circuits. Based on this representation, a polarity conversion algorithm is presented. Experimental results show that, in comparison with bit level representation, the proposed word level representation based polarity conversion algorithm can significantly reduce the time consumed for polarity conversion of multi-output MPRM circuits.

Multi-output Boolean function; mixed-polarity Reed-Muller circuit; polarity conversion; word-level representation; coefficient matrix

TP391.72

A

10.3969/j.issn.1674-8085.2014.06.013

1674-8085(2014)06-0061-05

2014-06-12；

2014-10-13

國家自然科學基金項目(61363014)

*卜登立(1975-），男，河北定州人，副教授，博士生，主要從事VLSI設計和可靠性評估、計算機輔助設計方面研究(Email: bodengli@163.com);

朱 平(1955-），男，上海人，教授，碩士，主要從事算法分析與設計方面研究(Email:zhuping810@163.com).