一种可重构线性反馈移位寄存器设计

杨 鹤

（保密通信重点实验室，四川 成都 610041）

0 引言

线性反馈移位寄存器是一种用于生成统计性能良好伪随机序列的方法[1-3]。

在伪随机序列发生器设计中，由于不同应用采用的线性反馈移位寄存器在类型、长度和反馈抽头方面有较大区别[1]，下面提出一种能够对线性反馈移位寄存器类型、长度和反馈抽头等进行配置的可重构线性反馈移位寄存器的设计方法。

1 线性反馈移位寄存器类型和结构

线性反馈移位寄存器按照反馈网络的结构分为Fibonacci型和 Galois型两种基本类型，其结构分别如图 1和图2所示。

图1 Fibonacci型线性反馈移位寄存器

图2 Galois型线性反馈移位寄存器

图2为Galois型线性反馈移位寄存器，Qi表示各级寄存器的输出， Gi表示 Qi是否与线性反馈移位寄存器输出端 Q0先进行异或运算，再将异或结果作为下一级寄存器的输入，Gi=1表示 Qi需要与 Q0先进行异或运算再将异或结果作为下一级寄存器的输入， Gi=0 表示 Qi不与 Q0进行异或运算，直接将iQ作为下一级寄存器的输入。

从反馈关系来看，Fibonacci型线性反馈移位寄存器是将若干个反馈抽头反馈至整个线性反馈移位寄存器输入端，Galois型线性反馈移位寄存器是将输出端反馈至若干位置。除了Fibonacci型和Galois型两种基本类型的线性反馈移位寄存器，一些伪随机序列应用中还使用了混合型线性反馈移位寄存器，其中既包含将若干个反馈抽头反馈至整个线性反馈移位寄存器输入端的反馈结构，也包含将输出端反馈至若干位置的反馈结构。

2 可重构线性反馈移位寄存器

可重构线性反馈移位寄存器结构上分为可重构线性反馈移位寄存器段（以下简称寄存器段）和可重构线性反馈移位寄存器链（以下简称寄存器链）两个层次[4]。

2.1 寄存器段的寄存器设置

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

①寄存器段本体 Q0, Q1, … ,。在每一个时钟周期保存寄存器段的数值；

②Fibonacci反馈配置寄存器 F0, F1, … ,。按位与寄存器段本体对应，Fibonacci反馈配置寄存器的某一位等于1，则选择寄存器段本体中的相应位作为反馈抽头，位置最前的反馈抽头决定了寄存器段的实际长度；

③Galois反馈配置寄存器 G0, G1, … ,。按位与寄存器段本体对应，Galois反馈配置寄存器的某一位等于 1，则将整个寄存器段的输出端与寄存器段本体中的相应位做异或运算，再作为下一级寄存器的输入。注意，Galois反馈配置寄存器中不包含寄存器段的实际长度信息；

④长度及链接配置寄存器。共9位，用于配置Galois寄存器段的实际长度和前向、后向链接情况，表1是寄存器各字段的说明。

表1 长度及链接配置寄存器字段说明

2.2 寄存器段的接口

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

表2 寄存器段的接口说明

2.3 寄存器段的反馈结构

2.3.1 Fibonacci反馈结构

寄存器段的Fibonacci反馈结构如图3所示。

图3 寄存器段的Fibonacci反馈结构

不考虑寄存器段链接的情况：寄存器段本体Q0, Q1, …,与Fibonacci反馈配置寄存器F0,F1,… ,做逐位相与运算，对相与运算结果进行异或运算，再将异或运算的结果反馈至寄存器段的输入端。

考虑寄存器段链接的情况：寄存器段本体 Q0, Q1, … ,与Fibonacci反馈配置寄存器 F0, F1, … ,做逐位相与运算，对相与运算结果进行异或运算，如果LINK_FW有效即前向链接有其他寄存器段，则还要与来自前向寄存器段的反馈信号FFB_IN异或；如果LINK_BW有效即后向链接有其他寄存器段，则将上述异或运算结果作为反馈信号FFB_OUT送入后向寄存器段，并使用来自后向寄存器段的移位输入信号SHIFT_IN输入至寄存器段的输入端；如果LINK_BW无效，则将上述异或运算的结果反馈至寄存器段的输入端。

2.3.2 Galois反馈结构

寄存器段的Galois反馈结构如图4所示。

图4 寄存器段的Galois反馈结构

不考虑寄存器段链接的情况：根据长度及链接配置寄存器中Galois寄存器段长度，从寄存器段本体 Q0, Q1, … ,中选择反馈位，根据Galois反馈配置寄存器 G0, G1, … ,确定反馈位是否与寄存器段本体 Q0, Q1, … ,做逐位异或运算。

考虑寄存器段链接的情况：根据长度及链接配置寄存器中Galois寄存器段长度，从寄存器段本体 Q0, Q1, … ,中选择反馈位，若LINK_FW有效，则选择来自前向寄存器段的反馈信号GFB_IN作为反馈位；根据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，则构成了寄存器链结构，如图5所示。

图5 由寄存器段组成的寄存器链结构

理论上，可以采用这种方法对寄存器链进行无限延长，但由于Fibonacci和Galois反馈信号的延时存在累积，而且512位以上的线性反馈移位寄存器很少使用，所以寄存器链不宜太长。

3 设计结果

采用了128位段长和4个寄存器段构成的寄存器链的参数配置，用 VerilogHDL对电路进行了描述[5]，采用 Xilinx XC5VLX30 FPGA器件综合[6]后，经过时序仿真和验证，功能和性能符合设计要求。具体参数为：时延4.808 ns，LUT数量为2 279个，触发器数量为1 575个。

4 结语

根据芯片设计对功能、性能、面积等方面的要求，提出了一种反馈类型可选择、反馈抽头可选、长度可配置和扩展的线性反馈移位寄存器的设计方法。在Xilinx XC5VLX30器件上做了实现，频率高、面积小，能够良好支持伪随机序列生成。

[1] 谯通旭，张文政，祝世雄.计算几类周期序列的最小周期[J].信息安全与通信保密,2009(08):211-213.

[2] 刘依依.ESTREAM和流密码分析现状[J].信息安全与通信保密,2009(12):87-89.

[3] 杨波.现代密码学[M].北京:清华大学出版社,2003.

[4] MARCOVITZ A B.逻辑设计基础[M].北京:清华大学出版社,2006.

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

[6] 贝斯.数字信号处理的FPGA实现[M].北京:清华大学出版社,2002.