異或門自治布爾網(wǎng)絡(luò)及物理隨機(jī)數(shù)發(fā)生器

杜海鋆，張建國，劉海芳，龔利爽，劉 鋒，王云才

1) 太原理工大學(xué)新型傳感器與智能控制教育部和山西省重點(diǎn)實(shí)驗(yàn)室, 山西太原 030024； 2) 太原理工大學(xué)物理與光電工程學(xué)院, 山西太原030024；3) 廣東工業(yè)大學(xué)信息工程學(xué)院, 廣東廣州510006

自治布爾網(wǎng)絡(luò)(autonomous Boolean network, ABN)是與離散映射布爾網(wǎng)絡(luò)相對(duì)應(yīng)的連續(xù)動(dòng)力學(xué)系統(tǒng)[1]，具有時(shí)間、空間及狀態(tài)連續(xù)性. 與同步布爾網(wǎng)絡(luò)(synchronous Boolean network, SBN)相比[2]，ABN的相空間從有限維擴(kuò)展到無限維，使其能夠產(chǎn)生更復(fù)雜的動(dòng)力學(xué)行為. 作為典型的非線性動(dòng)力學(xué)系統(tǒng)，ABN可以呈現(xiàn)周期振蕩、分岔及混沌等非線性狀態(tài). 混沌具有對(duì)初值敏感、隨機(jī)及不可預(yù)測(cè)等特性，在密碼學(xué)和物理隨機(jī)數(shù)產(chǎn)生等領(lǐng)域極具應(yīng)用前景[3-5]，激發(fā)了廣泛的研究興趣.

ROSIN等[6]首次提出基于三輸入異或門結(jié)構(gòu)的16節(jié)點(diǎn)ABN，并在現(xiàn)場(chǎng)可編程門陣列(field programmable gate array, FPGA)平臺(tái)產(chǎn)生單通道速率為100 Mbit/s、并行速率為12.8 Gbit/s的物理隨機(jī)數(shù). 在這項(xiàng)開創(chuàng)性研究的推動(dòng)下，ROSIN等[7-8]研究了ABN的受迫和集群同步等問題. 馬荔等[9-11]提出不同拓?fù)浣Y(jié)構(gòu)的ABN，并利用香農(nóng)熵、自相關(guān)性、最大李雅普諾夫指數(shù)及記憶時(shí)間等指標(biāo)分析混沌的隨機(jī)性和不可預(yù)測(cè)性. DONG等[10]研究時(shí)延參數(shù)對(duì)ABN的影響，指出時(shí)延參數(shù)的差異性是控制ABN產(chǎn)生混沌的關(guān)鍵. ROSIN等[12-13]則進(jìn)一步指出，ABN自身存在不穩(wěn)定機(jī)制，在一個(gè)拓?fù)浣Y(jié)構(gòu)固定的網(wǎng)絡(luò)中，當(dāng)節(jié)點(diǎn)數(shù)量超過閾值時(shí)，網(wǎng)絡(luò)會(huì)出現(xiàn)從周期態(tài)或穩(wěn)態(tài)到混沌態(tài)的相變. 與實(shí)驗(yàn)研究同步開展的還有ABN的理論建模工作，目前可用于ABN建模的數(shù)學(xué)方法主要有GHIL等[14-15]提出的布爾延遲方程(Boolean delay equations, BDEs)和GLASS等[16-18]提出的分段線性微分方程(piecewise-linear differential equations, PDEs). 相比于使用BDEs方程建模[19]，基于PDEs方程建立的ABN模型可以較準(zhǔn)確刻畫ABN電路中的混沌現(xiàn)象[6]，但該模型同樣存在不足，如模型未考慮節(jié)點(diǎn)的低通濾波效應(yīng)對(duì)ABN的影響，不能合理解釋ABN電路實(shí)驗(yàn)中出現(xiàn)的周期態(tài)到混沌態(tài)的相變等物理現(xiàn)象.

針對(duì)上述問題，本研究通過理論與實(shí)驗(yàn)研究一種基于二輸入異或門的18節(jié)點(diǎn)ABN. 基于PDEs，通過引入濾波系數(shù)建立該ABN的改進(jìn)數(shù)學(xué)模型，仿真分析該ABN在不同時(shí)延參數(shù)和濾波系數(shù)情況下的工作狀態(tài)(周期態(tài)和混沌態(tài))，證實(shí)濾波系數(shù)具有抑制和控制混沌產(chǎn)生的作用.采用通用的電子異或門器件實(shí)現(xiàn)ABN電路，實(shí)驗(yàn)結(jié)果與改進(jìn)數(shù)學(xué)模型的數(shù)值仿真結(jié)果基本一致，ABN電路中存在的“混沌-周期-混沌”2次相變物理現(xiàn)象，可以從改進(jìn)的ABN數(shù)學(xué)模型中得到合理解釋.實(shí)驗(yàn)還發(fā)現(xiàn)該ABN電路產(chǎn)生的混沌信號(hào)具有良好的隨機(jī)性、魯棒性及高帶寬特性[20-22]，利用其作為物理熵源可以產(chǎn)生實(shí)時(shí)速率達(dá)100 Mbit/s的高速物理隨機(jī)數(shù)序列，美國國家標(biāo)準(zhǔn)與技術(shù)研究院隨機(jī)性檢測(cè)結(jié)果表明，所產(chǎn)生隨機(jī)數(shù)具有良好的隨機(jī)統(tǒng)計(jì)特性.

