廖志雄，尚文祥，王士斌

(1. 河南科技學(xué)院新科學(xué)院，河南 新鄉(xiāng) 453000；2. 河南師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院，河南 新鄉(xiāng) 453000)

1 引言

通過檢測網(wǎng)絡(luò)用戶的軌跡數(shù)據(jù)，可以發(fā)現(xiàn)用戶流量中的規(guī)則，甚至挖掘潛在的、有意義的路徑序列，這是構(gòu)建網(wǎng)絡(luò)用戶軌跡序列模型的基礎(chǔ)。算領(lǐng)域中線性函數(shù)、冗余函數(shù)、自反函數(shù)和自雙反函數(shù)是特殊的邏輯函數(shù)，被廣泛應(yīng)用于邏輯功能分類、邏輯電路分析、設(shè)計(jì)和錯(cuò)誤檢測中，同時(shí)也是邏輯函數(shù)研究中一個(gè)重要的研究課題之一。

于鵬[1]應(yīng)用模糊集截集的方法，獲得最小項(xiàng)表達(dá)式，利用模糊集間的標(biāo)準(zhǔn)Hammin距離，定義了公式間的Hamming距離，邏輯函數(shù)最小項(xiàng)表達(dá)式和真值表及卡諾圖的對(duì)應(yīng)關(guān)系，揭示了邏輯函數(shù)各種表示方法的內(nèi)在聯(lián)系，從而給出了計(jì)量邏輯學(xué)基本概念的Hamming距離表示方法。邵梁[2]從冗余函數(shù)，線性函數(shù)，自反函數(shù)，自雙反函數(shù)四類特殊布爾函數(shù)出發(fā)，討論得出檢測含無關(guān)項(xiàng)特殊布爾函數(shù)的表格算法。應(yīng)用表格列出布爾函數(shù)1值最小項(xiàng)及無關(guān)項(xiàng)的二進(jìn)制編碼，取反1值最小項(xiàng)及無關(guān)項(xiàng)二進(jìn)制編碼中的相應(yīng)位產(chǎn)生新項(xiàng)。通過比較新項(xiàng)與原最小項(xiàng)之間的異同實(shí)現(xiàn)特殊布爾函數(shù)的檢測。孔德江等[3]提出時(shí)空嵌入式長短時(shí)記憶生成模型，利用時(shí)空信息引導(dǎo)LSTM訓(xùn)練門機(jī)制，致力于實(shí)時(shí)軌跡預(yù)測，利用時(shí)空信息增強(qiáng)判別真?zhèn)卧L問序列的能力，得到更好的用戶軌跡預(yù)測效果。

雖然上述方法可以有效檢測出特殊函數(shù)，但由于在確定函數(shù)取值時(shí)，都需要大量的計(jì)算，并且無法有效對(duì)含有任意項(xiàng)的特殊邏輯函數(shù)進(jìn)行檢測?；诖耍岢鰰r(shí)空嵌入式生成對(duì)抗網(wǎng)絡(luò)特殊邏輯函數(shù)檢測，關(guān)鍵在于分析生成式模型的特征，運(yùn)用分解圖方法對(duì)四種特殊邏輯函數(shù)檢測，并在二叉樹法映射下再利用分解圖進(jìn)行檢測含任意項(xiàng)的特殊邏輯函數(shù)，實(shí)現(xiàn)最終目的。

2 嵌入式生成對(duì)抗網(wǎng)絡(luò)分析

由于變分方法的局限性，GAN(Generative adversarial networks，生成式對(duì)抗網(wǎng)絡(luò))模擬的概率分布必然存在偏差，但GAN本身并不存在這個(gè)問題。理論上，GAN框架可以訓(xùn)練任意一個(gè)生成網(wǎng)絡(luò)，但是其它大多數(shù)框架都需要生成器，使其具有一些特定的函數(shù)形式，進(jìn)而使所有的發(fā)生器和鑒別器都能正常工作，因此，本文采用GAN框架為檢測框架。

3 分解圖下特殊邏輯函數(shù)檢測

3.1 分解圖

在邏輯分析和設(shè)計(jì)中，最常用的圖形工具是卡諾圖，或滾動(dòng)條中的K圖[4-5]。

