徐鋒，厲曉華

（浙江大學(xué)信息技術(shù)中心，浙江杭州310027）

旋轉(zhuǎn)對(duì)稱邏輯函數(shù)是布爾代數(shù)系統(tǒng)中的一類特殊函數(shù)[1]。該函數(shù)在密碼學(xué)函數(shù)構(gòu)造領(lǐng)域應(yīng)用廣泛[2-6]。檢測邏輯函數(shù)的旋轉(zhuǎn)對(duì)稱性是構(gòu)造非線性和高代數(shù)免疫度密碼學(xué)函數(shù)的前提和基礎(chǔ)。自文獻(xiàn)[7]提出檢測旋轉(zhuǎn)對(duì)稱邏輯函數(shù)的表格方法以來，研究人員還討論了檢測旋轉(zhuǎn)對(duì)稱邏輯函數(shù)的譜系數(shù)方法[8-9]。在布爾代數(shù)系統(tǒng)中，存在一類含無關(guān)項(xiàng)的邏輯函數(shù)，表格方法[7]和譜系數(shù)方法[8-9]不適合含無關(guān)項(xiàng)旋轉(zhuǎn)對(duì)稱邏輯函數(shù)檢測。本文在分析含無關(guān)項(xiàng)旋轉(zhuǎn)對(duì)稱邏輯函數(shù)特性的基礎(chǔ)上，提出了檢測含無關(guān)項(xiàng)旋轉(zhuǎn)對(duì)稱邏輯函數(shù)的快速算法。

1 含無關(guān)項(xiàng)邏輯函數(shù)

n變量含無關(guān)項(xiàng)邏輯函數(shù)f(x0～xn-1)的最小項(xiàng)展開式表示為[10]

di∈{0,1}為最小項(xiàng)展開式中的無關(guān)項(xiàng)系數(shù)，di=0表示mi不屬于無關(guān)項(xiàng)，di=1表示mi屬于無關(guān)項(xiàng)，di，ai不能同時(shí)為 1。

2 旋轉(zhuǎn)對(duì)稱邏輯函數(shù)性質(zhì)

定義1若xi(1≤i≤n)為邏輯變量，對(duì)任意k(1 ≤k≤n)，(xi)表示為

則邏輯函數(shù)的任意n變量(x1,x2,…,xn)可表示為

因此，即為n個(gè)變量的k次周期旋轉(zhuǎn)。

定義2若任意n變量邏輯函數(shù)f(x1～xn)，對(duì)1 ≤k≤n，有f((x1,x2,…,xn))=f(x1,x2,…,xn)，則稱函數(shù)f(x1～xn)為旋轉(zhuǎn)對(duì)稱邏輯函數(shù)。

定義3w1，w2表示n維二進(jìn)制編碼，若存在k(1 ≤k≤n-1)，滿足w2=(w1)，則w1，w2存在周期旋轉(zhuǎn)關(guān)系，旋轉(zhuǎn)編碼由滿足周期旋轉(zhuǎn)關(guān)系的編碼組成。