1 自治布爾網(wǎng)絡(luò)

本研究設(shè)計(jì)的自治布爾網(wǎng)絡(luò)如圖1，其由18個(gè)節(jié)點(diǎn)構(gòu)成，每個(gè)節(jié)點(diǎn)有兩路輸入和兩路輸出信號(hào)，輸入信號(hào)分別來自左右兩個(gè)相鄰節(jié)點(diǎn)，輸出信號(hào)也分別傳輸至這兩個(gè)節(jié)點(diǎn). 在該ABN中，除節(jié)點(diǎn)1執(zhí)行異或非運(yùn)算(XNOR)外，其余17個(gè)節(jié)點(diǎn)(2～18)均執(zhí)行異或運(yùn)算(XOR).

使用分段線性微分方程建立該ABN網(wǎng)絡(luò)的數(shù)學(xué)模型為

圖1 布爾網(wǎng)絡(luò)示意圖Fig.1 Autonomous Boolean network structure

(1)

(2)

2 ABN數(shù)值仿真

利用4階Runge-Kytta方法[23]對(duì)系統(tǒng)方程(1)進(jìn)行數(shù)值求解，研究當(dāng)參數(shù)τi, j和τLP取不同值時(shí)，ABN的動(dòng)態(tài)變化.

當(dāng)τi, j均相等時(shí)，令τi, j=T(T為常數(shù))，然后連續(xù)改變?chǔ)覮P的取值. 仿真結(jié)果表明，當(dāng)所有傳輸延遲τi, j都相等時(shí)，無不動(dòng)點(diǎn)的ABN網(wǎng)絡(luò)將處于周期振蕩狀態(tài).

當(dāng)τi, j不相等時(shí)，令τi, j=T±ε(ε為誤差)，然后連續(xù)改變?chǔ)覮P的取值. 仿真結(jié)果表明，若忽略方程參數(shù)τLP， 則無不動(dòng)點(diǎn)的ABN網(wǎng)絡(luò)將總是處于混沌狀態(tài)；當(dāng)引入?yún)?shù)τLP， 則無不動(dòng)點(diǎn)的ABN網(wǎng)絡(luò)將處于混沌或周期狀態(tài)，表明濾波系數(shù)τLP對(duì)混沌的產(chǎn)生具有調(diào)控或抑制作用. 圖2為τLP分別取2.4、3.9及4.3 ns、τi, j=2.7 ns及ε=0.5 ns時(shí)，ABN產(chǎn)生的時(shí)序和相圖.

最大李雅普諾夫指數(shù)是衡量非線性系統(tǒng)動(dòng)力學(xué)特征的重要參數(shù)指標(biāo)[24]，可以表征系統(tǒng)在相空間中相鄰軌道收斂或發(fā)散的平均指數(shù)率，當(dāng)最大李雅普諾夫指數(shù)值小于等于0時(shí)，系統(tǒng)為周期狀態(tài)；大于0時(shí)為混沌狀態(tài)；無窮大時(shí)為噪聲狀態(tài). 本研究利用軌道跟蹤法中的小數(shù)據(jù)法[25]，計(jì)算得到圖2中時(shí)間序列的最大李雅普諾夫指數(shù)(the largest Lyapunov exponent)分別為L1=0.32 ns-1、L2=0 ns-1及L3=0.26 ns-1.

圖2 自治布爾網(wǎng)絡(luò)輸出時(shí)序和相圖Fig.2 (Color online) Autonomous Boolean network output time series and phase diagrams

3 ABN電路實(shí)驗(yàn)

