卜登立，朱 平

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

卜登立1,2，朱 平1

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

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

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

0 引言

布爾函數(shù)既可以在操作域使用基于AND/OR的形式表示，也可以在功能域使用基于AND/XOR的形式表示，前者常稱為布爾邏輯，后者常稱為RM(Reed-Muller)邏輯[1]。與布爾邏輯實(shí)現(xiàn)的電路相比，采用RM邏輯能夠減少邏輯門及其內(nèi)部互聯(lián)的數(shù)量，并且可以減少最大路徑長度，因此，人們常用RM實(shí)現(xiàn)算術(shù)邏輯、通信系統(tǒng)和差錯(cuò)校驗(yàn)等電路[1-3]，并且使用RM邏輯實(shí)現(xiàn)的電路具有較好的可測(cè)性[4]，能夠降低測(cè)試復(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由于具有更大的極性空間，能夠得到更為簡化的表示形式，并且由于實(shí)際應(yīng)用中多為多輸出電路，因此近年來多輸出MPRM電路得到了更多的關(guān)注[1, 3]。極性轉(zhuǎn)換是MPRM電路極性優(yōu)化過程中的一個(gè)重要步驟[1,3]，極性轉(zhuǎn)換速度的快慢將影響整個(gè)優(yōu)化過程的性能[3]，因此極性轉(zhuǎn)換方法成為RM電路研究領(lǐng)域一個(gè)較為重要的研究方向，如文獻(xiàn)[1]中的多輸出列表技術(shù)和文獻(xiàn)[3]中的系數(shù)矩陣變換極性轉(zhuǎn)換方法。但是當(dāng)前的極性轉(zhuǎn)換方法主要是針對(duì)位級(jí)表示的多輸出布爾函數(shù)及其MPRM，而字級(jí)表示作為邏輯綜合領(lǐng)域中一種非常重要的方法與手段[6]，便于對(duì)多輸出電路進(jìn)行整體操縱，從而滿足并行處理、模擬和驗(yàn)證的要求[6]。近些年來矩陣表示在邏輯電路的設(shè)計(jì)、可靠性分析以及布爾網(wǎng)絡(luò)的控制等領(lǐng)域得到了廣泛的應(yīng)用。如文獻(xiàn)[7,8]使用矩陣描述邏輯門和邏輯電路的概率行為以及確定性行為，通過矩陣運(yùn)算來計(jì)算邏輯電路的信號(hào)可靠度，對(duì)邏輯電路的可靠性進(jìn)行評(píng)估。文獻(xiàn)[6]和[9]使用矩陣的張量積來計(jì)算布爾差分，而布爾差分又被應(yīng)用在電路可靠性分析[9]、測(cè)試、功耗估計(jì)等[6]領(lǐng)域。但這些應(yīng)用或者是使用矩陣在位級(jí)表示布爾函數(shù)，或者是使用矩陣在操作域表示布爾函數(shù)。由于MPRM是在功能域表示布爾函數(shù)，因此有必要結(jié)合字級(jí)表示以及矩陣表示對(duì)多輸出MPRM電路進(jìn)行研究。

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

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

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

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

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

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

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

else

end if

else

end if

end if

end while

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

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

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

圖1 的極性: 2à0

圖2 x1的極性: 2à1

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

3 實(shí)驗(yàn)及結(jié)果分析

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

算法測(cè)試的軟件環(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)換的平均時(shí)間、字級(jí)表示相對(duì)于位級(jí)表示極性轉(zhuǎn)換時(shí)間縮短的比例。

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

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

4 結(jié)束語

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

[1] 李輝, 汪鵬君, 王振海. 混合極性列表技術(shù)及其在MPRM電路面積優(yōu)化中的應(yīng)用[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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可靠度評(píng)估方法[J]. 井岡山大學(xué)學(xué)報(bào):自然科學(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é)基金項(xiàng)目(61363014)

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

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