用于对任意变量的两个布尔函数进行仿射等价的判定方法

摘要

本发明公开了一种用于对任意变量的两个布尔函数进行仿射等价的判定方法，属于数字集成电路与密码学领域，其包括以下步骤：一、确定布尔函数Fm；二、任意两个布尔函数，求出对应的变量取值矩阵；三、计算rank(Af)、rank(Ag);四、判断rank(Af)、rank(Ag)是否相等，代表元是否相同，若是f与g仿射等价；否则f与g仿射不等价。本发明可以应用到组合逻辑电路、FPGA的可编程逻辑单元和Reed-Muller码中。

说明书

技术领域

本发明属于数字集成电路与密码学领域，具体涉及一种用于对任意变量的两个布尔函数进行仿射等价的判定方法，该判定方法指出了两个布尔函数仿射等价的必要条件；以及在变量个数较小情况下，布尔函数的仿射等价类代表元的选取方式。 

背景技术

布尔函数在科学和技术的许多领域都有重要应用。仿射等价是布尔函数的一个基本等价关系，有着广泛的运用，如电路设计、密码学等领域。布尔函数的仿射等价分类在电路设计中的应用主要体现在组合逻辑电路的设计和FPGA(Filed Programmable Gate Array的缩写，即现场可编程逻辑阵列)的设计。在密码学领域，主要用在分组密码中，如S盒、Reed-Muller码等。 

在设计组合逻辑电路时，同一个仿射等价类的布尔函数可以共用一个电路。假如已经根据该等价类的代表元设计出一个电路，则其他函数只需要对输入变量做线性组合或者对其中的若干个变量取非，就可以用该电路实现该等价类中的其他布尔函数。通过这种方法可以简化电路的设计，从而提高组合电路设计的效率，此外，这种方法还可以应用到电路的等价性验证中。 

FPGA与传统的电路设计方法相比，FPGA具有功能强大，开发过程投资小，周期短，可反复编程修改，保密性能好，开发工具智能化等特点。其器件密度从数万系统门到数千万系统门不等，可以完成极其复杂的时序和组合逻辑电路功能，适用于高速、高密度的高端数字逻辑电路设计领域。FPGA由6个部分组成，分别为可编程的输入/输出单元、基本可编程逻辑单元、嵌入式RAM、丰富 的布线资源、底层嵌入功能单元和内嵌专用的硬核等构成。其中，底层嵌入功能单元和基本可编辑逻辑单元几乎都是由两种最基本的部件：触发器和查找表(LUT)组成的。其中，查找表就对应一个布尔函数的真值表。各种FPGA之所以不相同，就是因为查找表本身的结构(4输入或6输入)以及触发器和查找表组合的方式的不同。例如，Virtex-II系列的FPGA，它的片具有两个查找表和两个触发器，而Virtex-5FPGA的片具有4个查找表和4个触发器。 

我们可以对4元、6元等布尔函数进行仿射等价的讨论，对底层嵌入功能单元和基本可编程逻辑单元的查找表进等价分类，找出每个等价类的代表元。然后对每个代表元设计查找表(即：查找表所对应的逻辑电路)，而不需要对每个布尔函数设计查找表，从而简化了FPGA的底层嵌入功能单元的设计。通过可编程模块实现一系列的仿射变换，使一个基本可编程逻辑单元可以表示多种不同的功能，从而使可编程逻辑单元的功能更加丰富。 

在密码学领域，密码学界一直致力于寻找和构造具有优良密码学性质的密码函数，并为此提出了一套判定密码函数是否安全和优良的准则，以便使所构造的密码体制能抵抗不同的攻击和适应不同的需求。如：为抵抗仿射攻击，所选取的布尔函数必须有高的非线性度，布尔函数的非线性度刻划了布尔函数抵抗仿射攻击的能力，非线性度越高，抗仿射攻击的能力越强。布尔函数的相关函数也是刻划布尔函数密码性质的一个重要工具，它描述的是布尔函数的差分特性。 

