Better to know some... than all
|
||||||
|
Feedback Shift RegistersFeedback shift registers, in particular linear feedback shift registers, are the basic components of many keystream generators. Linear feedback shift registersLinear 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. 3. They can produce sequences with good statistical properties. 4. Because of their structure, they can be readily analyzed using algebraic techniques. 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. (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.  In figure, each ci 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 C L - i = 1. The LFSR of is denoted hL;C(D)i, where C(D) = 1+c1D + c2D2 + ... + cLDL € Z2[D] is the connection polynomial. The LFSR is said to be nonsingular 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 i, 0 < i < L - 1, then [sL - 1; .... ; s1; s0] is called the initial state of the LFSR. If the initial state of the LFSR in Figure 6.4 is [sL - 1; .... ; s1; s0], then the output sequence s = s0; s1; s2; .... is uniquely determined by the following recursion: sj = (c1sj - 1 + c2sj - 2 + ... + cLsj - L) mod 2 for j >= L: |
|||||