1
$\begingroup$

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
    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$.2012-12-12
  • 0
    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?2012-12-12
  • 0
    Also, check out what Dilip Sarwate has written in this site about LFSRs!2012-12-12
  • 0
    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.2012-12-12
  • 0
    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.2012-12-12
  • 0
    Thanks, I have heard about those sequences but didn't know what they were.2012-12-12

1 Answers 1

3

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

  • 0
    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$?2012-12-11