Simple high-speed counter (part of a random number generator)

Discussion in 'The Projects Forum' started by Corey Haddad, Oct 14, 2015.

  1. Corey Haddad

    Thread Starter New Member

    Oct 14, 2015
    13
    0
    This is my first time posting, and first time using this forum!

    Overview

    I have a project that needs a fast counting / timing circuit at its core. What needs to be counted is how many times an oscillator cycles between events. Yes, this is essentially a clock, but longer-term frequency drift is not a problem. As long as the jitter is less than 1% there shouldn't be much of a problem, but certainly the less jitter the better. The faster this can run, the better, although only up to the point that cost, stability and complexity are not compromised. I hope 50-Mhz will be pretty easy to hit, and maybe even as high as 500-Mhz? I would like to keep the cost of the components under $20. This is for a cryptography project that I am undertaking on my own time and budget, and I am making a prototype. Specifically this timer circuit will be a data source for a randomnumber generator. I know enough about circuits to ask the right questions, and am looking for help doing the actual design, and especially selecting the components. If this project goes somewhere I would be happy to offer credit and recognition if that is desired.

    More Details

    The aim is to count the number of one set of discrete events, the oscillator cycles, in between another discrete event, which in this case is the closings of a switch. Closing the switch will cause a rising edge, plateauing at +5 volts, (or +3.3, if that is better). Nothing should happen when the switch opens again, though the counter must be ready to observe the next rising edge.

    There will be an oscillator, and two counters. I'm not sure if it matters if the counters are synchronous or asynchronous, I think either would work. The counters will pass back and forth the duty of counting, while the other one enters a rest state so that its pins may be read. Each counter should be 32-bit, so probably it would make sense to have two 16-bit counters working together (the circuit would then have four 16-bit counters in total). The counters do not need to reset, they can just overflow and keep on counting up from 0. They should stop counting upon every-other rising edge so the pins can be accurately read. In this case I will be using an Arduino pull the pin states. A potential improvement would be to have just one counter circuit hooked up to the oscillator. Upon a rising edge signal, a second chip would have to capture the state of the counter and hold it until the next rising edge, where it would again poll the pin states. There has to be some kind of buffer as the Arduino will not be able to read pins at anywhere near the speed of the oscillator. I tend to think the two-counter setup would function more reliably, but that is just an educated guess. This is a best-effort circuit, there will be no minimum interval between rising edges, and there may be partial rises and partial falls. It is perfectly acceptable that the circuit malfunctions under such conditions and fail to provide an accurate count, as long as it can 'reset itself' upon detecting a clean rising edge and begin functioning well again.

    There are two attached diagrams, one shows the counting sequence timing, the other is a very rough schematic.

    New Doc 9_1.jpg New Doc 9_2.jpg

    Thanks for any help, and please let me know if more info or details will be helpful. I live near Seattle and will be in Boston Nov. 1st, in case there are any 'locals' on this board.
     
  2. pwdixon

    Member

    Oct 11, 2012
    488
    56
    If it's just a random number generator what's wrong with the random functions on the Arduino?
     
  3. Corey Haddad

    Thread Starter New Member

    Oct 14, 2015
    13
    0
    I almost didn't want to mention anything about the random number generator because I was concerned I would have to start justifying why I want to make the circuit. I never said there was anything wrong with the the random functions on the Arduino, but that is not what I am interested in.

    **What needs to be counted is how many times an oscillator cycles between events.** -> That is what I am trying to do.

    If you were trying to be helpful, thanks!
     
  4. GopherT

    AAC Fanatic!

    Nov 23, 2012
    6,068
    3,838
    If you are looking for randomness, I don't understand your concern for accuracy in reading the counted oscillator pulses, as long as a value is captured and stored.

    To do this easily, you need:
    - an oscillator connected to
    - a counter (likely a cascade of counters, like 4 dual 4-bit counters would work)
    - a latch (or cascade of latches)

    A latch grabs and holds the current values on the pins of another chip.

    Just activate the latch when you need a new value.

    50MHz might be more difficult than 10Mz - parts are much more available
     
    Last edited: Oct 14, 2015
  5. pwdixon

    Member

    Oct 11, 2012
    488
    56
    I suspect the OP is looking for something else and doesn't want to tell us anything about what he's really trying to do, fair enough, but then he's going to get a lot of random unhelpful help I expect.
     
  6. AnalogKid

    Distinguished Member

    Aug 1, 2013
    4,546
    1,252
    I understand what you are trying to do, create a pseudo-random number by controlling a really fast, semi-stable counter with a really slow, unstable and uncorrelated timing event, the randomness of a human pressing a button. Many low cost electronic dice kits run on the same idea. One problem with your idea is that a 50 MHz, 32 bit counter rolls over every 86 seconds. So if the counter starts over with each button press there will be a significantly non-randomness to the output. What good is a 32 bit number if the upper 8 bits are always zero?

    But to you questions... In your timing diagram, only one counter is running at any given time. That's a clue to reducing the circuit. A single counter with a latch will give exactly the same results with much less effort. If a counter can count reliably at 50 MHz, it can be latched and reset reliably at those speeds. If you want your randomness to extend to the upper bits, and it is not a requirement that the counter start from zero for each pattern cycle, I suggest letting the counter free run and have the control button clock the output latch to take a snapshot. A lot less work, less programming and way fewer inputs for the Arduino. Also, to further randomize the input you can change the order of the bits between the latch output and the Arduino input.

    A follow-up to that thought - why not let the Arduino capture the running counter output without a latch? It's a random number generator; if the Arduino reads in the four bytes while they are changing, so they do not represent the exact same overall counter output, so what?

    Back to a previous question, how did you determine that your random number needs 32 bits of precision?

    Also, a linear feedback shift register (LFSR) will do the same thing with the same number of (different) parts, and is a much more common approach because it does not have a monotonic output that depends on an external, unknown, uncontrolled event for its randomness. An LFSR is inherently random, even when sampled at a constant interval.

    OK, that's enough for round 1.

    ak
     
    Last edited: Oct 14, 2015
  7. Corey Haddad

    Thread Starter New Member

    Oct 14, 2015
    13
    0
    The counter rolling every 86 seconds will be just fine, I will be taking a read at least once per second. And if it does roll, that is fine too, though most likey data from a long interval (several to many seconds) would just be thrown out. And you are also on to something with questioning the need for a 32-bit number... I will indeed by tossing out most significant bits on the software side. I'll actually be tossing out some bits on the least significant side as well. An optimized, final design might easily make do with less bits, but as this is an experimental prototype, I would like to capture everything, if for nothing be analysis' sake.

    This is very good to know. Fewer inputs on the Arduino is a major advantage. Letting the counter run free and pulling a snapshop would be perfect. So it would be possible to have the output latch read the counter upon detection of a rising edge, totally ignore the falling edge, and then take a new snapshot of the counter on the next rising edge? On your last point, I DO NOT WANT to randomize the input... I want the input to be an as accurate representation of the true interval between the actual physical events (the button pushing) as possible.

    The Arduino is far far too slow to keep up with the 'middle' 16 or 24 bits that I am ultimately interested in. I probably will not need the least few significant bits, but how many will be experimentally determined in the software I write. The fourth-least significant bit would be operating at ~3-Mhz, and there is just no way the Arduino can capture every flip of that bit. Don't let the random concept throw you off track here, I want as real a count of the cycles between events as possible, and very low latency between the event and a capture of the counter's state is critical.

    32 is overkill, the true number of needed bits will be experimentally determined in software. But the more usable bits the better, so I wanted to err high for my prototype to get a complete picture of the behavior space. I also don't want the counter to roll too often, or it will start be annoying to keep track of. A 24-bit counter would roll over 3 times per second at 50-Mhz, which would probably be okay too. If 24-bits was going to be a lot cheaper or easier to deal with, then I could make it work, but my sense is that the complexity difference between 24- and 32- in this setup is 8 more wires to the Arduino, which is fine, and the cost difference is probably on the order of pennies, which is also fine.

    I am pursing the design I wrote about because as you noted, I am interested in the source of the randomness being 'the human pressing the button', and not some random activity in a chip. But I really hope to avoid a philosophical debate about the nature of randomness. Okay, I don't want to avoid that debate in general, but here I am hoping to stay focused on circuit design :). Thanks for your feedback, it is helpful.
     
  8. Corey Haddad

    Thread Starter New Member

    Oct 14, 2015
    13
    0
    I hope my bottom of my previous reply has given you some insight into my thinking on this. The source of the randomness really does matter, philosophically, and for the software I am working on, it will matter that the source of the randomness comes from outside of the circuit that have described. The circuit I working on has a job - to record some very precise and accurate data on a physical event, and even that originates and transpires outside of the detecting circuit. Yes, this is a detecting circuit. Any randomness introduced by the circuit can be considered noise, and is undesirable.

    10Mhz would be acceptable. I was hoping for higher, but cost and simplicity are important since this is a prototype. Higher Mhz would give more useful bits, but this is helpful since I have no intuition about what is easily and cheaply accomplished. I've got a multi-meter, but no scope. So I can't really be diagnosing high frequency problems. Simple is good. At 10Mhz, I could probably drop back to 24-bits for the counter and latch.

    I like your parts list.

    Thanks.
     
  9. AnalogKid

    Distinguished Member

    Aug 1, 2013
    4,546
    1,252
    "Higher Mhz would give more useful bits..."

    Nope. A 50 ppm clock oscillator ($4.00) is less than 15 bits of precision. 25 ppm ($50.00) is less than 16 bits. You can use either one to count up a 99-bit number, but only the 16 most significant bits will be ... significant.

    Your answers cleared up just about everything.
    Does the counter get reset each time it is latched, or continue to run?
    Is this to be hand-wired on perf board, assembled on a small pc board, or what?

    To reduce the number of Arduino pins from 32 to 12, the latches can have tri-state outputs.
    TI has 50 MHz counters in AC, ACT, ALS, AS, F, FCT, and S technologies. The majority of them are 4-bit devices.
    Digi-Key stocks everything.

    8 - 4-bit synchronous counters
    4 - 8-bit edge-triggered latches
    1 - Clock oscillator device
    1 or 2 logic gates to control the exact timing of the 4 latches latching.

    ak
     
  10. Corey Haddad

    Thread Starter New Member

    Oct 14, 2015
    13
    0
    That's a good reminder. Part of what I was thinking when I said "more useful bits".... I was thinking of the overall amount on entropy my device could produce. With a very fast clock, my "button pushing" could also happen very quickly, and the small time increments would have sufficient oscillations in between to that some of the bits would be random. And imagine the "button" could be pushed by some other unpredictable physical event, which could be significantly faster than a human could move. The converse, say the clock was just at 10 Hz, pushing the button a few times a second would yield very few useful bits. With 50ppm, 15 usable bits, a 32-bit counter is out the window. I'll still go for 24-bit so I can at least observe some of the junk data.


    The counter can continue to run, and just repeatedly overflow. I'll sort out the mess in software.
    This will all be done on a perf board.

    So would this work as the counter - https://www.digikey.com/product-search/en?keywords=568-7629-1-ND ? When synchronous counters are set up in a series, do they remain synchronous with each other?

    And this for the oscillator - https://www.digikey.com/product-detail/en/636L3C020M00000/CTX694CT-ND/604652

    I'm a little bit lost on which latch would work.

    And the logic control gates... is that about making sure the latch only reads the pins of the counter when they are stable? Or to keep the latches synchronized?

    Here is my little schematic of where I think we are at.
    latches.jpg
     
  11. AnalogKid

    Distinguished Member

    Aug 1, 2013
    4,546
    1,252
    Coming along nicely.

    The 163 you link to is rated for 55 MHz, too close to the target speed. Other versions are rated for over 100 MHz and are in stock at DK. Mo margin mo betta.

    The clock signal (which is a square wave, not a sine wave) drives all 4 counters in parallel so there is no skew in the timing. Other control signals among the counters combine them into a single 32 bit, fully synchronous entity. See figure 3 on page 12 here:
    http://www.ti.com/lit/ds/symlink/sn74als163b.pdf

    Your schematic shows half the number of counters and latches. And BTW, THANK YOU for the schematic. You can't imagine how many people try to get into deep detail about design or troubleshooting without a schematic or sketch or cell phone photo or anything.

    Option a - the logic is there to assure that the latches have enough setup time. That is the minimum time required between when the inputs stop changing and when the latch signal is applied. One way to do this is with a 2-stage shift register that synchronizes the latch signal with the clock signal. The idea is that the counters increment on the positive edge and the latches latch on the negative edge.

    ak
     
  12. Corey Haddad

    Thread Starter New Member

    Oct 14, 2015
    13
    0
    I've got an updated schematic.

    pencil.jpg

    I am going to use 6-4 bit counters for a total of 24-bits.

    About the ti-state output, I'm assuming that means that each latch will take it's 8-bit binary input and convert it to base-3 output? It seems like the Arduino should be able to handle ti-state input, I just don't have any experience with it. And I wonder if or how much slower a tri-state read would be vs a binary read (the Arduino, reading the latch pins).


    I've been struggling with the design of the triggering logic. Here what needs to happen. A high pulse will arrive from the trigger of unknown duration. The input should be inverted and passed onto the latches at the next falling edge. The now-low signal must be held for some period of time to give the Arduino a chance to read the latches. Ideally the Arduino would send a 'release' signal immediately after it had finished reading the pins on the latches. The release signal from the Arduino should unlock the latches and prime the trigger logic to be ready to receive the next trigger pulse. But what if the trigger happens to be engaged when then Arduino sends its release signal? There are two acceptable options. One is that the latches unlock, ignoring the fact the the trigger signal is high, and they would remain unlocked with the trigger signal went low. Then, as usual, the latches would lock when ever the trigger signal rose again. The second option is that the latches don't unlock until 1) the Arduino release signal has been sent and 2) The trigger signal is low. I've made some progress with a J/K flip flop, but I don't think am handling it well.

    Does it make sense to drive this circuit on 3.3 volts?


    Here is the running parts list:
    (1) 20 Mhz Clock-oscillator at 50 PPM - https://www.digikey.com/product-detail/en/636L3C020M00000/CTX694CT-ND/604652
    (6) 4-bit 167 Mhz synchronous counter - https://www.digikey.com/product-detail/en/MC74AC161DG/MC74AC161DGOS-ND/1479405
    (3) 8-bit transparent latches - https://www.digikey.com/product-detail/en/SN74HC373N/296-1591-5-ND/277237
    (1) Negative Edge J/K Flip-Flop - https://www.digikey.com/product-detail/en/SN74F112N/296-33892-5-ND/1570074

    I am going to use 6-4 bit counters for a total of 24-bits.


    About the ti-state output, I'm assuming that means that each latch will take it's 8-bit binary input and convert it to base-3 output? It seems like the Arduino should be able to handle ti-state input, I just don't have any experience with it. And I wonder if or how much slower a tri-state read would be vs a binary read (the Arduino, reading the latch pins).


    I've been struggling with the design of the triggering logic. Here what needs to happen. A high pulse will arrive from the trigger of unknown duration. The input should be inverted and passed onto the latches at the next falling edge. The now-low signal must be held for some period of time to give the Arduino a chance to read the latches. Ideally the Arduino would send a 'release' signal immediately after it had finished reading the pins on the latches. The release signal from the Arduino should unlock the latches and prime the trigger logic to be ready to receive the next trigger pulse. But what if the trigger happens to be engaged when then Arduino sends its release signal? There are two acceptable options. One is that the latches unlock, ignoring the fact the the trigger signal is high, and they would remain unlocked with the trigger signal went low. Then, as usual, the latches would lock when ever the trigger signal rose again. The second option is that the latches don't unlock until 1) the Arduino release signal has been sent and 2) The trigger signal is low. I've made some progress with a J/K flip flop, but I don't think am handling it well.

    Does it make sense to drive this circuit on 3.3 volts?


    Here is the running parts list:
    (1) 20 Mhz Clock-oscillator at 50 PPM - https://www.digikey.com/product-detail/en/636L3C020M00000/CTX694CT-ND/604652
    (6) 4-bit 167 Mhz synchronous counter - https://www.digikey.com/product-detail/en/MC74AC161DG/MC74AC161DGOS-ND/1479405
    (3) 8-bit transparent latches - https://www.digikey.com/product-detail/en/SN74HC373N/296-1591-5-ND/277237
    (1) Negative Edge J/K Flip-Flop - https://www.digikey.com/product-detail/en/SN74F112N/296-33892-5-ND/1570074
     
  13. GopherT

    AAC Fanatic!

    Nov 23, 2012
    6,068
    3,838
    A "tri-state" output is an output with three possible electrical states. Each pin can be High (+5V), Low (0V), or, neither (essentially disconnected) known as a High impedence state (Z). .
     
  14. djsfantasi

    AAC Fanatic!

    Apr 11, 2010
    2,812
    834
    As GopherT described, the result is that its output is NOT base 3.
     
  15. AnalogKid

    Distinguished Member

    Aug 1, 2013
    4,546
    1,252
    Easy part first, you do not want a transparent latch. An edge-triggered latch prevents the latched data from changing if the latch pulse is wider than a counter clock pulse. A blah-blah-blah-574 is the standard critter.
    http://www.digikey.com/product-sear...ts-ics/logic-flip-flops/2556318?k=574&stock=1

    Tri-state is not trinary logic. It is a signal multiplexing method to reduce pin counts at the expense of bandwidth. For example, your desktop computer might have 4 GB of ram, but it does not have 32 billion individual data lines running from the memory array to the CPU. Depending on its age and cost, it probably has 32 or 64 data lines. An address and decoding scheme selects which parts of which memory devices are connected to the data bus at any time. Same thing for your circuit. The 8 output lines from each of three 8-bit latches are connected in parallel, presenting only 8 data lines to the Arduino. Each latch has an output enable control input, and the Arduino drives these individually with three output lines. The Arduino sends out an enable-1 signal, waits a microsecond, then reads the 8-bit data input. Then it disables latch #1, enables latch #2, and reads in that data. 8 data lines plus 3 control lines is fewer than 24 data lines. Note that the three latches were clocked simultaneously, so no matter how long it takes to read the data, the data is exactly what you want - a snapshot of a single 24-bit counter value. There is not a big time penalty for this because even if the latches presented all 24 bits in parallel, the Arduino has to read them in with three separate port read commands. It is multiplexing the data internally anyway.

    All of the parts are available in 3.3 V, 5 V, or anything from 2 to 5 V. The Digi-Key parametric table lists all options. Totally up to you.

    Latch logic in a separate post. Two questions:
    What is the absolute minimum time between external event triggers?
    Is the Arduino polling an input to detect a trigger, or is the external event trigger signal pulling a hardware interrupt?

    ak
     
    Last edited: Oct 16, 2015
    GopherT likes this.
  16. AnalogKid

    Distinguished Member

    Aug 1, 2013
    4,546
    1,252
    Let's assume that the external event triggers (EET) are at least tens of milliseconds apart. This is enough time for the Arduino to read in the data without any kind of feedback to the timer circuit. The EET signal goes to the latches and the Arduino simultaneously. No timing issue here because the latches latch in 10 ns and the Arduino cannot possibly do anything that fast. So whenever the Arduino gets around to reading the latches (parallel, multiplexed, whatever), the data is just sitting there.

    What happens if another EET happens before the Arduino has read the data from the last one? The previous data is overwritten, gone, poof. There is no FIFO or other buffer structure in the design so far. If this is a problem, then the latches can wait for feedback from the Arduino before accepting another EET, but that means an EET might be skipped. If you want some kind of buffer memory to allow the Arduino the ability to catch up, things just go much more complex. It still can be done with discrete chips, but I'd recommend moving to a CPLD.

    One way to make sure that the counter outputs are stable before the latches latch is to play games with the logic polarities and edge directions of the control signals. I'm looking into that now.

    ak
     
    GopherT likes this.
  17. AnalogKid

    Distinguished Member

    Aug 1, 2013
    4,546
    1,252
    Potential problem - what is the minimum clock frequency your application can stand? While 16x counters are rated for up to 200 MHz, that speed rating does *not* extend to any form of multi-counter string. It has to do with the way the chips internally decode the carry or terminal count pulse. That pulse can have glitches, and when clock pulse widths are below about 30 ns a glitch might occur on top of a clock edge. So, how low can you go? If you really really really need 50 MHz, we're talking ECL or PECL for discrete logic, or a CPLD.

    If you can go with a slower clock speed, such a 10 or 20 MHz, then check this out:
    http://www.ti.com/lit/ds/symlink/sn74lv8154.pdf

    32 bit counter, snapshot latch, and tri-state drivers all in one chip for $1.10. That is just so sick.

    ak
     
    Last edited: Oct 16, 2015
    Sinus23 and GopherT like this.
  18. AnalogKid

    Distinguished Member

    Aug 1, 2013
    4,546
    1,252
    Here is a first pass based on the 8154. There might be race conditions in the latch enable, still thinking it through. Reset Out is there to clear the big counter at power on and any other time you want it to start over.

    An alternate arrangement has U2 cleared by the Arduino as in your sch.

    ak
    Random-2-c.gif
     
    GopherT likes this.
  19. Corey Haddad

    Thread Starter New Member

    Oct 14, 2015
    13
    0
    Good. Thanks for the link. https://www.digikey.com/product-detail/en/SN74AC574N/296-33651-5-ND/1575954 looks good.

    Okay, that makes total sense. I'll update the schematic.

    Noted.

    There is no guaranteed minimum between external triggers. I'll have control over the typical rate, which could be from a few per second to possibly hundreds or more events per second, depending on the empirical results and performance of the circuit. But the minimum time could dip between trigger-highs could be a nanosecond or less. There could even be no gap at all, a trigger event collision of sorts, which would obviously be indistinguishable from a single event. I know the circuit will not be able to gather data when the events are too close together, and that is fine. I'll use the event trigger to pull the hardware interrupt, which could be the same signal that locks the latches. I'm expecting to have the Arduino give a feed back signal when it is done collecting all the data of the latches, which would ready the circuit to receive the next event-trigger rising edge. If other trigger events happened before the Arduino readied the circuit, I would want them to just be ignored. And if the event trigger signal was high (as it could,periodically, persist for an extended time) at the moment the Arduino readied the circuit, I would want that input to be ignored, the logic waiting for the next rising edge instead.

    It is totally fine if EETs get skipped on account of the circuit not being ready. Waiting for feedback from the is what I was thinking. An alternative would be to have a tune-able delay on the circuit itself, locking the latches for x cycles. That amount of time could be adjusted to be longer than the longest it typically took the Arduino to get the data it needs. For now though, I prefer the idea of Arduino feedback.

    10 or 20 Mhz is totally fine to achieve simplicity. I could go to 2 Mhz if I had to. More Mhz would will give overall project a higher maximum output of entropy. But this is a prototype / proof of concept, and the concept will be just as relevant in lower-performance implementation. But I want the result to be awesome, and in this case more bits / second = more awesome.

    Nice find one that chip! It looks good on first review, I'll examine it a little more closely this evening. I must go for a bike ride this afternoon, the nice days are about to run out for the season.

    Edit: Look at that beautiful schematic you made! I am grateful.
     
  20. GopherT

    AAC Fanatic!

    Nov 23, 2012
    6,068
    3,838
    Wow, @AnalogKid You seem to have fallen in love with this project. That was a lot of effort.
     
Loading...