Implementing an LFSR with arduino?

Using Arduino Project Guidance
1

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

In computing, a linear feedback shift register (LFSR) is a shift register whose
input bit is a linear function of its previous state.
Linear-feedback shift register - Wikipedia

A definition that I found for a shift register is:

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.

2

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.

3

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

4

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

5

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..

6

"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.

7

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?

8

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

9

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