Fullscreen HTML5Med Res (??MB)HTML4

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