由于仿射等价的布尔函数具有许多相似的密码学性质，如非线性度、差分性质等。在纠错编码领域，通过对布尔函数进行仿射等价的分类的研究，可以帮助我们寻找具有优良性质的纠错码。 

两个布尔函数称为仿射等价(Affine equivalence)：若两个布尔函数f(x)和g(x)满足：g(x)＝f(XA+b)，其中：A为二元域(F₂)上的非奇异矩阵，b是F₂上的n维向量，则称f(x)与g(x)仿射等价，(A,b)称为一个仿射变换，所有的仿射变换构成的群称为仿射群，记为AG(n,2)。 

对布尔函数仿射等价的研究目前只有对特定代数次数的布尔函数集合进行仿射分类，对这方面的研究分为两个方向，一个方向是对Reed-Muller码的陪集进行划分，另一个方向是对一类特殊的齐次旋转对称布尔函数——MRS函数进行仿射等价分类。 

第一个方向的主要研究结果有:Berlekamp和Welch对5元变量R(1,5)的陪集进行仿射划分，利用R(1,5)的两个陪集的权重分布相同，则这两个陪集仿射等价的原理，并通过笔算给出了5元Reed-Muller码陪集仿射划分的结果。通过对Reed-Muller在R(1,5)下的陪集进行划分，可以得出次数大于1的布尔函数在模R(1,5)上的仿射分类。Maiorana给出了6元Reed-Muller码陪集仿射划分的结果，其基本思想是将6元函数分为两个5元函数，然后用5阶仿射群对这些5元函数对应的Reed-Muller码陪集进行分类。 

用以上方法对布尔函数进行仿射分类存在如下缺点：首先，这种方法并没有给出对任意变量个数n，判定两个布尔函数是否仿射等价的方法。也没有给出同一类布尔函数的代表元的选取标准。其次，这种方法没有解决对任意次数的布尔函数进行仿射分类；在对Reed-Muller码陪集进行仿射分类时，其定义的等价类型是：当g(x)＝f(XA+b)mod(R(1,n))，称f(x)和g(x)仿射等价。因此，这种方法并没有求出对所有的次数大于1的布尔函数的仿射分类，只是求出了部分次数大于1的布尔函数的仿射等价分类； 

第二个方向的主要研究结果是近几年Thomas W.Cusick等人对一类特殊的函数——MRS函数分类，对2次MRS函数的研究中，主要的思想是利用等价的两个MRS函数具有相同的权重和非线性度，并得出2次MRS函数仿射等价的两个充要条件。 

用上述方法对布尔函数的仿射分类有很大的局限性，因为这种方法针对的是一类特殊的布尔函数，并且只得出了2次MRS函数仿射等价的充要条件，对3次、4次的情况，只得出了部分变量个数的布尔函数的仿射分类，没有解决对任意变量布尔函数仿射等价的判定以及代表元的选取，也没有解决对某一变量任意次数的布尔函数的仿射等价的判定以及代表元的选取。 

发明内容

针对上述现有技术，本发明的目的在于如何提供一种用于对任意变量的两个布尔函数进行仿射等价的判定方法，对任意变量个数的布尔函数判定两个布尔函数是否仿射等价，并寻找每个仿射等价类的代表元。 

为了解决上述技术问题，本发明采用如下技术方案： 

一种用于对任意变量的两个布尔函数进行仿射等价的判定方法，其特征在于，包括以下步骤： 

一、将布尔函数按照其真值表中包含不同个数1进行分类研究； 

二、对含有m个1的布尔函数，记为F_m，对使f取值为1所对应的变量取值构成F₂上的矩阵A，即：A(i)＝(x₁,x₂,…,x_n)，其中：f(x₁,x₂,…,x_n)＝1。 

三、对任意两个布尔函数f,g∈F_m，求出对应的变量取值矩阵A_f、A_g，若f与g仿射等价，则rank(A_f)＝rank(A_g)＝r；反之，若rank(A_f)≠rank(A_g)，则f与g必然仿射不等价。 

四、求出不同类布尔函数对应的变量取值矩阵A； 

