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

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

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$$?

• Actually for your original sequence $s_n=s_{n-1}+s_{n-2}$ so I don't understand the Sage output. The LC should be 2. And 8 for the expanded sequence by filling in zeroes May 12, 2021 at 3:45
• It seems that SageMath code has some problems, as you noticed. I'll update the question with bozhu May 12, 2021 at 8:53

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.