計算布爾函數(shù)c-導數(shù)、c-偏導數(shù)的代數(shù)方法及其在檢測特殊布爾函數(shù)中的應(yīng)用

王　芳

(浙江藝術(shù)職業(yè)學院 影視技術(shù)系, 浙江 杭州 310053)

?

計算布爾函數(shù)c-導數(shù)、c-偏導數(shù)的代數(shù)方法及其在檢測特殊布爾函數(shù)中的應(yīng)用

王芳

(浙江藝術(shù)職業(yè)學院 影視技術(shù)系, 浙江 杭州 310053)

摘要：提出了c-偏導數(shù)的定義和計算c-導數(shù)及c-偏導數(shù)的代數(shù)方法，給出了基于c-偏導數(shù)檢測冗余函數(shù)、基于c-導數(shù)檢測線性函數(shù)、基于高階c-導數(shù)檢測自反函數(shù)和自雙反函數(shù)的方法．與圖形方法相比，代數(shù)方法具有不受變量限制、簡單方便等優(yōu)點．

關(guān)鍵詞：c-導數(shù)；c-偏導數(shù)； 冗余函數(shù)； 線性函數(shù)； 自反函數(shù)； 自雙反函數(shù)

布爾函數(shù)的布爾導數(shù)、e-導數(shù)[1]和c-導數(shù)[2]能全面描述布爾函數(shù)隨變量變化的各種情況，并在探討布爾函數(shù)內(nèi)部結(jié)構(gòu)、特殊布爾函數(shù)檢測、組合電路故障檢測以及Bent函數(shù)和H布爾函數(shù)的密碼學性質(zhì)中獲得了廣泛應(yīng)用[1-6]．文獻[2]討論了基于改進分解圖計算布爾函數(shù)c-導數(shù)的方法，然而該方法受變量數(shù)的限制，不適用于變量數(shù)大于5的布爾函數(shù)．針對此問題，本文提出了計算布爾函數(shù)c-導數(shù)和c-偏導數(shù)的代數(shù)方法，并討論了其在檢測冗余函數(shù)、線性函數(shù)、自反函數(shù)和自雙反函數(shù)等特殊布爾函數(shù)中的應(yīng)用，從而克服了圖形方法受變量數(shù)限制的缺點，省卻了煩瑣的畫圖程序.

1布爾函數(shù)的c-導數(shù)、c-偏導數(shù)及高階c-導數(shù)的定義和計算方法

定義1設(shè)f(x1～xn)為n變量的布爾函數(shù)，f對于變量xi的c-導數(shù)定義為

(1)

定義2設(shè)f(x1～xn)為n變量的布爾函數(shù)，f對于變量xi1～xik的k階c-導數(shù)定義為

(2)

定義3設(shè)f(x1～xn)為n變量的布爾函數(shù)，f對于變量xi1～xik的k階c偏導數(shù)定義為

(3)

顯然，一階c-偏導數(shù)即為c-導數(shù)．根據(jù)c-偏導數(shù)的定義，基于函數(shù)最小項展開式容易得到計算f對于變量xi、xj的二階c偏導數(shù)的代數(shù)方法，具體步驟如下：

(1)寫出以二進制編碼表示最小項的f(xi1～xik)的最小項展開式;

根據(jù)上述步驟可直接寫出：

2基于c-導數(shù)和c-偏導數(shù)檢測冗余函數(shù)及線性函數(shù)的代數(shù)方法

證明充分性：

故f為冗余函數(shù)，xi、xj為冗余變量．

必要性：如f為冗余函數(shù)，xi、xj為冗余變量，

則有

故有

定理3n變量布爾函數(shù)f(x1～xn)為冗余函數(shù)的必要條件是f的1值最小項數(shù)為偶數(shù)．

例3設(shè)

試檢驗f1和f3是否為冗余函數(shù)，如是需指出冗余變量．

證明充分性：由于

例4設(shè)

試檢驗f1和f4是否為線性函數(shù)，如是需指出線性變量．

