2
$\begingroup$

I have a school assignment where the problem lies in finding the cycle set of two different polynomials.

I tried to look up different tools on how to solve these problems, but I have a hard time finding it.

If anyone were so kind to help me, solve but also, understand the way to figuring things like this out.

The problem states:

Determine the cycle set for these polynomials:

$x^4 + x^2 + 1$ over $F_2$.

$x^3 + x + 1$ over $F_3$.

Thanks!

$\endgroup$
  • 2
    $\begingroup$ You should be able to do this by hand. Pick an element like 1, and step through the LFSR transformations. 1, x, x^2, x^3, x^2 + 1, ... That might leave out some elements, pick one of those and start over. $\endgroup$ – bmm6o Dec 17 '16 at 0:55
3
$\begingroup$

This is quite combinatorial in nature and the suggestion in the comment is exactly how one would do small examples. General results are much more complicated for arbitrary polynomials, but simple for primitive polynomials.

If the generating polynomial $f$ of degree $d$ over $F_q$ is primitive (i.e., $f$ is irreducible, and has a root in the splitting field of order $q^d-1,$) then the cycle length is maximal, and equal to $q^d-1$ for any nonzero loading, and is otherwise a single cycle at zero.

If the generating polynomial $f$ is not irreducible but is a product of irreducibles, the cycle structure can get quite messy.

Most generally, form the companion matrix $C_f$ of the polynomial $f$ of degree $d,$ which is a $d\times d$ polynomial over $F_q.$ Then the length of any cycle that can be generated by the given degree $d$ polynomial divides the order of $C_f$ in the general linear group $GL(F_q,d)$ of $d\times d$ invertible matrices where the group operation is matrix multiplication. This means that the length of any cycle will be a divisor of $$ q^{k(k-1)/2}(q-1)(q^2-1)\cdots (q^d-1) $$ and this is all we can say in general.

$\endgroup$
2
$\begingroup$

Now that I have some time, I'll turn my comment into an answer.

For small cases like your homework problem, you can manually calculate the cycle sets. In any LFSR that you would actually use in practice, this is not feasible. The idea is simply to pick an initial value and look how it progresses under the LFSR transform. You always know that there's the fixed point {0}. Then you might as well start with 1. In your first example, the first few values are $\{1, x, x^2, x^3\}$. The next value is $x^4$, but since we are reducing mod $x^4 + x^2 + 1$, we have $x^4 \equiv x^2 + 1$. So the next two values are $\{x^2 + 1, x^3 + x\}$. After that, the next value is 1 again and the cycle repeats. The cycle we found has 5 elements, which is one of the possible cycle lengths (they must divide $q^n-1$ = 15). If you had calculated a cycle of length 4 or 6 you would know that you had made a mistake somewhere. Pick an element we haven't seen yet, and repeat the process. $\{x+1, x^2 + x, ...\}$.

The process is identical for the second example, it's just that the math is a little different. We again start out $\{1, x, x^2\}$. Since $x^3+x+1\equiv 0, x^3\equiv 2x+2$, the cycle continues $\{2x+2, 2x^2+2x\}$. The field in this example is going to have 27 elements. Since our cycle is longer than 2 it will have length 13 or 26.

$\endgroup$
  • $\begingroup$ why do you say $x^3+x+1\equiv 0, x^3\equiv 2x+2$ and not $x^3+x+1\equiv 0, x^3\equiv x+1$? $\endgroup$ – user5389726598465 Mar 19 '19 at 22:01
  • 1
    $\begingroup$ @user5389726598465 The field in the second example is $F_3$, where -1 $\equiv$ 2. $\endgroup$ – bmm6o Mar 20 '19 at 16:19

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.