偽隨機(jī)信號(hào)在雷達(dá)、遙控、遙測(cè)、通信加密和無(wú)線電測(cè)量系統(tǒng)領(lǐng)域有著廣泛的應(yīng)用，其產(chǎn)生方法有多種途徑。進(jìn)位反饋移位寄存器（feedbackwithcarryshiftregiste，F(xiàn)CSR）由Klapper和Goresky于1993年提出，是一類較新穎的方法，其理論實(shí)質(zhì)類似于數(shù)學(xué)上產(chǎn)生隨機(jī)數(shù)的模2同余法。經(jīng)過(guò)一系列理論分析后普遍認(rèn)為在序列密碼的分析和設(shè)計(jì)中具有一定價(jià)值。

本文簡(jiǎn)要介紹了FCSR的基本原理和特性，重點(diǎn)討論基于硬件描述語(yǔ)言VHDL的可變長(zhǎng)FCSR的設(shè)計(jì)。VHDL可編程邏輯器件CPLD/FPGA結(jié)合使用，可以方便、靈活地實(shí)現(xiàn)此類偽隨機(jī)序列發(fā)生器。

1 FCSR產(chǎn)生原理和序列特性

某時(shí)刻一個(gè)r級(jí)（非退化）FCSR如圖1所示。其中ai∈GF（2）， （i=n-1，n-2，…，n -r），mn-1∈Z，qi∈GF（2），（i=1，2，…，r-1），qr=1，∑為一般的整數(shù)加法。工作過(guò)程如下：

FCSR能返回到自身的狀態(tài)稱為周期狀態(tài)。以q為連接數(shù)的FCSR的周期狀態(tài)個(gè)數(shù)為q+1，其中平凡的周期狀態(tài)（0；0，…，0）和（w-1；1，…，1）在狀態(tài)圖中形成2個(gè)長(zhǎng)為1的圈，非平凡周期狀態(tài)的個(gè)數(shù)為q-1，其余狀態(tài)都是非周期的。其中w=wt（q+1）為q+1的漢明重量，指qi（i=0，1，…，r）中qi≠0的個(gè)數(shù)。

且q為奇數(shù)。如果p和q互素，那么a有周期T=ordq（2）。特殊的，如果T=Φ（q）（φ為歐拉函數(shù)），即2為模q的本原根，那么該序列達(dá)到他的最大周期。由歐拉函數(shù)的性質(zhì)可知，此時(shí)Φ（q）=q-1。稱其為連接數(shù)為q的最大周期FCSR序列，或l序列。

由于在FCSR中，初始狀態(tài)、移位寄存器級(jí)數(shù)、抽頭數(shù)目、抽頭位置的變化都會(huì)產(chǎn)生不同的序列，因此可以通過(guò)設(shè)計(jì)參數(shù)可變的FCSR發(fā)生器來(lái)生成周期更長(zhǎng)的偽隨機(jī)序列。

2 FCSR序列發(fā)生器的VHDL實(shí)現(xiàn)

以n=10為例來(lái)設(shè)計(jì)參數(shù)可變的FCSR序列發(fā)生器。

2.1 功能描述及外部引腳

由圖1可知，進(jìn)位反饋移位寄存器由加法器、進(jìn)位寄存器和一組（n級(jí)）D觸發(fā)器組成。加法器實(shí)現(xiàn)FCSR的反饋運(yùn)算；進(jìn)位寄存器保存前一時(shí)刻運(yùn)算結(jié)果除2后的狀態(tài)mn-1，并為下一運(yùn)算提供輸入；n級(jí)D觸發(fā)器構(gòu)成移位寄存器，在時(shí)鐘控制下實(shí)現(xiàn)右移，依次輸出其內(nèi)部狀態(tài)。同時(shí)某些觸發(fā)器的輸出反饋回來(lái)，與進(jìn)位寄存器的輸出進(jìn)行運(yùn)算，和模2反饋至寄存器輸入端，和除2反饋至進(jìn)位寄存器。

式（1）中qi∈GF（2） ，（i=1，2，…，r-1）在實(shí)際電路中為抽頭的連接狀態(tài)，決定哪一級(jí)輸出反饋至加法器，qi=0表示斷開(kāi)，qi=1表示連接。

FCSR序列發(fā)生器的外部引腳定義如圖2所示。

其中，CLK為時(shí)鐘信號(hào)；RESET為置數(shù)信號(hào)；PRN為初態(tài)置數(shù)端；SEL為抽頭置數(shù)端；Q為輸出端。該FCSR序列發(fā)生器的特點(diǎn)在于可以通過(guò)設(shè)定SEL［9…0］的值來(lái)改變抽頭數(shù)、抽頭位置和發(fā)生器的有效級(jí)數(shù)n（1“10級(jí)）；當(dāng)RESET為低電平時(shí)，通過(guò)設(shè)定PR N［9…0］的值改變FCSR的初態(tài)，從而可以改變輸出序列周期，分析各種狀態(tài)下輸出 序列的變化。

2.2 可變參數(shù)部分的設(shè)計(jì)

