4
$\begingroup$

Given the first $5$ elements of a binary sequence $x_1 = 0, x_2 = 1, x_3 = 0, x_4 = 0, x_5 = 0$, the subsequent ones are determined as follows:

$$x_{n + 5} = x_{n} + x_{n + 2}$$

(this is an example of Linear Feedback Shift Register).

So,

$$01000010010110 \ldots$$

This sequence is periodic after $31$ elements. How is it possible to prove this?


$31 = 2^5 - 1$ and it can be related to the number of the first assigned elements $x_1, \ldots, x_5$.

I tried to expand the single items $x_i$ as a combination of the first $5$ items till no. $18$, with nothing relevant, except the fact that each $x_i$ can always be expressed as

$$x_i = a_1 x_1 + a_2 x_2 + a_3 x_3 + a_4 x_4 + a_5 x_5$$

where $a_i$ are integer coefficients.

Is this the right appoach to determine the periodicity of the sequence, or other ones are preferable?

$\endgroup$
  • 3
    $\begingroup$ The feedback polynomial is $p(x)=x^5+x^2+1$. This is irreducible over the field $\Bbb{Z}_2=GF(2)$ because A) it has no zeros $GF(2)$, and B) it is not divisible by the unique irreducible quadratic polynomial $x^2+x+1$. Do you see why irreduciblity of $p(x)$ follows? Ok, therefore all the zeros of $p(x)$ are in the field $K=GF(2^5)$. There are $32-1=31$ non-zero elements in $K$. By Lagrange this implies that those zeros have orders that are factors of $31$. Because $31$ is a prime those zeros have order exactly $31$. $\endgroup$ – Jyrki Lahtonen Jan 29 '18 at 14:31
  • 5
    $\begingroup$ @JyrkiLahtonen: I'm wary of your complete answers posted as comments. Why, as a moderator, you do that on a regular basis? $\endgroup$ – Christian Blatter Jan 29 '18 at 18:31
  • 3
    $\begingroup$ @ChristianBlatter A fair question. There are many reasons why I occasionally do this. In the present case I was just genuinely busy with other work, and wanted to add a totally different point of view (hoping that the asker could use it to post an answer themselves). I will flesh this out to a full answer shortly. I will make it CW, because this is more or less straight out of any of the standard books on LFSR sequences. $\endgroup$ – Jyrki Lahtonen Jan 30 '18 at 13:35
2
$\begingroup$

The simple way to prove it is to compute the first $36$ terms and show that $01000$ recurs starting at position $32$ and not before. As the length of the recurrence is $5$ the behavior is determined by five successive terms and you are done. You can do the computation in a spreadsheet computing one term, then copy down for all the rest of the terms.

$\endgroup$
2
$\begingroup$

Any five subsequent elements determine the rest of the sequence, by the recursive formula. There are only $2^5 = 32$ such combinations of five elements possible, which means two things:

  • The cycle, which inevitably occurs, will be at most of length $32$;
  • The cycle will start occurring within $32$ steps.

The actual length of the cycle, and the point at which the cycle starts occurring, depends on the initial conditions: $x_i=0$ for all $i\in\{1\ldots 5\}$ gives a trivial sequence $00000\ldots$), for example. I don't know if there is any proper way, besides trial and error, to find the cycle length based on the initial conditions and the formula alone.

$\endgroup$
  • $\begingroup$ Step nr. 32 defines element nr. 36, but the series is periodic from the start because the recurrence relation also works backwards. $\endgroup$ – random Jan 29 '18 at 14:58
2
$\begingroup$

Your system can be described by the following matrix:

$$\left(\matrix{0&1&0&0&0\\0&0&1&0&0\\0&0&0&1&0\\0&0&0&0&1\\1&0&1&0&0\\}\right)\left(\matrix{x_n\\x_{n+1}\\x_{n+2}\\x_{n+3}\\x_{n+4}}\right)=\left(\matrix{\matrix{x_{n+1}\\x_{n+2}\\x_{n+3}\\x_{n+4}\\x_{n+5}}}\right)$$

