Anyone know what LFSRs are?
- Gunroar:Cannon()
- Party member
- Posts: 1088
- Joined: Thu Dec 10, 2020 1:57 am
Anyone know what LFSRs are?
I randomly ended up reading about LFSRs when someone asked me a question related to them because they heard I was good with computers () 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
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?
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
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?
Re: Anyone know what LFSRs are?
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 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?
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: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.
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
Last edited by pgimeno on Wed Jan 04, 2023 8:45 pm, edited 1 time in total.
- Gunroar:Cannon()
- Party member
- Posts: 1088
- Joined: Thu Dec 10, 2020 1:57 am
Re: Anyone know what LFSRs are?
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?
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?
Re: Anyone know what LFSRs are?
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.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?
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;
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>)
Code: Select all
>>> div(_[1]*x, p, domain=GF(2))
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⎠
>>>
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.
- Gunroar:Cannon()
- Party member
- Posts: 1088
- Joined: Thu Dec 10, 2020 1:57 am
Re: Anyone know what LFSRs are?
(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.
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.
Re: Anyone know what LFSRs are?
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 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?
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.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.
Re: Anyone know what LFSRs are?
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.
Here's the output: http://www.formauri.es/personal/pgimeno ... -polys.txt
The output shows that there are: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:
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
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
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
- Gunroar:Cannon()
- Party member
- Posts: 1088
- Joined: Thu Dec 10, 2020 1:57 am
Re: Anyone know what LFSRs are?
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?
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?
Re: Anyone know what LFSRs are?
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 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
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).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?
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
Code: Select all
state = bit.lshift(state, 1)
if state > mask then
state = bit.bxor(state, poly)
output = 1
else
output = 0
end
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.
- zorg
- Party member
- Posts: 3444
- Joined: Thu Dec 13, 2012 2:55 pm
- Location: Absurdistan, Hungary
- Contact:
Re: Anyone know what LFSRs are?
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
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 True 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.
Who is online
Users browsing this forum: No registered users and 243 guests