feedforward logic. Linear Recursions There do indeed exist shift registers which, along with a minimal amount of feedback logic, produce binary sequences possessing very large period and excellent pseudo-randomness properties. However, an extreme mea- sure of luck would be necessary to randomly pick a sequence producible by a generator possessing relatively simple structural properties; analytical techniques must be used to determine structures which will serve ade- quately as PN generators. The PN generators to be explored in this chap- ter all are variations of a linear-feedback shift register (LFSR) with non-linear feedforward output logic (see Figure 5.4). LFSRs are amenable to analysis, and provide a register through which flows a steady stream of pseudorandom bits. Non-linear feedforward logic is added for several rea- sons; it suffices to say that the effect of this addition is to make the struc- ture of the shift register difficult to determine rapidly from observations of the output sequence. 5.2 LINEAR RECURSIONS 5.2.1 Fibonacci Generators A sequence {bn} of elements from a field F is said to satisfy a linear recur- sion if there exists a relation of the form bn== for all n, (5.6) which allows each sequence element to be calculated from the M immedi- ately preceding elements. The coefficients a in (5.6) are from the same field F , and, assuming am # 0, M is called the degree of the linear recursion. A sequence generator based on (5.6) can be constructed as shown in Figure 5.5. When properly initialized with the first M elements of the desired sequence, this shift register will, without further inputs, produce the remain- der of the periodic infinite-length sequence {bn}. A generator, structured as shown in Figure 5.5, is often said to be in the Fibonacci configuration (after the mathematician who studied linear recursions) to distinguish it from other LFSR forms. Every periodic sequence {bn} satisfies an infinite number of linear recur- sions, including the obvious recursions bn=bn+mn for all integers m