Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.)

share|cite|improve this question
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. – Yuval Filmus Feb 14 '11 at 0:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.