Therefore all you need is to prove that the $31$st power of this matrix is the identity over $\mathbb{Z}_2$ (which is true, btw!).

$\endgroup$
2
$\begingroup$

Your sequence of bits comes together with a matching generating function $$ X(t)=x_0+x_1t+x_2t^2+\cdots=\sum_{i=0}^\infty x_it^i\in\Bbb{F}_2[[t]]. $$ Because all the arithmetic is done modulo two, the recurrency relation can be written to read $x_n+x_{n+2}+x_{n+5}=0$ for all $n\ge0$. The sum $x_n+x_{n+2}+x_{n+5}$ appears as the coefficient of $t^{n+5}$ the product $ (1+t^3+t^5)X(t). $ Check this yourself if you have never seen it, but this is really bread&butter in the theory LFSR-sequences. Consult e.g. Solomon Golomb's book.

Anyway, this means that all the terms of degree $5$ or higher in the product $X(t)(1+t^3+t^5)$ vanish. We therefore have the equation $$ X(t)=\frac{A(t)}{1+t^3+t^5}\tag{1} $$ for some polynomial $A(t)\in\Bbb{F}_2[t]$ of degree $\le4$.

Let's continue. Next I claim that the feedback polynomial $P(t)=1+t^3+t^5$ is irreducible in $\Bbb{F}_2[t]$. It is of degree five, so if it were reducible, then it would necessarily have a factor of degree at most two. But, $P(0)=P(1)=1$, so it has no zeros (and hence no linear factors). Nor is it divisible by the only irreducible quadratic polynomial $Q(t)=t^2+t+1$. This is because $Q(t)(t+1)=t^3+1$, so if $P(t)$ were divisible by $Q(t)$ so would be the monomial $t^5$, but that is absurd (by the uniqueness of factorization).

The basic properties of finite fields then tell us that

  • the zeros of $P(t)$ are in the field $\Bbb{F}_{32}$ (aka $GF(32)$) and,
  • therefore the zeros of $P(t)$ have multiplicative order that is a factor of $32-1=31$, and
  • because $31$ is a prime (and $1$ is not a zero of $P(t)$), those zeros have order $31$ exactly.

Consequently $P(t)$ is a factor of the polynomial $t^{31}-1$. In many sources this fact is phrased as follows: the order of $P(t)$ is $31$. The argument outlined in the above sequence of bullets can be written using the concept of the order alone. I did it this way, because I think that on this site less people are familiat with that language.

Anyway, $P(t)R(t)=1-t^{31}$ for some polynomial $R(t)\in\Bbb{F}_2[t]$ of degree $31-5=26$. This allows us to rewrite $(*)$ as $$ X(t)=\frac{A(t)R(t)}{1-t^{31}},\tag{2} $$ where $$ Q(t)R(t)=b_0+b_1tb_2t^2+\cdots b_{30}t^{30}\tag{3} $$ is a polynomial of degree $\le30$.

By the familiar sum formula for the geometric series $$ \frac1{1-t^{31}}=1+t^{32}+t^{2\cdot31}+t^{3\cdot31}+\cdots=\sum_{k=0}^\infty t^{k\cdot31}.\tag{4} $$

Putting $(2),(3)$, and $(4)$ together we see that the coefficients of $X(t)$ follow a repeating period of length 31. A single period can be read from the coefficients of the product $A(t)R(t)$.

A final remark. A user of a linear feedback shift register with this feedback polynomial $P(t)$ can adjust the coefficients of the polynomial $A(t)$ be initializing the LFSR with those coefficients. Some other readers would think of doing the same by declaring another initial segment $x_0,x_1,x_2,x_3,x_4$. All according to which sequence you want to produce. Actually, in this case all the $31$ non-zero initializations simply produce the $31$ cyclic shifts of the same $m$-sequence, but let's leave that for the specialists.

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