卜登立，朱 平

基于字級表示的多輸出MPRM電路極性轉(zhuǎn)換算法

卜登立1,2，朱 平1

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

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

多輸出布爾函數(shù)；混合極性Reed-Muller電路；極性轉(zhuǎn)換；字級表示；系數(shù)矩陣

0 引言

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

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

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

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

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

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

2 多輸出MPRM電路極性轉(zhuǎn)換算法

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

算法1基于字級表示的多輸出MPRM極性轉(zhuǎn)換算法

else

end if

else

end if

end if

end while

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

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

現(xiàn)使用算法1得到其極性值為5的MPRM。

圖1 的極性: 2à0

圖2 x1的極性: 2à1

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

3 實驗及結(jié)果分析

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

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

表1 MCNC基準(zhǔn)電路測試結(jié)果

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

4 結(jié)束語

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

[1] 李輝, 汪鵬君, 王振海. 混合極性列表技術(shù)及其在MPRM電路面積優(yōu)化中的應(yīng)用[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 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] 卜登立, 江建慧. 使用系數(shù)矩陣變換極性轉(zhuǎn)換的MPRM電路面積優(yōu)化[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 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]. 井岡山大學(xué)學(xué)報:自然科學(xué)版, 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

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

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

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