A binary linear-feedback shift register of degree updates a -bit state by shifting and inserting a fixed linear combination over . With recurrence
its feedback polynomial is .
Under the convention that a register emits each shifted-out symbol, its first output symbols are exactly its initial fill. Thus a binary register of length has distinct outputs from nonzero fills. For lengths , at least one longer-register output is absent from the shorter register, guaranteeing a pair of unequal nonzero outputs. The two sets need not be disjoint: recurrences and both generate constant ones. Nor must they intersect: the length-one recurrence and have no common nonzero output, since constant ones fail the second recurrence.
The feedback polynomial records the coefficients of an LFSR recurrence. With the convention
it 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 a shortest linear recurrence consistent with a finite sequence over a field. It returns a register length and a connection polynomial such that
Missing coefficients are zero; for a finite prefix the polynomial degree of can be less than . The output describes the shortest recurrence for the observed prefix, rather than proving how an unknown infinite sequence continues.
Initialize , , , and . At index , compute the discrepancy . If , increase by one. Otherwise save and replace by . If , also set , , , and ; if , only increase . The saved discrepancy cancels the current failure of the linear recurrence, while the update of accounts for the extra memory it requires.[ref]
For the binary prefix , the result is and , corresponding to over the field with two elements. This is useful both in analyzing a linear-feedback shift register and in constructing a BCH code error-locator polynomial.
Suppose a connection polynomial of degree at most , with recurrence span gives zero recurrence discrepancies through index but a nonzero discrepancy at . If a polynomial of span successfully explains the prefix through and , evaluate the coefficient at in the convolution . Applying first makes it zero. Applying first leaves its nonzero discrepancy at , because the earlier discrepancies vanish and has constant coefficient one. This contradiction gives the displayed lower bound. It is the minimality step used by the Berlekamp-Massey algorithm; the algorithm cancels the new discrepancy with a shifted earlier failed polynomial.
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 .
For a binary linear-feedback shift register of length , a feedback polynomial with maximal period cannot have as a polynomial root. A root at would make the nonzero all-one state fixed, whereas maximal period requires all nonzero states to lie in one cycle of length greater than one.
Writing the monic polynomial as , this gives
Over the field with two elements, an even number of the feedback coefficients must therefore equal one, and has an odd number of nonzero coefficients. This is a necessary condition, not a sufficient test for a primitive polynomial. The restriction matters: for , has maximal nonzero-state period despite having as a polynomial root.
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 satisfies
so it is produced by an LFSR of length at most . Its period is exactly : any period would imply for every , hence by nondegeneracy.

There are no discussions about this article yet.

Articles by others on the same topic (1)

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.