楊 鶴

（保密通信重點實驗室，四川 成都 610041）

0 引言

線性反饋移位寄存器是一種用于生成統(tǒng)計性能良好偽隨機序列的方法[1-3]。

在偽隨機序列發(fā)生器設計中，由于不同應用采用的線性反饋移位寄存器在類型、長度和反饋抽頭方面有較大區(qū)別[1]，下面提出一種能夠?qū)€性反饋移位寄存器類型、長度和反饋抽頭等進行配置的可重構(gòu)線性反饋移位寄存器的設計方法。

1 線性反饋移位寄存器類型和結(jié)構(gòu)

線性反饋移位寄存器按照反饋網(wǎng)絡的結(jié)構(gòu)分為Fibonacci型和 Galois型兩種基本類型，其結(jié)構(gòu)分別如圖 1和圖2所示。

圖1 Fibonacci型線性反饋移位寄存器

圖2 Galois型線性反饋移位寄存器

圖2為Galois型線性反饋移位寄存器，Qi表示各級寄存器的輸出， Gi表示 Qi是否與線性反饋移位寄存器輸出端 Q0先進行異或運算，再將異或結(jié)果作為下一級寄存器的輸入，Gi=1表示 Qi需要與 Q0先進行異或運算再將異或結(jié)果作為下一級寄存器的輸入， Gi=0 表示 Qi不與 Q0進行異或運算，直接將iQ作為下一級寄存器的輸入。

從反饋關(guān)系來看，F(xiàn)ibonacci型線性反饋移位寄存器是將若干個反饋抽頭反饋至整個線性反饋移位寄存器輸入端，Galois型線性反饋移位寄存器是將輸出端反饋至若干位置。除了Fibonacci型和Galois型兩種基本類型的線性反饋移位寄存器，一些偽隨機序列應用中還使用了混合型線性反饋移位寄存器，其中既包含將若干個反饋抽頭反饋至整個線性反饋移位寄存器輸入端的反饋結(jié)構(gòu)，也包含將輸出端反饋至若干位置的反饋結(jié)構(gòu)。

2 可重構(gòu)線性反饋移位寄存器

可重構(gòu)線性反饋移位寄存器結(jié)構(gòu)上分為可重構(gòu)線性反饋移位寄存器段（以下簡稱寄存器段）和可重構(gòu)線性反饋移位寄存器鏈（以下簡稱寄存器鏈）兩個層次[4]。

2.1 寄存器段的寄存器設置

寄存器段支持的最大段長為定長，在下文中以128位段長舉例。寄存器段包括以下部分：

①寄存器段本體 Q0, Q1, … ,。在每一個時鐘周期保存寄存器段的數(shù)值；

②Fibonacci反饋配置寄存器 F0, F1, … ,。按位與寄存器段本體對應，F(xiàn)ibonacci反饋配置寄存器的某一位等于1，則選擇寄存器段本體中的相應位作為反饋抽頭，位置最前的反饋抽頭決定了寄存器段的實際長度；

③Galois反饋配置寄存器 G0, G1, … ,。按位與寄存器段本體對應，Galois反饋配置寄存器的某一位等于 1，則將整個寄存器段的輸出端與寄存器段本體中的相應位做異或運算，再作為下一級寄存器的輸入。注意，Galois反饋配置寄存器中不包含寄存器段的實際長度信息；

④長度及鏈接配置寄存器。共9位，用于配置Galois寄存器段的實際長度和前向、后向鏈接情況，表1是寄存器各字段的說明。

表1 長度及鏈接配置寄存器字段說明

2.2 寄存器段的接口

寄存器段的接口如表2所示。

表2 寄存器段的接口說明

2.3 寄存器段的反饋結(jié)構(gòu)

2.3.1 Fibonacci反饋結(jié)構(gòu)

寄存器段的Fibonacci反饋結(jié)構(gòu)如圖3所示。

圖3 寄存器段的Fibonacci反饋結(jié)構(gòu)

不考慮寄存器段鏈接的情況：寄存器段本體Q0, Q1, …,與Fibonacci反饋配置寄存器F0,F1,… ,做逐位相與運算，對相與運算結(jié)果進行異或運算，再將異或運算的結(jié)果反饋至寄存器段的輸入端。

