Max’s Cool Beans cunning coding tips and tricks
I
hope you’re familiar with the
American comic strip called Dilbert,
which is written and illustrated by
Scott Adams. Have you ever noticed that
there seems to be a Dilbert strip suitable
for every occasion?
In my previous Tips and Tricks (PE,
April 2021) we discussed the Arduino’s
random() function. Whenever I hear the
term ‘random,’ I never fail to think of the
Tour of Accounting strip from Thursday,
25 October 2001 (https://bit.ly/3uwjfnr) in
which Dilbert is introduced to a junior
accounting demon who is described as
being a random-number generator. The
junior demon is saying ‘Nine nine nine
nine nine nine...’, which prompts Dilbert
to ask, ‘Are you sure that’s random?’ The
accounting manager replies, ‘That’s the
problem with randomness – you can never
be sure.’ Truer words were never spoken.
So many recipes and flavours
When you are first introduced to the
concept of random numbers, everything
seems to sort of make sense. It’s only later
that you come to discover that there are
many different ‘recipes and flavors,’ as
it were. For example, your knee-jerk reaction to being told ‘here is a set of xxx
random numbers in the range yyy to zzz’
might be to expect a ‘uniform distribution’
across the total allowable number space.
In some cases, however, you might actually wish to see a ‘normal distribution’
a.k.a. ‘Gaussian distribution’ (https://bit.
ly/2PNdtPz) or even a ‘custom distribution’ (https://bit.ly/3g3UqeT).
Another consideration is how to implement a random number generator as part
of a computer programming language. Part
of this is the format of the statement you
use to invoke the generator and the way in
which it returns any results. In the case of
the Arduino, for example, successive calls
to random(-3, 3) will return random
integer values selected from the set comprising −3, −2, −1, 0, 1, and 2. That is, the
minimum value, which can be negative, 0,
or positive, is ‘inclusive’ while the maximum value is ‘exclusive.’ In some languages, the minimum value is always 0
and/or the maximum value is inclusive.
Also, the Arduino’s random() function is
non-volatile, which means that – unless
we take steps to prevent it – every time
we power-up or reset the processor and
re-run the program, we will receive the
same sequence of pseudo-random values.
By comparison, consider the RAND()
function in Microsoft’s Excel spreadsheet
Practical Electronics | June | 2021
d ata_ in
d
clock
d ata_ out
q
Fig.3. D-type flip-flop.
application. This function returns a real
value between 0 and 1. I just opened Excel,
placed my cursor in one of the cells, entered =RAND(), pressed the <Enter> key,
and received the value 0.657414199. In
this case, the function is volatile, because
when I saved and subsequently reopened
my spreadsheet, the new value displayed
was 0.980944837. It’s up to us to take
these values and manipulate them as we
will. For example, if we wished to generate random integer values between 0 and
100, we would use =ROUND(RAND() *
100, 0). What this does is to take the
real value between 0 and 1, multiply it
by 100, and then round it to the nearest integer (ie, 0 decimal places). How
about if we wanted to generate integer
values between −50 and +50? No problemo! All we would have to do would be
to modify our previous statement to read
=(ROUND(RAND() * 100, 0)) - 50
From software to hardware
OK, we’re poised to leap from topic-totopic with the agility of young mountain
goats, so may I recommend you don suitable attire. Let’s start with the fact that the
term ‘D-type flip-flop’ refers to a memory
element called a register that can store
a single bit (binary digit) of data in the
form of a 0 or 1 (Fig.3).
As indicated by the symbol (to those of
us who can read the arcane ‘language of
symbols’), this is an edge-triggered device.
A rising (0 to 1) transition (edge) on the
clock input will load whatever 0 or 1
value is present on the data_in input
into the register. After a short delay, this
new value will work its way through the
logic gates forming the register to appear
on the data_out output.
The register’s internal delay is important, because it allows us to daisychain a string of registers to form a more
Reg 2
d 2
d
Reg 1
q
ck
(a) SISO
2
1
0
(b) SIP O
2
1
0
ck
q 2
d
Reg 0
q
q 1
ck
clock
Fig.4. 3-bit SISO shift register.
d
q
ck
q 0
Fig.5. Simplified symbols for 3-bit SISO
and SIPO shift registers.
sophisticated function called a shift register. For example, consider a 3-bit serialin, serial-out (SISO) shift register (Fig.4).
When we clock this register, each element will load the value it currently sees
on its input. Suppose we start off with the
three registers containing 0, 1, 0, respectively (let’s simplify this to 010), and that
we present input d2 with a logic 1. When
we clock the register, it will end up containing 101. If we leave the input at 1 and
clock the register again, it will end up containing 110. One more clock will leave the
register containing 111. If we now set the
d2 input to 0 and clock the register again, it
will end up containing 011, and so it goes.
Since we are going to be drawing a few
of these registers, and as we know they
share a common clock, for the purposes
of these discussions we could simplify
our 3-bit SISO shift register symbol by
removing the clock (Fig.5a). Also, while
we’re at this point in our discussions, if
we wish, we could make a slight modification that allows us to access all of the
register bits simultaneously, resulting
in what we call a serial-in, parallel out
(SIPO) shift register (Fig.5b).
Now, just for giggles and grins, suppose we take the output from our 3-bit
SISO shift register and feed it back to the
input (Fig.6a). Let’s also assume we have
some way of pre-loading this register to
have an initial (seed) value of 001. Following the first clock, the register will
contain 100. The next clock will result
in 010. And one more clock will return
us to our original value of 001.
Ouroboros and the LFSR
I’m sure I don’t need to make mention of
the fact that the Ouroboros is an ancient
symbol of a serpent or dragon swallowing
its own tail, thereby forming a circle. This
symbol has been used by cultures around
the world to depict eternity or renewal.
(This is not to be confused with the Amphisbaena, which is a serpent in classical mythology having a head at both ends
and capable of moving in either direction
– much like some managers I’ve met.)
65
^
2
(a) SISO
XOR
(b) LFSR
1
0
^
2
1
0
a b
y
0
0
1
1
0
1
1
0
0
1
0
1
(c) XOR truth table
7
^
^
6
5
4
3
2
1
0
1
0
(a) Many-to-One implementation
7
6
^
5
^
4
^
3
2
(b) One-to-Many implementation
Fig.6. Simplified symbols for 3-bit SISO and LFSR shift registers.
I always think that the equivalent to the
Ouroboros in the world of digital electronics is the linear-feedback shift register
(LFSR). One of the more common ways
to create a LFSR is to start with a regular shift register and add feedback from
two or more points, called ‘taps,’ in the
register chain. These taps are fed into an
XOR function, whose output is used to
drive the input of the register chain. For
example, consider a simple 3-input LFSR
with two taps from register bits 2 and 0,
which we could represent as [2,0] (Fig.6b).
As for the regular SISO, let’s assume we
seed our LFSR with 001. Using the truth
table for the XOR (Fig.6c), we see that a
series of clocks will result in the sequence
100, 110, 111, 011, 101 and 010. One more
clock will return us to 001, which was our
original starting point. In decimal, this sequence would be 1, 4, 6, 7, 3, 5, 2... Since
we have three (n) bits, we have 2n = 23
= 8 possible combinations of 0s and 1s.
In a nutshell, our LFSR has pseudo-randomly cycled through all of the possible
combinations except 000; that is, (2n − 1)
= (23 − 1) = (8 − 1) = 7 values. Note that
we could have used an XNOR instead of
an XOR, in which case our LFSR would
have taken a different path to sequence
through all of the possible combinations
except 111. Also, instead of taps at [2,0],
we could have used taps at [1,0]. Once
again, this would cause the LFSR to follow
a different sequence as it worked its way
through the various values.
Now suppose we determine to create
an 8-bit LFSR. One combination of taps
that will result in a maximum length
sequence is [6,5,4,0] (Fig.7a). Taking
all of these taps and feeding them into
a 4-input XOR function that generates
a single feedback value is known as a
‘many-to-one’ implementation. Note
that there are no such beasts as 3-input
or 4-input XOR gates – only 2-input XOR
gates – which means we have to implement our 4-input XOR function using
three 2-input XOR gates, as illustrated
in the figure. This means we have two
levels of logic in our feedback path. The
more levels of logic, the greater the delay,
and the lower the frequency with which
we can clock the LFSR.
An alternative is to create a ‘one-tomany’ implementation (Fig.7b). In this
case, the tap at bit 0 is fed directly back
66
Fig.7. Many-to-one and one-to-many 8-bit LFSR shift registers.
into the input of bit 7, and it is also individually XORed with the other original
tap bits (those at [6,5,4] in this example).
Although the order of the generated values
will be different, both implementations
will result in maximal-length sequences.
From hardware to software
On the basis that this portion of the Cool
Beans column is called, cunning coding
tips and tricks, you may be wondering
about our foray into the hardware domain.
Well, the thing is, hardware and software
are two sides of the same coin, which
means we can also create software implementations of LFSRs. Furthermore,
as we shall see, the one-to-many LFSR
flavour is the easiest for us to transpose
into the software realm.
We introduced the & (AND) and | (OR)
bitwise operators in an earlier column
(PE, March 2021). As part of this, we
discussed using these operators to test
the state of bits, to set or clear bits, and
to act as masks. In the case of the & operator, for example, this accepts two integer values as inputs and performs an
AND on each pair of corresponding bits
(this is actually implemented using a
bunch of physical 2-input AND gates in
the computer’s central processing unit
(CPU)). The point is, there’s also a bitwise ^ (XOR) operator that we can use
to implement our LFSR function.
One thing we have to consider before
we start is when to perform the XOR operation. Do we execute the XOR and then
implement the shift, or would it be more
efficacious to perform the shift followed
by the XOR? The answer is ‘yes’ or ‘no’ or
‘maybe’ depending on ‘stuff’ (I hope I’ve
made myself clear). If we are working at
the assembly language level, for example,
in which we have access to the contents
of the carry flag in the CPU’s status register – along with a bunch of low-level
shift and rotate operators – then it may
be easier to perform the XOR followed
by the shift. However, since we are using
the C programming language, performing
the shift followed by the XOR is probably the better way to go.
Suppose we define SEED and MASK
values and declare our LFSR as an 8-bit
unsigned integer as follows (we introduced the concept of declaring fixedwidth values in PE, September 2020):
#define SEED 0x01 // 0000 0001
#define MASK 0xB8 // 1011 1000
uint8_t LFSR = SEED;
When we wish to ‘clock’ our LFSR to generate the next value in the sequence, the
way we are going to do this is to check
the state of the least-significant bit (LSB),
bit 0, to see if it contains a 0 or a 1. If it’s
a 0, all we have to do is to shift our LFSR
one bit to the right, which will automatically insert a 0 into the most-significant
bit (MSB). Alternatively, if the LSB is a
1, we again shift our LFSR one bit to the
right, but we then use the bitwise ^ operator to XOR this new value with the
contents of our MASK:
if ((LFSR & 0x01) == 0)
{
LFSR = LFSR >> 1;
}
else
{
LFSR = LFSR >> 1;
LFSR = LFSR ^ MASK;
}
I know this takes a bit of wrapping your
brain around, but this is the software equivalent of the one-to-many hardware implementation presented in Fig.7b. If you download
and run the sketch I just threw together (file
CB-Jun21-03.txt) and display the results in
the Arduino IDE’s Serial Monitor, you’ll
see that our LFSR pseudo-randomly cycles
through (28 − 1) = 255 different values (excluding 0x00 or 00000000 in binary) before
returning to its initial value.
Is this the best pseudo-random number
generator going? No! On the other hand,
this is a great technique to have available
to you in your tips and tricks toolchest
for those times when you are working
with a low-powered 8-bit microcontroller
with limited memory and clock cycles at
your disposal. And, of course, you could
easily extend this approach to implement
16-bit, 24-bit, or 32-bit LFSRs if you wish
(taps for maximal length LFSRs from 2 to
32 bits are given in my book Bebop to the
Boolean Boogie, https://amzn.to/3a0Qojz).
We will continue to dip our toes in the
LFSR waters in our next Tips and Tricks.
Until then, as always, I welcome your
comments, questions, and suggestions.
Practical Electronics | June | 2021