ABN電路實(shí)驗(yàn)裝置如圖3，電路中的節(jié)點(diǎn)由德州儀器公司的74AUC1G86異或門芯片構(gòu)成，其工作電壓為0.8～2.7 V. ABN電路中的節(jié)點(diǎn)間傳輸延遲可以表示為τi, j=tpd+tlink(tpd為異或門傳輸延遲時(shí)間；tlink為信號(hào)在導(dǎo)線上的傳輸延遲)，由于tpd?tlink， 有τi, j≈tpd. 由芯片手冊(cè)可知，tpd的工作電壓越低，tpd值越大. 根據(jù)該特性，實(shí)驗(yàn)中可以通過改變電路的供電電壓達(dá)到調(diào)諧節(jié)點(diǎn)信號(hào)傳輸延遲τi, j的目的. 此外，雖然異或門采用相同半導(dǎo)體工藝制造，但是制造中的微小誤差無法避免，因此，在ABN電路中，節(jié)點(diǎn)間的傳輸延遲τi, j總是不相等的.

圖3 布爾網(wǎng)絡(luò)電路實(shí)物圖Fig.3 (Color online) Prototype board of Boolean circuit

圖4為供電電壓為1.255、1.310和1.800 V時(shí)，ABN電路輸出信號(hào)(節(jié)點(diǎn)2輸出)的時(shí)序、功率譜和相圖. 可見， 當(dāng)供電電壓為1.255 V時(shí)，ABN電路的輸出信號(hào)呈單倍周期振蕩，其基頻頻率為459 MHz；當(dāng)供電電壓逐漸升高至1.310 V時(shí)，相圖呈現(xiàn)出二倍周期，基頻頻率為238 MHz；進(jìn)一步調(diào)節(jié)供電電壓至1.800 V時(shí)， ABN電路輸出信號(hào)隨時(shí)間的演化變得復(fù)雜、無規(guī)則，相圖出現(xiàn)吸引子，其功率譜由離散譜轉(zhuǎn)變?yōu)檫B續(xù)譜，這是混沌信號(hào)的典型特征；該信號(hào)還具有寬頻帶特征，其-10 dB帶寬可達(dá)390 MHz.

圖4 不同供電電壓時(shí)的布爾電路輸出信號(hào)時(shí)序、功率譜及相圖Fig.4 (Color online) Time series, power spectra and phase diagrams of the output signals of Boolean circuit with different supply voltages

根據(jù)文獻(xiàn)[18]方法，分別以ABN電路供電電壓和結(jié)點(diǎn)2輸出信號(hào)的相鄰兩個(gè)上升沿之間的時(shí)間隔為參數(shù)，繪制混沌時(shí)序分岔圖，如圖5(a). 其中，點(diǎn)帶狀區(qū)域(如區(qū)域a和d)表示電路進(jìn)入混沌振蕩狀態(tài)，周期振蕩窗口(如區(qū)域b和c)則分布其間.ABN電路中低通濾波效應(yīng)的作用導(dǎo)致周期狀態(tài)的小范圍出現(xiàn)，該現(xiàn)象也與數(shù)值仿真結(jié)果相互印證，表明ABN數(shù)學(xué)模型中引入濾波系數(shù)的合理性. 此外，寬闊的點(diǎn)帶狀區(qū)域d表明該ABN在較大的供電電壓參數(shù)范圍(1.4～2.7 V)內(nèi)可以穩(wěn)定工作于混沌振蕩狀態(tài)，具有較強(qiáng)魯棒性.

圖5 布爾電路輸出信號(hào)隨供電電壓增加的變化趨勢(shì)Fig.5 Output signals of the Boolean circuit as function of the supply voltage

排序熵(permutation entropy, PE)是度量混沌信號(hào)隨機(jī)性的重要指標(biāo)[21]，定義為

(2)

其中，h(p)為排序熵；π為符號(hào)序列；pi(π)為π相對(duì)出現(xiàn)頻率；M為嵌入維度.對(duì)式(2)歸一化可得

(3)

對(duì)于給定時(shí)間序列{x1,x2,…,xi,…,xN}，N為數(shù)據(jù)長度，使用TAKENS定理將其相空間重構(gòu)為S=[xt,xt+l,…,xt+(M-1)l]， 其中，l為時(shí)間延遲. 對(duì)重構(gòu)后的序列遞增排序可得s=[xt+(r1-1)l,xt+(r2-1)l, …,xt+(rM-1)l]. 式(2)中的π為該序列被映射為所有M!種排列中的唯一順序模式，即π=(r1,r2,…,rM)，r1,r2,…,rM代表重構(gòu)分量中每個(gè)元素的序號(hào). 式(2)中的π為符號(hào)序列，則π在時(shí)間序列分析中出現(xiàn)的次數(shù)可以用f(π)表示，對(duì)應(yīng)概率為

pi(π)=f(π)/(N-(M-1)τ)

(4)

