1
$\begingroup$

I am trying various combination of LFSR's to try to design sequence of period 1023. The linear span should be 55 and the output 1023 bits has to be balanced.

I have tried with five LFSR's with degree 10 and one LFSR with degree 5, XORing all ..which gives 55 as Linear span and period 1023. However, it is not balanced. With trial and error, I get a balanced output with XORing 9 LFSR of degree 10 and one LFSR of deg 5.

Can anyone give some idea what path to take to solve this ?

$\endgroup$
  • 1
    $\begingroup$ Can you define what you mean by "linear span" and "balanced"? I'm guessing "balanced" means equally distributed outputs? $\endgroup$ – Ella Rose Jul 18 '16 at 20:05
  • $\begingroup$ Balanced means : number of "1" is one more than number of "0" in the output. and Linear span is the addition of all the LFSR's in the design. $\endgroup$ – Niyaz Murshed Jul 18 '16 at 20:08
  • $\begingroup$ I dont think we are allowed to use the same polynomial more than once $\endgroup$ – Niyaz Murshed Jul 18 '16 at 21:15
4
$\begingroup$

The polynomial factorisation of $X^{2^L-1}+1$ into irreducible factors gives you all the polynomials $g_i(X)$ that can be used as LFSR polynomials in generating any sequence of period $2^L-1.$ Say your goal is to generate a sequence of this period with linear complexity $c.$ Assume

$$(X^{2^L-1}+1)=\prod_{i=1}^v g_i(X),$$ there will be no repeated factors. Not all factors will be primitive of course.

Then for each $g_i(X)|(X^{2^L-1}+1),$ find the linear complexity of the periodic sequence it generates, say it is $L_i.$ You can use Berlekamp Massey for this.

If you can find a subset $J\subset \{1,2,\ldots,v\}$ with $\sum_{i\in J}L_i=c,$ then the corresponding polynomials $$g_i(X),\quad i\in J$$ will generate the sequence you need, for some initial conditions. Some of these polynomials will generate a sequence of length dividing $2^L-1$ of course.

More generally, given polynomials $f_i$ and letting $\Omega(f_i)$ be the set of sequences they generate, then $$ \Omega(f_1)+\cdots+\Omega(f_v)=\Omega(lcm(f_1,\ldots,f_v)), $$ and this has been known since the 1950s, published by Zierler in 1959, in Siam Journal of Discrete Maths.

Another good and accessible but somewhat dated reference is the book by Rueppel, The Analysis and Design of Stream Ciphers.

Appendix:

Magma online calculator gives the following factors for $X^{1023}+1$ (truncated)

X + 1, X^2 + X + 1, X^5 + X^2 + 1, 1>, other degree 5 factors, X^10 + X^3 + X^2 + X + 1, other degree 10 factors

so what you found experimentally is not surprising.

Edit: As I alluded to, and this holds for any characteristic, but I will state it for binary, given any sequence $s(t)$ over $F_2$ with period dividing $2^L-1$ (and thus for period equal to $2^L-1$) there is an appropriate trace expansion for that sequence of the form $$ s(t)=\sum_{i \in J} tr^{L_i}_1(\theta_i \alpha^{i t}) $$ and each of those trace sequences are some cyclic shift of some maximal length sequence (equivalently some cyclic shift of the output of some primitive LFSR) with length $L_i | L,$ where $L_i$ is the number of elements in the cyclotomic coset of $i$ modulo $2^L-1.$ So if a sequence with the parameters you want exists (w.r.t. linear complexity) it can be constructed this way.

$\endgroup$
  • $\begingroup$ Is it possible to full fill all three conditions and design the desired system ? $\endgroup$ – Niyaz Murshed Jul 19 '16 at 1:23
  • $\begingroup$ The only issue is the linear complexity you desire, it may or may not be possible, given this decomposition. Otherwise, as I stated, every desired sequence of period $2^L-1$ can be obtained this way. $\endgroup$ – kodlu Jul 19 '16 at 4:45
  • $\begingroup$ Is there a way to get the LFSR from the DFT spectrum of the output series ? $\endgroup$ – Niyaz Murshed Jul 19 '16 at 21:24
  • $\begingroup$ Blahut's theorem states you can get the linear complexity from the DFT. Not the LFSR, though. Plus most sequences are nonlinear. $\endgroup$ – kodlu Jul 20 '16 at 3:10
1
$\begingroup$

This is really an extended comment followed by a suggestion.

You have the basic design down correctly, and are asking the wrong question.

Take five LFSRs with feedback polynomials that are different primitive binary polynomials of degree $10$, and one LFSR with feedback polynomial that is a primitive binary polynomial of degree $5$. Load each LFSR with a nonzero initial condition. Then, when the LFSRs are clocked with a common clock and the $6$ output bits are XORed together to result in just one bit, the sequence $x$ (of XORed bits) thus generated has period $1023$ and linear complexity $55$. If you want to verify this, run the Berlekamp-Massey algorithm on $x$, and you will find that

  1. The shortest LFSR that can generate $x$ is of length $55$

  2. The feedback polynomial of this length-$55$ LFSR is the product of the six feedback polynomials that you have chosen

  3. The initial loading of this long register is just the first $55$ bits of $x$.

Indeed, if you are willing to take #1 above on faith, you can readily compute the degree-$55$ feedback polynomial directly (that is, without generating $x$ first), but you will need to generate the first $55$ bits of $x$ to get the initial loading of the long LFSR.

What $x$ does not necessarily have is balance. Many sequences generated by the set-up described above are indeed balanced. If we categorize the possible output sequences simply as balanced or unbalanced, then the balanced sequences can be far fewer than the unbalanced sequences, but if we categorize the sequences by the degree of imbalance, then the balanced sequences are a plurality (and sometimes even a majority).

Be that as it may, finding (nonzero) initial conditions that will give a balanced sequence is a non-trivial task. Trial-and-error could be attempted, but the search space is large. This is the question you should have been asking, and it would more likely be answered on math.SE (where one of the moderators is an expert on coding theory).

I suggest that you ask the moderators of crypto.SE to migrate this question to math.SE. Please don't just repost it there, which will lead to unnecessary duplication of effort.

$\endgroup$
  • $\begingroup$ Hey thanks, I tried the trial and error method. I managed to get a combination which gives the required properties. I could paste the solution here here if required.....or maybe wait for someone else to ask in future !! $\endgroup$ – Niyaz Murshed Jul 24 '16 at 3:49

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.