Anyone know what LFSRs are?

General discussion about LÖVE, Lua, game development, puns, and unicorns.
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Anyone know what LFSRs are?

Post by Gunroar:Cannon() »

I randomly ended up reading about LFSRs when someone asked me a question related to them because they heard I was good with computers (:rofl:) So in approx. 30 minutes I got the basic understanding of them and what they do.
Then I was confused as to how to use a polynomial to get a tap and a bunch of other things, and then I realized I could ask here :awesome:

So I found a table that shows what taps to use for which length, and that the degree of the polynomial is the length of the lfsr? Is that right? And then the question implied that you could use the input of 3 primitive polynomials for one LSFR but I didn't see that anywhere else.

Is this making sense to anyone?
Attachments
* just means it's a prime number in case you wandered
* just means it's a prime number in case you wandered
media-1062054-lfsr-01-04.gif (7.09 KiB) Viewed 1749 times
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
User avatar
pgimeno
Party member
Posts: 3544
Joined: Sun Oct 18, 2015 2:58 pm

Re: Anyone know what LFSRs are?

Post by pgimeno »

Gunroar:Cannon() wrote: Wed Jan 04, 2023 11:15 am So I found a table that shows what taps to use for which length, and that the degree of the polynomial is the length of the lfsr? Is that right?
Yes, though originally it's the other way around: you choose a polynomial degree, then a primitive polynomial, and then you take the degree of the polynomial as binary length and the degrees of its non-zero monomials [edit: except the highest-degree one - forgot to specify that, see next posts] as taps.
Gunroar:Cannon() wrote: Wed Jan 04, 2023 11:15 am And then the question implied that you could use the input of 3 primitive polynomials for one LSFR but I didn't see that anywhere else.
That'd be three LFSRs combined, each with its own polynomial, not one LFSR out of 3 polynomials. It's indeed possible to combine the outputs of any number of LFSRs:
https://www.oreilly.com/library/view/co ... ec8.7.html
But it doesn't make sense to combine LFSRs if they have equal lengths. If you have two sequences with period 2^n-1, their XOR still has period 2^n-1; also I wouldn't be surprised if the combination is equivalent to another LFSR with a different polynomial, so you'd rather use that one instead. But if their periods are relatively prime, you have a combined period which is their product, i.e. you have a sequence with a bigger period. That's valid for any pair of sequences with known periods, not just for LFSRs. For example if you had a LFSR of degree 2 (length 2^2-1 = 3) and another one of degree 3 (length 2^3-1 = 7) then you would have a combined output of length 21. For example, say the first generator's full output before repeating again is 1 0 1, and the second's is 1 1 1 0 1 0 0. You would have:

Code: Select all

                    Point at which both sequences are in sync again
                                          |
|1 1 1 0 1 0 0|1 1 1 0 1 0 0|1 1 1 0 1 0 0|1 1 1 0 1 0 0|1...  1st. LFSR
|1 0 1|1 0 1|1 0 1|1 0 1|1 0 1|1 0 1|1 0 1|1 0 1|1 0 1|1 0...  2nd. LFSR
----------------------------------------------------------------
|0 1 0 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 0 0 1|0 1 0 1 1 1 1 1...  XOR
                                          ^
                            Period of the XOR = 7x3 = 21
You can in turn apply another sequence to that result; the new sequence would need to have a period which is relatively prime to that extended one, and you'd extend the period once again.
Last edited by pgimeno on Wed Jan 04, 2023 8:45 pm, edited 1 time in total.
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Re: Anyone know what LFSRs are?

Post by Gunroar:Cannon() »

Heheh, I summoned the great pgimeno-sama ^^

Okay, okay. I'm looking at the first half of your reply for now about the degree of a monomial being the taps.

So this primitive polynomial
x^4 + x^1 + 1
Has 3 monomials and it's taps are {4,1,0}? And then does that render that table I posted above not applicable?
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
User avatar
pgimeno
Party member
Posts: 3544
Joined: Sun Oct 18, 2015 2:58 pm

Re: Anyone know what LFSRs are?

Post by pgimeno »

