Quick background: The output of a Linear Feedback Shift Register (LFSR) with length $n$ is a binary sequence which is periodic of length dividing $2^n-1$. From a mathematical point of view, such a sequence is constructed recursively as follows: each state of the LFSR with length at most $n$ (such a state is an element of ${\mathbb{Z}_2}^n)$ is constructed using the previous state $s$ by "shifting" $s$ to the right and inserting a new bit $f(s)$ to the left-most position, where $f$ is a linear boolean function of degree $n$ corresponding to the LFSR (the feedback function. The right-most bit that is "ejected" from that shift, is the output bit for that state. All those output bits form a binary sequence of period $\leq2^n-1$. A Non Linear Feedback Shift Register (NLFSR) Sequence is one which follows the same principle as above, using however a Non Linear feedback function. Although there is a rich mathematical background and known facts for LFSR's, much less is known for NLFSR's due to their non-linear nature.

My Question: Can every binary sequence of arbitrary length $N$ be expressed as the output of some Feedback Shift Register (Linear or not)?

EDIT: When $N|2^n-1$ for some $n$ there is a $1-1$ correspondence between sequcences of period $N$ and boolean functions in ${\mathbb{Z}_2}^n$ (Golomb, Gong, Signal Design for Good Correlation, 2005). In other words, if a binary sequence has period $N=2^n-1$ for some $n$, there exists a Linear FSR with that ouputs this sequence. Can that be generalized to any $N$?

EDIT 2: So, my question was trivial, see joriki's answer below. I now wonder if we can now say anything about the minimal FSR that outputs a given sequence. For instance, a sequence with (potentially huge) period $N=2^n-1$ can be constructed from a LFSR with only $n$ stages. Can anything similar be said for a general $N$?

  • 1
    $\begingroup$ May be your background was too quick? The period of a sequence generated by an LFSR of length $n$ need not be a factor of $2^n-1$. For example you get period 2 with an LFSR of length two that simply copies the last bit to the first (feedback polynomial $1+D^2$). Also $n$ is not the number of taps. Taps are the positions fed back to be XORed (in a Fibonacci LFSR). The number of taps is thus one less than the number of terms in the feedback polynomial, so the number of taps in an LFSR of length $n$ can be anything between $1$ and $n$. $\endgroup$ – Jyrki Lahtonen Dec 12 '12 at 8:58
  • $\begingroup$ But your question about the generation of sequences with non-linear FSR is very interesting and difficult. I don't know the answer. Some experimenting has been done - I recall J.J.Rushanan from Mitre to have done extensive experimentation with quadratic feedback functions. The theory has the air of being messy. Undoubtedly you have checked what Berlekamp-Massey algorithm will say about minimizing the length of an LFSR generating a given sequence? $\endgroup$ – Jyrki Lahtonen Dec 12 '12 at 9:02
  • $\begingroup$ Also, check out what Dilip Sarwate has written in this site about LFSRs! $\endgroup$ – Jyrki Lahtonen Dec 12 '12 at 9:39
  • $\begingroup$ Indeed, my background was from the top of my head and wrong at times, I have corrected the parts of the question that were wrong, thanks. Indeed, I have been looking around and when it comes to the non-linear case things are messy. Finding NLFSR's with guaranteed long periods is apparently a notoriously hard problem and every now and then somebody may publish a paper examinning a specific family of such sequences, but this is definitely not a question that would get a straightforward answer. As you said, for the linear case, the minimal LFSR is given by the Berlekamp-Massey algorithm. $\endgroup$ – geo909 Dec 12 '12 at 20:54
  • $\begingroup$ The extra bit that I can offer that you may finding are the so called $\mathbb{Z}_4$-linear sequences. These are binary sequences. You may think of them as being generated by an LFSR with entries from $\mathbb{Z}_4$, but you then only take the most significant bit to get a binary sequence. Often you get periods of the form $2(2^n-1)$. If you want to generate such sequences with a binary LFSR you need a long one. Those mod-4 sequences have a relatively high linear complexity (quadratic on $n$) and that spells trouble for LFSRs. $\endgroup$ – Jyrki Lahtonen Dec 12 '12 at 21:05

The answer is trivially yes. Choose $n=N$, start out with the desired sequence in the register, and let the non-linear feedback function return the right-most bit of $s$.

  • $\begingroup$ You're right, that was trivial! Do you also know if we know anything about the minimal FSR which would output a given sequence? For instance, given a sequence with a (potentially huge) period 2^n-1 one can construct a LFSR with only $n$ stages that outputs this sequence.. Are there any similar in nature results for the general period $N$? $\endgroup$ – geo909 Dec 11 '12 at 18:38

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.