计算布尔函数c-导数、c-偏导数的代数方法及其在检测特殊布尔函数中的应用

王　芳

(浙江艺术职业学院 影视技术系, 浙江 杭州 310053)



计算布尔函数c-导数、c-偏导数的代数方法及其在检测特殊布尔函数中的应用

王芳

(浙江艺术职业学院 影视技术系, 浙江 杭州 310053)

摘要：提出了c-偏导数的定义和计算c-导数及c-偏导数的代数方法，给出了基于c-偏导数检测冗余函数、基于c-导数检测线性函数、基于高阶c-导数检测自反函数和自双反函数的方法．与图形方法相比，代数方法具有不受变量限制、简单方便等优点．

关键词：c-导数；c-偏导数； 冗余函数； 线性函数； 自反函数； 自双反函数

布尔函数的布尔导数、e-导数[1]和c-导数[2]能全面描述布尔函数随变量变化的各种情况，并在探讨布尔函数内部结构、特殊布尔函数检测、组合电路故障检测以及Bent函数和H布尔函数的密码学性质中获得了广泛应用[1-6]．文献[2]讨论了基于改进分解图计算布尔函数c-导数的方法，然而该方法受变量数的限制，不适用于变量数大于5的布尔函数．针对此问题，本文提出了计算布尔函数c-导数和c-偏导数的代数方法，并讨论了其在检测冗余函数、线性函数、自反函数和自双反函数等特殊布尔函数中的应用，从而克服了图形方法受变量数限制的缺点，省却了烦琐的画图程序.

1布尔函数的c-导数、c-偏导数及高阶c-导数的定义和计算方法

定义1设f(x1～xn)为n变量的布尔函数，f对于变量xi的c-导数定义为

(1)

定义2设f(x1～xn)为n变量的布尔函数，f对于变量xi1～xik的k阶c-导数定义为

(2)

定义3设f(x1～xn)为n变量的布尔函数，f对于变量xi1～xik的k阶c偏导数定义为

(3)

显然，一阶c-偏导数即为c-导数．根据c-偏导数的定义，基于函数最小项展开式容易得到计算f对于变量xi、xj的二阶c偏导数的代数方法，具体步骤如下：

(1)写出以二进制编码表示最小项的f(xi1～xik)的最小项展开式;

根据上述步骤可直接写出：

2基于c-导数和c-偏导数检测冗余函数及线性函数的代数方法

证明充分性：

故f为冗余函数，xi、xj为冗余变量．

必要性：如f为冗余函数，xi、xj为冗余变量，

则有

故有

定理3n变量布尔函数f(x1～xn)为冗余函数的必要条件是f的1值最小项数为偶数．

例3设

试检验f1和f3是否为冗余函数，如是需指出冗余变量．

证明充分性：由于

例4设

试检验f1和f4是否为线性函数，如是需指出线性变量．

3基于c-导数和高阶c-导数检测自反函数和自双反函数的代数方法

例5设

试检验f3和f5是否为部分自反函数，如是需指出部分自反变量．

因此f5满足定理6，故f5是部分自反函数，x1～x3是部分自反变量．

例6设

试检验f4和f6是否为部分自双反函数，如是需指出部分自双反变量．

f6满足定理8，所以f6是部分自双反函数，x2～x4为部分自双反变量．

4结语

提出了基于改进最小项展开式计算二阶c-偏导数和高阶c-导数的代数方法．文中仅给出了计算二阶c-偏导数的方法，然而该方法容易推广至任意k阶c-偏导数的计算．文中还提出了分别用c-偏导数、c-导数和k阶c-导数检测冗余函数、线性函数以及自反函数和自双反函数的方法．如果

参考文献(References)：

[1]王芳.基于改进分解图计算布尔函数e-导数、c-导数及布尔导数的方法[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]王芳,应时彦,肖林荣.布尔函数的c-导数及其在组合电路故障检测中的应用[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]陈偕雄,沈继忠.近代数字理论[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,女，副教授，硕士，主要从事数字电路与电子技术研究,E-mail:595297508@qq.com．

收稿日期：2015-06-29.

DOI:10.3785/j.issn.1008-9497.2016.03.009