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. (i) Let к be an integer, 1 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.The output of a maximum-length LFSR with non-zero initial state is called an m-sequence.įact 6.14 demonstrates that the output sequences of maximum-length LFSRs have good statistical properties. Fact 6.12(ii) motivates the following definition.Ħ.13 Definition If C(D) e Z2 is a primitive polynomial of degree L, then (L. Table 4.8 Usts a primitive polynomial of degree m over Z2 for each m, 1 < m < 229. C produces an output sequence with maximum possible period 2 L - 1.Ī method for generating primitive polynomials over Z 2 uniformly at random is given in Algorithm 4.78. The significance of an LFSR being non-singular is explained by Fact 6.11.įigure 6.5: The LFSR (4,1 + D + D 4) of Example 6.10.Ħ.11 Fact Eveiy output sequence (i.e., for all possible initial states) of an LFSR (L. (i) the content of stage 0 is output and forms part of the output sequence.During each unit of time the following operations are performed: ,L - 1, each capable of storing one bit and having one input and one output and a clock which controls the movement of data. 6.7 Definition A linear feedback shift register (LFSR) of length L consists of L stages (or delay elements) numbered 0,1.because of their structure, they can be readily analyzed using algebraic techniques. they can produce sequences with good statistical properties (Fact 6.14) and they can produce sequences of large period (Fact 6.12) LFSRs are well-suited to hardware implementation Linear feedback shift registers (LFSRs) are used in many of the keystream generators that have been proposed in the literature. Finally, nonlinear feedback shift registers are discussed in §6.2.4. 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. §6.2.1 introduces linear feedback shift registers. Feedback shift registers, in particular linear feedback shift registers, are the basic components of many keystream generators.

Non linear feedback shift register