3
$\begingroup$

Is there a way to construct a linear feedback shift register (LFSR) which outputs no more than k consecutive 1s or 0s? (It would have to be not a maximal-length LFSR, of course, if k < the degree of the characteristic polynomial)

edit: I am also looking for one where the period is at least 1/16 the maximum period of the LFSR.

(clarification: exclude the trivial case of all zeros. Also, I can initialize the LFSR to an arbitrary vector.)

  • 0
    You need to add some conditions. If the LFSR is to work for each initialization, then init it with zeroes to get a contradiction. Otherwise, every periodic sequence is output by an LFSR (use $x^n+1$), and it's easy to construct one without more than $k$ consecutive identical bits.2011-02-14

0 Answers 0