转载自: http://homepage.mac.com/afj/lfsr.html
Linear Feedback Shift Registers
For those unfamiliar with Linear Feedback Shift Registers, see the Primer following Figure 1. For quick information on any of the LFSR parts (shift register, feedback function, output stream, tap sequences) click on the corresponding part in Figure 1.
For a listing of tap sequences for registers 3 to 24 bits long and for 2, 4, and 6 tap sequences for registers 25 to 32 bits long, click here.
For C source code for an LFSR simulator, click here.
For a discussion of uses of LFSR's in cryptography, see "Applied Cryptography" by Bruce Schneier.For the math behind LFSR's, see "Shift Register Sequences" by Solomon Golomb.
Figure 1) 4-Bit LFSR, Tap Sequence; [4,1]
500)this.width=500'>
SHIFT REGISTER
One of the two main parts of an LFSR is the shift register (the other being the feedback function). A shift register is a device whose identifying function is to shift its contents into adjacent positions within the register or, in the case of the position on the end, out of the register. The position on the other end is left empty unless some new content is shifted into the register.
The contents of a shift register are usually thought of as being binary, that is, ones and zeroes. If a shift register contains the bit pattern 1101, a shift (to the right in this case) would result in the contents being 0110; another shift yields 0011. After two more shifts, things tend to get boring since the shift register will never contain anything other than zeroes.
Two uses for a shift register are 1) convert between parallel and serial data and 2) delay a serial bit stream. The conversion function can go either way -- fill the shift register positions all at once (parallel) and then shift them out (serial) or shift the contents into the register bit by bit (serial) and then read the contents after the register is full (parallel). The delay function simply shifts the bits from one end of the shift register to the other, providing a delay equal to the length of the shift register.
Figure 2) Shift Register
500)this.width=500'>
Some nomenclature:
Clocking) One of the inputs to a shift register is the clock; a shift occurs in the register when this clock input changes state from one to zero (or from zero to one, depending on the implementation). From this, the term "clocking" has arisen to mean activating a shift of the register. Sometimes the register is said to be "strobed" to cause the shift.
Shift direction) A shift register can shift its contents in either direction depending on how the device is designed. (Some registers have extra inputs that dictate the direction of the shift.) For the purposes of this discussion, the shift direction will always be from left to right.
Output) During a shift, the bit on the far right end of the shift register is moved out of the register. This end bit position is often referred to as the output bit. To confuse matters a bit, the bits that are shifted out of the register are also often referred to as output bits. To really muddy the waters, every bit in the shift register is considered to be output during a serial to parallel conversion. Happily, the context in which the term "output" is used generally clears things up.
Input) After a shift, the bit on the left end of the shift register is left empty unless a new bit (one not contained in the original contents) is put into it. This bit is sometimes referred to as the input bit. As with the output bit, there are several different references to input that are clarified by context.
Back to Top
FEEDBACK FUNCTION
In an LFSR, the bits contained in selected positions in the shift register are combined in some sort of function and the result is fed back into the register's input bit. By definition, the selected bit values are collected before the register is clocked and the result of the feedback function is inserted into the shift register during the shift, filling the position that is emptied as a result of the shift.
The feedback function in an LFSR has several names: XOR, odd parity, sum modulo 2. Whatever the name, the function is simple: 1) Add the selected bit values, 2) If the sum is odd, the output of the function is one; otherwise the output is zero. Table 1 shows the output for a 3 input XOR function.
Table 1) XOR Function
Input A
Input B
Input C
XOR Output
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
0
1
1
1
1
The bit positions selected for use in the feedback function are called "taps". The list of the taps is known as the "tap sequence". By convention, the output bit of an LFSR that is n bits long is the nth bit; the input bit of an LFSR is bit 1.
Back to Top
TAP SEQUENCES
An LFSR is one of a class of devices known as state machines. The contents of the register, the bits tapped for the feedback function, and the output of the feedback function together describe the state of the LFSR. With each shift, the LFSR moves to a new state. (There is one exception to this -- when the contents of the register are all zeroes, the LFSR will never change state.) For any given state, there can be only one succeeding state. The reverse is also true: any given state can have only one preceding state. For the rest of this discussion, only the contents of the register will be used to describe the state of the LFSR.
A state space of an LFSR is the list of all the states the LFSR can be in for a particular tap sequence and a particular starting value. Any tap sequence will yield at least two state spaces for an LFSR. (One of these spaces will be the one that contains only one state -- the all zero one.) Tap sequences that yield only two state spaces are referred to as maximal length tap sequences.
The state of an LFSR that is n bits long can be any one of 2^n different values. The largest state space possible for such an LFSR will be 2^n - 1 (all possible values minus the zero state). Because each state can have only once succeeding state, an LFSR with a maximal length tap sequence will pass through every non-zero state once and only once before repeating a state.
One corollary to this behavior is the output bit stream. The period of an LFSR is defined as the length of the stream before it repeats. The period, like the state space, is tied to the tap sequence and the starting value. As a matter of fact, the period is equal to the size of the state space. The longest period possible corresponds to the largest possible state space, which is produced by a maximal length tap sequence. (Hence "maximal length")
Table 2 is a listing of the internal states and the output bit stream of a 4-bit LFSR with tap sequence [4, 1]. (This is the LFSR shown in Figure 1.)
Table 2) 4-Bit LFSR [4, 1] States and Output
Register States
Bit 1 (Tap)
Bit 2
Bit 3
Bit 4 (Tap)
Output Stream
1
1
0
1
0
1
1
0
1
0
0
1
1
0
1
0
0
1
1
0
1
0
0
1
0
0
1
0
0
0
0
0
1
0
1
0
0
0
1
1
1
0
0
0
1
1
1
0
0
1
1
1
1
0
0
1
1
1
1
1
0
1
1
1
0
1
0
1
1
1
0
1
0
1
1
1
0
1
0
MAXIMAL LENGTH TAP SEQUENCES
LFSR's can have multiple maximal length tap sequences. A maximal length tap sequence also describes the exponents in what is known as a primitive polynomial mod 2. For example, a tap sequence of 4, 1 describes the primitive polynomial x^4 + x^1 + 1. Finding a primitive polynomial mod 2 of degree n (the largest exponent in the polynomial) will yield a maximal length tap sequence for an LFSR that is n bits long.
There is no quick way to determine if a tap sequence is maximal length. However, there are some ways to tell if one is not maximal length:
1) Maximal length tap sequences always have an even number of taps.2) The tap values in a maximal length tap sequence are all relatively prime. A tap sequence like 12, 9, 6, 3 will not be maximal length because the tap values are all divisible by 3.
Discovering one maximal length tap sequence leads automatically to another. If a maximal length tap sequence is described by [n, A, B, C], another maximal length tap sequence will be described by [n, n-C, n-B, n-A]. Thus, if [32, 3, 2, 1] is a maximal length tap sequence, [32, 31, 30, 29] will also be a maximal length tap sequence. An interesting behavior of two such tap sequences is that the output bit streams are mirror images in time.
Back to Top
CHARACTERISTICS OF OUTPUT STREAM
By definition, the period of an LFSR is the length of the output stream before it repeats. Besides being non-repetitive, a period of a maximal length stream has other features that are characteristic of random streams.
1) Sums of ones and zeroes. In one period of a maximal length stream, the sum of all ones will be one greater than the sum of all zeroes. In a random stream, the difference between the two sums will tend to grow progressively smaller in proportion to the length of the stream as the stream gets longer. In an infinite random stream, the sums will be equal.
2) Runs of ones and zeroes. A run is a pattern of equal values in the bit stream. A bit stream like 10110100 has six runs of the following lengths in order: 1, 1, 2, 1, 1, 2. One period of an n-bit LFSR with a maximal length tap sequence will have 2^(n-1) runs (e.g., a 5 bit device yields 16 runs in one period). 1/2 the runs will be one bit long, 1/4 the runs will be 2 bits long, 1/8 the runs will be 3 bits long, etc., up to a single run of zeroes that is n-1 bits long and a single run of ones that is n bits long. A random stream of sufficient length shows similar behavior statistically.
3) Shifted stream. Take the stream of bits in one period of an LFSR with a maximal length tap sequence and circularly shift it any number of bits less than the total length. Do a bitwise XOR with the original stream. The resulting pattern will exhibit the behaviors discussed in items 1 and 2. A random stream also shows this behavior.
One characteristic of the LFSR output not shared with a random stream is that the LFSR stream is deterministic. Given knowledge of the present state of the LFSR, the next state can always be predicted.
Back to Top