Gunroar:Cannon() wrote: Wed Jan 04, 2023 8:24 pm So this primitive polynomial
x^4 + x^1 + 1
Has 3 monomials and it's taps are {4,1,0}? And then does that render that table I posted above not applicable?
Sorry, I should have specified. The highest-degree monomial (the one that gives the degree of the polynomial) doesn't count. The taps would be 1, 0.

I haven't checked if x^4 + x^1 + 1 is primitive. Assuming it is, note that the table doesn't exhaustively list all primitive polynomials for a given degree (bit length); it just provides one for each.

Edit: Wait, those taps are numbered in the opposite way to how polynomial division works. For a 16th degree polynomial, for example, tap 15 corresponds to the monomial of degree 0, tap 14 to degree 1, ..., tap 0 to degree 15. So, actually (polynomial degree - 1 - monomial degree) gives the tap number. In the case of x^4 + x^1 + 1, the taps, following the convention of that table, would be 4 - 1 - 1 and 4 - 1 - 0, i.e. 2 and 3. The clue is that degree 0 (the 1 at the end) should always be present for the polynomial to be primitive, but the table shows many entries which lack a tap 0, even though all have tap (degree-1).

So, if the table is correct, then for example this entry: 16 65,535 [1, 2, 4, 15] means that the polynomial x^16 + x^14 + x^13 + x^11 + 1 is primitive. It isn't the only primitive polynomial of degree 16; for example the CCITT CRC polynomial, x^16 + x^12 + x^5 + 1 is also primitive. Edit: Sorry, it is not, see below.

Edit 2: If you have Python and the SymPy package, you can try this:

Code: Select all

>>> from sympy import *
>>> x = symbols('x')
>>> init_printing(True)
>>> p = <primitive polynomial>
>>> (0, <seed polynomial>)
then repeatedly enter this line:

Code: Select all

>>> div(_[1]*x, p, domain=GF(2))
The function div() divides two polynomials, giving you a tuple with the quotient and the remainder. We specify GF(2) as the domain for the coefficients, which causes the arithmetic operations to be computed modulo 2. Assuming you entered a polynomial with a maximum degree 15 as seed, the quotient will always be either 0 or 1 (the output of the LFSR), and the remainder will be the new state of the LFSR.

For example, let's say our seed is the binary number 0110101000111110. Converted to a polynomial, that's x**14+x**13+x**11+x**9+x**5+x**4+x**3+x**2+x so let's enter that as the seed polynomial and see what happens.

Code: Select all

