Linear Feedback Shift Registers
Linear Feedback Shift Registers
复制标题
线性反馈移位寄存器
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
U. Jetzek
中科院分区：
文献类型：
--
作者：
U. Jetzek
线性反馈移位寄存器（LFSR）是以随机方式步进所有可能的2 − 1非零n长位模式的最有效方法之一。LFSR是递归序列，使用二进制加法（模2加法或异或）从旧位生成新位。它们采用的模式取决于n次驱动多项式，它提供了抽头和初始填充。作为原始多项式的驱动多项式在循环之前生成所有可能的2 − 1非零n长位模式，使其非常适合准随机数生成。原始多项式最容易在表格中找到（尽管也有数学技巧来推导它们）。非基元驱动多项式不会生成所有可能的2−1非零n位模式。本页包含一些这些原始多项式，以八进制表示。最高的“on”位（1）决定多项式的次数。剩余的“开”位确定抽头。例如，235o表示用于八进制线性反馈移位寄存器的最小多项式。它的二进制表示和它表示的多项式是：
Linear feed back shift registers (LFSR) are one of the most efficient ways to step through all possible 2 − 1 non-zero n-long bit patterns in a random fashion. LFSR’s are a recursive sequence, with new bits generated from old using binary addition (mod two addition or exclusive-or’s). The pattern they take depends on the driving polynomial of degree n, which provides the taps, and the initial fill. Driving polynomials which are primitive polynomials generate all possible 2 − 1 non-zero n-long bit patterns before cycling, making them perfect for quasi-random number generation. Primitive polynomials are easiest to find in tables (though there are mathematical techniques for deriving them as well). A non-primitive driving polynomial will not generate all possible 2−1 non-zero n-bit patterns. This page contains some of these primitive polynomials, represented in octal. The highest ’on’ bit (one) determines the degree of the polynomial. The remaining ’on’ bits determine the taps. For example 235o represents a minimal polynomial used for linear feedback shift registers in octal. Its binary representation and the polynomial that it represents is: