【文章內(nèi)容簡介】 機序列 .簡 單的講，偽隨機序列就是具有某種隨機特性的確定序列。 偽隨機序列理論的發(fā)展史 偽隨機序列的理論與應用研究大體上可以分成三個階段 :(1)純粹理論研究階段 (1948年以前 )； (2)m序列研究的黃金階段 (19481969)； (3)非線性生成器的研究階段 (1969 )。 1948年以前，學者們研究偽隨機序列的理論僅僅是因 為其優(yōu)美的數(shù)學結(jié)構(gòu)。最早的研究可以追溯到 1894年，作為一個組合問題來研究所謂的 De Bruijn序列；上世紀 30年代，環(huán)上的線性遞歸序列則成為人們的研究重點 . 1948年 Shannon信息論誕生后，這種情況得到了改變。偽隨機序列己經(jīng)被廣泛的應用在通信以及密碼學等重要的技術(shù)領域。 Shannon證明了“一次一密”是無條件安全的，無條件保密的密碼體制要求進行保密通信的密鑰量至少與明文量一樣大。因此在此后的一段時間內(nèi)，學者們一直致力于研究具有足夠長周期的偽隨機序列。如何產(chǎn)生這樣的序列是 20世紀 50年代早期的研究 熱點。線性反饋移位寄存器 (LFSR)序列是這個時期研究最多的，因為一個 n級 LFSR可以產(chǎn)生周期為12?n 的最大長度序列，而且具有滿足 Golomb隨機性假設的隨機特性，通常稱為 m序列。這段時期的研究奠定了 LFSR序列的基本理論和一些經(jīng)典結(jié)論。 但是，在 1969年 Massey發(fā)表了“移位寄存器綜合與 BCH譯碼”一文，引發(fā)了序列研究方向的根本性變革，從此偽隨機序列的研究進入了構(gòu)造非線性序列生成器的階段。 BerlekampMassey算法 (簡稱 BM算法 )指出 :如果序列的線 性復雜度為n，則只需要 2n個連續(xù)比特就可以恢復出全部的序列。從這個結(jié)論可以看出 m序列是一種“極差”的序列，它的線性復雜度太小，因而不能夠直接用來做流密碼系 統(tǒng)的密鑰流序列。從這里還可以看到僅僅靠 Golomb的三個隨機性假設來評測序列是不夠的，還需要其它的一些指標。此后直到今天，密碼學界的學者們一直在努力尋找構(gòu)造“好”的偽隨機序列的方法。 偽隨機序列的構(gòu)造方法 就現(xiàn)有的文獻，可以把構(gòu)造偽隨機序列的方法分成兩大類 :一類是基于數(shù)學 13 的理論構(gòu)造偽隨機序列；另一類是基于 LFSR構(gòu)造偽隨機序列。兩種構(gòu)造方法各有優(yōu) 缺點，前者在理論上容易分析序列的隨機性質(zhì)，但往往不容易實現(xiàn)或者實現(xiàn)的代價比較高；而后者則恰恰相反，在工程上很容易實現(xiàn)，成本較低，但有的情況下不容易分析其隨機性質(zhì)。 基于數(shù)學理論構(gòu)造偽隨機序列又可以分為兩類 :基于數(shù)論的構(gòu)造和基于有限域的構(gòu)造。前者利用的數(shù)學工具主要是二次剩余理論和割圓理論，像 Legendre序列、 Jacobi序列、 m序列、差集序列和割圓序列等就屬于此類構(gòu)造；后者利用的數(shù)學工具主要是跡函數(shù)，像 Bent序列、 GMW序列和橢圓曲線序列等為該類構(gòu)造的代表。 基于 LFSR的偽隨機序列生成器有很多，總體 上可以分為兩大類 :一類是用一個 n元布爾函數(shù)作用于 n個輸入比特，布爾函數(shù)的輸出作為密鑰流序列；另一類是用一個 LFSR控制另一個 LFSR。前者包含兩種生成器，即熟知的非線性組合生成器和非線性濾波生成器。由于 m序列的線性復雜度太小，不能直接用作密鑰流序列，因此通常采用將 m序列作驅(qū)動序列，然后用一個布爾函數(shù)作用于這些驅(qū)動序列的方法來提高序列的線性復雜度。非線性組合生成器由 n個 LFSR和一個非線性組合器組成；非線性濾波生成器由一個 LFSR和一個前饋邏輯組成。第二類生成器也包含兩種控制模型，鐘控生成器和縮減生成器。這兩 種生成器的原理都是用一個控制序列對另一個基序列做不規(guī)則采樣。鐘控生成器是在基序列中插入新的符號，其輸出序列指數(shù)冪的依賴于產(chǎn)生它的生成器的輸入?yún)?shù)；而縮減生成器包括自縮減生成器則是在基序列中刪除符號，這種構(gòu)造結(jié)構(gòu)簡單易于用硬件實現(xiàn)。 4 序列信號發(fā)生器原理 序列信號發(fā)生器是能夠循環(huán)產(chǎn)生一組或多組序列信號的時序電路，它可以用以為寄存器或計數(shù)器構(gòu)成。序列信號的種類很多，按照序列循環(huán)長度 M和觸發(fā)器數(shù)目 n的關(guān)系一般可分為三種： （ 1） 最大循環(huán)長度序列碼， M＝ 2n。 （ 2） 最大線性序列碼（ m序列碼）， M=2n－ 1。 （ 3） 任意循環(huán)長度序 列碼， M＜ 2n。 14 通常在許多情況下，要求按照給定的序列信號來設計序列信號發(fā)生器。序列信號發(fā)生器一般有兩種結(jié)構(gòu)形式：一種是反饋移位型，另一種是計數(shù)型。 反饋移位型序列信號發(fā)生器 反饋移位型序列碼發(fā)生器的結(jié)構(gòu)框圖如圖所示，它由移位寄存器和組合反饋網(wǎng)絡組成，從移存器的某一輸出端可以得到周期性的序列碼。其設計按以下步驟進行： （ 1）根據(jù)給定序列信號的循環(huán)長度 M，確定移存器位數(shù) n， 2n1＜ M≤ 2n。（ 2）確定移位寄存器的 M個獨立狀態(tài)。 將給定的序列碼按 照移位規(guī)律 n 位一組，劃分位 M 個狀態(tài)。若 M個狀態(tài)中出現(xiàn)重復現(xiàn)象，則應增加移存器位數(shù) 。用 n+1 位再重復上述過程，直到劃分為 M個獨立狀態(tài)為止。 組合反饋網(wǎng)絡Q1Q2QnSR(SL) n 位移位寄存器ZCP… 圖 3 反饋移位型序列信號發(fā)生器框圖 （ 3）根據(jù) M 個不同狀態(tài)列出移存氣的狀態(tài)表和反饋函數(shù)表，求出反饋函數(shù) F 的表式。（ 4）檢查自啟動性能（ 5）畫邏輯圖。 下面通過舉例說明反饋移位序列信號發(fā)生器的設計過程。 方法一： 比如要設計一個 00011101 序列發(fā)生器。具體可以這樣來解決： (1) 確定移存器的位數(shù) n。因 M=8，故 n≥ 3，選定為三位，用 74LS194 的三位。 15 (2) 確定移存器的八個獨立狀態(tài)。將序列碼 00011101 按照每三位一組，劃分為八個狀態(tài)，其遷移關(guān)系如下所示： (3) 作出反饋函數(shù)表，如表所示，由遷移關(guān)系可看出移存器只進行左移操作，因此 S1=1, S0=0。將 F(SL)的卡諾圖填入圖 (a)中，選用四選一實現(xiàn) F(SL)函數(shù)，其邏輯圖如圖 (b) 表 4 反饋函數(shù)真值表 Q1 Q2 Q3 F(SL) 0 O O 1 0 0 1 1 0 1 1 1 1 1 1 0 1 1 0 1 1 0 1 0 0 1 0 0 1 0 0 0 ( a )1 1 1 000 01 11Q1Q2Q0100 0 0 101( b )7 4 L S 1 9 4Q1S0S101CPCrQ0Q2A1A0D0D1D2D3四選一SLF輸出1 圖 4 00011101 序列信號發(fā)生器 方法二： 設計一個產(chǎn)生 100111 序列的反饋移位型序列信號發(fā)生器。具體解決方法： (1) 確定移存器位數(shù) n。因 M=6，故 n≥ 3； (2) 確定移存器的六個獨立狀態(tài)：將序列碼 100111 按照移位規(guī)律每三位一組，劃 16 分六個狀態(tài)為 100、 00 01 11 11 110。其中狀 態(tài) 111 重復出現(xiàn)，故取n=4，并重新劃分六個獨立狀態(tài)為 100 001 011 111 11 1100。因此確定 n=4，用一片 74LS194 即可。 (3) 反饋激勵函數(shù)表，求反饋函數(shù) F 的表達式：根據(jù)每一狀態(tài)所需要的移位輸入即反饋輸入信號，列出反饋函數(shù)表如表所示。從表中可見，移存器只需進行左移操作，因此反饋函數(shù) F=SL。表也表明了組合反饋網(wǎng)絡的輸出和輸入之間的函數(shù)關(guān)系，因此可填出 F的卡諾圖如圖 (a)所示，并求得： 表 5 _____ 20__2__0)( SF L ??? 反饋函數(shù)真值表 Q0 Q1 Q2 Q3 F(SL) 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 0 0 1 1 0 0 1 (4) 檢查自啟動性能。 根據(jù)以上結(jié)果，作出完全狀態(tài)圖如圖 (b)所示?？梢姡幸粋€無效循環(huán)。為了使電路具有自啟動性能，應重新修改設計。其思路就是打破無效循環(huán)，引入主有效循環(huán)，將 0110→ 1100， 0010→ 0100，其完全狀態(tài)圖如圖 (a)所示卡諾圖的圈如圖 (b)所示，求得 F=Q2+Q0Q3。如選用四選一數(shù)據(jù) 選折器實現(xiàn)地址選 Q0Q2＝ A1A0，得 D0=1， D1=Q3， D2=1， D3=0，則具有自啟動能力的電路如圖所示。 1 11 1 0 0 00 01 11 1000011110Q0 Q1Q2 Q31010 0100 1001 00110010 01011100 1110主( a )( b )011111110000 0001 10001011 01101101F ( SL) 圖 5 卡諾圖和移存器的全狀態(tài)圖 17 1 1 1 11 1 1 11 1 0 00 0 0 000 01 11 1000011110Q0 Q1Q2 Q3( b )F ( SL)1010 0100 1001 00110110 1100 主( a )000101110010 0000100011111110101111010101 圖 6 修正后的狀態(tài)圖和 F的卡諾圖 7 4 L S 1 9 4Q0Q1Q2Q3S1S0SL10CPD0D1D2D3A0A1ZYF 四選一M U X“ 1 ” 圖 7 邏輯電路圖 . 計數(shù)型序列碼發(fā)生器 計數(shù)型序列碼發(fā)生器結(jié)構(gòu)框圖如圖所示。它由計數(shù)器和組合輸出網(wǎng)絡兩部分組成，序列碼從組合輸出網(wǎng)絡輸出。 設計過程分兩步： （ 1） 根據(jù)序列碼的長度 M 設計模 M 計數(shù)器，狀態(tài)可以自定； （ 2） 按計數(shù)器的狀態(tài)轉(zhuǎn)移關(guān)系和序列碼的要求設計組合輸出網(wǎng)絡。由于計數(shù)器的狀態(tài)設置和輸出序列的更改比較方便，而且還能同時產(chǎn)生多組序列碼。 下面以具體實例來說明： 方法一 ： 設計 1101000101 由于給定序列長度 P=10，故先用 74LS161 設計一個模 10 的計數(shù)器，我們利用 74LS161 的預置端 LD，用后 10 個狀態(tài)，即 0110~1111。令該 10 個狀態(tài) 18 中每一個狀態(tài)的輸出符合給定序列的要求，列出其真值表如表所示，對應的輸出卡諾圖如圖 (a)所示。采用八選一數(shù)據(jù)選擇器實現(xiàn)，電路如圖 (b) 所示。 組合反饋網(wǎng)絡Q1Q2Qn模 M 計數(shù)器ZCP… 圖 8 電路原理圖 表 6 真值表 S QD QC QB QA F 1 0 1 1 0 1 2 0 1 1 1 1 3 1 0 0 0 0 4 1 0 0 1 1 5 1 0 1 0 0 6 1 0 1 1 0 7 1 1 0 0 0 8 1 1 0 1 1 9 1 1 1 0 0 10 1 1 1 1 1 00 01 11QBQAQD QC10 1 10 1 1 00 1 0 0D0D1D2D3D4D5D6A2A1A010F0 1 1 01 八選一數(shù)據(jù)選擇器( a ) ( b )00011110 D77 4 L S 1 6 1QDQCQBQAOCLDCP01010DADBDCDD“ 1 ”PTCr“ 1 ” 圖 9 設計過程及邏輯圖 方法二： 設計一個能同時產(chǎn)生兩組代碼的信號發(fā)生器， 這兩組代碼分別是：F1=110101 和 F2=010110。具體解決辦法： 首先用 74LS194 設計一個具有自校正的 模 6 扭環(huán)型計數(shù)器如圖 (a)所示，并畫出輸出序列卡諾圖如圖 (b)所示。然 19 后用一片 3 8 譯碼器和與非門實現(xiàn) 1 1 0 00 01 11Q1Q2Q0101 1 001F10 0 1 00 01 11Q1Q2Q0101 1 001F2( a ) ( b ) ( c )Q0Q1Q2Q3S