邏輯函數高階布爾e偏導數求解算法的實現

羅文強，王倫耀，夏銀水

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

布爾導數和e導數能反映布爾函數值隨變量變化的關系，二者被廣泛應用于圖像處理[1]、邏輯電路的故障檢測[2-5]和布爾函數密碼學性質的研究[6-9]．

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

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

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

1 定 義

一個n變……