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

  • 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