【文章內(nèi)容簡介】 y發(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)測序列是不夠的，還需要其它的一些指標(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)。4 序列信號(hào)發(fā)生器原理序列信號(hào)發(fā)生器是能夠循環(huán)產(chǎn)生一組或多組序列信號(hào)的時(shí)序電路，它可以用以為寄存器或計(jì)數(shù)器構(gòu)成。序列信號(hào)的種類很多，按照序列循環(huán)長度M和觸發(fā)器數(shù)目n的關(guān)系一般可分為三種：（1） 最大循環(huán)長度序列碼，M＝2n。（2） 最大線性序列碼（m序列碼），M=2n－1。（3） 任意循環(huán)長度序列碼，M＜2n。 通常在許多情況下，要求按照給定的序列信號(hào)來設(shè)計(jì)序列信號(hào)發(fā)生器。序列信號(hào)發(fā)生器一般有兩種結(jié)構(gòu)形式：一種是反饋移位型，另一種是計(jì)數(shù)型。 反饋移位型序列信號(hào)發(fā)生器 反饋移位型序列碼發(fā)生器的結(jié)構(gòu)框圖如圖所示，它由移位寄存器和組合反饋網(wǎng)絡(luò)組成，從移存器的某一輸出端可以得到周期性的序列碼。其設(shè)計(jì)按以下步驟進(jìn)行：（1）根據(jù)給定序列信號(hào)的循環(huán)長度M，確定移存器位數(shù)n，2n1＜M≤2n。（2）確定移位寄存器的M個(gè)獨(dú)立狀態(tài)。 將給定的序列碼按照移位規(guī)律n位一組，劃分位M個(gè)狀態(tài)。若M個(gè)狀態(tài)中出現(xiàn)重復(fù)現(xiàn)象，則應(yīng)增加移存器位數(shù) 。用n+1位再重復(fù)上述過程，直到劃分為M個(gè)獨(dú)立狀態(tài)為止。 圖3 反饋移位型序列信號(hào)發(fā)生器框圖（3）根據(jù)M個(gè)不同狀態(tài)列出移存氣的狀態(tài)表和反饋函數(shù)表，求出反饋函數(shù)F的表式。（4）檢查自啟動(dòng)性能（5）畫邏輯圖。下面通過舉例說明反饋移位序列信號(hào)發(fā)生器的設(shè)計(jì)過程。方法一：比如要設(shè)計(jì)一個(gè) 00011101 序列發(fā)生器。具體可以這樣來解決：(1) 確定移存器的位數(shù)n。因M=8，故n≥3，選定為三位，用74LS194 的三位。 (2) 確定移存器的八個(gè)獨(dú)立狀態(tài)。將序列碼00011101按照每三位一組，劃分為八個(gè)狀態(tài)，其遷移關(guān)系如下所示：(3) 作出反饋函數(shù)表，如表所示，由遷移關(guān)系可看出移存器只進(jìn)行左移操作，因此S1=1, S0=0。將F(SL)的卡諾圖填入圖(a)中，選用四選一實(shí)現(xiàn)F(SL)函數(shù)，其邏輯圖如圖(b)所示。表4 反饋函數(shù)真值表Q1Q2Q3F(SL)0OO10011011111101101101001001000圖4 00011101 序列信號(hào)發(fā)生器方法二：設(shè)計(jì)一個(gè)產(chǎn)生 100111序列的反饋移位型序列信號(hào)發(fā)生器。具體解決方法：(1) 確定移存器位數(shù)n。因M=6，故n≥3；(2) 確定移存器的六個(gè)獨(dú)立狀態(tài)：將序列碼100111按照移位規(guī)律每三位一組，劃分六個(gè)狀態(tài)為 100、00011111110。其中狀態(tài)111 重復(fù)出現(xiàn)，故取n=4，并重新劃分六個(gè)獨(dú)立狀態(tài)為 100001011111111100。因此確定n=4，用一片74LS194 即可。 (3) 反饋激勵(lì)函數(shù)表，求反饋函數(shù)F的表達(dá)式：根據(jù)每一狀態(tài)所需要的移位輸入即反饋輸入信號(hào)，列出反饋函數(shù)表如表所示。從表中可見，移存器只需進(jìn)行左移操作，因此反饋函數(shù)F=SL。表也表明了組合反饋網(wǎng)絡(luò)的輸出和輸入之間的函數(shù)關(guān)系，因此可填出F的卡諾圖如圖(a)所示，并求得： 表5 反饋函數(shù)真值表Q0Q1Q2Q3F(SL)100110011101111111101110011001(4) 檢查自啟動(dòng)性能。 根據(jù)以上結(jié)果，作出完全狀態(tài)圖如圖(b)所示。可見，它有一個(gè)無效循環(huán)。為了使電路具有自啟動(dòng)性能，應(yīng)重新修改設(shè)計(jì)。其思路就是打破無效循環(huán)，引入主有效循環(huán)，將0110→1100，0010→0100，其完全狀態(tài)圖如圖(a)所示卡諾圖的圈如圖(b)所示，求得F=Q2+Q0Q3。如選用四選一數(shù)據(jù)選折器實(shí)現(xiàn)地址選Q0Q2＝A1A0，得D0=1，D1=Q3，D2=1，D3=0，則具有自啟動(dòng)能力的電路如圖所示。 圖5 卡諾圖和移存器的全狀態(tài)圖 圖6 修正后的狀態(tài)圖和F的卡諾圖圖7 邏輯電路圖 . 計(jì)數(shù)型序列碼發(fā)生器計(jì)數(shù)型序列碼發(fā)生器結(jié)構(gòu)框圖如圖所示。它由計(jì)數(shù)器和組合輸出網(wǎng)絡(luò)兩部分組成，序列碼從組合輸出網(wǎng)絡(luò)輸出。設(shè)計(jì)過程分兩步：（1） 根據(jù)序列碼的長度M設(shè)計(jì)模M計(jì)數(shù)器，狀態(tài)可以自定；（2） 按計(jì)數(shù)器的狀態(tài)轉(zhuǎn)移關(guān)系和序列碼的要求設(shè)計(jì)組合輸出網(wǎng)絡(luò)。由于計(jì)數(shù)器的狀態(tài)設(shè)置和輸出序列的更改比較方便，而且還能同時(shí)產(chǎn)生多組序列碼。下面以具體實(shí)例來說明：方法一：設(shè)計(jì) 1101000101 序列信號(hào)發(fā)生器。具體解決辦法：由于給定序列長度P=10，故先用 74LS161 設(shè)計(jì)一個(gè)模10的計(jì)數(shù)器，我們利用74LS161 的預(yù)置端LD，用后 10 個(gè)狀態(tài)，即 0110~1111。令該 10 個(gè)狀態(tài)中每一個(gè)狀態(tài)的輸出符合給定序列的要求，列出其真值表如表所示，對(duì)應(yīng)的輸出卡諾圖如圖 (a)所示。采用八選一數(shù)據(jù)選擇器實(shí)現(xiàn)，電路如圖 (b) 所示。 圖8 電路原理圖表6 真值表SQDQCQBQAF1011012011113100004100115101006101107110008110119111001011111圖9 設(shè)計(jì)過程及邏輯圖方法二：設(shè)計(jì)一個(gè)能同時(shí)產(chǎn)生兩組代碼的信號(hào)發(fā)生器， 這兩組代碼分別是：F1=110101和F2=010110。具體解決辦法： 首先用 74LS194 設(shè)計(jì)一個(gè)具有自校正的模6 扭環(huán)型計(jì)數(shù)器如圖 (a)所示，并畫出輸出序列卡諾圖如圖(b)所示。然后用一片 3 8 譯碼器和與非門實(shí)現(xiàn)圖10 設(shè)計(jì)過程及邏輯圖輸出組合邏輯。最后畫出邏輯圖如圖(c)所示。 5 移位寄存器 寄存器一般有多個(gè)觸發(fā)器組成，通常有鎖存寄存器和移位寄存器。本次介紹的寄存器是由若干個(gè)D觸發(fā)器組成的線性移位寄存器（反饋型）。移位寄存器中的數(shù)據(jù)可以在移位脈沖作用下一次逐位右移或左移，數(shù)據(jù)既可以并行輸入、并行輸出，也可以串行輸入、串行輸出，還可以并行輸入、串行輸出，串行輸入、并行輸出，十分靈活，用途也很廣。 線性反饋移位寄存器是一種應(yīng)用廣泛的數(shù)字部件，其結(jié)構(gòu)簡單、速度快，被應(yīng)用于許多領(lǐng)域。例如，在擴(kuò)頻通信系統(tǒng)中，由它構(gòu)成的偽隨機(jī)數(shù)（PN碼）發(fā)生器是這類系統(tǒng)的核心。在內(nèi)建自測試系統(tǒng)中，由它構(gòu)成測試圖案發(fā)生器。另外，它也被廣泛應(yīng)用于糾錯(cuò)編碼、數(shù)字加密等領(lǐng)域。 在數(shù)字系統(tǒng)中，常需要一些數(shù)碼暫時(shí)存放起來，這種暫時(shí)存放數(shù)碼。一個(gè)觸發(fā)器可以寄存1位二進(jìn)制數(shù)碼，要寄存幾位數(shù)碼，就應(yīng)具備幾個(gè)觸發(fā)器，此外，寄存器還應(yīng)具有由門電路構(gòu)成的控制電路，以保證信號(hào)的接收和清除。，接收脈沖到達(dá)后，將待存數(shù)據(jù)送至各D觸發(fā)器 ， 取數(shù)脈沖加入后將所存數(shù)據(jù)送出，輸入與輸出為并行工作方式。 并行輸入并行輸出的寄存器 移位寄存器 移位寄存器除了具有寄存數(shù)碼的功能外，還具有移位功能，即在移位脈沖作用下，能夠把寄存器中的數(shù)依次向右或向左移。它是一個(gè)同步時(shí)序邏輯電路,根據(jù)移位方向，常把它分成左移寄存器、右移寄存器 和 雙向移位寄存器三種；根據(jù)移位數(shù)據(jù)的輸入－輸出方式，又可將它分為串行輸入－串行輸出、串行輸入－并行輸出、并行輸入－串行輸出和并行輸入－并行輸出四種電路結(jié)構(gòu)。由D觸發(fā)器構(gòu)成的簡單移位寄存器： 用D觸發(fā)器構(gòu)成的四位移位寄存器，從CP上升沿開始到輸出新狀態(tài)的建立需要經(jīng)過一段傳輸延遲時(shí)間，所以當(dāng)CP上升沿同時(shí)作用于所有觸發(fā)器時(shí)，它們輸入端的狀態(tài)都未改變。于是，F(xiàn) F0按DI原來的狀態(tài)翻轉(zhuǎn)，F(xiàn) F1按Q0原來的狀態(tài)翻轉(zhuǎn)， F F2按Q1原來的狀態(tài)翻轉(zhuǎn)，F(xiàn) F3按Q2原來的狀態(tài)翻轉(zhuǎn)，同時(shí)，輸入端的代碼存入F0，總的效果是寄存器的代碼依次右移一位。 用D觸發(fā)器構(gòu)成的移位寄存器 可見，經(jīng)過4個(gè)CP信號(hào)后，串行輸入的四位代碼全部移入了移位寄存器，并在四個(gè)輸出端得到并行輸出代碼。利用移位寄存器可實(shí)現(xiàn)代碼的串行—并行轉(zhuǎn)換。若再加4個(gè)CP信號(hào)，寄存器中的四位代碼還可以從串行端依次輸出。 線性反饋移位寄存器結(jié)構(gòu)，寄存器除了D觸發(fā)器之外，構(gòu)成反饋電路的是由異或門組成的。 D觸發(fā)器負(fù)跳沿觸發(fā)的主從觸發(fā)器工作時(shí)，在正跳沿前加入輸入信號(hào)。如果在CP 高電平期間輸入端出現(xiàn)干擾信號(hào)，那么就有可能使觸發(fā)器的狀態(tài)出錯(cuò)。而邊沿觸發(fā)器允許在CP 觸發(fā)沿來到前一瞬間加入輸入信號(hào)。這樣，輸入端受干擾的時(shí)間大大縮短，受干擾的可能性就降低了。邊沿D觸發(fā)器也稱為維持阻塞邊沿D觸發(fā)器。電路結(jié)構(gòu): 該觸發(fā)器由6個(gè)與非門組成，其中G1和G2構(gòu)成基本RS觸發(fā)器。：SD 和RD 接至基本RS 觸發(fā)器的輸入端，分別是預(yù)置和清零端，低電平有效。當(dāng)SD=0且RD=1時(shí) ,不論輸入端D為何種狀態(tài)，都會(huì)使Q=1，Q=0，即觸發(fā)器置1；當(dāng)SD=1且RD=0時(shí)，觸發(fā)器的狀態(tài)為0,SD和RD通常又稱為直接置1和置0端。我們設(shè)它們均已加入了高電平，不影響電路的工作。工作過程如下： （1）CP=0時(shí)，與非門G3和G4封鎖，其輸出Q3=Q4=1，觸發(fā)器的狀態(tài)不變。同時(shí)，由于Q3至Q5和Q4至Q6的反饋信號(hào)將這兩個(gè)門打開，因此可接收輸入信號(hào)D，Q5=D，Q6=Q5=D。 （2）當(dāng)CP由0變1時(shí)觸發(fā)器翻轉(zhuǎn)。這時(shí)G3和G4打開，它們的輸入Q3和Q4的狀態(tài)由G5和G6的輸出狀態(tài)決定。Q3=Q5=D，Q4=Q6=D。由基本RS觸發(fā)器的邏輯功能可知，Q=D。 （3）觸發(fā)器翻轉(zhuǎn)后，在CP=1時(shí)輸入信號(hào)被封鎖。這是因?yàn)镚3和G4打開后，它們的輸出Q3和Q4的狀態(tài)是互補(bǔ)的,即必定有一個(gè)