Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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