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 216 – 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.
FIGURE 3. Excel-generated graph of
sequential contents in LFSR register.
48
January 2008