What is the linear complexity of a modified LFSR sequence with a fixed length of zeroes inserted between every pair of successive terms

Question

There was a deleted question that asked;

We know that if $n$ zeros are inserted between every pair of successive terms of the sequence in LFSR (variable changed $x$ to $x^n$) then linear complexity (shortest LFSR which produces the given seq) will be $n$ times the original one.
My question is that: in the new sequence what is the period (assume period of original one is $p$)

The period was easy to answer;

Let $m$ be a sequence output from $L$ bit maximal LFSR. Then we know that the period of the sequence $m$ is $2^L-1$

Let $m'$ be the modified sequence of $m$ such that for every two successive elements $n$ zeros are inserted. An example with $n=3$

   m  = 1   1   0   1   1   0   1
   m' = 1000100000001000100000001000

It is obvious that the period of $m'$ is $(2^L-1)\cdot n$. One can prove this with a counter-argument; if the period is smaller, then remove the added zeroes to find a smaller period for $m$.

What about the linear complexity?

I couldn't see a general rule for this; My was example already a counterexample for the multiple; run with SageMath code the online;

[1,1,0,1,1,0,1,1] has x^2 + x^1 + 1
[1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0] has x^8 + x^4 + 1

and for the $n=1$ case;

[1,1,0,1,1,0,1,1] has x^2 + x^1 + 1
[1,0,1,0,0,0,1,0,1,0,0,0,1,0] has x^4 + x^2 + 1
[1,1,0,1,1,1,1,1] has x^4 + x^3
[1,0,1,0,0,0,1,0,1,0,1,0,1,0] has x^7 + x^5

Is there a work or a result on the bounds of the Linear complexity of $m'$ related to $L$ and $n$?

Answer 1

There are no general lower/upper bounds that are not combinatorial in nature.

If you have a sequence $S=(s_0,s_1,\ldots,s_{N-1})$ which has period $N$ over a finite field $\mathbb{F}_q$ there are two related formalisations of the linear complexity $L(S)$ of the sequence. The first one is the classical

$$L(S)=N-\deg(\gcd(S^N(x),x^N-1)),\tag{1}$$

where $S^N(x)=s_0+s_1x+\cdots+s_{N-1} x^{N-1}.$

Now, for $q=2,$ which is what we are interested in, $x^N-1$ has a canonical factorisation as $$ x^N-1=\prod_{t=1}^h f_t(x)\quad with\quad f_t(x)=\prod_{j \in C_t} (x-\alpha^j) $$ where $\alpha$ is an element of order $N$ in $\mathbb{F}_{q'}$ which is defined to be the smallest extension field containing an element of that order. Then the degree of the gcd in (1) can be written as a sum of cardinalities of cyclotomic cosets modulo $N.$

If you insert $k-1$ zeroes between each symbol, for $k\geq 2,$ to obtain a new sequence $S'$ of period $kN,$ it is straightforward to see that the new linear complexity is $$L(S')=kN-\deg(\gcd(S^N(x^k),x^{kN}-1))\tag{1}$$

A related characterisation can be made using a finite field valued (not complex-valued) DFT. Firstly you need enough points in the finite field $GF(q')$ over which you will define the DFT to make it one-to-one, thus $q'\geq N$ is needed. For the arithmetic operations leading to the DFT to make sense, $\mathbb{F}_q$ must be a subfield of $\mathbb{F}_{q'}.$

If you can find $\mathbb{F}_{q'}$ such that $\gcd(q',N)=1,$ you can define the DFT vector of the sequence $S$ as

$$ A=[a_0,\ldots,a_{N-1}] $$ where $$ a_j=\sum_{i=0}^{N-1} s_j \alpha^{ij},\quad j=0,\ldots,N-1 $$ and all arithmetic is in $\mathbb{F}_{q'}.$

A relationship called Blahut's Theorem in coding theory literature states that the Linear Complexity $L(S)$ is equal to the Hamming Weight (over $\mathbb{F}_{q'}$) of the DFT vector $A.$

Note: Some of the algebraic details of this answer can be found for example in Lidl and Niederreiter's Introduction to Finite Fields book.