本文研究故障圖在線性函數(shù)、超額函數(shù)、反應(yīng)函數(shù)和自動(dòng)雙反函數(shù)檢測中的應(yīng)用。對(duì)于n變量函數(shù)要畫2n方格的圖，為了避免繁瑣的繪圖工作，圖1中只標(biāo)注了跳閘變量，并分別標(biāo)注了4個(gè)變量的邏輯函數(shù)，以x1，x2，x3，x4為行變量的簡化分解圖如圖1(a)～(d)所示，圖中十進(jìn)制數(shù)字為最小項(xiàng)展開系數(shù)cj的角標(biāo)j。

圖1 行變量為單變量的4變量函數(shù)分解圖

3.2 分解圖下線性函數(shù)與冗余函數(shù)檢測

定義1：如果n變量邏輯函數(shù)f(x1～xn)滿足f(x1…xi…xn)=f(x1…xi…xn)，則稱函數(shù)f為冗余函數(shù)，變量xi為冗余變量[6-7]。

定義2：如果n變量邏輯函數(shù)f(x1～xn)滿足f(x1…xi…xn)=f(x1…xi…xn)，則稱函數(shù)f為線性函數(shù)，變量xi為線性變量[8]。

根據(jù)上述定義和單行變量分解圖的特點(diǎn)，證得以下定理。

定理1：n變量邏輯函數(shù)f(x1～xn)為冗余函數(shù)，xi為冗余變量的充分必要條件是以xi為行變量的f分解圖中各列最小項(xiàng)之異或均為0。

定理2：n變量邏輯函數(shù)f(x1～xn)為線性函數(shù)，xi為線性變量的充分必要條件是以xi為行變量的f分解圖中各列最小項(xiàng)之異或均為1。

根據(jù)上述結(jié)論，可以得到由分解圖檢測到的一個(gè)多余函數(shù)和一個(gè)線性函數(shù)：

1)應(yīng)完成將每個(gè)變量作為變量線的簡化分解圖。

2)如果一個(gè)簡化的線變量分配方案中至少有一個(gè)變量且沒有涉及任何元素，則該變量為冗余變量；如果至少有一個(gè)變量，且簡化進(jìn)度表中不包含任何項(xiàng)目，如果存在，則為冗余變量函數(shù)；至少有一個(gè)變量和簡化分布圖不包括相應(yīng)的元素，如果結(jié)果是線性函數(shù)和線性變量，則結(jié)果是多余的；否則就不是多余函數(shù)或線性函數(shù)[9]。

下列本文將利用上述兩個(gè)特殊函數(shù)進(jìn)行舉例說明，并根據(jù)其計(jì)算結(jié)果，

例1：

假設(shè)：

f1(x1～x4)=∑m(2，3，4，5，6，9，11，12)+∑d(13，14，15)，試用分解圖檢測該函數(shù)是否為線性函數(shù)和冗余函數(shù)。將f1填入各簡化分解圖，分別如圖2(a)～(d)所示，由圖2可見，該函數(shù)為非線性函數(shù)或冗余函數(shù)[10]。

圖2 f1以各變量為行變量的簡化分解圖

例2：

如果令

f2(x1～x4)=∑m(1，2，4，5，9，10，12，13)+∑d(14，15)，試用分解圖檢測該函數(shù)是否為線性函數(shù)和冗余函數(shù)。將f2填入各簡化分解圖，分別如圖3(a)～(d)所示。

圖3 f2以各變量為行變量的簡化分解圖

根據(jù)定理1，當(dāng)d14=d15=0時(shí)，x1為冗余變量，f2為冗余函數(shù)，根據(jù)定理3，當(dāng)d14=d15=0時(shí)x3為線性變量，f2為線性函數(shù)[11]。

3.3 分解圖下自反函數(shù)和自雙反函數(shù)檢測

定義3：設(shè)f(x1～xn)為n變量邏輯函數(shù)，如果滿足f(x1～xn)=f(x1～xn)，則稱函數(shù)f為自反函數(shù)，記作fSN(x1～xn)。

定義4：設(shè)f(x1～xn)為n變量邏輯函數(shù)，如果滿足f(x1～xn)=f(x1～xn)，則稱函數(shù)f為自雙反函數(shù)，記作fSD(x1～xn)。

定義5：在以變量xi為行變量的函數(shù)f的簡化分解圖中，將下面一行元素倒置的分解圖稱為單變量倒置分解圖。

以4變量函數(shù)為例，它以各變量為行變量的單變量倒置分解圖分別如圖4(a)～(d)所示。

