This is only a preview of the December 2020 issue of Practical Electronics. You can view 0 of the 72 pages in the full issue. Articles in this series:
|
LFSR
Random
Number
Generator
Using
Logic ICs
By combining just a few logic ICs, it is possible to digitally generate a
pseudo-random number sequence. There are two reasons why you
might want to build this circuit: one, it’s interesting and will help you
learn how logic ICs work. And two, it can do something useful: it can
generate LED patterns to display on our very popular Stackable LED
Christmas Tree that we published in last month’s issue.
T
he LED Christmas Tree is electrically
by Tim Blythman
quite simple: it takes a DC power source
and a serial data stream, and switches the dozens
or even hundreds of LEDs on and off to create the pattern
that’s described by that serial data.
This simplicity is its strength; its low per-board cost and
expandability mean that you can build an impressive LED
Christmas Tree display without spending much money.For
more information on that LED Christmas Tree project, see
the November 2020 issue.
You do need a way to generate interesting patterns to
show on those LEDs, and we did that with a PC or an Arduino in the original project.
However, another project that we
published last year, in the September 2019 issue, gave us an
idea. That was the Digital
White Noise Generator by
John Clarke.
In that article,
John programmed
a small microcontroller to produce a seemingly random
(but not quite)
series of 1s and 0s that
would not repeat until about
four billion cycles.
By running this random generator
at quite a high speed, and filtering the output, it produces a convincing ‘white noise’ sound,
which doesn’t repeat for a very long time (some digital
white noise generators have noticeable repetition, which
is annoying!).
28
So we’ve combined a couple of shift register chips with a few other bits and pieces
to make a similar random number generator without using a microcontroller. And we’ve made it so that you can
use it to drive the LED Christmas Tree, or just as a way to
investigate and understand its principle of operation. It’s
nice and simple, so it’s easy to build and straightforward
to understand.
We describe it as ‘pseudo-random’ and not truly random
because if you know the current state, you can predict the
next state, and the pattern does eventually repeat. But in
practice, the outputs change so fast that the output is not
really predictable and the repetition period is long enough
that you’re unlikely to notice it.
The computations needed to generate this random string
of binary digits are quite simple. This is a technique
known as a Linear Feedback Shift Register
(LFSR), but note that the word ‘linear’ is not used here in the electronic sense – we’ll have
more on that shortly. That means that
you don’t necessarily
need a microcontroller
to use this technique.
Old-fashioned discrete
shift registers can do the
job, too.
Shift register basics
Fig.1 shows how a shift
register works. Data is fed
into one end of the shift
register, and on each clock
pulse, that value (zero or one)
Practical Electronics | December | 2020
Fig.1: this shows one way of building a
16-bit LFSR with a maximum non-repeat
interval of 65,535 clocks. It’s a relatively
simple method, so it’s the one we’ve chosen
to use in this project. The binary values
in each cell move one step to the right in
time with the clock signal. The XOR gates
calculate a new bit value which is fed in as
the first bit of the sequence. Three iterations
of the pattern are shown.
0
1
0
1
0
1
0
1
1
0
0
1
1
1
0
0
0
0
1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0
1
0
1
0
1
1
0
0
1
1
1
0
0
0
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1
0
1
0
1
0
1
1
0
0
1
1
1
0
0
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
is loaded into the first position in the shift register. The data
which was previously in the first position then moves into
the second position, and so on until the last value which
used to be in the last position ‘falls out’ and may go on to
be used elsewhere, or is simply discarded.
Some shift registers also include an output latch, so that
you can shift all new data into the register without the output states changing, and the new data is then fed through
to the output latches when a separate clock pin is pulsed.
We don’t need that sort of function in this project: the shift
register ICs we’re using update their output states the instant that they receive a clock pulse.
Generating random numbers
The idea behind the LSFR is to feed back the data
which is about to ‘fall out’ of the end of the shift
register back to the input side. But it isn’t fed
back as-is, because if it were, the pattern
would repeat every eight cycles for an
8-bit register, or 16 cycles for a 16-bit register. That’s far too predictable to be considered random.
However, if the data coming out of the shift register
is combined with the state of some of the bits already in
the shift register, even in a very simple way, that prevents
the pattern from repeating until a much larger number of
steps have occurred.
In our circuit, we have combined two 8-bit shift register ICs to form a single 16-bit shift register. The aforementioned Digital White Noise Generator used a 32-bit register
which gave a much longer repeat period; however, being
implemented in software using a microcontroller, those
extra bits didn’t take up physical space.
We decided that having four shift register ICs, plus the supporting componentry,
would be too large; after all, we want to
keep this device simple, so you can easily
see how it works. And anyway, the Digital
White Noise Generator had a high clock
rate of around 154kHz, which was necessary to produce pleasant-sounding noise
over the audio bandwidth of 20Hz-20kHz.
In this example, we want to be able to
see the patterns generated, so even if you
are updating a large set of LEDs quite rapidly, you don’t need a clock rate of more
than a couple of kilohertz. So despite the
much smaller register size, the repetition
period is still quite long.
The way that we are combining the output of the shift register with some of its
Practical Electronics | December | 2020
contents is a basic boolean logic operation called ‘exclusive or’, abbreviated to ‘XOR’. A two-input XOR has a balanced truth table, with four possible input combinations
(00, 01, 10, 11) and the result is equally likely to be a zero
or a one (00 => 0, 01 => 1, 10 => 1, 11 => 0).
This is important, because operations which do not produce an equal number of zero or one outcomes for a random
distribution of input values will rapidly cause the bits in
the register to become all zero or all one; not what we want
when we are trying to generate a random-looking pattern!
By the way, we haven’t explained how the random values translate into light patterns, but hopefully you have
figured it out: we can feed the ‘random’ series of zeros and
ones into the Christmas Tree and for each
bit which is one, the corresponding LED
will be on, and for each bit which is
zero, it will be off. If we shift these
values in rapidly, the LEDs will
appear to twinkle, like stars.
Linear operations in logic
We mentioned earlier that the term
‘linear’ does not mean the same thing in
mathematics as it does in electronics. In
electronics, it suggests that the circuit is operating in the analogue domain; this circuit
is decidedly digital.
In boolean logic, the term ‘linear’ basically means that the function F satisfies the
equation aF(x + y) = aF(x) + aF(y). Our XOR
operation satisfies that condition.
To expand on why XOR is a good choice,
and why we said earlier that it’s good that
it has a ‘balanced’ truth table, consider what
would happen if we used the similar AND function instead. A zero at the output of the shift
register would always give a zero at the input,
and as a result, it wouldn’t take long for all the
bits to become zero. They would then stay that
way forever.
Similarly, if we used an OR function instead,
the register would fill with ones in short order. On the other hand, XNOR could be used
instead of XOR, as it has a very similar truth
table to XOR.
There is one scenario in which the XOR function doesn’t work well, and that’s when all the
inputs all start as zero, as then the output is always zero, so the register will get stuck in this
state. Our circuit has extra components to detect
this state and override the output in that case.
29
CON1
CON4
+5V
+5V
0V
2
100nF
CON2
IC4a
14
1
2
13
3
IC4: 74HC14
IC4f
+5V
GND
DI
4
12
5
7
1kW
1
IC4c
5
USB
MINI B
470mF
IC4d
9
6
8
IC4e
11
IC4b
3
6
10
LT
CLK
TO XMAS TREE
CON3
1
4
2
3
INVERT
IN PHASE
GND
+5V
100nF
100nF
14
1
2
9
SDa
Vcc
14
O7
O6
SDb
O5
MR
1
12
2
11
10
9
IC2
O4
6
74HC164
O3
8
13
O2
O1
CP
GND
O0
Vcc
SDa
O7
O6
SDb
O5
MR
3
12
Q14
11
Q13
10
Q12
5
Q10
4
Q9
O3
8
Q15
IC3
O4
6
74HC164
5
4
CON5
13
O2
O1
CP
O0
GND
7
D16
A
3
LK1
BUF
XOR
1
Q3
2
Q2
3
D7
K
D6
K
A
A
D5
K
D4
K
A
A
D3
K
D2
K
A
A
Q0
K
A
A
Q1
D9
K
D8
Q4
K
A
A
Q6
D11
K
D10
Q5
K
A
A
Q7
7
D13
K
D12
Q8
K
A
A
Q11
D15
K
D14
K
D1
A
+5V
100nF
1kW
IC1: 74HC86
IC1b
6
IC1c
8
3
5
9
10
IC1a 14
4
IC1d
11
7
1
2
C
Q1
BC547
E
10kW
B
JP1–4
12
13
Pseudo-random
Generator
SC PSEUDO-RANDOM Sequence
SEQUENCE GENERATOR
1
Q10
2
Q12
3
Q13
4
Q15
CON6
Ó2019
1
Fig.2: the circuit which implements this 16-bit LFSR uses just four standard ICs
and a few other bits and pieces. IC4a is the oscillator which provides the clock
to drive shift registers IC2 and IC3. The four 2-input XOR gates in IC1 are used
as the feedback function, while spare inverters IC4b-IC4e buffer the Q15 bit
value so it can be fed to various external circuits.
2
We have also carefully chosen which bits are XORed together to ensure our sequence does not repeat prematurely.
With a 16-bit linear feedback shift register and wellchosen ‘taps’, we can cycle through 65535 (216 – 1) states
before the sequence repeats.
With a 2Hz update rate, that means the sequence will
take over nine hours to repeat. The taps we’re using are
shown in Fig.1. These guarantee the maximum repetition
period, as stated above. (See the September 2019 Digital
White Noise Generator article for more background on how
a pseudo-random number generator works.)
Circuit description
The Pseudo-random Sequence Generator circuit is shown
in Fig.2. We’ve kept it as simple as possible, so it’s based
30
K
D1–D16: 1N4148
3
4
XOR BITS
on just four logic ICs, one transistor, sixteen diodes and a
handful of resistors and capacitors.
IC2 and IC3 are the two eight-bit shift registers, and they
are cascaded to form a single 16-bit shift register. This is
done by holding the O7 output of IC2 to the SDb input (pin
2) of IC3, tying the clock input pins (pin 8 of each IC) together and holding the SDa and MR pins high. This means
that the SDb input determines the input state of the shift
register, and the chips are always active.
As a result, the value of a bit fed into pin 2 of IC2 (zero
or one) will appear 16 clock pulses later at pin 13 of IC3.
Pins 3-7 and 10-13 of both ICs are outputs carrying the values of the individual bits from each shift register.
The common clock pins are driven from pin 12 of IC4f,
a Schmitt trigger inverter, which buffers the output of
Practical Electronics | December | 2020
oscillator IC4a. This is another Schmitt
trigger inverter with a resistor and
capacitor in the feedback loop, causing
it to oscillate at around 2Hz. You can
change this frequency by varying either
the resistor or capacitor values; increase
either to slow it down or decrease either
to speed it up.
It’s important that a Schmitt trigger
inverter is used for this oscillator since
the built-in hysteresis (ie, the difference
in positive-going and negative going input switching voltage thresholds) ensures that it oscillates and also makes
the frequency fairly predictable.
Parts list –
Pseudo-Random Sequence Generator
1 double-sided PCB coded 16106191, 91.5mm x 63mm
1 2-pin header (CON1)
1 SMD mini type-B USB socket (CON2; optional)
2 3-pin headers (CON3,LK1)
1 6-way female header (CON4)
1 16-way female header (CON5; optional)
1 4-way female header (CON6; optional)
1 2x4-way pin header (JP1-JP4)
5 jumper shunts (for JP1-JP4 and LK1)
4 14-pin DIL IC sockets (for IC1-IC4; optional)
Semiconductors
1 74HC86 quad XOR gate, DIP-14 (IC1)
2 74HC164 8-bit shift register, DIP-14 (IC2, IC3)
1 74HC14 hex Schmitt trigger inverter, DIP-14 (IC4)
16 1N4148 small-signal diodes (D1-D16)
1 BC547 NPN transistor (Q1)
XOR gates
IC1 is a 74HC86 quad XOR gate. The four
gates are combined to effectively provide
a single five-input XOR gate, with these
inputs being at pins 1, 2, 5, 12 and 13
Capacitors
and the result is available at pin 8.
1 470µF 10V electrolytic
Usually, jumpers JP1-JP4 will be in4 100nF ceramic or MKT
serted, and LK1 will be in the position
shown in Fig.2, so four of these inputs
Resistors (all 1/4W 5% or 1%)
are connected to outputs Q10, Q12, Q13
1 10kΩ
2 1kΩ
and Q15 of the shift register. This gives
us the configuration shown earlier in
Fig.1, with one additional XOR input.
This fifth XOR input comes from a 16-input NOR gate, The buffered clock signal is taken to the CLK and LT pins
built from diodes D1-D16, NPN transistor Q1 and its two on CON4, so that each bit of pseudo-random data fed to the
biasing resistors. In practice, what this means is that tran- tree is synchronously shifted all through the tree.
sistor Q1 is switched on as long as at least one of the Q1The power supply for this circuit is elementary: a 5V DC
Q16 outputs of the shift register is high (1). In this case, externally regulated supply is fed in via either USB socket
its collector will be low, so the fifth XOR input at pin 1 of CON2 or pin header CON1. Bulk bypassing is not required;
IC1a will also be low.
one 100nF capacitor per IC is sufficient.
However, if the shift register contains all zeros, none of
Note that the USB socket provides a measure of reverse
diodes D1-D16 will be forward biased and so transistor Q1 polarity protection, as the USB plug can only be insertswitches off, allowing the 1kΩ resistor to pull its collector ed one way, while there is no protection when using pin
high, to +5V. This then causes the output of our five-way header CON1. So be careful when wiring CON1 as you’ll
XOR gate to be one, not zero, ensuring that the shift register fry the board if you reverse it.
cannot stay in the all-zeros state for more than one cycle,
as a one will be fed into its input in this case.
Construction
The output of the XOR gate is normally fed to the shift Use the PCB overlay diagram (Fig.3) and the photos as a
register input, pin 2 of IC2, via LK1. If LK1 is instead placed guide during construction. The Pseudo-random Number
in its alternative position, the output of the shift register Generator is built on a PCB coded 16106191, which measis merely fed back into the input. Because Q1 prevents it ures 91.5 x 63mm and is available form the PE PCB Service.
from being all zeros all the time, this has the effect of one
If you are fitting CON2, the optional surface-mounted
output being high, which then moves from one end of the mini-USB socket for power, do this first. Apply some solshift register to the other, before repeating.
der flux to the pads on the PCB and locate the socket with
When this unit is connected to the LED Christmas Tree, its pins into the holes on the PCB. Solder one of the side
that causes it to generate a ‘chaser’ effect as one lit LED mechanical tabs in place and ensure that the pins line up
moves through the tree every seventeen clock pulses.
with their pads before proceeding.
Load the iron with a small amount of solder and touch
Driving external circuitry
the iron to the pads. The solder should flow onto the pad
The four spare inverters in IC4 (ie, those not used for the os- and the pins. Only the two end pins for power are needcillator) are paired up to buffer the output of the shift regis- ed. Check that there are no bridges to adjacent pins, and if
ter. The O7 output from pin 13 of IC3 is fed to input pins 5 there are, carefully remove with solder braid or wick. Once
and 9 of inverters IC4c and IC4d, and their outputs are also you are happy that the power pins are soldered correctly,
paralleled and connected to pin 1 of CON3, to provide a bit solder the remaining mechanical pins.
more drive current for any external circuitry connected there.
Now move onto the resistors and diodes. Make sure that
That signal is then similarly re-inverted by IC4b and the diodes are all oriented correctly, ie, with their cathodes
IC4e, to provide an in-phase buffered output at pin 2 of stripes towards the top of the board.
CON3. This gives us complementary signals at pins 1 and
Then solder the ICs in place. You can use sockets if
2 of CON3, which could provide a 10V peak-to-peak sig- you wish. These must also be oriented correctly, with
nal for driving a piezo (for example).
the pin 1 dot/notch in each case towards the bottom of
The in-phase output is also fed to the DI pin of CON4, the board. Don’t get the chips mixed up since there are
which has a pinout designed to match the Stackable LED three different types, but they all have the same number
Christmas Tree, so it can be used to drive a tree directly. of pins (14).
Practical Electronics | December | 2020
31
D1
D3
D2
D4
D5
D6
D7
D8
D9
D10
D11
D12
D14
D13
D15
D16
Testing
If you have a Christmas Tree PCB, plug it into CON4,
ensuring the pin functions line up correctly (ie, it is not
reversed) and apply regulated 5V DC power through either the USB socket (CON2) or pin header (CON1). You
should see the LEDs on the tree start to flash, although
depending on the initial state of the shift registers, it may
take 10-15 seconds before you see anything.
Hint: if you aren’t using CON2, you can easily get the
5V DC required to feed to CON1 from the pins of a USB/
serial adaptor plugged into a USB port.
If you don’t have a Christmas Tree PCB, you can
connect a simple LED in series with a 1kΩ series
resistor across pins 2 and 3 of CON3, or even connect a piezo speaker (eg, Jaycar AB3440) to these
pins (in this case, a faster clock rate is advised.
Alternatively, you can connect these devices to CON3,
between either pin 1 or pin 2, and pin 3 (GND).
4148
4148
4148
4148
4148
4148
4148
4148
4148
4148
4148
4148
4148
4148
4148
CON3
INVERTED
IN PHASE
32
100nF
CK LT DI GND 5V
IC1 74HC86
IC2 74HC164
IC3 74HC164
IC4 74HC14
4148
Further experimentation
Finally, if you want to see what makes the LFSR ‘tick’,
16106191
GND
JP1-JP4, CON5 and CON6 can be used to change the
100nF
‘taps’, ie, which shift register bits are combined to de15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
CON5
fine the shift register’s input state.
10k
Q1
To do this, remove the shorting blocks from JP1-JP4
CON1
JP1-4
1k
and use patch leads to connect the four outputs that you
GND
XOR BUF
100nF
+5V
CON6
want to feed back from the terminals of CON5 to the pins
LK1
15 13 12 10
of CON6 (the order doesn’t matter).
CON4
If you want to use fewer than four inputs to the
1k
XOR gate, wire the unused pins of CON6 to either
GND or +5V.
+
470 F
The taps we have used with JP1-JP4 inserted provide
a so-called maximal-length sequence (65,535
100nF
CON2
LINEAR FEEDBACK SHIFT REGISTER R
16106191
19160161
steps for a 16-bit shift register), but there are other combinations of taps which also create a maximal length, as
Fig.3: like the circuit, the PCB layout is quite simple. The
well as a number that are much shorter.
main thing to watch while building it is the orientations
Also note that if Q15 (ie, the last bit of the shift register)
of IC1-IC4 and D1-D16. Various headers and jumpers are
is
not fed into the XOR gate, then that will necessarily reprovided so you can experiment with and probe the circuit
sult in a shorter sequence.
to see what happens if you change it slightly. A header
The article at http://bit.ly/pe-dec20-shift has more insocket is provided to allow the board to directly drive a
formation on the mathematical theory of linear feedback
Stackable LED Christmas Tree, with as few as 10 LEDs or
as many as several hundred.
shift registers, and also how they are used in fields such
as cryptography and digital communications.
As mentioned earlier, if used to drive the LED Christmas
You may need to carefully bend the legs on the ICs so
Tree,
you can place LK1 in its alternative position to switch
that they are straight and vertical before they will fit. Solthe circuit into chaser mode.
der two diagonally opposite pins on each IC, then check
If you decide to adjust the operating frequency as dethe orientation and that the IC is flat against the PCB bescribed above, by varying the value of either the 470µF cafore soldering the remaining pins.
pacitor or nearby 1kΩ resistor, keep in mind that this reThe four small 100nF capacitors are not polarised. Fit
sistor value can’t go much below 470Ω due to the limited
them now. Follow with the sole transistor (Q2) with its flat
output current of IC4a.
face oriented as shown. You may need to carefully bend
So to increase the frequency, you’re better off reducits legs to fit the PCB.
ing
the capacitor value (lower value capacitors are usuFit the pin headers next, including CON1, CON3, LK1
ally cheaper, too!).
and JP1-JP4. Follow with header socket CON4, mounted at
You can increase the resistor value, so if you want to
right-angles, so it can plug into the male header on an LED
make the frequency variable, you could connect a 10kΩ
Christmas Tree board. This can be done by surface-mountpotentiometer (or similar) in series with a 470Ω resistor
ing it to the pads on top of the PCB rather than soldering
between pins 1 and 2 of IC4a, then reduce the timing cait into the through-holes. If you want your tree to project
pacitor value to 4.7µF to give an adjustable frequency of
up from this board, CON4 can be fitted vertically instead.
around 2-40Hz.
Now fit optional headers CON5 and CON6, if desired.
If you reduce the timing capacitor to 33nF, that will give
These are provided to allow you to experiment by feeding
a clock rate of about 20kHz, and you will then get a signal
different combinations of the sixteen shift register outputs
that’s suitable for basic audio use, as a white-noise source.
into the XOR gate inputs. We’ve recommended using feBut note that at this rate, it’s hardly even a pseudo-random
male headers for these so that so you can make connections
number generator: the sequence will repeat every few secusing male-male jumper wires, but other combinations are
onds, and that will be quite apparent.
possible. Finally, fit the electrolytic capacitor, ensuring its
longer positive lead goes into the hole marked with the ‘+’
Reproduced by arrangement with
sign, then plug jumper shunts into JP1-JP4 and LK1 as shown
SILICON CHIP magazine 2020.
www.siliconchip.com.au
in Fig.2 and Fig.3.
C 2019
Practical Electronics | December | 2020
|