Linear feedback Shift register

I’d admit frankly that I’ve been interested in The haverstman Zorlon Cannon for quite som times. Firstly because I didn’t really understand on what it was built on (although  the name of the module is self-explanatory: It’s a battery of linear feedback shift register…duh!).

That linear thingy is actually a counter that is incremeted in a non linear fashion with XOR logic. I took me a bit of time to understand and most of all implement that thing in software (the representation in textbook and article is done in the left to right reading direction but a register works in the oposite direction, so it was a bit annoying but once you got the trick…)

The magic is actually to change the length and the taps of the register to access different “random” patterns. We usually make the arragement in order to get the full “random” possibilities (2^bits – 1) but with different taps the register can be locked in a loop offering only a few numbers out with the result of interesting purposes for the modular world. Obviously the less you have the bits in your register, the more repetitive (and quick) the output will be. Clocked the computation with high speed clock and you can get some nasty-8bit sound. The harvestman took a very nice advantage of that.

lfsr_taps

Of course, an external random number can be loaded into the register to offer another sequences of random sequences. This can be done in sampling a waveform for instance and load it in once the previous sequences (from the previous sample) are done.

Here’s a bit of code, which is actually the main core of the piece.  Taps are in an array containing the informations for the taps

xor_bit = ((lfsr_out >> taps[0]) ^ (lfsr_out >> taps[1]) ^\
(lfsr_out >> taps[2]) ^ (lfsr_out >> taps[3])) & 1;
lfsr_out = (lfsr_out >> 1) | (xor_bit << length);
bin_out = lfsr_out & 1;

The idea is really to build a “battery” of those. Codewise, the simpler would be to manage the registers and associated data in a structure data type. Although the fonctions to work with those datas should be more pointer/adresses oriented to avoid writting the same over and over for all the lfsr you want.

typedef struct
{
uint16_t lfsr_out;
uint8_t taps[4];
uint8_t xor_bit;
uint8_t length;
uint8_t bin_out;
}lfsr_output;

once all bin_out variable are loaded, you can build the output data and send it to the output on the clock edge.

As always the more challenging will be to build a user-friendly interface to make its use very nice and flawless.

I wish to build that electronic thing, the electronic part won’t be that hard since it’s just about digital outputing (good old CMOS) and maybe a bit of analog stuff for the ADC front end. unfortunately I haven’t layed down my hand on 16HP front panel yet and they’re really the essential key for a module to see its birth happening.

http://en.wikipedia.org/wiki/Linear_feedback_shift_register

Advertisements

Leave a comment

Filed under Uncategorized

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s