# Confused by the definition of Linear Complexity of an LFSR sequence?

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.

• $\{0,1\}$ is not a sequence but a set. Mind the notation. – Henno Brandsma 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.
• 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. – fgrieu Aug 18 '18 at 10:37