>>> p = x**16 + x**12 + x**5 + 1  # CCITT
>>> (0, x**14+x**13+x**11+x**9+x**5+x**4+x**3+x**2+x)
⎛    14    13    11    9    5    4    3    2    ⎞
⎝0, x   + x   + x   + x  + x  + x  + x  + x  + x⎠
>>> div(_[1]*x, p, domain=GF(2))
⎛    15    14    12    10    6    5    4    3    2⎞
⎝0, x   + x   + x   + x   + x  + x  + x  + x  + x ⎠
>>> div(_[1]*x, p, domain=GF(2))
⎛    15    13    12    11    7    6    4    3    ⎞
⎝1, x   + x   + x   + x   + x  + x  + x  + x  + 1⎠
>>> div(_[1]*x, p, domain=GF(2))
⎛    14    13    8    7    4        ⎞
⎝1, x   + x   + x  + x  + x  + x + 1⎠
>>> div(_[1]*x, p, domain=GF(2))
⎛    15    14    9    8    5    2    ⎞
⎝0, x   + x   + x  + x  + x  + x  + x⎠
>>> div(_[1]*x, p, domain=GF(2))
⎛    15    12    10    9    6    5    3    2    ⎞
⎝1, x   + x   + x   + x  + x  + x  + x  + x  + 1⎠
>>> 
The output of the LFSR would be 0 1 1 0 1 (the successive quotients; the first 0 doesn't count because we entered it ourselves) and the successive states of the LFSR would be the binary numbers:
0110101000111110 (seed)
1101010001111100 (x**15 + x**14 + x**12 + x**10 + x**6 + x**5 + x**4 + x**3 + x**2)
1011100011011001 (x**15 + x**13 + x**12 + x**11 + x**7 + x**6 + x**4 + x**3 + 1)
0110000110010011 (x**14 + x**13 + x**8 + x**7 + x**4 + x + 1)
1100001100100110 (x**15 + x**14 + x**9 + x**8 + x**5 + x**2 + x)
1001011001101101 (x**15 + x**12 + x**10 + x**9 + x**6 + x**5 + x**3 + x**2 + 1)

Note how the direct implementation of the division of polynomials requires shifting to the left, even though many explanations of LFSRs use shifting to the right.
Last edited by pgimeno on Fri Jan 06, 2023 9:16 am, edited 1 time in total.
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Re: Anyone know what LFSRs are?

Post by Gunroar:Cannon() »

(I got the primitive polynomials from www.partow.net/programming/polynomials/index.html )

Okay, things are making more sense. But then if the taps for the primitive polynomial of degree 4 is 2 and 3 why does the table say 0 and 3?

And I found this lua LFSR https://gist.githubusercontent.com/inma ... d/lfsr.lua

But I can't see where I can change the arguments/input of it.
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
User avatar
pgimeno
Party member
Posts: 3544
Joined: Sun Oct 18, 2015 2:58 pm

Re: Anyone know what LFSRs are?

Post by pgimeno »

Gunroar:Cannon() wrote: Thu Jan 05, 2023 9:12 am Okay, things are making more sense. But then if the taps for the primitive polynomial of degree 4 is 2 and 3 why does the table say 0 and 3?
Once again, the table doesn't list the primitive polynomial, it lists a primitive polynomial. There can be many primitive polynomials with coefficients in GF(2) for a certain degree. If the table says 0 and 3, it's implying that the polynomial x^4+x^3+1 is primitive. I've just checked; the table is right, that polynomial is indeed primitive. The other table only lists x^4+x+1, which I've checked and is also primitive; that means that this other table is not exhaustive either.

Gunroar:Cannon() wrote: Thu Jan 05, 2023 9:12 am And I found this lua LFSR https://gist.githubusercontent.com/inma ... d/lfsr.lua

But I can't see where I can change the arguments/input of it.
That program is somewhat sketchy. It only works with 16-bit polynomials; the polynomial is given in the 'value' field (as bits, in reverse order, like the first table) and the seed is set in the 'state' field.
User avatar
pgimeno
Party member
Posts: 3544
Joined: Sun Oct 18, 2015 2:58 pm

Re: Anyone know what LFSRs are?

Post by pgimeno »

Sorry for double posting; I thought that if I edited, you could miss my edits if you already read the post.

I made a mistake in a previous post, wrongly assuming that the CRC-CCITT polynomial x^16+x^12+x^5+1 was primitive. It is not; it's divisible by x+1. The first comment in this answer explains some details: https://math.stackexchange.com/a/783193

Since you were having trouble with the tables because they were not exhaustive, I've written a program to generate all primitive polynomials of degrees 1 to 16. The program shows that in fact, x^4 + x^3 + 1 and x^4 + x + 1 are the only primitive polynomials of degree 4, there aren't any more. It outputs the polynomial as a bit string (including the term that gives the degree of the polynomial) and the taps (which exclude it); the period is 2^degree-1 in every case, e.g. 2^16-1 = 65535 for degree 16. I dislike that convention for the taps, but since it seems to be somewhat common, I've preserved it.

Code: Select all

local bit = require('bit')

local function bitlen(x) -- up to 17 bits
  if x >= 65536 then
    return 17
  end
  if x >= 256 then
    if x >= 4096 then
      if x >= 16384 then
        if x >= 32768 then
          return 16
        end
        return 15
      end
      if x >= 8192 then
        return 14
      end
      return 13
    end
    if x >= 1024 then
      if x >= 2048 then
        return 12
      end
      return 11
    end
    if x >= 512 then
      return 10
    end
    return 9
  end
  if x >= 16 then
    if x >= 64 then
      if x >= 128 then
        return 8
      end
      return 7
    end
    if x >= 32 then
      return 6
    end
    return 5
  end
  if x >= 4 then
    if x >= 8 then
      return 4
    end
    return 3
  end
  if x >= 2 then
    return 2
  end
  return x
end

local function fullperiod(poly)
  local deg = bitlen(poly) - 1
  local mask = bit.lshift(1, deg) - 1
  local state = 1
  local count = 0
  repeat
    count = count + 1
    state = bit.lshift(state, 1)
    if state > mask then
      state = bit.bxor(state, poly)
    end
  until state == 1 or count == mask
  if state ~= 1 then
    return false
  end
  return count == mask
end

local function printpoly(p)
  local taps = {}
  local bits = {}
  local deg = bitlen(p) - 1
  for i = deg - 1, 0, -1 do
    local nextbit = bit.band(p, bit.lshift(1, i)) == 0 and '0' or '1'
    table.insert(bits, nextbit)
    if nextbit ~= '0' then
      table.insert(taps, deg - 1 - i)
    end
  end
  print(("poly = 1%s taps = %s"):format(table.concat(bits), table.concat(taps, ", ")))
end

for deg = 1, 16 do
  print()
  print("Degree " .. deg)
  local primcnt = 0
  for poly = 2^deg, 2^(deg+1)-1 do
    assert(bitlen(poly) == deg+1) -- check that bitlen() is working
    if fullperiod(poly) then
      printpoly(poly)
      primcnt = primcnt + 1
    end
  end
  print("Total " .. primcnt .. " polynomials of degree " .. deg)
end
Here's the output: http://www.formauri.es/personal/pgimeno ... -polys.txt

The output shows that there are:
  • 1 primitive polynomial of degree 1
  • 1 of degree 2
  • 2 of degree 3
  • 2 of degree 4
  • 6 of degree 5
  • 6 of degree 6
  • 18 of degree 7
  • 16 of degree 8
  • 48 of degree 9
  • 60 of degree 10
  • 176 of degree 11
  • 144 of degree 12
  • 630 of degree 13
  • 756 of degree 14
  • 1800 of degree 15
  • 2048 of degree 16
Edit: I've extended it to count the number of primitive polys up to degree 22. Not more than that because the time grows exponentially and it gets prohibitively slow, but here are the counts for degrees 17-22:
Edit2: I forgot about this number-theoretic result. There are phi(2^n-1)/n primitive polynomials of degree n; it's a single line in Python with sympy:

Code: Select all

>>> print('\n'.join('%d of degree %d'%(totient(2**i-1)//i, i) for i in range(17, 33)))
  • 7710 of degree 17
  • 7776 of degree 18
  • 27594 of degree 19
  • 24000 of degree 20
  • 84672 of degree 21
  • 120032 of degree 22
  • 356960 of degree 23
  • 276480 of degree 24
  • 1296000 of degree 25
  • 1719900 of degree 26
  • 4202496 of degree 27
  • 4741632 of degree 28
  • 18407808 of degree 29
  • 17820000 of degree 30
  • 69273666 of degree 31
  • 67108864 of degree 32
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Re: Anyone know what LFSRs are?

Post by Gunroar:Cannon() »

Wow. Dang. Thanks.^^

From all these I've picked up these facts (with my ultimate goal being to solve a certain question I got sent):
>>> n = degree of polynomial
>>> bit length = period = 2^n-1
>>> combined length = bitLen1 x bitLen2
>>> taps = {n-1-(non zero degree of monomial)}
>>> to combine LFSRs XOR their outputs.
>>> also found out how to convert binary bit to polynomial
>>>>> Ajx^j-1 ....

I hope this is all correct. Hmmm. The question said calculate on paper or on a computer. I don't currently have a decide on me that can run anything (except ...lua...on my phone) so is there a way to do this by hand like they implied? Or is there a lua solution to get LFSRs?
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
User avatar
pgimeno
Party member
Posts: 3544
Joined: Sun Oct 18, 2015 2:58 pm

Re: Anyone know what LFSRs are?

Post by pgimeno »

Gunroar:Cannon() wrote: Sat Jan 07, 2023 8:43 am From all these I've picked up these facts (with my ultimate goal being to solve a certain question I got sent):
[...]
>>> combined length = bitLen1 x bitLen2
Only if they have different periods, and these periods don't have a common divisor, i.e. they are what's called "relatively prime" to each other. For example, periods 3 and 7 (degrees 2 and 3). Or 15 and 31 (degrees 4 and 5). But not e.g. 15 and 63 (degrees 4 and 6) because both 15 and 63 are divisible by 3: their GCD is not 1. In that case, the combined period is the product of the periods divided by the GCD. In the case of 15 and 63, the period would be 15*63/3 = 315, not 15*63 = 945. For equal periods, the GCD of a number and itself is the same number, therefore you would have a period of p*p/p = p, so there's no gain in period with combining them.

Gunroar:Cannon() wrote: Sat Jan 07, 2023 8:43 am I hope this is all correct. Hmmm. The question said calculate on paper or on a computer. I don't currently have a decide on me that can run anything (except ...lua...on my phone) so is there a way to do this by hand like they implied? Or is there a lua solution to get LFSRs?
You can certainly do it on paper for short bit lengths, otherwise getting the full period would take you a very long time. If you want to combine three, you can use degrees 2, 3 and 5, whose periods are relatively prime, but you'll have to calculate 31 outputs of the 5th-degree generator (and 7 of the 3rd-degree and 3 of the 2nd-degree one, but these are relatively easy).

Yes, in Lua you can create a LFSR. I did that in the program that I posted; you need the bit library for XOR though, but if your Lua is LuaJit, it comes included. The basic LFSR update step, copied from the program, is:

Code: Select all

    state = bit.lshift(state, 1)
    if state > mask then
      state = bit.bxor(state, poly)
    end
where state is the current state, which is initialized to the seed (must not be 0), poly the polynomial with the degree term included (with bits set for monomials of the same bit position, i.e. reversed with respect to tap numbers), and mask is 2^degree - 1, which is also the period. The output would be 0 if state <= mask and 1 if state > mask after the shift. So, you can do:

Code: Select all

    state = bit.lshift(state, 1)
    if state > mask then
      state = bit.bxor(state, poly)
      output = 1
    else
      output = 0
    end
Note that due to floating-point limitations, it works for generators of up to degree 52. You'll also probably need a 64-bit machine to use degrees greater than 31, because AFAIK the bit library works with the machine word size. Edit: You can't use a degree bigger than 31, see zorg's post below.

An example polynomial to use in the code is 0x3D. That's the 5th-degree polynomial x^5 + x^4 + x^3 + x^2 + 1, i.e. bits 5, 4, 3, 2 and 0 set. That one is primitive and gives a sequence of length 31. The mask would need to be set to 31 (0x1F).

Edit2: Here's the fastest XOR function I've been able to create under LuaJIT in compiled mode (it's not the fastest in interpreter mode but it's close, but for PUC Lua it's slow compared to others). It would let you avoid using the bit library completely, after replacing state = bit.lshift... with state = state * 2. That would allow you to use degrees bigger than 31.

Code: Select all

local function bxor(a, b)
  local pow = 2
  local c = 0
  while a + b ~= 0 do
    local ahalf = a * 0.5
    local bhalf = b * 0.5
    c = c + (ahalf + bhalf) % 1 * pow
    a = floor(ahalf)
    b = floor(bhalf)
    pow = pow * 2
  end
  return c
end
Last edited by pgimeno on Sat Jan 07, 2023 10:41 pm, edited 2 times in total.
User avatar
zorg
Party member
Posts: 3436
Joined: Thu Dec 13, 2012 2:55 pm
Location: Absurdistan, Hungary
Contact:

Re: Anyone know what LFSRs are?

Post by zorg »

pgimeno wrote: Sat Jan 07, 2023 9:50 am Note that due to floating-point limitations, it works for generators of up to degree 52. You'll also probably need a 64-bit machine to use degrees greater than 31, because AFAIK the bit library works with the machine word size.
From what i read on the website, luaJIT bitops lib always uses 32 bits; if the lua you'd use the separate library with was compiled to use floats as numeric types, the extension would also refuse to work due to the inability of single precision floats to represent 32 mantissa bits.


...also, i kinda want to ask what's with the recent-CS-graduate bitlen function :D
this is probably better

Code: Select all

function bitlen(x) return x == 0 and 1 or math.ceil(math.log(x+1)/math.log(2)) end
Me and my stuff :3True Neutral Aspirant. Why, yes, i do indeed enjoy sarcastically correcting others when they make the most blatant of spelling mistakes. No bullying or trolling the innocent tho.
Post Reply

Who is online

Users browsing this forum: No registered users and 41 guests