考慮寄存器段鏈接的情況：寄存器段本體 Q0, Q1, … ,與Fibonacci反饋配置寄存器 F0, F1, … ,做逐位相與運算，對相與運算結(jié)果進行異或運算，如果LINK_FW有效即前向鏈接有其他寄存器段，則還要與來自前向寄存器段的反饋信號FFB_IN異或；如果LINK_BW有效即后向鏈接有其他寄存器段，則將上述異或運算結(jié)果作為反饋信號FFB_OUT送入后向寄存器段，并使用來自后向寄存器段的移位輸入信號SHIFT_IN輸入至寄存器段的輸入端；如果LINK_BW無效，則將上述異或運算的結(jié)果反饋至寄存器段的輸入端。

2.3.2 Galois反饋結(jié)構(gòu)

寄存器段的Galois反饋結(jié)構(gòu)如圖4所示。

圖4 寄存器段的Galois反饋結(jié)構(gòu)

不考慮寄存器段鏈接的情況：根據(jù)長度及鏈接配置寄存器中Galois寄存器段長度，從寄存器段本體 Q0, Q1, … ,中選擇反饋位，根據(jù)Galois反饋配置寄存器 G0, G1, … ,確定反饋位是否與寄存器段本體 Q0, Q1, … ,做逐位異或運算。

考慮寄存器段鏈接的情況：根據(jù)長度及鏈接配置寄存器中Galois寄存器段長度，從寄存器段本體 Q0, Q1, … ,中選擇反饋位，若LINK_FW有效，則選擇來自前向寄存器段的反饋信號GFB_IN作為反饋位；根據(jù)Galois反饋配置寄存器G0, G1, … ,確定反饋位是否與寄存器段本體Q0,Q1, … ,做逐位異或運算；若LINK_BW有效，則將上述反饋位作為反饋信號GFB_OUT送入后向寄存器段，并使用來自后向寄存器段的移位輸入信號 SHIFT_IN輸入至寄存器段的輸入端；如果LINK_BW無效，則將上述反饋位反饋至寄存器段的輸入端。

2.4 寄存器鏈

將后向寄存器段的SHIFT_OUT鏈接至前向寄存器段的SHIFT_IN，將前向寄存器段的FFB_OUT和GFB_OUT鏈接至后向寄存器段的FFB_IN和GFB_IN，則構(gòu)成了寄存器鏈結(jié)構(gòu)，如圖5所示。

圖5 由寄存器段組成的寄存器鏈結(jié)構(gòu)

理論上，可以采用這種方法對寄存器鏈進行無限延長，但由于Fibonacci和Galois反饋信號的延時存在累積，而且512位以上的線性反饋移位寄存器很少使用，所以寄存器鏈不宜太長。

3 設計結(jié)果

采用了128位段長和4個寄存器段構(gòu)成的寄存器鏈的參數(shù)配置，用 VerilogHDL對電路進行了描述[5]，采用 Xilinx XC5VLX30 FPGA器件綜合[6]后，經(jīng)過時序仿真和驗證，功能和性能符合設計要求。具體參數(shù)為：時延4.808 ns，LUT數(shù)量為2 279個，觸發(fā)器數(shù)量為1 575個。

4 結(jié)語

根據(jù)芯片設計對功能、性能、面積等方面的要求，提出了一種反饋類型可選擇、反饋抽頭可選、長度可配置和擴展的線性反饋移位寄存器的設計方法。在Xilinx XC5VLX30器件上做了實現(xiàn)，頻率高、面積小，能夠良好支持偽隨機序列生成。

[1] 譙通旭，張文政，祝世雄.計算幾類周期序列的最小周期[J].信息安全與通信保密,2009(08):211-213.

[2] 劉依依.ESTREAM和流密碼分析現(xiàn)狀[J].信息安全與通信保密,2009(12):87-89.

[3] 楊波.現(xiàn)代密碼學[M].北京:清華大學出版社,2003.

[4] MARCOVITZ A B.邏輯設計基礎[M].北京:清華大學出版社,2006.

[5] THOMAS D E, MOORBY P R.硬件描述語言 Verilog[M].北京:清華大學出版社,2001.

[6] 貝斯.數(shù)字信號處理的FPGA實現(xiàn)[M].北京:清華大學出版社,2002.