1
$\begingroup$

What is the total length for the sequence for a linear feedback shift register generated with a maximum length sequence, before repeating?

$\endgroup$
  • $\begingroup$ There can be no general answer: if you built a LFSR with relay technology, you'd get maybe two operations per second, if you built it in RF/high-speed semiconductor technology, you might get a couple dozen billion operations per second. The speed at which a semiconductor LFSR works is a direct result of the substrate, gate charge (and thus, gate size), power consumption and all in all, device cost, and can scale over multiple orders of magnitude. $\endgroup$ – Marcus Müller May 29 '17 at 12:01
  • 1
    $\begingroup$ Your question is an XY Problem: you have to solve a problem X, and think that solving Y gives you a solution, but in reality, Y is a "strange" question to ask, and the experts (in this case: us) are left to wonder why you even ask about Y. Don't forget to mention X and why you think Y is significant for your problem! $\endgroup$ – Marcus Müller May 29 '17 at 12:02
  • $\begingroup$ Also, this is a electrical engineering question, and not a signal processing question, so it's off-topic here. $\endgroup$ – Marcus Müller May 29 '17 at 12:02
  • 1
    $\begingroup$ I'm voting to close this question as off-topic because it belongs on electronics.stackexchange.com, not here. $\endgroup$ – Marcus Müller May 29 '17 at 12:03
  • 2
    $\begingroup$ @MarcusMüller I think it is a valid signal processing question if I understood correctly that the OP is simply asking how long an LFSR takes to cycle through its complete sequence before repeating. Perhaps the question needs to be better stated but that is how I read it. (Also I had coffee with your colleague and my good friend Neel yesterday!) $\endgroup$ – Dan Boschen May 29 '17 at 14:08
4
$\begingroup$

The duration of the linear feedback shift register (LFSR) in number of "chips" is $2^N-1$ where N is the number of states in the shift register (and order of the generator polynomial), and chips refers to each unique output that is generated in the sequence. This is assuming that you are using a maximum length sequence in the implementation of your shift register, which means the generator polynomial is both primitive and irreducible in GF(2).

Primitive: Repeated multiplying by x (representing a shift of one position in the shift register) will generate every possible state (except for the all 0 state). If the generator is not primitive, possible states (combinations of the register values) will be skipped and the sequence will be less than $2^N-1$ in length before repeating.

Irreducible: Cannot be factored, see example:

Reducible: $1+x+x^2+x^3 = (1+x^2)(1+x)$

Irreducible: $1+x+x^3$

Note the above polynomials are in GF(2) so the only elements are 0,1. 1+1=0, 0-1=1, etc

All primitive polynomials are irreducible but the converse is not true!

Primitive and irreducible polynomials are well tabulated. For a handy table of primitive and irreducible polynomials in GF(2), see Peterson's Table of Irreducible Polynomials

The graphic below shows the two common implementation approaches for the LFSR from the generator polynomial, in this case N=4, using generator polynomial $1+x^3+x^4$ which would generate $2^4-1=15$ chips before repeating:LFSR Implementation

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.