3基于c-導數(shù)和高階c-導數(shù)檢測自反函數(shù)和自雙反函數(shù)的代數(shù)方法

例5設(shè)

試檢驗f3和f5是否為部分自反函數(shù)，如是需指出部分自反變量．

因此f5滿足定理6，故f5是部分自反函數(shù)，x1～x3是部分自反變量．

例6設(shè)

試檢驗f4和f6是否為部分自雙反函數(shù)，如是需指出部分自雙反變量．

f6滿足定理8，所以f6是部分自雙反函數(shù)，x2～x4為部分自雙反變量．

4結(jié)語

提出了基于改進最小項展開式計算二階c-偏導數(shù)和高階c-導數(shù)的代數(shù)方法．文中僅給出了計算二階c-偏導數(shù)的方法，然而該方法容易推廣至任意k階c-偏導數(shù)的計算．文中還提出了分別用c-偏導數(shù)、c-導數(shù)和k階c-導數(shù)檢測冗余函數(shù)、線性函數(shù)以及自反函數(shù)和自雙反函數(shù)的方法．如果

參考文獻(References)：

[1]王芳.基于改進分解圖計算布爾函數(shù)e-導數(shù)、c-導數(shù)及布爾導數(shù)的方法[J].浙江大學學報:理學版,2015,42(3):298-302.

WANG Fang. The method of calculating e-derivative, c-derivative and Boolean derivative of Boolean functions based on improved D-map[J]. Journal of Zhejiang University: Science Edition, 2015,42(3):298-302.

[2]王芳,應(yīng)時彥,肖林榮.布爾函數(shù)的c-導數(shù)及其在組合電路故障檢測中的應(yīng)用[J].浙江大學學報:理學版,2014,41(2):153-155.

WANG Fang, YING Shiyan, XIAO Linrong. The c-derivative of Boolean functions and its application in fault detection of combinational circuits[J]. Journal of Zhejiang University: Science Edition,2014,41(2):153-155.

[3]陳偕雄,沈繼忠.近代數(shù)字理論[M].杭州:浙江大學出版社,2001.

CHEN Xiexiong, SHENG Jizhong. Modern Digital Theory[M]. Hangzhou: Zhejiang University Press,2001.

[4]LI W W, WANG Z, HUANG J L. The e-derivative of Boolean functions and its application in the fault detection and cryptographic system [J]. Keyhernetes, 2011,40(5/6):905-911.

[5]LI Weiwei, WANG Zhuo, ZHANG Zhijie. The application of derivative and e-derivative in the research on H-Boolean functions[J]. CHINA SCI-TEC,2008 (1):267-271.

[6]ZHANG Zhijie, WANG Zhuo, LI Weiwei. The application of e-derivative in studying Bent function[J]. CHINA SCI-TEC,2008(1):278-283.

WANG Fang
(DepartmentofFilmandTVTechnology,ZhejiangVocationalAcademyofArt,Hangzhou310053,China)
Algebraic method for calculating c-derivative, c-partial derivative and its application in detecting special boolean function.Journal of Zhejiang University(Science Edition), 2016,43(3):303-306

Abstract:The algebraic methods calculating c-derivative and c-partial derivative are presented . The methods for detecting redundant function based on c-partial derivative, detecting linear function based on c-derivative and detecting self-negative and self-dual function based on high-order c-derivative are given. In comparison with the graphic method, this method has several advantages such as no limitation of variable number, simplicity and so on.

Key Words:c-derivative; c-partial derivative; redundant function; linear function; self-negative function; self-dual function

中圖分類號：TP 331

文獻標志碼：A

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

作者簡介：王芳(1981-)，ORCID:http://orcid.org/0000-0002-5639-813X,女，副教授，碩士，主要從事數(shù)字電路與電子技術(shù)研究,E-mail:595297508@qq.com．

收稿日期：2015-06-29.

DOI:10.3785/j.issn.1008-9497.2016.03.009