Fibonacci Generator

I get the biggest kick from hijacking cryptography algorithms and re-designing them to make music.  Earlier I built a few implementations of the Linear Feedback Shift Register (LFSR) and used these algorithms to sequence drums (bird box), for direct synthesis of audio waveforms (musewave), and to generate op-art graphics (geometric oscillator and money synthesizer).   There are other examples of hardware-based LFSR algorithms in music, notably the Triadex Muse, and a few DIY examples sprinkled around the literature of Forest Mims III, who refers to it as PSEUDO-RANDOM SEQUENCER (Forrest Mims Engineer’s Notebook pg. 36)… this list is far from complete though and I welcome any additions to it.

Although the LFSR does generate rich patterns, I wanted something that spits out patterns with more bit depth (4- or 8-bits).  You can get higher bit depth from an LFSR, but it seems sort of hokey to me because it involves attaching multiple taps to the same register.

Researching other algorithms that have been used to generate encryption keys, I happened upon the wikipedia entry for the Lagged Fibonacci Generator (LFG).  This is an interesting variation on the Fibonacci Sequence, a series of numbers where each number is the sum of the two numbers before it.

0  1  1  2  3  5  8  13  21  34  55 …

 S(n) = S(n-1) + S(n-2)

Fans of the Golden Ratio know that it is built-in to the Fibonacci Sequence, being the ratio of S(n)/S(n-1) when n is very large.

But lets make it more complicated.

The Lagged Fibonacci Generator is a generalized version that looks at a wider “history window”; instead of the two previous numbers, it lets you go back farther in the list with parameters j and k.

S(n) = S(n-j) + S(n-k)

These numbers are limited to whatever bit depth you choose to represent them.   Whenever the addition generates a “carry”, it rolls over at zero again and outputs a carry flag.  For example, if you’re using 8 bits, the m value is 2^8, or 256.  What happens then is magic because instead of an ever-increasing string of numbers, you get a set of numbers that hop around back and forth between zero and m.  The complexity of the sequence grows rapidly with larger j and k values, but its never random or chaotic.

All fired up for some soldering (who isn’t!?) I designed a hardware version of the LFG with j and k variable from 1-64, and m=16.  In addition, I gave it some extra controls, such as a SEED input that hits the data stream thru an XOR bitmask.  I also gave the j and k registers separate clock inputs, on the whim that this would lead to something interesting.  Here’s the block diagram:

In the diagram, OVERFLOW is the same as the carry flag I mentioned before.  I added a set of vintage BCD codewheel switches to enter j, k, and SEED.  In the photo, you can see the j- and k- buffers built with stacked MC14557’s to simplify wiring.

Ok, so it works.  Now what to do with this crazy stream of numbers coming out?

The first thing I did was turn up the clock to measure its maximum rate.   This version seems glitch free up to about 1.5 MHz.   At this speed, if you listen to the digital signal, it just sounds like noise.  I had some cards laying around from the MuseWave that convert this type of data into analog waveforms.  So, I sent the j-buffer data stream to one card, and k-buffer to another card.  Now there were two analog waveforms coming from the same algorithm.  Which are nice to drive an X-Y oscilloscope display:

The next step in getting to know the LFG algorithm was to design an add-on board that converts its output into 1V/octave CV for analog synthesizer VCOs.  Here are a few examples of the LFG driving a pair of CD4069 VCO’s… which might be the easiest 1V/oct VCO you can build.   Mine didnt turn out very accurate or temperature-stable but thats cool.

 Fibonacci Generator solo in c minor

ABoT with LFG pizzicato-acid morph

LFG melody patterns

ABoT with LFG