3
$\begingroup$

I designed 8 bit lfsr in vhdl. According to mathematical theory, I xor processed the outputs of registers 1, 4, 5, 6 and 8 and connected them to the input of register 1. theory says that if I give the inputs the polynomial "10111000", I get the repetition of (2^8)-1.

I tried some more. And I tried the circuit without connecting the output of the 1st register to the xor gate. interestingly I got the same (2^8)-1 repetition again. however, this time every 8-bit polynomial containing a 1-bit "1" signal produced the same signal. For example, when I gave "00100000" to the inputs, I got the same signal again.

What I'm wondering is why when I bind the output of register 1 to the xor gate I only get the repeat (2^8)-1 with 1 polynomial, while I get it with every polynomial when I don't?

enter image description here

enter image description here

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ By "give the input the polynomial 01000" you mean the loading of the LFSR? The question is unclear. Draw a diagram. Or state what the characteristic polynomial is, and what is the numbering of LFSR bits that you are using. It is absolutely impossible to get a full period when you disconnect register 1 [which is at one end] since you no longer have an LFSR of length 8. $\endgroup$
    – kodlu
    Apr 13 at 1:58
  • 1
    $\begingroup$ I added 2 images. If I make my circuit as in the first image, I get a repetition of (2^8)-1 when I only give the correct polynomial (ie P= x^8+ x^6 + x^5 x^4 +1) to the register inputs. My circuit works perfectly. If I make my circuit in the second image, no matter what polynomial I give to the inputs (for example, P= x^3+ x^2 + x^5 x^7+1) I get the loop of (2^8)-1. Whereas, if I only give the correct polynomial in the first circuit, I get a loop of (2^8)-1. $\endgroup$
    – Doğukan Karakaya
    Apr 13 at 8:37
  • 1
    $\begingroup$ so I think if your described behaviour is correct something is wrong with your circuits or VHDL code. $\endgroup$
    – kodlu
    Apr 13 at 22:48
  • $\begingroup$ Yes that's true. It was due to a problem in VHDL code. I solved the problem with some fiddling. $\endgroup$
    – Doğukan Karakaya
    Apr 24 at 14:13
  • $\begingroup$ I am glad that you sorted it out. You can accept the answer if it was satisfactory. $\endgroup$
    – kodlu
    Apr 24 at 15:53

1 Answer 1

Reset to default
4
$\begingroup$

OK, it is a question of what the connection polynomial is, the figure helps clarify what you are doing. In both cases the polynomial is degree 8.

Originally, your connection polynomial is $1+x+x^4+x^5+x^6+x^8$ (I wrote it in the order of the LFSR connections). This polynomial is not primitive, it's not even irreducible, with the factorization $$ 1+x+x^4+x^5+x^6+x^8=(x+1)^2(x^4+x^3+1)(x^2 + x + 1) $$ so there is no question of obtaining the full period of $2^\text{degree}-1=2^8-1$ from it. Depending on the loading it will give shorter periods but never full period. See this question Non primitive lfsr sequence for more info on what periods are possible.

When you change the connection you have the polynomial $1+x^4+x^5+x^6+x^8$ which has no factorisation into a product of lower degree polynomials (so it is irreducible). This polynomial is actually primitive and will give a maximum possible length sequence with period $2^8-1.$

See also Wikipedia here. I have used the following commands on Magma to check these properties.

R:=PolynomialRing(GF(2)); f:=1+x+x^4+x^5+x^6+x^8; IsPrimitive(f); Factorisation(f); f:=1+x^4+x^5+x^6+x^8; IsPrimitive(f); Factorisation(f);

with output

false

[ <x + 1, 2>, <x^2 + x + 1, 1>, <x^4 + x^3 + 1, 1> ]

true

[ <x^8 + x^6 + x^5 + x^4 + 1, 1> ]

Gadiel Seroussi has given a very long list of primitive polynomials up to degree 10,000 here.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Addition: Jörg Arndt has lists of binary primitive and irreducible polynomials to degree 11. Note: All binary irreducible polynomials have an odd number of terms including high-order and 1 (the later corresponding to the output of the XOR in the convention of the answer). This is equivalent to an even number of inputs to the XOR. Thus counting the 5 inputs to the XOR is enough to disprove that the first drawing yields (minimal) period $2^8-1$, regardless of initial state. $\endgroup$
    – fgrieu ♦
    Apr 13 at 11:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.