The Linear Complexity of a sequence is defined as the length of the shortest LFSR that produces this sequence. It also corresponds to the degree of the minimal polynomial ( i.e. the smallest reccurence produce the sequence) of the sequence.

Now consider the sequence {0,1} the degree of the minimal polynomial is equal to 1 therefore the LC must be equal to 1, but we need an LFSR of length 2 including both 0,1 (an arrow going out from stage 0 box, to backward feedback itself). No need a connection coefficient for stage 1 box. Thus LC is equal to 2 according to this definition.

So there must be a problem in the definition of LC being equal to the length of smallest LFSR? It looks like if the definition would be the "length of the LFSR for the periodic part or nondegenerate part of the sequence" then the two definitions would coincide.

Which definition is correct? What is the Linear Complexity of this sequence; 1 or 2, and why?

By the way both definitions are from Rueppel's book.

  • 2
    $\begingroup$ $\{0,1\}$ is not a sequence but a set. Mind the notation. $\endgroup$ Aug 18 '18 at 10:39

Length 2: one tap at the rightmost cell, going back into the left side without further additions. Starting with initial filling $01$ we get the sequence $101010\ldots$. The same sequence can also be achieved with two taps on both cells and the xor of them going in the left and the same initial filling. With register length $1$ only constant sequences are possible in Rueppel's definition: I don't think he even really considers such trivial cases.

So (10)* has linear complexity 2.

  • $\begingroup$ This is the correct answer. Yet, a singe-tap LFSR with the output fed to input thru an inverter generates the sequence (10)* and would have LC of 1 per a different definition allowing free inverters. $\endgroup$
    – fgrieu
    Aug 18 '18 at 10:37
  • 2
    $\begingroup$ @fgrieu Rueppel does not allow for inverters, IIRC. $\endgroup$ Aug 18 '18 at 10:38
  • 1
    $\begingroup$ @fgrieu As you will recall, the L in the acronym LFSR stands for Linear and thus feeding the output back to the input through an inverter is not allowed in the definition of linear complexity. $\endgroup$ Aug 18 '18 at 14:26
  • $\begingroup$ well, with { 01}, I actually mean a finite part of a sequence. Please think of as if I am calculating the Linear Complexity Profile of a periodic sequence such as: 10010011111000.. According to the rules of the Linear Complexity Profile of a sequence, we take finite parts and calculate the lenght of the shortest LFSR which produces that part, ignoring the rest of the sequence each time. $\endgroup$
    – esra
    Aug 18 '18 at 18:15
  • $\begingroup$ @esra you have to take the minimal sequence that repeats. All LFSR sequences have a finite period. $\endgroup$ Aug 18 '18 at 18:21

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.