圖4 變量函數(shù)的單變量倒置分解圖

從圖4的每一列的分解圖中可以看出，每一列的分解是每一列的小數(shù)之和。根據(jù)逆分解圖的特點(diǎn)和自二重逆函數(shù)和自反函數(shù)的定義，可以證明如下定理：

定理3：n變量邏輯函數(shù)f(x1～xn)是自反函數(shù)的充要條件是f任何單變量逆分解圖的異或?yàn)榱鉡12]。

定理4：n變量邏輯函數(shù)f(x1-xn)是自雙逆函數(shù)的一個(gè)充要條件是f任何單變量逆分解圖的列異或?yàn)?。

根據(jù)上述定理，可以給出反分解圖用于自反函數(shù)和自雙反函數(shù)的具體步驟如下：

1)f作為x1行變量填入倒分解圖中；

2)如果每列的異或結(jié)果為0，則為自反函數(shù)；如果每列的異或結(jié)果為1，則f為自雙折射函數(shù)；否則f既不是自反函數(shù)，也不是自雙折射函數(shù)。

4 分解圖下含任意項(xiàng)特殊邏輯函數(shù)檢測

任意項(xiàng)特殊邏輯函數(shù)與普通特殊邏輯函數(shù)不同，它不具備規(guī)則可言，只能通過映射轉(zhuǎn)變進(jìn)行尋找。為了加強(qiáng)分解圖檢測能力，本文引入二叉樹映射變換方法，一方面可以提高對(duì)特定邏輯函數(shù)檢測的理論研究，另一方面提供了一種檢測具有任意項(xiàng)的特定邏輯函數(shù)的計(jì)算機(jī)編程方法。

根據(jù)上述特殊邏輯函數(shù)系數(shù)性質(zhì)研究得知，運(yùn)用二叉樹圖像化后，再利用分解圖實(shí)現(xiàn)對(duì)含任意項(xiàng)邏輯函數(shù)進(jìn)行檢測，其中檢測過程如下所示：

1)首先選取出一個(gè)函數(shù)變量xi，然后將其設(shè)置為根節(jié)點(diǎn)，通過函數(shù)自變量xi下標(biāo)順序，對(duì)自變量的不同取值結(jié)果進(jìn)行展開樹形結(jié)構(gòu)，持續(xù)到每個(gè)自變量都被處理過，這樣即可在樹葉節(jié)點(diǎn)處標(biāo)出對(duì)應(yīng)的最小項(xiàng)值，實(shí)現(xiàn)分解圖下最小項(xiàng)二叉樹函數(shù)。

2)根據(jù)最小項(xiàng)二叉樹函數(shù)，對(duì)二叉樹進(jìn)行對(duì)稱處理。根據(jù)計(jì)算結(jié)果，如果褶皺的兩側(cè)完全重疊，或者某些葉節(jié)點(diǎn)可能不重合，但至少有一個(gè)葉節(jié)點(diǎn)被任意移除，則該函數(shù)為每個(gè)日期的反射函數(shù)。

3)為樹深度分支的每個(gè)級(jí)別節(jié)點(diǎn)繪制中心軸。任何給定分支深度節(jié)點(diǎn)的左、右細(xì)中心軸都是背景。如果對(duì)應(yīng)的葉節(jié)點(diǎn)在翻譯后重疊，或者某些葉節(jié)點(diǎn)可能不重疊，但至少給定的子類型文本節(jié)點(diǎn)是任意值，

4)對(duì)應(yīng)樹的葉節(jié)點(diǎn)在節(jié)點(diǎn)與根節(jié)點(diǎn)之間的路徑(即路徑中的右分支數(shù))中標(biāo)記為1，并遍歷具有相同分支數(shù)的葉節(jié)點(diǎn)。如果這些節(jié)點(diǎn)函數(shù)的最小值完全相等或包含任何項(xiàng)，則稱它們?yōu)榫哂腥我忭?xiàng)的對(duì)稱函數(shù)，否則稱為非對(duì)稱函數(shù)。

5 仿真研究

本文以NS2為仿真平臺(tái)，并以MICA2傳感器節(jié)點(diǎn)的實(shí)際指標(biāo)取值為參考，為了進(jìn)一步驗(yàn)證所提算法的有效性，將根據(jù)分析結(jié)果對(duì)該算法的檢測效率以及精準(zhǔn)度進(jìn)行檢測，并從嵌入式生成對(duì)抗網(wǎng)絡(luò)傳輸節(jié)點(diǎn)的吞吐量方法對(duì)所提算法進(jìn)行分析。實(shí)驗(yàn)參數(shù)如表1所示：

