Pseudo-Randomness with an LFSR in Forth

I’ve gotten into microcontroller programming as a way to learn and experiment with Forth. My goal is to create an electronic version of the Magic 8-Ball toy. The Magic 8-Ball gives a random answer to a yes-or-no question. In the digital realm, true randomness is actually difficult to achieve.

The original Magic 8-Ball toy is a fluid-filled sphere made to look like an oversized billiard ball. The sphere contains a polyhedron having text inscribed onto each of it’s faces. The ball has a window that, when oriented upward, allows the user to see one face of the polyhedron when it floats to the top of the sphere. The randomness comes from the way the user moves the 8-ball during use.

I built my digital 8-ball using FlashForth on an ATMega328 microcontroller (this is the microcontroller at the heart of the Arduino ecosystem). The microcontroller is connected to an LCD display that can show two 16-character lines of text. The microcontroller is also connected to a button that, when pressed, causes it to display a message on the LCD.

My first attempt at randomizing those messages was to use an on-chip millisecond counter. FlashForth has a built-in word, ticks, that returns the value of this counter. I shifted off the bits I didn’t need and used the resulting value as an index into an array of messages. I expected to get random responses with each button press but, in practice, I got a lot of the same messages over and over.

I set the problem aside until I saw Julian Ilett’s video about his experiments with a linear feedback shift register (LFSR). A LFSR can be used to generate a pseudo-random series of values. Importantly, the configuration I chose would return all the values between 1 and 31 once each cycle. To prevent messages from being shown in a discernible pattern, I cycled the value periodically, four times per second. When the user hit the button, the current value in the register was used as the index into the messages array.

In my Forth implementation, I first needed to create a variable that would hold the value of the LFSR and initialize it.

variable idx 1 idx !

My LFSR uses a five-bit value and shifts in the most-significant bit by XORing bits 1 and 4. In LFSR lingo, bits 1 and 4 are called taps. I created words that would take a given value and return the taps.

: 1tap ( n -- bit )
  %1 and
;

: 4tap ( n -- bit ) 
    %1000 and 3 rshift
;

The taps are XORed to get the feedback bit that will be shifted into the register.

: xortaps ( n -- bit )
    dup 1tap
    swap 4tap
    xor
; 

Now we apply the feedback bit. First, we shift the register value to the right by one place. Then, we shift the feedback bit to the left four places. Finally, we OR these two values to set the feedback bit. In the code below, the order of operations is slightly different, but the effect is the same.

: apply ( n bit -- n )
    4 lshift        \ move bit to 5th place
    swap 1 rshift   \ shift register value right by one
    or              \ OR with new MSB
;

Finally, we can put it all together. The word lfsr takes a value and applies the LFSR algorithm to it. The word advanceidx fetches the value of idx, invokes lfsr, and stores the result back in idx.

: lfsr ( n -- n )
    dup xortaps apply
;

: advanceidx ( -- )
    idx c@ lfsr idx c!
;

I used the value of idx as the index into the array of messages. This resulted in a greater variety of messages being shown when compared with using the timer value.