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 November last year. by Tim Blythman T he LED Christmas Tree is electrically 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 Christmas Tree, see the November and December 2018 issues or visit our website at: siliconchip.com. au/Article/11297 You do need a way to generate interesting patterns to show on those LEDs, and we did this from a PC or an Arduino in the original project. But another project that we published last year, in the September 2018 issue, gave us an idea. That was the Digital White Noise Generator by John Clarke (siliconchip.com.au/Article/11225). 84 Silicon Chip 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!). 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 Australia’s electronics magazine siliconchip.com.au 0 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. 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 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) 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, though; 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 was, the pattern would repeat every eight cycles for an 8-bit register, or 16 cycles for a 16-bit register etc. 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 siliconchip.com.au 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 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 White Noise Generator had a very 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 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 Australia’s electronics magazine August 2019  85 CON1 CON4 +5V +5V 0V 2 100nF CON2 IC4a 14 1 13 2 3 IC4: 74HC14 IC4f +5V GN D 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 SD b O5 MR 1 12 2 11 10 9 IC2 O4 6 74HC164 O3 8 13 O2 O1 CP GND O0 Vcc SD a O7 O6 S Db O5 MR 5 8 3 Q15 12 Q14 11 Q13 10 O2 O1 CP O0 G ND 7 D16 A 5 Q10 4 Q9 3 Q8 LK1 BUF XOR Q3 2 Q2 3 K A A D7 K D6 K A A D5 K D4 K A A D3 K D2 K A A Q0 D9 K D8 Q1 K A A Q4 1 D11 K D10 Q6 K A A Q5 D13 K D12 Q7 7 K A A Q11 D15 K D14 Q12 IC 3 O4 6 74HC164 O3 4 CON5 13 K D1 K A D1–D16: 1N4148 +5V 100nF 1kW IC1: 74HC86 IC1b 6 IC1c 8 5 9 10 IC1a 14 4 IC1d 11 3 7 1 2 SC PSEUDO-RANDOM SEQUENCE GENERATOR 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. 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 analog domain; this circuit is decidedly digital. In boolean logic, ‘linear’ basically means that the func86 Silicon Chip E 10kW B JP1–4 12 13 Ó2019 C Q1 BC547 1 Q10 2 Q12 3 Q13 4 Q15 CON6 1 2 3 4 XOR BITS tion 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. Australia’s electronics magazine siliconchip.com.au 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. 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 well-chosen ‘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 2018 White Noise Generator article (link above) for more background on how this type of a pseudo-random number generator works. 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 & 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) Capacitors 1 470µF 10V electrolytic 4 100nF ceramic or MKT Resistors (all 1/4W 5% or 1%) 4-band code (5%) 5-band code (1%) 1 10kΩ brown black orange gold brown black black red brown 2 1kΩ brown black red gold brown black black brown brown Circuit description The circuit is shown in Fig.2. We’ve kept it as simple as possible, so it’s based on just four logic ICs, one transistor, sixteen diodes and just a few 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 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. 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 & 13 and the resiliconchip.com.au sult is available at pin 8. Usually, jumpers JP1-JP4 will be inserted, and LK1 will be in the position shown in Fig.2, so four of these inputs are connected to outputs Q10, Q12, Q13 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, built from diodes D1-D16, NPN transistor Q1 and its two biasing resistors. In practice, what this means is that transistor Q1 is switched on as long as at least one of the Q1Q16 outputs of the shift register is high (1). In this case, its collector will be low, so the fifth XOR input at pin 1 of IC1a will also be low. However, if the shift register contains all zeros, none of diodes D1-D16 will be forward biased and so transistor Q1 switches off, allowing the 1kΩ resistor to pull its collector high, to +5V. This then causes the output of our five-way XOR gate to be one, not zero, ensuring that the shift register cannot stay in the all zeros state for more than one cycle, as a one will be fed into its input in this case. The output of the XOR gate is normally fed to the shift register input, pin 2 of IC2, via LK1. If LK1 is instead placed in its alternative position, the output of the shift register is merely fed back into the input. Because Q1 prevents it from being all zeros all the time, this has the effect of one output being high, which then moves from one end of the shift register to the other, before repeating. When this unit is connected to the LED Christmas Tree, that causes it to generate a ‘chaser’ effect as one lit LED moves through the tree every seventeen clock pulses. Driving external circuitry The four spare inverters in IC4 (ie, those not used for the Australia’s electronics magazine August 2019  87 Note that the USB socket provides a measure of reverse polarity protection, as the USB plug can only be inserted one way, while there is no protection when using pin header CON1. So be careful when wiring CON1 as you’ll fry the board if you reverse it. Construction D3 D1 4148 D6 4148 D2 D7 4148 4148 D8 4148 D4 D9 4148 4148 D10 4148 D5 D11 4148 4148 D12 4148 4148 D14 D13 4148 D15 4148 D16 4148 88 Silicon Chip 100nF CK LT DI GND 5V IC1 74HC86 IC2 74HC164 IC3 74HC164 IC4 74HC14 4148 Use the PCB overlay diagram, Fig.3, and the photos as a guide during construction. The Pseudo-random Number Generator is built on a PCB coded 16106191 which measures 91.5 x 63mm. If you are fitting CON2, the optional surfacemounted mini-USB socket for power, do this first. Apply some solder flux to the pads on the PCB and locate the socket with its pins into the holes on the PCB. Solder one of the side mechanical tabs in place and ensure that the pins line up with their pads before proceeding. Load the iron with a small amount of solder and touch CON3 the iron to the pads. The solder should flow onto the INVERTED C 2019 pad and the pins. Only the two end pins for power are IN PHASE 16106191 GND needed. Check that there are no bridges to adjacent pins, 100nF and if there are, carefully remove with solder braid or 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 CON5 wick. Once you are happy that the power pins are sol10k Q1 dered correctly, solder the remaining mechanical pins. CON1 JP1-4 1k Now move onto the resistors and diodes. Make sure GND XOR BUF 100nF +5V that the diodes are all orientated correctly, ie, with their CON6 LK1 15 13 12 10 cathodes stripes towards the top of the board. CON4 Then solder the ICs in place. You can use sockets 1k if you wish. These must also be orientated correctly, with the pin 1 dot/notch in each case towards + 470 F the bottom of the board. Don’t get the chips mixed up since there are three different types, but they all 100nF CON2 LINEAR FEEDBACK SHIFT REGISTER R 16106191 19160161 have the same number of pins (14). Fig.3: like the circuit, the PCB layout is quite simple. The main You may need to carefully bend the legs on the ICs so thing to watch while building it is the orientations of IC1-IC4 that they are straight and vertical before they will fit. Soland D1-D16. Various headers and jumpers are provided so you der two diagonally opposite pins on each IC, then check can experiment with and probe the circuit to see what happens the orientation and that the IC is flat against the PCB beif you change it slightly. A header socket is provided to allow the board to directly drive a Stackable LED Christmas Tree, (as fore soldering the remaining pins. The four small 100nF capacitors are not polarised. Fit seen on page 85) with as few as 10 LEDs or as many as several them now. Follow with the sole transistor, Q2, with its flat hundred. face orientated as shown. You may need to carefully bend oscillator) are paired up to buffer the output of the shift its legs to fit the PCB. Fit the pin headers next, including CON1, CON3, LK1 register. The O7 output from pin 13 of IC3 is fed to input pins 5 and 9 of inverters IC4c and IC4d, and their outputs and JP1-JP4. Follow with header socket CON4, mounted at are also paralleled and connected to pin 1 of CON3, to right-angles, so it can plug into the male header on an LED provide a bit more drive current for any external circuitry Christmas Tree board. This can be done by surface-mounting it to the pads on top of the PCB rather than soldering connected there. That signal is then similarly re-inverted by IC4b and it into the through-holes. If you want your tree to project IC4e, to provide an in-phase buffered output at pin 2 of up from this board, CON4 can be fitted vertically instead. Now fit optional headers CON5 and CON6, if desired. CON3. This gives us complementary signals at pins 1 & 2 of CON3, which could provide a 10V peak-to-peak signal These are provided to allow you to experiment by feeding different combinations of the sixteen shift register outputs for driving a piezo (for example). The in-phase output is also fed to the DI pin of CON4, into the XOR gate inputs. We’ve recommended using fewhich has a pinout designed to match the Stackable LED male headers for these so that so you can make connections Christmas Tree, so it can be used to drive a tree directly. using male-male jumper wires, but other combinations The buffered clock signal is taken to the CLK and LT pins are possible. Finally, fit the electrolytic capacitor, ensuring on CON4, so that each bit of pseudo-random data fed to the its longer positive lead goes into the hole marked with the “+” sign, then plug jumper shunts into JP1-JP4 and LK1 as tree is synchronously shifted all through the tree. The power supply for this circuit is elementary: a 5V DC shown in Figs.2 and 3. externally regulated supply is fed in via either USB socket CON2 or pin header CON1. Bulk bypassing is not required; Testing If you have a Christmas Tree PCB, plug it into CON4, enone 100nF capacitor per IC is sufficient. Australia’s electronics magazine siliconchip.com.au suring 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 advsed. Alternatively, you can connect these devices to CON3, between either pin 1 or pin 2, and pin 3 (GND). Further experimentation Finally, if you want to see what makes the LFSR’ tick’, JP1-JP4, CON5 and CON6 can be used to change the ‘taps’, ie, which shift register bits are combined to define the shift register’s input state. To do this, remove the shorting blocks from JP1-JP4 and use patch leads to connect the four outputs that you want to feed back from the terminals of CON5 to the pins of CON6 (the order doesn’t matter). If you want to use fewer than four inputs to the XOR gate, wire the unused pins of CON6 to either GND or +5V. The taps we have used with JP1-JP4 inserted provide a so-called maximal length sequence (65,535 steps for a 16bit shift register), but there are other combinations of taps which also create a maximal length, as well as a number that are much shorter. Also note that if Q15 (ie, the last bit of the shift register) is not fed into the XOR gate, then that will necessarily result in a shorter sequence. The article at siliconchip.com.au/link/aasj has more information on the mathematical theory of linear feedback 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 Tree, you can place LK1 in its alternative position to switch the circuit into chaser mode. If you decide to adjust the operating frequency as described above, by varying the value of either the 470µF capacitor or nearby 1kΩ resistor, keep in mind that this resistor value can’t go much below 470Ω due to the limited output current of IC4a. So to increase the frequency, you’re better off reducing the capacitor value (lower value capacitors are usually cheaper, too!). You can increase the resistor value, so if you want to make the frequency variable, you could use connect a 10kΩ potentiometer (or similar) in series with a 470Ω resistor between pins 1 and 2 of IC4a, then reduce the timing capacitor value to 4.7µF to give an adjustable frequency of around 2-40Hz. If you reduce the timing capacitor to 33nF, that will give a clock rate of about 20kHz, and you will then get a signal that’s suitable for basic audio use, as a white noise source. But note that at this rate, it’s hardly even a pseudo-random number generator: the sequence will repeat every few seconds, and that will be quite apparent. SC siliconchip.com.au KCAB ISSUES First the good news: Did you know . . . that back issues of SILICON CHIP magazine are still available, with only a few exceptions, for the LAST TWENTY YEARS +? Check out the following list to see if the issue you want is still in stock. Order any of these issues online or by phone for just $12.00 INCLUDING p&p in Australia! See the website address below or call (02) 9939 3295 9-4, Mon-Fri 1997: all except August & September 1998: all except March 1999: all except February 2000: all except April 2001: all except October & December 2002: all except June & July 2003-2005: all available 2006: all except January & October 2007-2010: all available 2011: all except November & December 2012: all except December 2013: all except February 2014: all except January 2015: all except January 2016-2019: all available And the even better news: Did you know . . . that if the issue you want is out of stock, we can supply a copy of any article from any issue (nominate which article you require. Price is the same as a back issue due to the extra work required). And now the best news: Did you know . . . that you can also view most articles on the SILICON CHIP website! And if you’re a subscriber, (print or online) there’s even a discount on the price (as there is with any other SILICON CHIP ONLINE SHOP merchandise). Log on today for all the details: www.siliconchip.com.au Australia’s electronics magazine August 2019  89