Linear feedback shift register?
- by Mattia Gobbi
Lately I bumped repeatedly into the concept of LFSR, that I find quite interesting because of its links with different fields and also fascinating in itself. It took me some effort to understand, the final help was this really good page, much better than the (at first) cryptic wikipedia entry. So I wanted to write some small code for a program that worked like a LFSR. To be more precise, that somehow showed how a LFSR works. Here's the cleanest thing I could come up with after some lenghtier attempts (Python):
def lfsr(seed, taps):
sr, xor = seed, 0
while 1:
for t in taps:
xor += int(sr[t-1])
if xor%2 == 0.0:
xor = 0
else:
xor = 1
print xor
sr, xor = str(xor) + sr[:-1], 0
print sr
if sr == seed:
break
lfsr('11001001', (8,7,6,1)) #example
I named "xor" the output of the XOR function, not very correct.
However, this is just meant to show how it circles through its possible states, in fact you noticed the register is represented by a string. Not much logical coherence.
This can be easily turned into a nice toy you can watch for hours (at least I could :-)
def lfsr(seed, taps):
import time
sr, xor = seed, 0
while 1:
for t in taps:
xor += int(sr[t-1])
if xor%2 == 0.0:
xor = 0
else:
xor = 1
print xor
print
time.sleep(0.75)
sr, xor = str(xor) + sr[:-1], 0
print sr
print
time.sleep(0.75)
Then it struck me, what use is this in writing software? I heard it can generate random numbers; is it true? how?
So, it would be nice if someone could:
explain how to use such a device in software development
come up with some code, to support the point above or just like mine to show different ways to do it, in any language
Also, as theres not much didactic stuff around about this piece of logic and digital circuitry, it would be nice if this could be a place for noobies (like me) to get a better understanding of this thing, or better, to understand what it is and how it can be useful when writing software. Should have made it a community wiki?
That said, if someone feels like golfing... you're welcome.
