計算含無關(guān)項布爾c-導(dǎo)數(shù)的K圖方法

厲曉華， 趙建華

(1. 浙江大學(xué) 信息中心, 浙江 杭州 310027； 2. 麗水市住建局 地理信息中心， 浙江 麗水 323000)

?

計算含無關(guān)項布爾c-導(dǎo)數(shù)的K圖方法

厲曉華1， 趙建華2

(1. 浙江大學(xué) 信息中心, 浙江 杭州 310027； 2. 麗水市住建局 地理信息中心， 浙江 麗水 323000)

摘要：為簡化與-或-非代數(shù)系統(tǒng)中含無關(guān)項邏輯函數(shù)布爾c-導(dǎo)數(shù)的計算過程，從邏輯函數(shù)布爾c-導(dǎo)數(shù)的定義出發(fā)，提出了計算含無關(guān)項一階布爾c-導(dǎo)數(shù)和二階布爾c-導(dǎo)數(shù)的K圖方法．該方法通過折疊映射K圖中的填入格值，并對相應(yīng)格值進(jìn)行“或”運算以計算含無關(guān)項布爾c-導(dǎo)數(shù)．應(yīng)用實例表明，該方法直觀有效，且能直接得到布爾c-導(dǎo)數(shù)的最簡與/或式．

關(guān)鍵詞：K圖；無關(guān)項；布爾c-導(dǎo)數(shù)；邏輯函數(shù)

LI Xiaohua， ZHAO Jianhua

(1.CampusInformationCenter,ZhejiangUniversity,Hangzhou310027，China; 2.GeomaticsCenter,HousingConstructionBureau,Lishui323000,ZhejiangProvince,China)

布爾代數(shù)系統(tǒng)中存在布爾減、布爾差分、布爾e-導(dǎo)數(shù)等特殊運算[1-2]，其中布爾c-導(dǎo)數(shù)在密碼學(xué)函數(shù)構(gòu)造[3-4]、組合電路故障檢測[5]等領(lǐng)域應(yīng)用廣泛．計算布爾c-導(dǎo)數(shù)是各類應(yīng)用的基礎(chǔ)．文獻(xiàn)[6]討論了計算布爾c-導(dǎo)數(shù)的K圖和降維K圖方法，尚缺少對含任意項布爾c-導(dǎo)數(shù)計算方法的研究．本文從邏輯函數(shù)布爾c-導(dǎo)數(shù)的定義出發(fā)，提出了計算含無關(guān)項的一階布爾c-導(dǎo)數(shù)和二階布爾c-導(dǎo)數(shù)的K圖方法．應(yīng)用實例表明，該方法直觀有效，且能直接得到布爾c-導(dǎo)數(shù)的最簡與/或式．

1相關(guān)定義

當(dāng)k=2時，

定義3邏輯函數(shù)的輸入變量在某些取值下，輸出函數(shù)值可以是任意的，或者這些輸入變量的取值根本不會出現(xiàn)，其對應(yīng)的最小項稱為無關(guān)項．任一包含無關(guān)項的布爾函數(shù)表示為：

其中，∑為“或”運算，mi表示最小項，ai為最小項系數(shù)，ai∈{0,1}表示mi是否在展開中出現(xiàn)，di為無關(guān)項系數(shù)，di∈{0,1}表示mi是否為無關(guān)項．

2計算含無關(guān)項一階布爾c-導(dǎo)數(shù)的K圖方法

2.1原理

由K圖特點得到計算含無關(guān)項一階布爾c-導(dǎo)數(shù)的步驟如下：

(1)畫出邏輯函數(shù)f(x1,…,xi,…,xn)的K圖；

2.2實例

圖1　一階布爾c-導(dǎo)數(shù)的K圖計算過程Fig.1　The calculating process of the first-order c-derivative based on K-map

cf1/cx1=∑m(0,2,3,5,7,8,10,11,13,15)+

∑d(14)+∑d6(14).

化簡后得

3計算含無關(guān)項二階布爾c-導(dǎo)數(shù)的K圖方法

3.1原理

與計算含無關(guān)項一階布爾c-導(dǎo)數(shù)的K圖方法類似，計算含無關(guān)項二階布爾c-導(dǎo)數(shù)的步驟如下：

(1)畫出邏輯函數(shù)f(x1,…,xi,…,xj,…,xn)的K圖；

若變量xi、xj同為K圖的行變量或列變量，則進(jìn)行折疊映射；若一個變量為列變量，另一個為行變量，則以xi、xj軸的交點為中心進(jìn)行旋轉(zhuǎn)映射[7]．

3.2實例

圖2　邏輯函數(shù)f2(x1～x4)的K圖Fig.2　The K-map of Boolean function f2(x1～x4)

圖3　二階布爾c-導(dǎo)數(shù)的K圖計算過程Fig.3　The calculating processes of the second-order c-derivative based on K-map

∑d(14)+∑d2(14).

化簡后得

c2f2/c(x1,x2)=x3+x4.

c2f2/c(x2,x3)=∑m(0,1,3,7,9,10,11,13)+

∑d(14,15)+∑d4(14)+∑d5(15).

化簡后得

4結(jié)論

含無關(guān)項邏輯函數(shù)是布爾代數(shù)系統(tǒng)中普遍存在的一類函數(shù)，文獻(xiàn)[8]討論了含無關(guān)項邏輯函數(shù)布爾差分的圖形化算法，文獻(xiàn)[9]提出了含無關(guān)項布爾e-導(dǎo)數(shù)的新算法．本文在分析邏輯函數(shù)布爾c-導(dǎo)數(shù)定義的基礎(chǔ)上，提出了計算含無關(guān)項一階布爾c-導(dǎo)數(shù)和二階布爾c-導(dǎo)數(shù)的K圖方法，并舉例說明了計算過程．雖然文中只討論了計算含無關(guān)項一階和二階布爾c-導(dǎo)數(shù)的K圖方法，但該方法亦適用于高階布爾c-導(dǎo)數(shù)的計算．

參考文獻(xiàn)(References)：

[1]陳偕雄，沈繼忠. 近代數(shù)字理論[M]. 杭州：浙江大學(xué)出版社，2001.

CHEN Xiexiong, SHEN Jizhong. Modern Digital Thoery[M]. Hangzhou：Zhejiang University Press, 2001.

[2]溫巧燕，鈕心忻，楊義先. 現(xiàn)代密碼學(xué)中的布爾函數(shù)[M]. 北京：科學(xué)出版社，2000.WEN Qiaoyan，NIU Xinxin，YANG Yixian. Boolean Function in Modern Cryptology[M]. Beijing: Science Press, 2000.

[3]趙美玲，陳偕雄. 布爾函數(shù)的c-導(dǎo)數(shù)及其在揭示H-布爾函數(shù)性質(zhì)中的應(yīng)用[J]. 浙江大學(xué)學(xué)報：理學(xué)版，2015，42(2):153-156.ZHAO Meiling, CHEN Xiexiong. c-derivative of Boolean functions and its application in revealing the properties of H-Boolean function[J]. Journal of Zhejiang University: Science Edition, 2015, 42(2):153-156.

[4]馬汝星，陳偕雄. 布爾特殊運算c-導(dǎo)數(shù)及其在Bent函數(shù)研究中的應(yīng)用[J]. 浙江大學(xué)學(xué)報：理學(xué)版，2015,42(2): 157-161.

MA Ruxing，CHEN Xiexiong. Boolean special operation c-derivative and its application in studying Bent function[J]. Journal of Zhejiang University: Science Edition, 2015, 42(2):157-161.

[5]王芳，應(yīng)時彥，肖林榮. 布爾函數(shù)的c-導(dǎo)數(shù)及其在組合電路故障檢測中的應(yīng)用[J]. 浙江大學(xué)學(xué)報：理學(xué)版，2014, 41(2)：153-155.WANG Fang, YING Shiyan, XIAO Linrong. The c-derivative of Boolean function and its application in fault detection of combinational circuit[J]. Journal of Zhejiang University: Science Edition, 2014, 41(2):153-155.

[6]朱耀東，袁菊明，肖林榮. 邏輯函數(shù)布爾c-導(dǎo)數(shù)的圖形計算方法[J]. 浙江大學(xué)學(xué)報：理學(xué)版，2015, 42(2)：162-165.

ZHU Yaodong，YUAN Juming，XIAO Linrong. Graphic method calculating c-derivative of Boolean function[J]. Journal of Zhejiang University: Science Edition, 2015, 42(2):162-165.

[7]陳偕雄，余黨軍.數(shù)字邏輯的圖形方法[M]. 北京：機械工業(yè)出版社，2004.

CHEN Xiexiong, YU Dangjun. Digital Logic Graphic Methods[M]. Beijing: China Machine Press, 2004.

[8]王勇超，謝永凱. 含任意項邏輯函數(shù)布爾差分的圖形化算法研究[J]. 浙江大學(xué)學(xué)報：理學(xué)版，2009, 36(6)：666-669.

WANG Yongchao，XIE Yongkai. Research of map method for Boolean difference calculation in logic functions including don’t-care-terms[J]. Journal of Zhejiang University: Science Edition, 2009, 36(6):666-669.

[9]厲曉華，杭國強. 計算布爾e-導(dǎo)數(shù)的新算法[J]. 電路與系統(tǒng)學(xué)報，2012, 17(5):1-5.

LI Xiaohua, HANG Guoqiang. The new algorithm of calculating Boolean e-derivative[J]. Journal of Circuits and Systems,2012, 17(5):1-5.

The K-map method for calculating c-derivative of Boolean function with don’t-care-terms. Journal of Zhejiang University(Science Edition), 2016,43(3):307-309

Abstract:To simplify the process for calculating c-derivative of Boolean function with don’t-care-terms in the Boolean logic algebra system based on AND-OR-NOT operation, the K-map method for calculating the first and second-order c-derivative of Boolean function with don’t-care-terms is proposed according to the definition of c-derivative. The c-derivative is calculated by folding the square corresponds of the K-map, and then conducts OR operation. The application results show that the presented method is simple and convenient for operation. The simplest AND/OR expansion of c-derivative of Boolean function with don’t-care-terms can also be obtained from K-map.

Key Words:K-map； don’t-care-terms； c-derivative； logic function

中圖分類號：TP331

文獻(xiàn)標(biāo)志碼：A

文章編號：1008-9497(2016)03-307-03

作者簡介：厲曉華(1975-)，ORCID:http://orcid.org/0000-0003-2482-9000,男，高級工程師，碩士，主要從事數(shù)字電路與網(wǎng)絡(luò)信息安全研究，E-mail:xiaohua@zju.edu.cn.

基金項目：國家科技支撐計劃項目(2013BAH27F01，2013BAH27F02).

收稿日期：2015-06-18.

DOI:10.3785/j.issn.1008-9497.2016.03.010