五、将矩阵A进行一系列初等列变换如对列进行取非、把其中一列加到任意一列、两列之间的交换，找出该类仿射等价类的代表元。 

与现有技术相比，本发明的有益效果表现在： 

一、本发明不只是对部分的布尔函数进行仿射等价的判定，其能够对含n个变量的布尔函数全体进行仿射等价的判定，并给出了仿射等价的必要条件，用这个条件可以判定两个布尔函数是否存在仿射等价的关系； 

二、利用本发明可对变量个数较少的布尔函数，确定出仿射等价的代表元。 

三、布尔函数仿射等价的判定可以用在组合逻辑电路和FPGA的查找表中，从而减少电路设计的工作量；代表元的选取可以用在FPGA的基本逻辑单元的查找表中，丰富了FPGA的功能；用在纠错编码的选取中，通过该方法可以选出具有优良性质的纠错码。 

上述发明可以应用到组合逻辑电路、FPGA的可编程逻辑单元和Reed-Muller码中：1、用到组合逻辑电路设计中，可以简化电路的设计。2、对FPGA中底层嵌入功能单元和基本逻辑功能单元的查找表所对应的布尔函数进行仿射等价分析，可以为简化和丰富查找表的设计。3、对Reed-Muller码进行仿射等价分析，可挑选出具有良好性质的纠错码。 

附图说明

图1为判定两个布尔函数是否仿射等价的流程图； 

图2为n＝3时所有仿射等价类代表元； 

图3为n＝4，m＝7的所有仿射等价类代表元； 

图4为该方法应用到组合逻辑电路设计的流程图； 

图5为将该方法应用到FPGA可编程逻辑单元的流程图； 

图6为实施例三中的代表元r2的电路图； 

图7为实施例三中组合逻辑电路C’的示意图； 

图8为实施例四中4输入的查找表L0对应的逻辑电路。 

具体实施方式

下面将结合附图及具体实施方式对本发明作进一步的描述。 

实施例一 判定两个布尔函数是否仿射等价 

按照图1的流程，以n＝3为例，其中含有4个1的布尔函数的集合设为F₄，对F₄中的任意两个布尔函数f和g，真值表如表1所示，分别对应的变量取值矩阵如公式(1)。并把f和g简写为：f＝(0,1,1,0,1,1,0,0)，g＝(1,1,0,0,0,0,1,1)。 

表1：f和g的真值表 

X₁X₂X₃f g 0 0 0 0 1 0 0 1 1 1 0 1 0 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 1 1 0 0 1 1 1 1 0 1

$A_f=\left(\begin{array}{ccc}0& 0& 1\\ 0& 1& 0\\ 1& 0& 0\\ 1& 0& 1\end{array}\right)A_g=\left(\begin{array}{ccc}0& 0& 0\\ 0& 0& 1\\ 1& 1& 0\\ 1& 1& 1\end{array}\right)---\left(1\right)$

通过仿射变换的规则，对矩阵进行若干次列初等变换，得出rank(A_f)＝3,rank(A_g)＝2，因此f与g不是仿射等价的。 

反之，若两个函数仿射等价，则两个函数对应的变量取值矩阵的秩相等。例如：设f对应的真值表如表1，其在仿射变换(A,b)(如公式(2)所示)的作用下得到与其等价的布尔函数h，真值表如表2。h所对应的变量取值矩阵如公式(3)， 

$(A,b)=\left(\begin{array}{cc}\left(\begin{array}{ccc}0& 0& 1\\ 1& 0& 1\\ 0& 1& 0\end{array}\right),& \left(\begin{array}{ccc}1& 1& 0\end{array}\right)\end{array}\right)---\left(2\right)$

通过计算得到h＝(0,1,0,1,0,1,1,0)，其对应的真值表如表2。 

$A_h=\left(\begin{array}{ccc}0& 0& 1\\ 0& 1& 1\\ 1& 0& 1\\ 1& 1& 0\end{array}\right)---\left(3\right)$

表2:h的真值表 

X₁X₂X₃h 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0

通过验证得到：rank(A_f)＝rank(A_h)＝3。 

