龍德浩,陳志清

(1.四川大學(xué),成都 610064;2.成都大學(xué),成都 610106)

1 引 言

1963年,Lorenz在研究天氣預(yù)報(bào)方程時(shí)發(fā)現(xiàn)了混沌現(xiàn)象。隨后,混沌算法以其獨(dú)特的初值敏感性深深地吸引著一代又一代學(xué)者,直到今天。因?yàn)槌踔得舾行陨婕暗拿孑^寬,涵蓋自然、政治、經(jīng)濟(jì)等學(xué)科領(lǐng)域。就抗干擾而言,初值敏感性強(qiáng)意味著能同時(shí)提高定位系統(tǒng)的速度分辯能力和距離分辯能力;能有效抑制擴(kuò)頻通信的地址干擾和人為相關(guān)干擾;對(duì)信息安全而言,是反“相關(guān)分析”、反密碼丟失的根本方法;對(duì)弱信號(hào)接收,例如無(wú)線探礦、深空通信等,是一條全新的數(shù)字編碼思路。因此,人們希望找到一種新的編碼方法,它既具有經(jīng)典混沌算法獨(dú)特的初值敏感性,又能克服經(jīng)典混沌算法難以克服的“同步難”問題。到如今,混沌理論經(jīng)歷了上世紀(jì)70年代的“機(jī)理”、80年代的“建模”、90年代及其隨后的“應(yīng)用”研究,已逐步邁向應(yīng)用,特別是變初值變結(jié)構(gòu)(VIVS)準(zhǔn)混沌算法[1-4]克服了經(jīng)典混沌算法的“同步難”問題。至于初值敏感性,不同領(lǐng)域、不同學(xué)者,其理解是不盡相同的。催化化學(xué)家把它理解為“催化劑”,只需添加極少量的“催化劑”,即可使化學(xué)反應(yīng)的速率提高百倍、千倍、萬(wàn)倍……就通信而言,我們把它理解為:任意鄰近的初值產(chǎn)生的0/1混沌序列都是彼此無(wú)關(guān)的,進(jìn)而是統(tǒng)計(jì)獨(dú)立的。然而,在用數(shù)學(xué)語(yǔ)言表達(dá)此定義時(shí),卻遇到了互相關(guān)函數(shù)絕對(duì)極大值的“統(tǒng)計(jì)分布難”問題。盡管極值分布理論在上世紀(jì)60年代早有定論,但由經(jīng)典的3種分布類型[5]所導(dǎo)出的結(jié)果,偏離物理概念較遠(yuǎn)。不得已我們擬議了“雙序列平面圖解法”,這種方法簡(jiǎn)單、直觀,但只能定性[6]。定性檢驗(yàn)結(jié)果表明,VIVS編碼算法具有初值敏感性,故簡(jiǎn)記為VIVS準(zhǔn)混沌算法。如何定量地檢驗(yàn)編碼(含混沌)算法的初值敏感性呢?工程應(yīng)用專家很關(guān)心這個(gè)問題。然而,近半世紀(jì)過(guò)去了,至今仍未解決。筆者近兩年基于Г л й в е н к о極限定理[7],再次探討了通用編碼算法的初值敏感性檢驗(yàn)方法,旨在拋磚引玉。

2 通用編碼算法的初值敏感性檢驗(yàn)方法

2.1 初值敏感性檢驗(yàn)方法的定義

我們擬議的初值敏感性檢驗(yàn)方法的定義包含5個(gè)步驟。

(1)首先,給定任意鄰近初值矩陣

共計(jì)m+1行,v列。其中,ii,j(i=1,2,…,m+1;j=1,2,…,v)的取值決定于被檢編碼算法所采用的數(shù)制。但無(wú)論哪種數(shù)制,任意相鄰兩行的數(shù)值都必須盡量接近,例如,彼此相鄰1 bit。而后把這組初值I逐行代入待檢編碼算法,從而生成待檢數(shù)據(jù)矩陣

共計(jì) m+1行,n 列。其中,ai,j=′0′或′1′;i=1,2,…,m+1;j=1,2,…,n。n=2 000～3 000,不宜太長(zhǎng),因?yàn)槌踔得舾行钥偸前l(fā)生在啟動(dòng)編碼算法的初始階段;但也不能太短,否則無(wú)法檢驗(yàn)到某些算法存在的初值敏感性的過(guò)渡過(guò)程。m=2 000～8 000,旨在使所求的經(jīng)驗(yàn)分布更接近于母體的理想概率分布。

(2)求出矩陣J中任意一行,例如第i行的自相關(guān)函數(shù),而后除以序列的長(zhǎng)度n,即得歸一化自相關(guān)函數(shù)矢量b11。

(3)依次求出矩陣J中相鄰兩行的互相關(guān)函數(shù)

共計(jì)m行,n列。

