Feedback shift registers
Feedback shift registers, in particular linear feedback shift registers, are the basic components of many keystream generators. §6.2.1 introduces linear feedback shift registers. The linear complexity of binary sequences is studied in §6.2.2, while the Berlekamp-Massey algorithm for computing it is presented in §6.2.3. Finally, nonlinear feedback shift registers are discussed in §6.2.4.
Linear feedback shift registers
Linear feedback shift registers (LFSRs) are used in many of the keystream generators that have been proposed in the literature. There are several reasons for this:
- 1. LFSRs are well-suited to hardware implementation;
- 2. they can produce sequences of large period (Fact 6.12);
- 3. they can produce sequences with good statistical properties (Fact 6.14); and
- 4. because of their structure, they can be readily analyzed using algebraic techniques.
- 6.7 Definition A linear feedback shift register (LFSR) of length L consists of L stages (or delay elements) numbered 0,1,... ,L — 1, each capable of storing one bit and having one input and one output; and a clock which controls the movement of data. During each unit of time the following operations are performed:
- (i) the content of stage 0 is output and forms part of the output sequence;
- (ii) the content of stage i is moved to stage i - 1 for each i, 1 < i < L — 1; and
- (iii) the new content of stage L — 1 is the feedback bit Sj which is calculated by adding together modulo 2 the previous contents of a fixed subset of stages 0,1,... , L — 1.
Figure 6.4 depicts an LFSR. Referring to the figure, each c,; is either 0 or 1; the closed semi-circles are AND gates; and the feedback bit Sj is the modulo 2 sum of the contents of those stages i, 0 < i < L - 1, for which CL-i = 1.
Figure 6.4: A linear feedback shift register (LFSR) of length L.
6.8 Definition The LFSR of Figure 6.4 is denoted {L,C{D)), where C(D) = 1 + cD +
c_{2}D^{2} +----1- clD^{l} € Z_{2} [D is the connection polynomial. The LFSR is said to be non
singular if the degree of C(D) is L (that is, cl = 1). If the initial content of stage i is Si € {0,1} for each г, 0 < i < L — 1, then [.«£,_ 1,... , si, so] is called the initial state of the LFSR.
6.9 Fact If the initial state of the LFSR in Figure 6.4 is ... , «1, so], then the output
sequence s = so, si, S2, . ■ . is uniquely determined by the following recursion:
6.10 Example (output sequence of an LFSR) Consider the LFSR (4.1 + D + D^{4}) depicted in Figure 6.5. If the initial state of the LFSR is [0.0,0,0], the output sequence is the zero sequence. The following tables show the contents of the stages D_{3}, D_{2}, D1, D_{0} at the end of each unit of tune t when the initial state is [0,1,1,0].
t |
D_{3} |
d_{2} |
Di |
Do |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
2 |
1 |
0 |
0 |
1 |
3 |
0 |
1 |
0 |
0 |
4 |
0 |
0 |
1 |
0 |
5 |
0 |
0 |
0 |
1 |
6 |
1 |
0 |
0 |
0 |
7 |
1 |
1 |
0 |
0 |
t |
D_{3} |
d_{2} |
D_{x} |
Do |
8 |
1 |
1 |
1 |
0 |
9 |
1 |
1 |
1 |
1 |
10 |
0 |
1 |
1 |
1 |
11 |
1 |
0 |
1 |
1 |
12 |
0 |
1 |
0 |
1 |
13 |
1 |
0 |
1 |
0 |
14 |
1 |
1 |
0 |
1 |
15 |
0 |
1 |
1 |
0 |
The output sequence is s = 0,1,1,0,0,1,0,0,0,1,1,1,1,0.1,..., and is periodic with period 15 (see Definition 5.25). □
The significance of an LFSR being non-singular is explained by Fact 6.11.
Figure 6.5: The LFSR (4,1 + D + D^{4}) of Example 6.10.
6.11 Fact Eveiy output sequence (i.e., for all possible initial states) of an LFSR (L. C{D)) is periodic if and only if the connection polynomial C(D) has degree L.
If an LFSR (L, C(D)) is singular (i.e., C(D) has degree less than L), then not all output sequences are periodic. However, the output sequences are ultimately periodic; that is, the sequences obtained by ignoring a certain finite number of terms at the beginning are periodic. For the remainder of this chapter, it will be assumed that all LFSRs are nonsingular. Fact 6.12 determines the periods of the output sequences of some special types of non-singular LFSRs.
- 6.12 Fact (periods of LFSR output sequences) Let C(D) e Z_{2} [£>] be a connection polynomial of degree L.
- (i) If C(D) is irreducible over Z2 (see Definition 2.190), then each of the 2^{L} - 1 nonzero initial states of the non-singular LFSR {L. C(D)} produces an output sequence with period equal to the least positive integer N such that C(D) divides 1 + D^{N} in Z2[D]. (Note: it is always the case that this N is a divisor of 2^{L} — 1.)
- (ii) If C(D) is a primitive polynomial (see Definition 2.228), then each of the 2^{l} -1 nonzero initial states of the non-singular LFSR {L. C(D)} produces an output sequence with maximum possible period 2^{L} - 1.
A method for generating primitive polynomials over Z_{2} uniformly at random is given in Algorithm 4.78. Table 4.8 Usts a primitive polynomial of degree m over Z2 for each m, 1 < m < 229. Fact 6.12(ii) motivates the following definition.
6.13 Definition If C(D) e Z2[D] is a primitive polynomial of degree L, then (L. C(D)) is called a maximum-length LFSR. The output of a maximum-length LFSR with non-zero initial state is called an m-sequence.
Fact 6.14 demonstrates that the output sequences of maximum-length LFSRs have good statistical properties.
- 6.14 Fact (statistical properties of m-sequences) Let s be an ?n-sequence that is generated by a maximum-length LFSR of length L.
- (i) Let к be an integer, 1 < к < L, and let s be any subsequence of s of length 2^{h} + к - 2. Then each non-zero sequence of length к appears exactly 2^{L}~^{k} times as a subsequence of A Furthermore, the zero sequence of length к appears exactly 2^{L}~^{k} - 1 times as a subsequence of s. In other words, the distribution of patterns having fixed length of at most L is almost uniform.
- (ii) s satisfies Golomb’s randomness postulates (§5.4.3). That is, every m-sequence is also a pn-sequence (see Definition 5.29).
6.15 Example (m-sequence) Since C(D) = 1 + D + D^{4} is a primitive polynomial over Z_{2}, the LFSR (4,1 + D + D^{4}) is a maximum-length LFSR. Hence, the output sequence of this LFSR is an m-sequence of maximum possible period N = 2^{4}-l = 15 (cf. Example 6.10). Example 5.30 verifies that this output sequence satisfies Golomb’s randomness properties.
□