偽隨機信號在雷達、遙控、遙測、通信加密和無線電測量系統領域有著廣泛的應用，其產生方法有多種途徑。進位反饋移位寄存器（feedbackwithcarryshiftregiste，FCSR）由Klapper和Goresky于1993年提出，是一類較新穎的方法，其理論實質類似于數學上產生隨機數的模2同余法。經過一系列理論分析后普遍認為在序列密碼的分析和設計中具有一定價值。

本文簡要介紹了FCSR的基本原理和特性，重點討論基于硬件描述語言VHDL的可變長FCSR的設計。VHDL可編程邏輯器件CPLD/FPGA結合使用，可以方便、靈活地實現此類偽隨機序列發生器。

1 FCSR產生原理和序列特性

某時刻一個r級（非退化）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，∑為一般的整數加法。工作過程如下：

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

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

由于在FCSR中，初始狀態、移位寄存器級數、抽頭數目、抽頭位置的變化都會產生不同的序列，因此可以通過設計參數可變的FCSR發生器來生成周期更長的偽隨機序列。

2 FCSR序列發生器的VHDL實現

以n=10為例來設計參數可變的FCSR序列發生器。

2.1 功能描述及外部引腳

由圖1可知，進位反饋移位寄存器由加法器、進位寄存器和一組（n級）D觸發器組成。加法器實現FCSR的反饋運算；進位寄存器保存前一時刻運算結果除2后的狀態mn-1，并為下一運算提供輸入；n級D觸發器構成移位寄存器，在時鐘控制下實現右移，依次輸出其內部狀態。同時某些觸發器的輸出反饋回來，與進位寄存器的輸出進行運算，和模2反饋至寄存器輸入端，和除2反饋至進位寄存器。

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

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

其中，CLK為時鐘信號；RESET為置數信號；PRN為初態置數端；SEL為抽頭置數端；Q為輸出端。該FCSR序列發生器的特點在于可以通過設定SEL［9…0］的值來改變抽頭數、抽頭位置和發生器的有效級數n（1“10級）；當RESET為低電平時，通過設定PR N［9…0］的值改變FCSR的初態，從而可以改變輸出序列周期，分析各種狀態下輸出 序列的變化。

2.2 可變參數部分的設計

本設計通過手動或軟件自動設定SEL［9…0］的值來改變抽頭數、抽頭位置和發生器的有效級數3個參數，其中改變最高抽頭位置可使有效長度可變。具體電路中，由SEL［9…0］設定值作為加法器的輸入，輸出結果進行下一步運算，因此需要設計輸入變量較多、延遲時間較短的加法器電路。

這里的求和運算可以等效為計算輸入變量中“1”的個數。對此有多種實現方案，如計數法、邏輯函數法、查表法、求和網絡法等。單純使用一種方法，在輸入變量較多的情況下會有占用資源太多、延遲時間太大或表達式太繁瑣等問題，因此需要綜合使用這些方法。該加法器綜合使用邏輯函數-求和網絡法，由1位累加器和3位串行加法器實現。

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

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

這里求和網絡只有1級，不難由此擴充成多級。該電路延遲至多為8級邏輯門的延遲時間，占用資源也較少。

2.3 主程序

根據FCSR序列產生的原理，采用VHDL語言的混合描述方式對該邏輯進行硬件描述。主程序l_seq如下：

其中元件例化語句中所引用的元件已經作為組件在components.vhd用戶包進行定義，在主程序中調用即可。

3 時序仿真

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

4 需要注意的問題

（1）通過調整SEL及PRN的值并分析輸出序列變化可知，不是任意整數作為連接數都能使F C SR達到最大周期。在工程應用當中，l-序列是最希望得到的。因此在使用FCSR時，應該優先選用那些可以產生l-序列的特殊的連接數，如文獻［1］中提供的一些連接數。

（2）當q為非最大周期連接數時，某些初態會有周期更小的序列輸出。例如當q=17時，ord17（2）=8，即他有最大周期T=8。而實際上除2個平凡狀態外，某些初態會導致輸出T=6的周期序列。在密碼設計中，由于FCSR的初態對應著初始密鑰，這就意味著基于FCSR發生器有弱密鑰。因此，在實際應用中要仔細選擇。

（3）本例中，由于抽頭數最大為9，所以4位進位寄存器即可滿足要求。實際上，當t 》2時（t為抽頭數），進位寄存器最小應為log2t。

（4）當加法器采用組合電路實現時，需注意邏輯門延遲影響。在抽頭數較大時，應適當調整電路的時鐘頻率。

5 結語

FCSR是一類較新穎的思想，其數學特性目前還不太清晰。因此今后可以從理論和技術實踐兩方面來分析FCSR的隨機特性和應用特點。本軟件在通過時序仿真和適配后，配置La ttice公司的CPLD器件，輸出序列達到了設計目標。