Nuts and Volts - January 2008

implemented to eliminate pushbutton contact-bounce issues.

The interesting part of the firmware actually lies in determining the output values to the LED displays. In order to make sure that this dice algorithm produces a truly random result, I decided to use a random number generator (RNG). There are a number of software RNG algorithms out there. In fact, the CCS library includes an RNG function (RAND()). Initially, I did try using this function. However, the code that was generated in the background quickly ate up my data memory. Therefore, a different approach was necessary. I decided to go with what is called a linear feedback shift register (LFSR) algorithm. Figure 2 shows a 16-bit LFSR.

This type of RNG is based off of a “Taps” system that is described by a characteristic polynomial. Each of these tap positions indicates what bit positions within the LFSR itself will be XOR’d with a shifted out bit. Remember how the XOR operation works — if two bits differ (e.g., 1 and 0), then the result is 1. If the bits are the same (e.g., 1 and 1 or 0 and 0), the result of the XOR operation is 0.

As shown in Figure 2, the algorithm starts by shifting the LFSR bit by bit. The shifted-out bit is then XOR’d with the new value at bit position 16, since this is where a tap is located. The result of that operation is then XOR’d with the next tap at bit position 5 and so on, to the tap at bit position 2. The one-bit result of all these XOR operations is placed at bit position 1 and the process starts over.

Repeatedly performing this operation should generate seemingly unpredictable, subsequent values in

the LFSR. This LFSR style of RNG is an example of a pseudo-random number generator. This means that, if scrutinized closely enough, one would observe a definite pattern in the sequence of values generated. The trick here is to make these values seem to occur randomly.

An idea 16-bit RNG should generate 2¹⁶– 1 = 65535 values before repeating a value (not counting zero). The secret is to make sure that a characteristic polynomial of maximal length is chosen. Maximal length simply means a tap sequence that will generate the longest possible run of sequential values, before the sequence repeats itself.

Some basic rules are applied to selecting a maximal length characteristic polynomial:

confusion in the code. Different bit numbering conventions are used between the characteristic polynomial and the compiler. The compiler (and PIC16F57 datasheet) identifies a 16-bit register as bits 0– 15, while the polynomial identifies these same bits as 1– 16. The randnum_ generator() function performs the LFSR algorithm to generate each value as follows:

1) First, the 16th bit of the current value in the LFSR variable is saved to the Ouput_bit variable.

2) The contents of the register are then shifted left by one.

1) There should be an even number of taps.

3) The Output_bit is now XOR’d with the new contents of LFSR to generate the least significant bit in the register as follows:

2) The polynomial should be relatively prime and irreducible (the polynomial cannot be further reduced).

LFSR_1 = ((((Output_bit ^ LFSR_16)
^ LFSR_5) ^ LFSR_3) ^ LFSR_2);

I chose the polynomial and tap sequence shown in Figure 2. To implement this in software, I first declare a 16-bit integer variable named LFSR and initialize it to 1. I realized I needed to save the most significant bit before the register is shifted so that it can be XOR’d with bits located at the tap positions. This is accomplished by declaring a one-bit variable of type int1 named Output_bit. To identify the tap locations, the #bit directive is used to name individual bit locations in the LFSR as follows:

4) If at some point the LFSR register is filled with zeros, the XOR operation will no longer work, and the algorithm will fail and produce an endless series of zero values. Therefore, this condition will need to be taken care of using a conditional IF statement to reseed the LFSR with decimal 1 to restart the sequence.

if (LFSR == 0b0000000000000000)
LFSR = 1;

#bit LFSR_16 = LFSR.15

Why am I assigning LFSR. 15 (bit 15) to LFSR_ 16? This is to avoid

The randnum_generator() executes immediately on any RESET or power-up and continues to execute, so long as the MCU has power. This idea stems from the basic operating theory of slot machines. A slot machine constantly runs a RNG while there is power to the machine. Once the user hits a button or pulls a lever, the current random number is stored, compared against a table of possible output combinations and the result displayed accordingly. Using this basic methodology, as long as the dice application is running, a random number is generated.