【正文】 數(shù)與 1 的個(gè)數(shù)相等若 L 為奇數(shù)則 0 的個(gè)數(shù)比 1 的個(gè)數(shù)多 1 或少 1 R2 長為 1 的游程占 12 且 0 游程和 1 游 程的個(gè)數(shù)相等或至多差一個(gè) R3 序列的異相自相關(guān)函數(shù)為一個(gè)常數(shù)即序列為二值自相關(guān)序列 能否產(chǎn)生真正的隨機(jī)序列一直都處在激烈的爭論中但可以肯定的是隨機(jī)序列的產(chǎn)生復(fù)制和控制在實(shí)際中都是難以實(shí)現(xiàn)的如果一個(gè)序列一方面它的結(jié)構(gòu)是可以預(yù)先確定的并且可以重復(fù)的產(chǎn)生和復(fù)制另一方面又具有某種隨機(jī)特性 R1R3 便稱這種序列為偽隨機(jī)序列簡單的講偽隨機(jī)序列就是具有某種隨機(jī)特性的確定序列 序列理論的發(fā)展史 偽隨機(jī)序列的理論與應(yīng)用研究大體上可以分成三個(gè)階段 1 純粹理論研究階段 1948 年以前 2 m 序列研究的黃金階段 19481969 3 非線性生成器的研究階段 1969 1948 年以前學(xué)者們研究偽隨機(jī)序列的理論僅僅是因?yàn)槠鋬?yōu)美的數(shù)學(xué)結(jié)構(gòu)最早的研究可以追溯到 1894 年作為一個(gè)組合問題來研究所謂的 De Bruijn 序列上世紀(jì) 30 年代環(huán)上的線性遞歸序列則成為人們的研究重點(diǎn) 1948 年 Shannon 信息論誕生后這種情況得到了改變偽隨機(jī)序列己經(jīng)被廣泛的應(yīng)用在通信以及密碼學(xué)等重要的技術(shù)領(lǐng)域 Shannon 證明了一次一密是無條件安全的無條件保密的密碼體制要求進(jìn)行保密通信的密鑰量至少與明文量一樣大因此在此后的一段時(shí)間 內(nèi)學(xué)者們一直致力于研究具有足夠長周期的偽隨機(jī)序列如何產(chǎn)生這樣的序列是 20 世紀(jì) 50 年代早期的研究熱點(diǎn)線性反饋移位寄存器 LFSR 序列是這個(gè)時(shí)期研究最多的因?yàn)橐粋€(gè) n級(jí) LFSR可以產(chǎn)生周期為的最大長度序列而且具有滿足 Golomb 隨機(jī)性假設(shè)的隨機(jī)特性通常稱為 m 序列這段時(shí)期的研究奠定了 LFSR 序列的基本理論和一些經(jīng)典結(jié)論 但是在 1969年 Massey發(fā)表了移位寄存器綜合與 BCH譯碼一文引發(fā)了序列研究方向的根本性變革從此偽隨機(jī)序列的研究進(jìn)入了構(gòu)造非線性序列生成器的階段 BerlekampMassey 算法 簡稱 BM 算法 指出如果序列的線性復(fù)雜度為 n 則只需要 2n 個(gè)連續(xù)比特就可以恢復(fù)出全部的序列從這個(gè)結(jié)論可以看出 m 序列是一種極差的序列它的線性復(fù)雜度太小因而不能夠直接用來做流密碼系 統(tǒng)的密鑰流序列從這里還可以看到僅僅靠 Golomb 的三個(gè)隨機(jī)性假設(shè)來評(píng)測(cè)序列是不夠的還需要其它的一些指標(biāo)此后直到今天密碼學(xué)界的學(xué)者們一直在努力尋找構(gòu)造好的偽隨機(jī)序列的方法 偽隨機(jī)序列的構(gòu)造方法 就現(xiàn)有的文獻(xiàn)可以把構(gòu)造偽隨機(jī)序列的方法分成兩大類一類是基于數(shù)學(xué)的理論構(gòu)造偽隨機(jī)序列另一類是基于 LFSR 構(gòu)造偽隨機(jī)序列兩種構(gòu)造方法各有優(yōu)缺點(diǎn)前者在理 論上容易分析序列的隨機(jī)性質(zhì)但往往不容易實(shí)現(xiàn)或者實(shí)現(xiàn)的代價(jià)比較高而后者則恰恰相反在工程上很容易實(shí)現(xiàn)成本較低但有的情況下不容易分析其隨機(jī)性質(zhì) 基于數(shù)學(xué)理論構(gòu)造偽隨機(jī)序列又可以分為兩類基于數(shù)論的構(gòu)造和基于有限域的構(gòu)造前者利用的數(shù)學(xué)工具主要是二次剩余理論和割圓理論像 Legendre 序列Jacobi 序列 m 序列差集序列和割圓序列等就屬于此類構(gòu)造后者利用的數(shù)學(xué)工具主要是跡函數(shù)像 Bent 序列 GMW 序列和橢圓曲線序列等為該類構(gòu)造的代表 基于 LFSR 的偽隨機(jī)序列生成器有很多總體上可以分為兩大類一類是用一個(gè) n元布爾函數(shù)作用于 n個(gè)輸入比特布爾函數(shù)的輸出作為密鑰流序列另一類是用一個(gè) LFSR控制另一個(gè) LFSR前者包含兩種生成器即熟知的非線性組合生成器和非線性濾波生成器由于 m 序列的線性復(fù)雜度太小不能直接用作密鑰流序列因此通常采用將 m 序列作驅(qū)動(dòng)序列然后用一個(gè)布爾函數(shù)作用于這些驅(qū)動(dòng)序列的方法來提高序列的線性復(fù)雜度非線性組合生成器由 n 個(gè) LFSR 和一個(gè)非線性組合器組成非線性濾波生成器由一個(gè) LFSR 和一個(gè)前饋邏輯組成第二類生成器也包含兩種控制模型鐘控生成器和縮減生成器這兩種生成器的原理都是用一個(gè)控制序列對(duì)另一個(gè)基序列做不規(guī)則采樣鐘控生成器是在基序 列中插入新的符號(hào)其輸出序列指數(shù)冪的依賴于產(chǎn)生它的生成器的輸入?yún)?shù)而縮減生成器包括自縮減生成器則是在基序列中刪除符號(hào)這種構(gòu)造結(jié)構(gòu)簡單易于用硬件實(shí)現(xiàn) 信號(hào) 偽隨機(jī)信號(hào)具有類似于隨機(jī)噪聲的一些統(tǒng)計(jì)特性同時(shí)又便于重復(fù)產(chǎn)生和處理目前廣泛使用的偽隨機(jī)信號(hào)都是由數(shù)字電路產(chǎn)生的周期序列得到的 m序列是最有名和最簡單的也是研究的最透徹的序列 m序列還是研究其它序列的基礎(chǔ)它序列平衡有最好的自相關(guān)特性但互相關(guān)滿足一定條件的族序列數(shù)很少 對(duì)于本原多項(xiàng)式的階數(shù)小于等于 13 的 m 序列互為優(yōu)選對(duì)的序列數(shù)不多于 6 且線性復(fù)雜度很小 偽隨機(jī)信號(hào)是一種長周期信號(hào) 若觀測(cè)時(shí)間大于一個(gè)周期便是確定性周期信號(hào)并顯示出它的非隨機(jī)性若觀測(cè)時(shí)間小于一個(gè)周期它便是真實(shí)的隨機(jī)二進(jìn)制信號(hào)偽隨機(jī)信號(hào) x t 與隨機(jī)二進(jìn)制信號(hào) y t 的區(qū)別如圖 1 所示在鉆柱系統(tǒng)辨識(shí)中 正是要用到偽隨機(jī)信號(hào)的隨機(jī)性偽隨機(jī)信號(hào)是以零對(duì)稱的正負(fù)兩電平信號(hào) x t 它的產(chǎn)生分成兩步 首先通過反饋式移位寄存器獲得 10兩狀態(tài)信號(hào)然后通過電平轉(zhuǎn)移把 1 轉(zhuǎn)換成正電平把 0 轉(zhuǎn)換成對(duì)稱的負(fù)電平下面僅討論 10 兩狀態(tài)信號(hào)的產(chǎn)生在圖 2 中從 n 級(jí)移位寄存器的第 n 級(jí)和第 k 級(jí)取出信號(hào)進(jìn)行模 2 相加后反饋至第 1 級(jí)當(dāng)輸入移位時(shí)鐘脈沖后在移位寄存器各級(jí)的輸出端 Q 得到2 n 1 位偽隨機(jī)信號(hào)所謂模 2 相加就是表 1 所示真值表完成的邏輯運(yùn)算圖 3 是 n 4 k 3 時(shí) 4 級(jí)偽隨機(jī)信號(hào)產(chǎn)生的邏輯框圖圖 3 a 是初始狀態(tài) 圖 3 b 為第一個(gè)移位時(shí)鐘脈沖加入后各級(jí)的變化狀態(tài) 圖 3 c d 是第二三個(gè)移位時(shí)鐘脈沖加入后各級(jí)移位寄存器狀態(tài)右移的情況以后移位時(shí)鐘脈沖加入后各級(jí)狀態(tài)以此右移 4 級(jí)移位寄存器 每 1 級(jí)輸出均有 15 個(gè)狀態(tài) 到了第 16 個(gè)狀態(tài)便開始重復(fù)推廣到 n級(jí) 反饋式移位寄存器在反饋線取得合適時(shí)可得到最大長度信號(hào)其長度 N 為 N 2 n 1 若移位時(shí)鐘脈沖周期為Δ t 則偽隨機(jī)信號(hào)的周期 T 為 T NΔt 圖 2 n 級(jí)移位寄存器 表 1 模 2 相加真值表 圖 1 偽隨機(jī)信號(hào) x t 與隨機(jī)二進(jìn)制信號(hào) y t 圖 3 4 級(jí)偽隨機(jī)信號(hào)產(chǎn)生的邏輯框圖 按照?qǐng)D 2 所示邏輯框圖得到 N 較大的信號(hào)是很麻煩的而用遞推法卻簡單得多它是由給定的任意 n 個(gè)初始狀態(tài)以及反饋級(jí)數(shù) k 遞推出偽隨機(jī)信號(hào)的所有狀態(tài)遞推公式為 Qr Qr k Y Qr n 式中 Qr 表示偽隨機(jī)信號(hào)的某一位狀態(tài) Qr k 表示從 Qr 1 開始倒數(shù) k 位對(duì)應(yīng)的狀態(tài) Qr n 表示從 Qr 1 開始倒數(shù) n 位對(duì)應(yīng)的狀態(tài)遞推前給定 n 位初始狀態(tài)則第 n 1 位初始狀態(tài) Qn1 等于從 Qn 開始倒數(shù) k 位對(duì)應(yīng)的狀態(tài) Qn1 k 與從 Qn 開始倒數(shù) n 位對(duì)應(yīng)的狀態(tài) Qn1 n 模 2 相加第 n 2 位狀態(tài) Qn2 等于從 Qn1 開始倒數(shù) k 位對(duì)應(yīng)的狀態(tài) Qn2 k 與從 Qn1 開始倒數(shù) n 位對(duì)應(yīng)的狀態(tài)Qn2 n 模 2 相加以此類推可得出整個(gè)周期的偽隨機(jī)信號(hào) 用遞推公式產(chǎn)生的偽隨機(jī)信號(hào) 在數(shù)字計(jì)算機(jī) 上可以用軟件來實(shí)現(xiàn) m 序列碼發(fā)生器 m 序列碼也稱偽隨機(jī)序列碼其主要特點(diǎn)是 1 每個(gè)周期中 1 碼出現(xiàn) 2n1 次 0 碼出現(xiàn) 2n11 次即 0 3 分布無規(guī)律具有與白噪聲相似的偽隨機(jī)特性 由于具有這些特點(diǎn) m 序列碼在通信雷達(dá)系統(tǒng)可靠性測(cè)試等方面獲得了廣泛地應(yīng)用 m序列碼發(fā)生器是一種反饋移位型結(jié)構(gòu)的電路它由 n位移位寄存器加異或反饋網(wǎng)絡(luò)組成其序列長度 M＝ 2n1只有一個(gè)多余狀態(tài)即全 0狀態(tài)所以稱為最大線性序列碼發(fā)生器由于其結(jié)構(gòu)已定型且反饋函數(shù)和連接形式都有一定的規(guī)律因此利用查表的 方式就可以設(shè)計(jì)出 m序列碼列出部分 m序列碼的反饋函數(shù) F和移存器位數(shù) n的對(duì)應(yīng)關(guān)系如果給定一個(gè)序列信號(hào)長度 M則根據(jù) M＝ 2n1求出 n 由 n查表便可以得到相應(yīng)的反饋函數(shù) F 例如要產(chǎn)生 M 7 的 m 序列碼首先根據(jù) M 2n1 確定 n 3 再查表可得反饋函數(shù) 即 74LS194 的 但由于電路處于全 0 狀態(tài)時(shí) F 0 故采用此方法設(shè)計(jì)的 m 序列發(fā)生器不具有自啟動(dòng)特性為了使電路具有自啟動(dòng)特性可以采取兩種方法 1 在反饋方程中加全 0 校正項(xiàng) Q1Q2Q3 F Q1??Q3Q1Q2Q3 Q1??Q2 Q1Q2Q3 其邏輯電路如圖 a 所示 M 序列反饋函數(shù)表 n M 2n1 反饋函數(shù) F 1 1 1 2 3 12 3 7 13 或23 4 15 43 5 31 53 6 63 65 7 127 76 8 225 8654 9 511 95 10 10232 107 11 2047 119 12 4095 121186 13 8191 1312109 14 16383 1413119 15 32767 1514 16 65535 16141311 17 131071 1714 18 262143 18171613 19 52287 19181714 20 1048575 2017 21 2097151 2119 22 4194303 2221 23 838