实施例二 选取同一个等价类的代表元 

对步骤四、五，按照图1的流程，以n＝3的情况为例，当m＝4时，选取F4中每一个仿射等价类的代表元。 

设与f同类的的布尔函数所构成的集合记为M_f，M_f中的代表元r_f选取方式如下： 

把f所对应的矩阵A_f进行一系列初等列变换，把A_f矩阵化为R_f，如公式(4)，则R_f所对应布尔函数就是这类仿射等价的布尔函数的代表元。 

$R_f=\left(\begin{array}{ccc}0& 0& 0\\ 0& 0& 1\\ 0& 1& 0\\ 1& 0& 0\end{array}\right)---\left(4\right)$

则M_f的代表元r_f＝(1,1,1,0,1,0,0,0,0)。 

g所对应的代表元可以通过类似的方法得到R_g，如公式(5)； 

$R_g=\left(\begin{array}{ccc}0& 0& 0\\ 0& 0& 1\\ 0& 1& 0\\ 0& 1& 1\end{array}\right)---\left(5\right)$

M_g所对应的代表元r_g＝(1,1,1,1,0,0,0,0)。 

用这种方法可以对少于5个变量的布尔函数，求出每个仿射等价类的代表元。详见附图2、3。 

实施例三 组合逻辑电路中的应用 

以4个变量的布尔函数为例，当m＝7时，通过上述方法确定出布尔函数的代表元如图3所示，按照图4的流程，对每个代表元ri可以设计出一个电路Ci，这里设r1＝(1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0)，r2＝(1,1,1,1,1,1,0,0,1,0,0,0,0,0,0,0)，r3＝(1,1,1,1,1,0,0,0,1,0,0,0,1,0,0,0)。这里以r2为例设计电路C如图7，根据r2的真值表化简后得到r2的CNF表达式为r2＝x1’x2’+x1’x2x3’+x1x2’x3’x4’。 

与之仿射等价的布尔函数f＝(1,1,1,1,1,0,0,0,1,1,0,0,0,0,0,0)的电路实现可以通过对输入门电路进行线性组合得到，这里f＝x1’x2’+x1x2’x3’+x1’x2x3’x4’。根据f＝r2(AX+b)得到仿射变换(A,b)公式(6)如下： 

$(A,b)=(\left(\begin{array}{cccc}0& 1& 0& 0\\ 1& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 1& 1\end{array}\right),\left(\begin{array}{c}0\\ 0\\ 0\\ 0\end{array}\right))---\left(6\right)$

那么只需要对电路C进行相应的线性组合就可以实现布尔函数f，这个线性组合如公式(7)所示： 

$\left(\begin{array}{c}y1=x2\\ y2=x1\\ y3=x3\\ y4=x3+x4\end{array}\right)---\left(7\right)$

那么实现f的组合逻辑电路C’只需要对输入变量进行如公式(7)所示的线性变换就可以得到。图7为C’的电路。 

实施例四 

Virtex-II和Spartan-3系列的FPGA芯片都是用4输入的查找表来实现真正的4输入信号的16种组合。图8就是一个4输入查找表(L0)的逻辑电路实现的例子，查找表L0对应的布尔函数为F0＝(1110000100010001)，按照图5的流程，若需要实现新的逻辑功能函数F1，需要先用上述方法判定F0是否与F1仿射等价，若判定得出F0与F1是仿射等价的，我们只需要在输入端进行编程，实现输入门的相应线性组合，然后，用这个查找表来实现F1，从而完成F1所对应的查找表的功能。 

Reed-Muller码上的应用 

利用已经得到的仿射等价类的代表元，计算每类代表元的非线性度和差分性质，选出具有好的非线性度和差分性质的那些布尔函数，用这些布尔函数构造Reed-Muller码。布尔函数的非线性度和差分性质可以通过分别计算布尔函数的Walsh谱和自相关函数得到。因此，我们只需要计算每个仿射等价类的代表元的Walsh谱和自相关函数。选出非线性度最大，差分性质最好的布尔函数作为Reed-Muller的布尔函数。