Pages: [1]   Go Down
Author Topic: Implementing an LFSR with arduino?  (Read 750 times)
0 Members and 1 Guest are viewing this topic.
Offline Offline
Newbie
*
Karma: 0
Posts: 8
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Hello all,

I'm new to arduino (my first kit with uno arrives soon). I am definitely going to
spend some time on implementing and modifying some starter projects from
the web but I also had this idea that I would like to do.. I would really appreciate
your feedback about this.

So I would like to implement a Linear Feedback Shift Register ("LFSR").
The definition from wikipedia is
Quote
In computing, a linear feedback shift register (LFSR) is a shift register whose
input bit is a linear function of its previous state.
http://en.wikipedia.org/wiki/LFSR

A definition that I found for a shift register is:
Quote
An n stage shift register is a circuit consisting of n consecutive 2 state storage
units ( ip ops) regulated by a single clock. At each clock pulse, the state
(1 or 0) of each memory stage is shifted to the next stage in line.

An LFSR, if designed properly, will produce a sequence of huge period with
very good randomness properties (e.g. number of zeros ~ number of ones
and other). LFSR's are used a lot for pseudorandom number generation
(for instance, in cryptography).

A google search for "arduino lfsr" would give some results, but it is pretty
much people who have done lfsr simulations, for instance this guy:


However, I would like to do the 'real thing', that is, not create code that
simulates the lfsr, but create the circuit itself using a feedback shift register
and perform xor operations on some bits of the current stage somehow and
then feed the result back to the register. Each bit of the stage would correspond
to a led that is on when the bit is 1 and off when the bit is 0.

I don't really have any use for that (although at my level everything contributes
to learning!) and the only reason I want to build "the real thing" instead of a
simulator is that I'm a math grad student, I have spent lots of my time on the
pure abstract mathematics behind lfsr's and I never saw one of those damn
things in my life! I want to see a real lfsr live!

So, do you think something like that would be easily implemented? Any hints
as of how (and if) I should start planning? Also, what parts should I buy? Any
recommendations of the specific parts? What kind of shift register should I
buy?

Any feedback would be appreciated.. Many thanks in advance.

Logged

Offline Offline
Edison Member
*
Karma: 33
Posts: 1447
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Should be very doable, you just need some SR's that let you read (to get output) and write (to set the seed) the individual stages and some XOR gates for the feedback. If you have a large number of bits, you may run out of Arduino pins to set the thing, so you may need an I/o expander shield, or another set of shift registers to shift the seed into or results out of your LFSR.
Logged

Offline Offline
Newbie
*
Karma: 0
Posts: 8
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Thanks a lot, glad to know it's simple enough. I'll get back with more
questions maybe when I start building it.
Logged

Offline Offline
Jr. Member
**
Karma: 2
Posts: 60
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Not sure about linear feedback shift registers, but for serial in - parallel out shift registers (74HC595) check this out:

Logged

Offline Offline
Newbie
*
Karma: 0
Posts: 8
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

I think that's perfect for me.. The 'linear' refers to the way the output is
manipulated and fed back in the register rather than the type of
register, I think..
Logged

0
Online Online
Shannon Member
****
Karma: 206
Posts: 12178
Arduino rocks
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

"Linear" here means linear in the Galois Field GF(2^N), which means XOR operations...  So something like some
74HC595's and 74HC86's clocked from the Arduino (with an option to preload from the Arduino?).  Alternative
to several XOR gates would be a parity generator chip such as 74HC180.
Logged

[ I won't respond to messages, use the forum please ]

Offline Offline
Newbie
*
Karma: 0
Posts: 8
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Thanks a lot for the suggestions, that helps. I think I'm starting to understand a few
things better now but I still have a couple of other questions:

First, I'm looking at the specifications of the 2 first shift registers you suggested
but I don't understand too much: could you tell me if these are serial-in-parallel-out
or parallel-in-serial-out? I understand the theory behind lfsr's but when it comes to
the actual hardware I essentially know nothing..

The second thing that I wanted to ask is: is using an arduino for that an overkill?
I mean, of course you can use an arduino to make a simple cirquit with only one led,
but you could as well use some wire, a led, and a battery. Do we have a simlar case
here? Could we just use a soldering board, a shift register, a few xor gates, a serial
clock (ok, I have a question about that too), some leds, and a battery?

Lastly, I still don't think I understand the concept of clocking.. Do we always need to
use a (quite too powerful for such a task, I guess) microcontroller like arduino? Are
there any alternatives, like an actual component which is a clock of some sort? For
instance in the following picture that I found somewhere, we see that the circuit is
connected to a "clock". How could that be translated in real life?



Logged

0
Online Online
Shannon Member
****
Karma: 206
Posts: 12178
Arduino rocks
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Any oscillator circuit that can develop a logic level signal will do - the ubiquitous NE555 for instance.
Logged

[ I won't respond to messages, use the forum please ]

Offline Offline
Newbie
*
Karma: 0
Posts: 8
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Thanks for the suggestion.. I'll look more into that..
Logged

Pages: [1]   Go Up
Jump to: