2

I would like to design an old-school pseudorandom pulse generator to trigger various types of events (hardware suggestions only please - no programmable ICs). The events that I want to control need to happen, generally speaking, in the following categories of frequency: many times a minute, a few times a minute, once a minute, once every few minutes, once or twice an hour. Within each category of frequency, the event should occur "randomly," which is to say, the event's recurrence should not be exactly predictable. To give you a sense for why I want to build this: imagine a video game that has various scene elements, some of which occur very often, some that happen pretty frequently, and others which are infrequent... you get the idea, I hope.

The reason that I would like a hardware-only solution is that I am purposefully trying to learn about discrete logic - things like shift registers, multiplexers, Boolean logic, etc. Efficiency, speed, size, and cost are not my primary concerns. Hopefully there are some vintage electronics fanatics out there who will help me in my quest for knowledge! Thanks :-) PS: a drawn schematic would be tremendously appreciated since I am learning and probably won't be able to understand or build vague suggestions.

Kelly Heaton
  • 31
  • 5
  • Welcome to EE.SE. By not using MPU's to program, you need many stages to randomize the original data stream. –  Sep 06 '18 at 00:58
  • cant you search google images? – Tony Stewart EE75 Sep 06 '18 at 00:58
  • 2
    This https://nerdist.com/wall-of-lava-lamps-protect-internet-traffic/ is the ultimate analog random number generator – crj11 Sep 06 '18 at 01:07
  • Many stages are OK. Yes, I can search Google images. Thank you for the lava lamp suggestion! – Kelly Heaton Sep 06 '18 at 01:13
  • 2
    Shift registers, and multiplexers are generally considered digital devices, not analog (though there is also a device called an analog multiplexer). Boolean logic is the mathematics behind digital logic. If you want to make your design from individual gates and flip-flops, we'd call that a design from "discrete logic devices", not "analog computation". – The Photon Sep 06 '18 at 01:13
  • 1
    The lava lamp device is meant to produce truly random output, not pseudo random. And just about any device you make with actual analog devices is likely to be the same ---- random rather than pseudorandom. – The Photon Sep 06 '18 at 01:14
  • Thanks for clarifying terms - that's helpful for my searching, as I often do not know what is the correct terminology. Yes, a discrete logic is what I am seeking (as opposed to a wall of lava lamps, albeit very cool). – Kelly Heaton Sep 06 '18 at 01:16
  • Do you want pseudo random as in you can repeat the same sequence if you start with the same input conditions, or would non-repeatable also be acceptable? – crj11 Sep 06 '18 at 01:32
  • Non-repeatable is preferred. It is important that I have *general* categories of event frequency, but randomness within those categories is ideal, even if that means an occasional outlier. – Kelly Heaton Sep 06 '18 at 01:43
  • I see your dilemma. The more random stages you add the more chance of 'harmonics', where sub-patterns begin to repeat. You are emulating encryption to a degree –  Sep 06 '18 at 03:36
  • If you never want the pattern to repeat then it must always change feedback or random noise on each full loop. If it takes 1,000 iterations before a partial repeat then you have succeeded. –  Sep 06 '18 at 03:41
  • You can make a LFSR out of shift registers and XOR gates. Then you can AND n different bits together to make an output that's true 1/2^n of the time. – user253751 Sep 06 '18 at 04:23
  • Pseudo random looks like random, but it's not a trully random. So what do you ask for: random or pseudo random? – Marko Buršič Sep 06 '18 at 07:01
  • A suggestion is to use a long sequence generator of say 24 bits that you clock each time you need a random delay of 8 or 16 bits and scale accordingly but pre-load it with _random_ counts at the start of game play at 15MHz for the duration of the _on press_ plus bit more depending on the light intensity or supply voltage error. – KalleMP Sep 06 '18 at 07:29

2 Answers2

4

A good way to generate randomness using discrete logic is to exploit the metastability characteristics of a flip-flop.

A D flip-flop is a type of flip-flop that has a clock (triangle looking input) and a data input (D input) as shown below. Normally, the state of the D input is transferred to the Q/!Q output one propagation delay after a rising edge on the clock.

