A binary linear-feedback shift register of degree updates a -bit state by shifting and inserting a fixed linear combination over . With recurrenceits feedback polynomial is .
A feedback shift register updates a finite state by shifting its stored symbols and inserting the value of a feedback function of the previous state. The feedback function need not be linear.
The Berlekamp-Massey algorithm finds the shortest linear recurrence satisfied by a finite sequence over a field. It processes symbols incrementally, updating the connection polynomial whenever the current recurrence has a nonzero discrepancy.
The shortest binary linear recurrence producing the prefix has length three:Its connection polynomial is .
A degree- binary register has states. The zero state is fixed, so a nonzero periodic orbit has length at most .
A maximal-period feedback polynomial cannot have as a root. Over , this saysso an even number of the coefficients equal one and the full monic polynomial has an odd number of nonzero coefficients.
If an output prefix contains consecutive zeros followed by a one, no register of degree at most can generate it: the all-zero state would have been reached and would remain zero forever.
The seven consecutive zeros followed by one force degree at least eight. Degree eight is attained by , with initial state and feedback polynomial .
Let , let generate , and let be nonzero linear with nondegenerate bilinear form . If the minimal polynomial of is , then satisfiesso it is produced by an LFSR of length at most . Its period is exactly : any period would imply for every , hence by nondegeneracy.
Articles by others on the same topic
A Linear Feedback Shift Register (LFSR) is a type of sequential circuit that consists of a shift register and a linear feedback mechanism. It is widely used in digital systems for a variety of applications, including pseudorandom number generation, cryptography, error detection and correction, and digital signal processing.