(4)將C以“同一 n”標(biāo)準(zhǔn)化之,即得標(biāo)準(zhǔn)化互相關(guān)函數(shù)矩陣

而后取絕對(duì)值,再取極大值,即得R的絕對(duì)極大值矢量

并稱之為待檢編碼算法的“初值敏感性檢驗(yàn)樣本”,記為 b12。這樣,一切可能 b12的總體,就是初值敏感性檢驗(yàn)的樣本空間 Ψ;當(dāng)I給定時(shí),b12即為總體Ψ的一組觀測(cè)值。因?yàn)閎12是一個(gè)絕對(duì)極大值向量,故本文提出的初值敏感性檢驗(yàn)方法實(shí)質(zhì)上屬于極大值檢驗(yàn)范疇。鑒于此,初值敏感性檢驗(yàn)的首要任務(wù)就是求“b12不大于預(yù)先給定的門限值th”這一事件的概率。為此,必須先求出總體 Ψ的概率分布。

(5)由 Г л й в е н к о極限定理得知 :當(dāng) m 很大時(shí) ,總體 Ψ觀測(cè)值b12的經(jīng)驗(yàn)分布,就是母體 Ψ的良好的近似概率分布。這樣,有了母體 Ψ的概率分布,即可求出上述“事件”的概率及其相關(guān)參數(shù)。

2.2 初值敏感性檢驗(yàn)步驟

這個(gè)“檢驗(yàn)步驟”實(shí)質(zhì)上是編寫“通用編碼算法初值敏感性檢驗(yàn)程序”的流程圖。

第一,依照2.1節(jié),求初值敏感性檢驗(yàn)的觀測(cè)值矢量 b12;第二,求 b12的升序結(jié)構(gòu);第三,求初值敏感性檢驗(yàn)樣本空間 Ψ的概率分布;第四,求b12不大于門限值th的概率;第五,求 b12大于門限值 th的概率;第六,求門限值 th在b12升序結(jié)構(gòu)中的位置;第七,求 b12中任意一點(diǎn),例如極大值、中位置等的概率;第八,求 b12的極大值;第九,求 b12的樣本平均值;第十,求 b12的統(tǒng)計(jì)平均值;第十一,求b12的樣本標(biāo)準(zhǔn)差;第十二,求b12的統(tǒng)計(jì)標(biāo)準(zhǔn)差。

2.3 初值敏感性檢驗(yàn)的判決準(zhǔn)則

設(shè)門限值 th=0.1000∈b12。如果觀測(cè)值 b12不大于門限值th的概率為

或 其“補(bǔ)”概率為

則產(chǎn)生此被檢序列的編碼算法具有初值敏感性;反之亦然。

3 通用編碼算法初值敏感性檢驗(yàn)文件

按照第2.2節(jié)的“檢驗(yàn)步驟”,逐一寫出“通用編碼算法初值敏感性檢驗(yàn)”文件

的參數(shù):主文件名:dh-nist-Lsinitsensibility31,計(jì)算機(jī)語(yǔ)言:matlab;輸入矩陣的行數(shù):N-pattern,2 000～8 000;調(diào)用子函數(shù)的符號(hào):F,matlab語(yǔ)言調(diào)用自編功能函數(shù)的符號(hào);輸入數(shù)據(jù)文件名:c3.mat,一切符合式(1)和式(2)要求的matlab(0,1)數(shù)據(jù)文件;輸入矩陣的列數(shù):n,2 000～3 000;最大相關(guān)時(shí)間:k,k=n,2 000～3 000;任意指定的數(shù)值:n1,n1∈b12,檢驗(yàn)者感興趣的數(shù)值,例如中位數(shù)、極大值、極小值等;初值敏感性門限值:th∈b12,隨工程要求而定,本例th=0.1000;反饋矢量和頻率:[g,ni],ni為所求的b12的密度函數(shù),g為所求的功能參數(shù)矢量。

4 VIVS準(zhǔn)混沌算法初值敏感性檢驗(yàn)

(1)調(diào)用初值敏感性檢驗(yàn)通用文件

(2)VIVS-c6001.b12樣本觀測(cè)值的數(shù)據(jù)結(jié)構(gòu)

被檢母體 Ψ的本次觀測(cè)值VIVS-c6001.b12的數(shù)據(jù)結(jié)構(gòu)(參見2.2節(jié)的檢驗(yàn)步驟)為

其圖像如圖1所示。

圖1 彼此相鄰1 bit的VIVS-c6001.b12的升序圖Fig.1 Sorting chart of VIVS-c6001.b12 adjacent to each other 1 bit

由圖1可知,VIVS準(zhǔn)混沌算法的互相關(guān)函數(shù)的絕對(duì)極大值共計(jì)2 000個(gè),最大值劣于0.12,即互相關(guān)系數(shù)較小。