定義4設(shè)f(x1～xn)為任意n變量函數(shù)，當(dāng)輸入的是同一組旋轉(zhuǎn)編碼時(shí)，函數(shù)值f(x1～xn)=1，否則f(x1～xn）=0，稱f(x1～xn)為基本旋轉(zhuǎn)對(duì)稱邏輯函數(shù)，記作Tk(x1～xn)。

旋轉(zhuǎn)對(duì)稱邏輯函數(shù)具有以下性質(zhì)：

性質(zhì)1基本旋轉(zhuǎn)對(duì)稱邏輯函數(shù)組成旋轉(zhuǎn)對(duì)稱邏輯函數(shù)的基礎(chǔ)完備集，任意旋轉(zhuǎn)對(duì)稱邏輯函數(shù)由基本旋轉(zhuǎn)對(duì)稱邏輯函數(shù)的或運(yùn)算實(shí)現(xiàn)。

性質(zhì)2若f(x1～xn)為旋轉(zhuǎn)對(duì)稱邏輯函數(shù)，則滿足周期旋轉(zhuǎn)關(guān)系的最小項(xiàng)展開系數(shù)相等。以四變量邏輯函數(shù)為例，則有

性質(zhì)3若邏輯函數(shù)f(x1～xn)以1值最小項(xiàng)表示，則f(x1～xn)為旋轉(zhuǎn)對(duì)稱邏輯函數(shù)的充分必要條件為所有1值最小項(xiàng)的二進(jìn)制編碼滿足周期旋轉(zhuǎn)關(guān)系。

以f1(x1～x4)=m(1,2,4,5,7,8,10,11，13，14)為例，該邏輯函數(shù)的1值最小項(xiàng)二進(jìn)制編碼為

0001 0010 0100 1000

0101 1010

0111 1110 1101 1011

所有1值最小項(xiàng)的二進(jìn)制編碼滿足周期旋轉(zhuǎn)關(guān)系，該邏輯函數(shù)為旋轉(zhuǎn)對(duì)稱邏輯函數(shù)。

性質(zhì)4若邏輯函數(shù)f(x1～xn)含無關(guān)項(xiàng)，則f(x1～xn)為旋轉(zhuǎn)對(duì)稱邏輯函數(shù)的充分必要條件是所有1值最小項(xiàng)的二進(jìn)制編碼與相關(guān)無關(guān)項(xiàng)[10]的二進(jìn)制編碼滿足周期旋轉(zhuǎn)關(guān)系。

以f2(x1～x4)= ∑m(1,2,4,5,7,8,10,11)+∑d(12,13,14)為例，該邏輯函數(shù)的1值最小項(xiàng)二進(jìn)制編碼與相關(guān)無關(guān)項(xiàng)的二進(jìn)制編碼為

0001 0010 0100 1000

0101 1010

0111 d1110 d1101 1011

所有1值最小項(xiàng)的二進(jìn)制編碼與相關(guān)無關(guān)項(xiàng)的二進(jìn)制編碼滿足周期旋轉(zhuǎn)關(guān)系，該邏輯函數(shù)為旋轉(zhuǎn)對(duì)稱邏輯函數(shù)。

在f2中，無關(guān)項(xiàng)d13，d14為相關(guān)無關(guān)項(xiàng)，取1值，d12取0值。

3 含無關(guān)項(xiàng)旋轉(zhuǎn)對(duì)稱邏輯函數(shù)檢測算法

3.1 算法原理

根據(jù)旋轉(zhuǎn)對(duì)稱邏輯函數(shù)性質(zhì)1～性質(zhì)4，得到檢測含無關(guān)項(xiàng)旋轉(zhuǎn)對(duì)稱邏輯函數(shù)的步驟：

（1）繪制表格。將邏輯函數(shù)的1值最小項(xiàng)和無關(guān)項(xiàng)的二進(jìn)制編碼列入表格的第1列。

（2）將表格第1列第1項(xiàng)的1值最小項(xiàng)二進(jìn)制編碼進(jìn)行周期旋轉(zhuǎn)，產(chǎn)生的新編碼列于第2列。比較第2列和第1列編碼，如果第2列與第1列的二進(jìn)制編碼相同，則刪去第1列中1值最小項(xiàng)二進(jìn)制編碼的重復(fù)項(xiàng)，轉(zhuǎn)步驟（3）；如果第2列有與第1列的不同項(xiàng)，則該邏輯函數(shù)不是旋轉(zhuǎn)對(duì)稱邏輯函數(shù)。

（3）依次對(duì)第1列的其他剩余1值最小項(xiàng)重復(fù)步驟（2），若全相同，則該邏輯函數(shù)為旋轉(zhuǎn)對(duì)稱邏輯函數(shù)。

3.2 算法實(shí)例

例1f3(x1～x4)= ∑m(0,1,3,6,9,10,11)+∑d(14,15)，試檢測其旋轉(zhuǎn)對(duì)稱性。

按算法原理中的檢測步驟，先列出f3的1值最小項(xiàng)和無關(guān)項(xiàng)的二進(jìn)制編碼，如表1所示。在f3檢測表的第2列中，周期旋轉(zhuǎn)產(chǎn)生的新項(xiàng)與第1列相同，刪除第1列中的相同項(xiàng)后轉(zhuǎn)第3列。在第3列中，周期旋轉(zhuǎn)產(chǎn)生的新項(xiàng)有與第1列不相同項(xiàng)，因此，該函數(shù)不是旋轉(zhuǎn)對(duì)稱邏輯函數(shù)。

表1 f3的檢測表Table 1 The detection table off3

例2f4(x1～x4)=∑m(3,5,6,9)+∑d(10,12)，試檢測其旋轉(zhuǎn)對(duì)稱性。

按算法原理中的檢測步驟，先列出f4的1值最小項(xiàng)和無關(guān)項(xiàng)的二進(jìn)制編碼，如表2所示。在f4檢測表的第2列中，周期旋轉(zhuǎn)產(chǎn)生的新項(xiàng)均與第1列相同，刪除第1列中的相同項(xiàng)后轉(zhuǎn)第3列。在第3列中，周期旋轉(zhuǎn)產(chǎn)生的新項(xiàng)與第1列的剩余項(xiàng)都相同。第1列中的1值最小項(xiàng)全部刪除，表示1值最小項(xiàng)的二進(jìn)制編碼周期旋轉(zhuǎn)后都相同，因此，該函數(shù)是旋轉(zhuǎn)對(duì)稱邏輯函數(shù)。從表2中可以看出，無關(guān)項(xiàng)d12和d13也被刪除，表示d12=d13=1。

表2 f4的檢測表Table 2 The detection table off4

例3f5(x1～x4)=m(1,2,4,5,7,8,10,11)+∑d(12,13,14)，試檢測其旋轉(zhuǎn)對(duì)稱性。

按算法原理中的檢測步驟，先列出f5的1值最小項(xiàng)和無關(guān)項(xiàng)的二進(jìn)制編碼，如表3所示。在f5檢測表的第2列中，周期旋轉(zhuǎn)產(chǎn)生的新項(xiàng)均與第1列相同，刪除第1列中的相同項(xiàng)后轉(zhuǎn)第3列。在第3列中，周期旋轉(zhuǎn)產(chǎn)生的新項(xiàng)與第1列的剩余項(xiàng)相同，刪除第1列中的相同項(xiàng)后轉(zhuǎn)第4列。在第4列中，周期旋轉(zhuǎn)產(chǎn)生的新項(xiàng)與第1列的剩余項(xiàng)相同。第1列中的1值最小項(xiàng)均被刪除，表示1值最小項(xiàng)的二進(jìn)制編碼周期旋轉(zhuǎn)后都相同，因此，該函數(shù)是旋轉(zhuǎn)對(duì)稱邏輯函數(shù)。從表3中可以看出，無關(guān)項(xiàng)d13和d14也被刪除，表示d13=d14=1，d15未被刪除，表示d15=0。

表3 f5的檢測表Table 3 The detection table off5 x1x2x3x4

4 算法實(shí)現(xiàn)

步驟1定義二維數(shù)組y1，y2和y3。y1用于保存被檢測函數(shù)的1值二進(jìn)制編碼，y2用于保存被檢測函數(shù)的無關(guān)項(xiàng)二進(jìn)制編碼。y3用于保存1值最小項(xiàng)二進(jìn)制編碼周期旋轉(zhuǎn)后產(chǎn)生的新編碼。

以本文3.2節(jié)中的例2為例，得到的二維數(shù)組y1和y2如表4和表5所示。

表4 二維數(shù)組y1 Table 4 Representation of columns of arrayy1

表5 二維數(shù)組y2Table 5 Representation of columns of arrayy2

步驟2將二維數(shù)組y1中的第1行進(jìn)行周期旋轉(zhuǎn)，產(chǎn)生的新編碼存放于二維數(shù)組y3中。以3.2節(jié)中的例2為例，y3如表6所示。

表6 二維數(shù)組y3Table 6 Representation of columns of arrayy3

比較y3與y1中的編碼。若y3與y1中的編碼相同，則刪除y1中的相應(yīng)編碼，轉(zhuǎn)步驟3；若y3中存在不相同項(xiàng)，則將不相同項(xiàng)與y2中的編碼進(jìn)行比較，若存在不相同項(xiàng)，則該函數(shù)不是旋轉(zhuǎn)對(duì)稱邏輯函數(shù)；若全相同，則轉(zhuǎn)步驟3。

步驟3依次對(duì)二維數(shù)組y1中所有剩余的1值最小項(xiàng)二進(jìn)制編碼重復(fù)步驟2。

步驟4終止循環(huán)。

算法流程圖如圖1所示。

圖1 算法流程圖Fig.1 The flowchart of the algorithm

5 方法比較

3種檢測方法的性能比較見表7。通過以上分析含無關(guān)項(xiàng)對(duì)稱邏輯函數(shù)檢測算法的過程可知，若y2數(shù)組中無數(shù)據(jù)，則表示該邏輯函數(shù)不存在無關(guān)項(xiàng)。該算法同樣適用于對(duì)不含無關(guān)項(xiàng)的旋轉(zhuǎn)對(duì)稱邏輯函數(shù)的檢測。表格方法、譜系數(shù)方法不適合對(duì)含無關(guān)項(xiàng)邏輯函數(shù)的旋轉(zhuǎn)對(duì)稱性檢測。在譜系數(shù)方式中，計(jì)算譜系數(shù)的過程很煩瑣，一般只適合變量數(shù)小于6的邏輯函數(shù)。表格方法需不斷比較1值二進(jìn)制編碼的重復(fù)性，一般也只適合變量數(shù)小于6的邏輯函數(shù)。本算法在適合邏輯變量數(shù)、含無關(guān)項(xiàng)旋轉(zhuǎn)對(duì)稱邏輯函數(shù)檢測的適用性和檢測過程的復(fù)雜度方面均較優(yōu)。

6 結(jié) 語

通過分析含無關(guān)項(xiàng)旋轉(zhuǎn)對(duì)稱邏輯函數(shù)的特性，提出了檢測含無關(guān)項(xiàng)邏輯函數(shù)的快速算法。該算法主要用于檢測與-或-非代數(shù)系統(tǒng)中的邏輯函數(shù)，對(duì)以最大項(xiàng)展開的邏輯函數(shù)，可將最大項(xiàng)展開式轉(zhuǎn)化為最小項(xiàng)展開式，而后再進(jìn)行檢測。

表7 3種方法比較Table 7 Three methods for comparison