表1 仿真參數(shù)設(shè)置

在實(shí)際仿真中，將本文方法與文獻(xiàn)方法[1]、[2]進(jìn)行對(duì)比，其中對(duì)比結(jié)果圖如圖5所示：

圖5 特殊邏輯函數(shù)檢測效率對(duì)比圖

從圖4可知，在檢測效率方面，所提算法具有明顯的優(yōu)勢，因?yàn)樗岱椒ㄍㄟ^觀察樣本和數(shù)據(jù)標(biāo)簽的聯(lián)合概率分布來獲取訓(xùn)練模型，該模型捕獲數(shù)據(jù)的高階相關(guān)性，而不需要目標(biāo)類的標(biāo)簽信息。而其它文獻(xiàn)方法雖然能夠檢測出特殊邏輯函數(shù)，但是需要分別對(duì)特殊邏輯函數(shù)進(jìn)行判別，所以檢測不出含任意項(xiàng)函數(shù)，檢測效率不高。

由于特殊邏輯函數(shù)可以有效減少生成對(duì)抗網(wǎng)絡(luò)的設(shè)計(jì)步驟，并具有簡化用戶數(shù)據(jù)的作用，所以在對(duì)其檢測過程中會(huì)要求一定的檢測精準(zhǔn)度，此處將對(duì)檢測精準(zhǔn)度進(jìn)行對(duì)比，如圖6所示。

圖6 檢測精準(zhǔn)度對(duì)比圖

根據(jù)圖6所呈現(xiàn)的曲線圖即可看出，所提算法精準(zhǔn)度呈緩慢下降趨勢，而文獻(xiàn)算法則是較為明顯的下降，也就間接說明了所提算法的優(yōu)勢，這是因?yàn)樗运惴ㄍㄟ^二叉樹映射變換檢測含任意項(xiàng)的特殊邏輯函數(shù)，分析了自反函數(shù)的充要條件，有效提高檢測精準(zhǔn)度，最高可達(dá)92.5%。

在不同類型的函數(shù)檢測數(shù)據(jù)中，三個(gè)方法的數(shù)據(jù)融合時(shí)間都隨著數(shù)據(jù)檢測數(shù)量的增加而增大，這很可能是網(wǎng)絡(luò)吞吐量過大造成的網(wǎng)絡(luò)時(shí)延，為此，驗(yàn)證不同方法的網(wǎng)絡(luò)傳輸節(jié)點(diǎn)的實(shí)際吞吐量，對(duì)比結(jié)果如圖7所示。

圖7 三種方法網(wǎng)絡(luò)傳輸節(jié)點(diǎn)實(shí)際吞吐量對(duì)比圖

由圖7可知，隨著數(shù)據(jù)容量的增長，三種方法的逐漸趨于線性，對(duì)比三種方法發(fā)現(xiàn)本文方法的節(jié)點(diǎn)間融合時(shí)間更少，說明吞吐量較小，對(duì)樹葉節(jié)點(diǎn)的處理效果更好。

6 結(jié)論

1)在定義特殊函數(shù)和分解圖的基礎(chǔ)上，所提方法推導(dǎo)了冗余函數(shù)、線性函數(shù)、對(duì)稱函數(shù)、反射函數(shù)和自乘反演的相關(guān)理論，定義了允許通過計(jì)算機(jī)編程從任意項(xiàng)中檢測出特殊的邏輯函數(shù)。

2)在具有任意截止期的特定函數(shù)檢測中，研究了時(shí)間表映射理論的應(yīng)用，隨著實(shí)驗(yàn)次數(shù)的增加，盡管檢測時(shí)間處于上升狀態(tài)，但是整體試件一直保持在4-6s。

3)提出分解圖下特殊邏輯函數(shù)檢測，從任意項(xiàng)中檢測不必要函數(shù)、線性函數(shù)、對(duì)稱函數(shù)、反應(yīng)函數(shù)和自動(dòng)二次反演的方法，其檢測精準(zhǔn)度得到題提高，最高可達(dá)92.5%，且實(shí)際應(yīng)用過程簡單明了，可用于多種變量。