楊 鶴

（保密通信重點(diǎn)實(shí)驗(yàn)室，四川 成都 610041）

0 引言

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

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

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

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

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

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

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

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

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

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

2.1 寄存器段的寄存器設(shè)置

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

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

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

③Galois反饋配置寄存器 G0, G1, … ,。按位與寄存器段本體對(duì)應(yīng)，Galois反饋配置寄存器的某一位等于 1，則將整個(gè)寄存器段的輸出端與寄存器段本體中的相應(yīng)位做異或運(yùn)算，再作為下一級(jí)寄存器的輸入。注意，Galois反饋配置寄存器中不包含寄存器段的實(shí)際長(zhǎng)度信息；

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

表1 長(zhǎng)度及鏈接配置寄存器字段說(shuō)明

2.2 寄存器段的接口

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

表2 寄存器段的接口說(shuō)明

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,… ,做逐位相與運(yùn)算，對(duì)相與運(yùn)算結(jié)果進(jìn)行異或運(yùn)算，再將異或運(yùn)算的結(jié)果反饋至寄存器段的輸入端。

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

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

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

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

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

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

2.4 寄存器鏈

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

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

理論上，可以采用這種方法對(duì)寄存器鏈進(jìn)行無(wú)限延長(zhǎng)，但由于Fibonacci和Galois反饋信號(hào)的延時(shí)存在累積，而且512位以上的線性反饋移位寄存器很少使用，所以寄存器鏈不宜太長(zhǎng)。

3 設(shè)計(jì)結(jié)果

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

4 結(jié)語(yǔ)

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

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

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

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

[4] MARCOVITZ A B.邏輯設(shè)計(jì)基礎(chǔ)[M].北京:清華大學(xué)出版社,2006.

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

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