本設(shè)計(jì)通過(guò)手動(dòng)或軟件自動(dòng)設(shè)定SEL［9…0］的值來(lái)改變抽頭數(shù)、抽頭位置和發(fā)生器的有效級(jí)數(shù)3個(gè)參數(shù)，其中改變最高抽頭位置可使有效長(zhǎng)度可變。具體電路中，由SEL［9…0］設(shè)定值作為加法器的輸入，輸出結(jié)果進(jìn)行下一步運(yùn)算，因此需要設(shè)計(jì)輸入變量較多、延遲時(shí)間較短的加法器電路。

這里的求和運(yùn)算可以等效為計(jì)算輸入變量中“1”的個(gè)數(shù)。對(duì)此有多種實(shí)現(xiàn)方案，如計(jì)數(shù)法、邏輯函數(shù)法、查表法、求和網(wǎng)絡(luò)法等。單純使用一種方法，在輸入變量較多的情況下會(huì)有占用資源太多、延遲時(shí)間太大或表達(dá)式太繁瑣等問(wèn)題，因此需要綜合使用這些方法。該加法器綜合使用邏輯函數(shù)-求和網(wǎng)絡(luò)法，由1位累加器和3位串行加法器實(shí)現(xiàn)。

由于n=10，則抽頭數(shù)至多為10，可以分2組進(jìn)行求和。因此首先設(shè)計(jì)5輸入、3位輸出的累加器。用卡諾圖簡(jiǎn)化后，寫(xiě)邏輯表達(dá)式如下：

3位串行加法器的設(shè)計(jì)比較簡(jiǎn)單，不再贅述，則10輸入變量、3位輸出的加法器電路原理圖如圖3所示。

這里求和網(wǎng)絡(luò)只有1級(jí)，不難由此擴(kuò)充成多級(jí)。該電路延遲至多為8級(jí)邏輯門的延遲時(shí)間，占用資源也較少。

2.3 主程序

根據(jù)FCSR序列產(chǎn)生的原理，采用VHDL語(yǔ)言的混合描述方式對(duì)該邏輯進(jìn)行硬件描述。主程序l_seq如下：

其中元件例化語(yǔ)句中所引用的元件已經(jīng)作為組件在components.vhd用戶包進(jìn)行定義，在主程序中調(diào)用即可。

3 時(shí)序仿真

該程序在Lattice公司的ispLEVER軟件環(huán)境下編譯、運(yùn)行和仿真。該FCSR序列發(fā)生器可選級(jí)數(shù)為1”10級(jí)，周期范圍為1“2 029。經(jīng)分析知，當(dāng)初態(tài)為平凡周期狀態(tài)（0；0，…，0）和（w -1；1，…，1）時(shí)，輸出為全“0”或全“1”。當(dāng)抽頭置數(shù)為“0100000110”，即q9=q3 =q2=1，實(shí)際上是一個(gè)n=9的l序列發(fā)生器；置FCSR初態(tài)為（0，0，0，0；0，0， 0，1，1，0，1，0，1，0）時(shí)，波形如圖3所示，此時(shí)輸出序列的周期T=523。

4 需要注意的問(wèn)題

（1）通過(guò)調(diào)整SEL及PRN的值并分析輸出序列變化可知，不是任意整數(shù)作為連接數(shù)都能使F C SR達(dá)到最大周期。在工程應(yīng)用當(dāng)中，l-序列是最希望得到的。因此在使用FCSR時(shí)，應(yīng)該優(yōu)先選用那些可以產(chǎn)生l-序列的特殊的連接數(shù)，如文獻(xiàn)［1］中提供的一些連接數(shù)。

（2）當(dāng)q為非最大周期連接數(shù)時(shí)，某些初態(tài)會(huì)有周期更小的序列輸出。例如當(dāng)q=17時(shí)，ord17（2）=8，即他有最大周期T=8。而實(shí)際上除2個(gè)平凡狀態(tài)外，某些初態(tài)會(huì)導(dǎo)致輸出T=6的周期序列。在密碼設(shè)計(jì)中，由于FCSR的初態(tài)對(duì)應(yīng)著初始密鑰，這就意味著基于FCSR發(fā)生器有弱密鑰。因此，在實(shí)際應(yīng)用中要仔細(xì)選擇。

（3）本例中，由于抽頭數(shù)最大為9，所以4位進(jìn)位寄存器即可滿足要求。實(shí)際上，當(dāng)t 》2時(shí)（t為抽頭數(shù)），進(jìn)位寄存器最小應(yīng)為log2t。

（4）當(dāng)加法器采用組合電路實(shí)現(xiàn)時(shí)，需注意邏輯門延遲影響。在抽頭數(shù)較大時(shí)，應(yīng)適當(dāng)調(diào)整電路的時(shí)鐘頻率。

5 結(jié)語(yǔ)

FCSR是一類較新穎的思想，其數(shù)學(xué)特性目前還不太清晰。因此今后可以從理論和技術(shù)實(shí)踐兩方面來(lái)分析FCSR的隨機(jī)特性和應(yīng)用特點(diǎn)。本軟件在通過(guò)時(shí)序仿真和適配后，配置La ttice公司的CPLD器件，輸出序列達(dá)到了設(shè)計(jì)目標(biāo)。