5
$\begingroup$

Consider the following excerpt from Rueppels paper, titled When Shift Registers Clock Themselves:

Excerpt from Rueppel's paper

His example includes $C(D) = 1 + D + D^2 + D^3 + D^4 + D^5$ as a primitive connection polynomial. However, this polynomial is not irreducible, let alone primitive, since it can be factored as $(1+D)(1+D+D^2)^2$ over $\text{GF}(2)$.

What am I missing?

$\endgroup$
3
  • $\begingroup$ Is your question regarding the hardware or just the mathematics. You would be required to have 5 flip-flops, whether or not it is irreducible. The single vs. double clocking is interesting as it effectively behaves as adding some logic between blocks. $\endgroup$
    – b degnan
    Oct 8 '17 at 0:29
  • $\begingroup$ @bdegnan I've come to this question, dunno why, It took 15 minutes to code -with a library- to see the error in the article. $\endgroup$
    – kelalaka
    Apr 14 at 16:05
  • 1
    $\begingroup$ @kelalaka I really have no idea how you found this again. :) $\endgroup$
    – b degnan
    Apr 14 at 17:29
1
$\begingroup$

There is a typo in the article. The primitive polynomial must be $$x^5 + x^4 + x^3 + x^2 + 1$$


The easiest way to see that there is a mistake or not is coding!

There is an almost good pylfsr library. This library also lists primitive polynomials in their format.

L.get_fpolyList(m=5)

  • [5, 2]
  • [5, 4, 2, 1]
  • [5, 4, 3, 2]

The list verified, too.

  • $x^5 + x^2 + 1$
  • $x^5 + x^4 + x^2 + x^1 + 1$
  • $x^5 + x^4 + x^3 + x^2 + 1$

I've created a python program to test these. Luckily I've found it on the first try!

import numpy as np
from pylfsr import LFSR

state = [1,1,1,1,1]
fpoly = [5, 4, 3, 2]
L = LFSR(fpoly=fpoly,initstate =state, verbose=False)
L.info()

for i in range(1,21):
    print(L.state[-1], end=",")
    if L.outbit == 0:
        L.next()
    else :
        L.next()
        L.next()
print("\n")
print("1,1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1")  

It produces the output

5 bit LFSR with feedback polynomial  x^5 + x^4 + x^3 + x^2 + 1
Expected Period (if polynomial is primitive) =  31
Current :
 State        :  [1 1 1 1 1]
 Count        :  0
 Output bit   :  -1
 feedback bit :  -1
 1,1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1,

 1,1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1

Thanks to Nikesh Bajaj to indicate better usage of the library ( See in the other library).

Therefore there is a typo in the article. The primitive polynomial must be $$x^5 + x^4 + x^3 + x^2 + 1$$

$\endgroup$
1
$\begingroup$

Answer to WHY -1? [Updates: Fixed pylfsr]

The output of LFSR is indeed the last bit of intial state, but there is no output bit, if no clock cycle (L.next()) is excuted. -1 has been intentionally used to show that LSFR has not been passed any clock.

The print line should be at end not in start.

import numpy as np
from pylfsr import LFSR

state = [1,1,1,1,1]
fpoly = [5, 4, 3, 2]
L = LFSR(fpoly=fpoly,initstate =state, verbose=False)
L.info()

for i in range(1,21):
    if L.outbit == 0:
        L.next()
    else :
        L.next()
        L.next()
    print(L.outbit, end=",")
print("\n")
print("1,1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1") 

Output:

5 bit LFSR with feedback polynomial  x^5 + x^4 + x^3 + x^2 + 1
Expected Period (if polynomial is primitive) =  31
Current :
 State        :  [1 1 1 1 1]
 Count        :  0
 Output bit   :  -1
 feedback bit :  -1
1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1,1,

1,1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1

Due to clock consideration, this is a shifted version of the output sequence. An alternative code to produce exact response is here

state = [1,1,1,1,1]
fpoly = [5, 4, 3, 2]
L = LFSR(fpoly=fpoly,initstate =state, verbose=False)
L.info()

for i in range(1,21):
    print(L.state[-1], end=",")
    if L.outbit == 0:
        L.next()
    else :
        L.next()
        L.next()
    #
print("\n")
print("1,1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1") 

which produces:

5 bit LFSR with feedback polynomial  x^5 + x^4 + x^3 + x^2 + 1
Expected Period (if polynomial is primitive) =  31
Current :
 State        :  [1 1 1 1 1]
 Count        :  0
 Output bit   :  -1
 feedback bit :  -1
1,1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1,

1,1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1

UPDATE

Thanks @kelalaka for pointing out. I have fixed the issue in updated version=1.0.5 of pylfsr, with an additional parameter counter_start_zero, which initialize the output bit with -1, untill first clock is passed. So your original code produces the expected answer by either setting counter_start_zero=False or executing L.next() before checking the first output. See here detail

So yes, there is a typo in the article, x^5+x^4+x^3+x^2+1 is correct primitive polynomial, which can also be verfying by three properties (1) balance (2) runlength (3) autocorrelation

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