3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – kodlu
    May 12 at 3:45
  • $\begingroup$ It seems that SageMath code has some problems, as you noticed. I'll update the question with bozhu $\endgroup$
    – kelalaka
    May 12 at 8:53
2
+100
$\begingroup$

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.

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