(3)VIVS-c6001.b12母體 Ψ的概率密度函數(shù)(數(shù)字式)及其參數(shù)[g,ni]

母體 Ψ的觀測(cè)值VIVS-c6001.b12的經(jīng)驗(yàn)分布函數(shù)(見2.2節(jié)的檢驗(yàn)步驟)為

其圖像如圖2所示。

圖2 彼此相鄰1 bit的VIVS-c6001.ni概率密度Fig.2 Probability density of VIVS-c6001.ni adjacent to each other 1 bit

由 Г л й в е н к о極限定理得知 ,因?yàn)橛^測(cè)值 VIVS-c6001.b12的數(shù)據(jù)量較大,等于2 000,故其經(jīng)驗(yàn)分布VIVS-c6001.ni是總體 Ψ的概率密度的一個(gè)良好近似。由此,即可求出與VIVS準(zhǔn)混沌算法有關(guān)的幾個(gè)主要參數(shù),如表1所示(見2.2節(jié)的檢驗(yàn)步驟)。

表1 VIVS準(zhǔn)混沌算法初值敏感性檢驗(yàn)主要結(jié)果Table 1 Sensitivity of the initial value with VIVS quasi-chaos algorithm

(4)初值敏感性樣本值VIVS-c6001.b12不大于門限值th=0.100 0的概率是

5 結(jié) 論

由式(8)得知,對(duì)于任意給定的彼此相鄰1 bit的初值矩陣I產(chǎn)生的樣本VIVS-c6001.b12不大于給定門限電平 th=0.100 0的概率為0.985 5,大于0.95,故依據(jù)判決準(zhǔn)則式(6),被檢驗(yàn)的VIVS準(zhǔn)混沌算法以概率0.985 5具有初值敏感性,從而為證明VIVS準(zhǔn)混沌算法滿足Shannon完全保密性定理的充要條件和探索大容量CDMA碼族奠定了理論基礎(chǔ),節(jié)省了大量的計(jì)算時(shí)間。

[1]陳志清,龍德浩.復(fù)合迭代算法及其應(yīng)用[J].四川大學(xué)學(xué)報(bào)(自然科學(xué)版),1997,34(5):621-628.CHEN Zhi-qing,L ONG De-hao.Composite iterative algorithm andits application[J].Journal of Sichuan University(Natural Science Edition),1997,34(5):621-628.(in Chinese)

[2]陳志清,龍德浩.二重變初值流密碼算法[J].四川大學(xué)學(xué)報(bào)(自然科學(xué)版),1997,34(6):791-800.CHEN Zhi-qing,LONG De-hao.Double Varying Initial Values Stream Cipher Algorithms[J].Journal of Sichuan University(Natural Science Edition),1997,34(6):791-800.(in Chinese)

[3]陳志清,龍德浩.變初值變結(jié)構(gòu)準(zhǔn)混沌:密碼學(xué)發(fā)展的新方向[J].大自然探索,1997,16(4):46-49.CHEN Zhi-qing,LONG De-hao.Varying Initial Conditions/Varying Structure Quasi-Chaotic Cipher Streams:A New Direction in Cryptography[J].Discovery of Nature,1997,16(4):46-49.(in Chinese)

[4]陳志清,龍德浩.變初值/變結(jié)構(gòu)準(zhǔn)混沌滾動(dòng)密鑰發(fā)生器[J].電訊技術(shù),1997,37(6):48-52.CHEN Zhi-qing,LONG De-hao.Change the initial value/variable structure quasi-chaos scroll key generator[J].Telecommunications Engineering,1997,37(6):48-52.(in Chinese)

[5]陳希孺.數(shù)理統(tǒng)計(jì)引論[M].北京:科學(xué)出版社,1981:534.CHEN Xi-ru.Mathematical Statistics Introduction[M].Beijing:Science Press,1981:534.(in Chinese)

[6]陳志清,龍德浩.變結(jié)構(gòu)密碼算法[J].四川大學(xué)學(xué)報(bào)(自然科學(xué)版),1998,35(2):210-217.CHEN Zhi-qing,LONG De-hao.Variable structure cryptographic algorithms[J].Journal of Sichuan University(Natural Science),1998,35(2):210-217.(in Chinese)

[7]茆詩(shī)松,程依明,濮曉龍.概率論與數(shù)理統(tǒng)計(jì)教程[M].北京:高等教育出版社,1983:229.MAO Shi-song,CHENG Yi-ming,PU Xiao-long.Probability and Statistics tutorial[M].Beijing:Higher Education Press,1983:229.(in Chinese)

[8]龍德浩.編碼識(shí)別汽車防撞雷達(dá)[J].電訊技術(shù),2009,49(7):41-46.LONG De-hao.Encoding recognition automotive collision avoidance radar[J].Telecommunications Engineering,2009,49(7):41-46.(in Chinese)