D Flip Flop

(from http://www.learningaboutelectronics.com/images/D-flip-flop.png)

The data must "set up" a specific amount of time before the clock edge and "hold" a specific amount of time after the clock edge in order to assure that the input is correctly transferred to the output. If the setup and hold times are not met, then the state of the output at the normal propagation delay time for the flip flop becomes random. The randomness can be tuned by varying the frequency and phase of the clock and data and the amount of time that you wait to check the state of the output.

The graph below is from a TI paper that discusses the metastability characteristics of various 5V logic families. In general, the slower the logic, the worse the metastability and the more often random errors occur. This means that older logic families are more useful for generating random errors. The graph shows that using 74HC style logic, the error rate can be tuned from thousands of times per second to once per day by varying the wait time after a clock at which you look at the output of the flip-flop (tx). This specific graph is for a 1 MHz clock and a 500 KHz data input.

enter image description here

Note that metastability is delay, temperature, and voltage sensitive, so tuning to a specific event rate could be challenging. But it might be possible to build something good enough for your needs.

The test circuit from the TI paper is shown below. It can be a starting point to a random event generation circuit.

metastability test circuit

crj11
  • 5,480
  • 1
  • 13
  • 32
  • @KellyHeaton If you feel that the answer is helpful, please upvote it. After a while, choose the best answer and accept the answer. – Hazem Sep 06 '18 at 02:59
  • @Hazem I would happily upvote but don't see an option in my interface (I think because I am a new user I don't yet have this privilege). Plus, I am still considering the different answers - there isn't only one. – Kelly Heaton Sep 06 '18 at 03:04
1

The answer to this question is that there are many answers, but the most common approach is to use a linear feedback shift register. I started with this idea and breadboarded two 8-bit shift registers (TI part CD54/74AC164E) clocked by a 555 timer in astable mode. I left the data serial inputs of the shift registers floating. Prior to adding XOR gates (the linear feedback part), I tested this circuit with LEDs to visualize what is happening. As it turns out, the two shift registers start out in different states (presumably because their data inputs are floating). Their states remain unsynchronized as they continue to shift, which you can see in this video:

https://www.kellyheatonstudio.com/blog/2018/9/6/shift-registers

The two 8-bit shift registers are in the center region of my breadboard. On the right is a 555 timer in astable mode which provides a clock pulse of about 1x per second. On the left is a 5 volt regulator - this part is irrelevant if you have the correct DC supply voltage, but mine is 12 VDC.

Perhaps this hacked approach is all the apparent randomness that I need (I am an artist, not a cryptographer). If not, I will add linear feedback and/or follow @crj11's advice below regarding the exploitation of the metastable characteristics of flip flops (which are what's inside of the shift registers). Either way, I think by using multiple shift registers and multiple 555 timers I won't need a lot of feedback and certainly nothing fancy in order to make the system appear random --even though it's not, technically.

As for the frequency of my events (often, sometimes, rarely...), I plan to clock different shift registers at different speeds. Applying logic gates to the outputs of these different registers (at different clock speeds) should give me the general categories of event frequency that I am seeking, since faster clock speeds will result in more logical "positives" (or whatever is the correct terminology). I hope this makes sense.

Below are a few resources for people who, like me, don't know the correct terminology or understand how shift registers are used for pseudorandom number generation.

Good general overview to answer the question “what is a linear feedback shift register” (LFSR): https://zipcpu.com/dsp/2017/11/11/lfsr-example.html

On choosing taps for a linear feedback shift register: https://cs.stackexchange.com/questions/1121/choosing-taps-for-linear-feedback-shift-register

Mini project on how to implement a LFSR: https://www.slideshare.net/KishoreChandrahasVanam/lfsr

Another helpful paper on using an 8-bit LFSR (i.e. Texas Instruments chip CD54/74AC164): https://pdfs.semanticscholar.org/320a/8b2e781ac6165b400eca96047489685fd1f7.pdf

Kelly Heaton
  • 31
  • 5