實(shí)驗(yàn)中取M=5，l=30. 圖5(c)為ABN電路在不同供電電壓下的排序熵測(cè)量結(jié)果.當(dāng)電路處于混沌狀態(tài)時(shí)，PE的值始終接近于1，表明ABN電路在較大的供電電壓參數(shù)范圍內(nèi)可以輸出的混沌信號(hào)具有良好的隨機(jī)性.

4 基于ABN的物理隨機(jī)數(shù)發(fā)生器

ABN電路輸出的混沌序列具有高帶寬、高熵值以及較強(qiáng)魯棒性的特點(diǎn)，可作為物理隨機(jī)數(shù)發(fā)生器(physical-RNG)的熵源. 本研究設(shè)計(jì)的physical-RNG如圖6，分為ABN熵源和熵提取器2部分. 熵提取器由1個(gè)3輸入XOR門和4個(gè)D觸發(fā)器構(gòu)成，其中，利用3個(gè)D觸發(fā)器實(shí)現(xiàn)對(duì)ABN熵源輸出混沌信號(hào)(節(jié)點(diǎn)1、節(jié)點(diǎn)7 和節(jié)點(diǎn)13)的采樣和量化，產(chǎn)生0、1比特隨機(jī)序列. 而后隨機(jī)序列再經(jīng)3路異或和D觸發(fā)器波形整形，進(jìn)一步降低序列中的偏差和相關(guān)性，最終產(chǎn)生高質(zhì)量的物理隨機(jī)數(shù)序列.

圖6 物理隨機(jī)數(shù)發(fā)生器Fig.6 Physical random number generator

實(shí)驗(yàn)中將D觸發(fā)器的時(shí)鐘設(shè)定為100 MHz，此時(shí)該physical-RNG實(shí)時(shí)輸出速率為100 Mbit/s的隨機(jī)數(shù)序列. 當(dāng)ABN電路供電電壓為1.8 V時(shí)，τi, j=1 ns，ε=0.4 ns，采集1 Gbit隨機(jī)數(shù)(1 000組， 每組1 Mbit)進(jìn)行美國國家標(biāo)準(zhǔn)與技術(shù)研究院NIST SP 800-22 規(guī)定的15項(xiàng)測(cè)試，顯著水平α設(shè)置為0.01，測(cè)試結(jié)果包括p值及proportion，當(dāng)p≥0.000 1, proportion≥0.980 6時(shí)，表示通過.測(cè)試結(jié)果如圖7，可見，產(chǎn)生的隨機(jī)數(shù)能通過全部測(cè)試.

圖7 NIST測(cè)試結(jié)果Fig.7 Typical results of NIST statistical test

表1是基于ABN網(wǎng)絡(luò)的物理隨機(jī)數(shù)發(fā)生器與文獻(xiàn)[6,26-28]的對(duì)比結(jié)果. 可見，本研究提出的物理隨機(jī)數(shù)發(fā)生器具有速率高和每比特消耗能量較低的特點(diǎn).

表1 本研究physical-RNG與其他文獻(xiàn)中隨機(jī)數(shù)發(fā)生器的性能比較

結(jié) 語

本文研究一種二輸入異或門的18節(jié)點(diǎn)ABN，在PDEs基礎(chǔ)上引入濾波系數(shù)建立該ABN的改進(jìn)數(shù)學(xué)模型，利用4階Runge-Kytta方法對(duì)模型進(jìn)行求解. 當(dāng)改變時(shí)延參數(shù)和濾波系數(shù)時(shí)，ABN會(huì)呈現(xiàn)周期態(tài)和混沌態(tài)，表明濾波系數(shù)具有抑制和控制混沌產(chǎn)生的作用.

實(shí)驗(yàn)采用電子器件構(gòu)建仿真模型，通過改變電路的供電電壓調(diào)節(jié)節(jié)點(diǎn)之間的傳輸延遲，從繪制的分岔圖中可以觀察到電路的混沌和周期狀態(tài)，與仿真結(jié)果一致. 李雅普諾夫指數(shù)和排序熵隨電壓變化的演變過程表明該網(wǎng)絡(luò)在寬幅工作電壓范圍內(nèi)均可以輸出隨機(jī)性良好的混沌信號(hào)，因此，使用100 MHz高頻時(shí)鐘信號(hào)對(duì)其進(jìn)行量化采樣，高速物理隨機(jī)數(shù)生成速率100 Mbit/s，國際行業(yè)標(biāo)準(zhǔn)NIST SP 800-22 測(cè)試結(jié)果表明，獲得的隨機(jī)比特序列具有良好的統(tǒng)計(jì)學(xué)特性. 以上仿真和實(shí)驗(yàn)研究完善了自治布爾網(wǎng)絡(luò)熵源結(jié)構(gòu)的理論分析，為混沌物理隨機(jī)數(shù)發(fā)生器的深入研究提供參考.