邏輯函數(shù)高階布爾e偏導(dǎo)數(shù)求解算法的實(shí)現(xiàn)

羅文強(qiáng)，王倫耀，夏銀水

(寧波大學(xué) 信息科學(xué)與工程學(xué)院， 浙江 寧波 315211)

布爾導(dǎo)數(shù)和e導(dǎo)數(shù)能反映布爾函數(shù)值隨變量變化的關(guān)系，二者被廣泛應(yīng)用于圖像處理[1]、邏輯電路的故障檢測[2-5]和布爾函數(shù)密碼學(xué)性質(zhì)的研究[6-9]．

目前，學(xué)者對(duì)布爾e導(dǎo)數(shù)求解方法的研究主要有3種： 基于K圖和降維K圖的圖形法[10]、基于最小項(xiàng)的表格法[11]和基于改進(jìn)D圖的算法[12]．利用K圖和降維K圖求解布爾e導(dǎo)數(shù)，具有計(jì)算方法簡單、物理意義清晰的特點(diǎn)，但隨著輸入變量數(shù)n的增大，其圖形規(guī)模將以2n的速度迅速增加，因此此方法對(duì)輸入變量超過30的大邏輯函數(shù)不適用；同樣，通過列布爾1值最小項(xiàng)表求解布爾e導(dǎo)數(shù)，其最小項(xiàng)數(shù)量與輸入變量數(shù)n成2n關(guān)系，亦不適合處理大函數(shù)；而基于改進(jìn)D圖求解布爾e導(dǎo)數(shù)的方法，其圖形規(guī)模不僅與輸入變量數(shù)n成an(1

布爾e偏導(dǎo)數(shù)[13]的求解較布爾e導(dǎo)數(shù)更難．文獻(xiàn)[11]提出了一種基于最小項(xiàng)表求解布爾e偏導(dǎo)數(shù)的方法，即根據(jù)待求導(dǎo)變量累次列布爾1值最小項(xiàng)求解布爾e偏導(dǎo)數(shù)，其與基于最小項(xiàng)的布爾e導(dǎo)數(shù)求解方法一樣，亦不適合求解大函數(shù)的布爾e偏導(dǎo)數(shù)．

本文給出了一種便于計(jì)算機(jī)編程實(shí)現(xiàn)的邏輯函數(shù)高階布爾e導(dǎo)數(shù)和e偏導(dǎo)數(shù)的求解算法．利用乘積項(xiàng)集合之間的不相交操作[14]，實(shí)現(xiàn)邏輯函數(shù)的邏輯“與”操作，并結(jié)合布爾e導(dǎo)數(shù)和e偏導(dǎo)數(shù)的定義，給出了求解算法．采用二級(jí)邏輯綜合工具espresso，對(duì)算法的最終輸出結(jié)果進(jìn)行簡化，進(jìn)而得到更加緊湊的求導(dǎo)結(jié)果．

1 定 義

一個(gè)n變量布爾函數(shù)f(x1～xn)總可以寫成式(1)所示的乘積項(xiàng)之和(sum of product, SOP)：

(1)

式(1)中pi為布爾函數(shù)f的第i個(gè)乘積項(xiàng)，k為乘積項(xiàng)的個(gè)數(shù)，符號(hào)“∑”表示乘積項(xiàng)之間是邏輯“或”關(guān)系，并記f的乘積項(xiàng)集合為Cf．若乘積項(xiàng)pi∈Cf，則pi可寫成：

(2)

例如，乘積項(xiàng)p=x1x2x3=-1-，按上述約定可將變量x1,x3全取“-”，寫成DC(x1,x3)；變量x1,x2,x3不全取“-”寫成EN(x1,x2,x3)．

定義1設(shè)f(x1～xn)為n變量的布爾函數(shù)，則f(x1～xn)對(duì)于變量xj(1≤j≤n)的一階布爾e導(dǎo)數(shù)為

(3)

定義2設(shè)f(x1～xn)為n變量的布爾函數(shù)，則f(x1～xn)對(duì)于變量xj1～xjk(2≤k≤n)的k階布爾e導(dǎo)數(shù)可表示為

(4)

推論1設(shè)n變量布爾函數(shù)f對(duì)應(yīng)的乘積項(xiàng)集合Cf由(s+t)個(gè)不相交乘積項(xiàng)構(gòu)成，即pi·pj=? (i≠j)，其中,s個(gè)乘積項(xiàng)中的待求導(dǎo)變量均不出現(xiàn)，而另外t個(gè)乘積項(xiàng)中的每個(gè)乘積項(xiàng)至少有1個(gè)待求導(dǎo)變量出現(xiàn)，則k(1≤k≤n)階布爾e導(dǎo)數(shù)可表示為

證明將構(gòu)成邏輯函數(shù)f的(s+t)個(gè)不相交乘積項(xiàng)拆分成g和h兩部分，且f=g+h．其中，g中包含s個(gè)不相交乘積項(xiàng)，且任一乘積項(xiàng)中的待求導(dǎo)變量均未出現(xiàn)；h中包含t個(gè)不相交乘積項(xiàng)，顯然屬于h的任一乘積項(xiàng)中的待求導(dǎo)變量至少出現(xiàn)1個(gè)．因此，g和h可以表示為

由條件pi·pj=?(i≠j)可知g·h=?，故

證畢!

解由推論1可得

由定義2及計(jì)算可得

以上2種方法的計(jì)算結(jié)果是一致的．用推論1來實(shí)現(xiàn)布爾e導(dǎo)數(shù)，其求導(dǎo)過程中邏輯表達(dá)式之間的邏輯“與”操作更加簡單．

定義3設(shè)f(x1～xn)為n變量的布爾函數(shù)，則f(x1～xn)對(duì)于變量xj(1≤j≤n)的一階布爾e偏導(dǎo)數(shù)為一階布爾e導(dǎo)數(shù)．

定義4設(shè)f(x1～xn)為n變量的布爾函數(shù)，則f(x1～xn)對(duì)于變量xj1～xjk(2≤k≤n)的k階布爾e偏導(dǎo)數(shù)可表示為

(6)

推論2設(shè)n變量布爾函數(shù)f對(duì)應(yīng)乘積項(xiàng)集合Cf由pi·pj=?(i≠j)個(gè)不相交乘積項(xiàng)構(gòu)成，即pi·pj=?(i≠j)，其中s個(gè)乘積項(xiàng)中的待求偏導(dǎo)變量均不出現(xiàn)，而另外t個(gè)乘積項(xiàng)中每項(xiàng)至少有1個(gè)待求偏導(dǎo)變量，則k(1≤k≤n)階布爾e偏導(dǎo)數(shù)可表示為

(7)

式(7)中，h為布爾函數(shù)f的子函數(shù)，

證明用數(shù)學(xué)歸納法：

(1) 當(dāng)階數(shù)k=1時(shí)，由定義3知，利用推論1可證明式(7)成立，即

(2) 假設(shè)當(dāng)階數(shù)k=q(1

由步驟(1)～(3)可知，對(duì)任意階數(shù)k(1≤k≤n)，推論2成立．

證畢!

2 算法實(shí)現(xiàn)

由布爾e導(dǎo)數(shù)和e偏導(dǎo)數(shù)的定義可知，邏輯函數(shù)的布爾e導(dǎo)數(shù)和e偏導(dǎo)數(shù)的求解過程中都涉及求解函數(shù)之間的“與”運(yùn)算．因此，求解邏輯函數(shù)的邏輯“與”直接影響布爾e導(dǎo)數(shù)的求解速度和規(guī)模．下文將討論邏輯函數(shù)之間“與”運(yùn)算的求解方法以及大函數(shù)高階布爾e導(dǎo)數(shù)和e偏導(dǎo)數(shù)算法．考慮現(xiàn)有的布爾e導(dǎo)數(shù)和e偏導(dǎo)數(shù)的求解方法只適用于輸入變量較少的邏輯函數(shù)的低階求導(dǎo)，且對(duì)求導(dǎo)結(jié)果未進(jìn)行邏輯簡化，本文將借用已有的二級(jí)邏輯綜合工具espresso，對(duì)布爾e導(dǎo)數(shù)及e偏導(dǎo)數(shù)的計(jì)算結(jié)果進(jìn)行邏輯簡化．

2.1 邏輯函數(shù)之間邏輯“與”運(yùn)算的實(shí)現(xiàn)

定義5若Cf和Cg分別為邏輯函數(shù)f和g所對(duì)應(yīng)的乘積項(xiàng)集合，則Cf與Cg之間的不相交運(yùn)算用Cf?Cg表示，且Cf?Cg=Cf-Cf∩Cg，符號(hào)“?”為2個(gè)邏輯函數(shù)之間的不相交運(yùn)算符．

從定義5可以看出，Cf?Cg的實(shí)質(zhì)是在Cf中除去與Cg相交的部分，因此，Cf?Cg的結(jié)果屬于Cf且不與Cg相交的部分；由此可得：Cf與Cg相交部分等于在Cf中除去與Cg不相交的部分，即邏輯函數(shù)f和g“與”的結(jié)果可表示為

Cf∩Cg=Cf?(Cf?Cg).

(8)

算法偽代碼如下：

圖1中，Cf和Cg分別包含w和v個(gè)乘積項(xiàng)，Cdis=piΘqj表示乘積項(xiàng)pi與qj之間進(jìn)行不相交銳積運(yùn)算，運(yùn)算結(jié)果寄存在Cdis中．顯然，結(jié)合圖1算法和式(8)可實(shí)現(xiàn)邏輯函數(shù)f和g之間的邏輯“與”運(yùn)算．

2.2 k階布爾e導(dǎo)數(shù)算法的實(shí)現(xiàn)

本文中，k階布爾e導(dǎo)數(shù)運(yùn)算用程序E_Derivative(Cf,L)來實(shí)現(xiàn)，其中Cf是布爾函數(shù)f轉(zhuǎn)化為不相交乘積項(xiàng)SOP形式的乘積項(xiàng)集合，L是一個(gè)鏈表，用來寄存待求導(dǎo)變量，其偽代碼如下：

圖2中，Cen和Cr_en為2個(gè)乘積項(xiàng)集合緩存，CT是運(yùn)算結(jié)果；子函數(shù)Apart(Cf,L)的功能是根據(jù)鏈表L中寄存的待求導(dǎo)變量出現(xiàn)的情況將Cf中的乘積項(xiàng)拆分成兩部分，其中集合Cdc中寄存待求導(dǎo)變量均不出現(xiàn)的乘積項(xiàng)，剩余部分寄存在集合Cen中；子函數(shù)Reverse(Cen,L)的功能是將Cen中在全部乘積項(xiàng)中出現(xiàn)的待求導(dǎo)變量取反；Cand=Cen?(Cen?Cr_en)實(shí)現(xiàn)了Cen∩Cr_en功能，即實(shí)現(xiàn)2個(gè)邏輯函數(shù)之間的邏輯“與”運(yùn)算；最后，借用espresso工具對(duì)CT進(jìn)行邏輯簡化，得到更加緊湊的邏輯表達(dá)形式．

2.3 k階布爾e偏導(dǎo)數(shù)算法的實(shí)現(xiàn)

本文k階布爾e偏導(dǎo)數(shù)運(yùn)算可用程序E_PartialDerivative(Cf,L)來實(shí)現(xiàn)，其中Apart(Cf,L)的含義同圖2，其偽代碼如下：

圖3中的Cen是乘積項(xiàng)集合緩存，CT是運(yùn)算結(jié)果；Cpar=e_Derivative(Cen,Lxi)表示對(duì)鏈表Lxi中的唯一待求偏導(dǎo)變量xi求一階布爾e導(dǎo)數(shù)，即一階布爾e偏導(dǎo)數(shù)；最后，借用espresso對(duì)CT實(shí)現(xiàn)邏輯簡化．

之后求Cen∩Cr_en，即

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

本文給出的邏輯函數(shù)高階布爾e導(dǎo)數(shù)和e偏導(dǎo)數(shù)的求解算法已經(jīng)在Windows10/CPU 2.40 GHz/ RAM 8.00 GB/VS2010環(huán)境下使用C語言編程實(shí)現(xiàn)，并利用MCNC標(biāo)準(zhǔn)測試電路進(jìn)行了實(shí)驗(yàn)驗(yàn)證．

表1給出的是k階布爾e導(dǎo)數(shù)和e偏導(dǎo)數(shù)的實(shí)驗(yàn)數(shù)據(jù)．表1中的電路f取自MCNC標(biāo)準(zhǔn)測試電路；i/o/p分別表示電路f對(duì)應(yīng)的輸入變量、輸出變量和乘積項(xiàng)的數(shù)量；階數(shù)k表示對(duì)電路f的任意k個(gè)變量求解布爾e導(dǎo)數(shù)和e偏導(dǎo)數(shù)，1≤k≤n，n為變量數(shù)；Cd表示布爾e導(dǎo)數(shù)計(jì)算結(jié)果經(jīng)espresso邏輯簡化后的乘積項(xiàng)數(shù)量；Cp表示布爾e偏導(dǎo)數(shù)計(jì)算結(jié)果經(jīng)espresso邏輯簡化后的乘積項(xiàng)數(shù)量；td表示布爾e導(dǎo)數(shù)的求解時(shí)間，單位ms；tp表示布爾e偏導(dǎo)數(shù)的求解時(shí)間，單位ms；“<1”表示求解時(shí)間小于1 ms．

表1給出了11組MCNC測試電路的實(shí)驗(yàn)數(shù)據(jù)，這些電路的變量數(shù)為7～199，其輸出和乘積項(xiàng)數(shù)均具有一定的規(guī)模；每個(gè)電路均測試了3組不同階數(shù)k的情況．從表1中可以明顯看出，算法處理時(shí)間較短，大部分都<1 ms，無超過1 s的．

如果用|Cd|和|Cp|分別表示Cd和Cp中所包含的乘積項(xiàng)數(shù)量，從表1可以看出，一般情況下|Cd|≥|CP|，其原因除了與espresso邏輯優(yōu)化有關(guān)外，還與它們的定義有關(guān)．對(duì)于邏輯函數(shù)f的k階布爾e導(dǎo)數(shù)而言，是2個(gè)邏輯函數(shù)之間的“與”運(yùn)算；但對(duì)于k階布爾e偏導(dǎo)數(shù)，則是2k個(gè)邏輯函數(shù)之間的“與”運(yùn)算；一般情況下，2k個(gè)邏輯函數(shù)之間的公共部分更少，

表1 布爾e導(dǎo)數(shù)和e偏導(dǎo)數(shù)的實(shí)驗(yàn)數(shù)據(jù)

即多次“與”運(yùn)算后對(duì)應(yīng)的乘積項(xiàng)數(shù)量更少，導(dǎo)致|Cd|≥|Cp|．

函數(shù)間不相交運(yùn)算的速度與每個(gè)函數(shù)包含的乘積項(xiàng)數(shù)量有關(guān)，待處理的邏輯函數(shù)的輸入變量數(shù)對(duì)其不敏感．有些函數(shù)適合拆分，拆分后實(shí)際參與不相交運(yùn)算的乘積項(xiàng)數(shù)量不多，因此速度快.例如電路i7、xparc．本文中邏輯函數(shù)的布爾e導(dǎo)數(shù)用不相交運(yùn)算來求解，顯然不相交運(yùn)算的調(diào)用次數(shù)將直接影響算法的速度．對(duì)于邏輯函數(shù)f的k階布爾e導(dǎo)數(shù)而言，由式(8)知，需要2次不相交運(yùn)算，但k階布爾e偏導(dǎo)數(shù)卻需要2k次不相交運(yùn)算，因此有tp≥td．

4 結(jié) 論

實(shí)現(xiàn)大函數(shù)的布爾e導(dǎo)數(shù)和e偏導(dǎo)數(shù)的求解主要由以下兩部分構(gòu)成： (1)用邏輯函數(shù)之間的不相交運(yùn)算替代．待處理的邏輯函數(shù)的輸入變量數(shù)對(duì)不相交運(yùn)算的速度不敏感，故在處理大邏輯函數(shù)時(shí)效率較高；(2)在求導(dǎo)過程中，將函數(shù)拆分成兩部分，即不包含待求導(dǎo)變量的乘積項(xiàng)集合Cdc和包含待求導(dǎo)變量的乘積項(xiàng)集合Cen．Cdc求布爾e導(dǎo)數(shù)的結(jié)果是其本身，因此，實(shí)際上只有Cen參與了求導(dǎo)過程中的不相交運(yùn)算，顯然Cen中包含的乘積項(xiàng)數(shù)量不會(huì)大于原函數(shù)，從而達(dá)到減少參與不相交運(yùn)算的乘積項(xiàng)數(shù)量的目的，提高了算法速度．實(shí)驗(yàn)表明，本文提出的方法可以快速計(jì)算輸入變量數(shù)在199內(nèi)的大函數(shù)的高階布爾e導(dǎo)數(shù)和e偏導(dǎo)數(shù)．為了簡化求導(dǎo)后的邏輯函數(shù)的表達(dá)式，算法最后借用二級(jí)邏輯綜合工具espresso，實(shí)現(xiàn)了函數(shù)的邏輯簡化．