-3
\$\begingroup\$

Most interfaces to ADCs (analog to digital converters) look like the following: Start the ADC and wait for it to finish the measurement.

Buridan's principle [1] says that a discrete decision based on a continuous range of values cannot be taken in a bounded length of time. It seems that voltages are inherently continuous (and not discrete) https://physics.stackexchange.com/questions/131674/are-voltages-discrete-when-we-zoom-in-enough

So it seems that a perfect ADC cannot do its job in a bounded length of time. [1] also says : "Another often-suggested escape from Buridan’s Principle is noise—the introduction of randomness into the system .... In classical physics, randomness is a manifestation of a lack of knowledge."

My question is : Is it possible to build an imperfect (non-deterministic) ADC whose (digital) output pins arrive valid logical values (close to 0V or 5V, but not close to the middle) within a bounded amount of time? For simplicity consider a 1 bit ADC with a 5V reference voltage. Ideally, it has to tell me whether the input is less then 2.5V or larger(or equal). However I allow some non-determinism. More precisely, for some small value (say ε), I allow the ADC to output any logically valid value if the input is between 2.5V - ε and 2.5V + ε Furthermore, the output need not be deterministic if the input is the above range. The ADC can take other inputs, perhaps as a source of randomness. ε should be a small value, say 0.2V

If you think I'm being paranoid, please read about the arbiter problem [2]. I have a life-critical application in mind. Ideally, I would like to read a paper proving properties desired above.

[1] : Lamport, L. (2012). Buridan’s Principle. Found Phys 42, 1056–1066. http://link.springer.com/article/10.1007/s10701-012-9647-7

[2] : Chaney, T.J., and Molnar, C.E. (1973). Anomalous behavior of synchronizer and arbiter circuits. IEEE Transactions on Computers 22, 421–422. http://ibm-1401.info/AnomalousSynchronizer_ChaneyMolnar_IEEE1973.pdf

\$\endgroup\$
10
  • 2
    \$\begingroup\$ As a practical matter, yes, of course. You are thinking primarily of successive-approximation ADCs, but the opposite extreme of a flash ADC having one comparator for each possible output code has a well bounded conversion time (often permitting many million samples per second). Of course there are many sources of error. \$\endgroup\$ Aug 21 '14 at 20:31
  • \$\begingroup\$ I have a life critical application in mind. So "as a practical matter" does not seem to be a very satisfactory answer to me. What are the sources of error? I already allowed erroneous but logically valid digital outputs when the input is between 2.5V - ε and 2.5V + ε \$\endgroup\$ Aug 21 '14 at 20:38
  • \$\begingroup\$ Have you checked out the "guaranteed" spec on any ADCs recently? \$\endgroup\$
    – Andy aka
    Aug 21 '14 at 20:38
  • \$\begingroup\$ Could you perhaps clarify something for me? It sounds to me very much like you've just asked whether a CMOS non-inverting buffer is possible. \$\endgroup\$ Aug 21 '14 at 21:24
  • 4
    \$\begingroup\$ @Abishek, any digital sampling circuit has some possibility to enter a metastable state. However with sufficient syncronization stages it's possible to make the mean time to failure exceed the lifetime of the universe. Here's a reasonable introduction (unfortunately, Powerpoint link): google.com/… \$\endgroup\$
    – The Photon
    Aug 21 '14 at 21:38
4
\$\begingroup\$

What you're missing in your "analysis" is time scale. Buridan's ass comes from a family of formal logic constructs that are used to point out logical fallacies and paradox's that are useful in thinking about things. Just blindly going to the progenitor concept misses out some very important domain specific ideas and concepts. In other words, if you want to talk philosophy go else where , it doesn't apply. Making a simple concept sound more erudite by obfuscation doesn't help you understand. And yes, I used needlessly large words on purpose.

What does apply is the fact of meta-stability, in which a changing input could manifest itself in a indeterminate outcome on the output. However, this is well understood, and in modern circuits limits the practical applications to switching speeds that are no longer than in the range of picoseconds, to perhaps 100's of picoseconds. Another way of looking at this is that if you wait long enough, metastability issues will not complicate you output decisions and will manifest themselves as small scale noise or uncertainly. This time scale is far far less than anything happening within your hypothetic ADC (operating at 10's nanoseconds or longer).

I am far more concerned about the architectural completeness of the ADC and making sure that it doesn't miss any codes than I am about one easily avoided contributor to internal timing constraints of the design.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ The essence of the Buridan's Ass problem is that even an unchanging input can manifest itself as meta-stability in the decision circuit, and that meta-stability can be arbitrarily long. This appears to be some kind of fundamental law; it cannot be fixed. In situations where there exists a safe default for the decision, any "waffling" can be routed to the safe default after a fixed time. But there are situations in which the answer must be correct, with no safe default. \$\endgroup\$
    – Kaz
    Aug 22 '14 at 0:13
  • 1
    \$\begingroup\$ There is a meta-stability in some classes of circuits, to call something arbitrarily long is flat out wrong. There is an exponential relationship with time whereas after (in most modern processes) this meta-stability is infinitesimally small. This time scale is on the order of ps. Buridan's ass is a philosophy tool and is not a fundamental "law". To speak of laws you need to speak to mechanisms. \$\endgroup\$ Aug 22 '14 at 1:04
  • \$\begingroup\$ @Kaz: The cases where "waffling" would be a problem are those in which either answer would be correct but only if everyone agrees upon it. If trains A and B approach a junction, and whichever one arrived first should be allowed to go first, then in cases where the system can't tell which one arrived first, having A go first or B go first would be equally acceptable. What would not be acceptable would be to have the decision-making circuit waffle such that A's signal thinks it's saying "A" should go first, and B's signal thinks it's saying "B" should go first. \$\endgroup\$
    – supercat
    Aug 22 '14 at 15:54
  • \$\begingroup\$ @Kaz: Note that it would be possible to design the signalling apparatus such that A would only be allowed to proceed if the signalling apparatus unambiguously favored A, and B could only proceed if it unambiguously favored B, and that in case of a tie both trains would be told to stop unless or until the signalling apparatus made up its mind. Such an approach can be helpful in some situations, but often merely ends up deferring "hard" decisions; further, the amount of logic it requires can grow exponentially with the length of the deferral. \$\endgroup\$
    – supercat
    Aug 22 '14 at 15:58
  • \$\begingroup\$ @Kaz if time is continuous, then deciding whether to use the output or the safe default suffers from the same problem. What if the safe default is A, and you get a result of B at the same moment (or within ε picoseconds). How long will you wait for the meta-stability-detector to decide whether the original circuit was meta-stable or not? Will you add a meta-stability-detector-meta-stability-detector to detect when the meta-stability-detector itself is metastable? \$\endgroup\$
    – user253751
    Aug 24 '14 at 5:39
4
\$\begingroup\$

Try to solve this from the 'opposite' direction.

Find all of the ADCs which provide a life-critical guarantee which have enough resolution and claim to settle within the time you require. I believe that will be a very small number of manufacturers and parts. Most manufacturers explicitly do not guarantee products for life-critical or safety-critical applications.

Once you have a non-empty list of candidate parts, ask the manufacturers.

\$\endgroup\$
1
  • \$\begingroup\$ Can't be said much more clearly than that!! \$\endgroup\$ Aug 22 '14 at 0:20
3
\$\begingroup\$

Buridan's problem doesn't mean that ADC's do not finish in a bounded amount of time, but rather than they don't necessarily settle on deciding the correct value in a bounded amount of time.

The problem will manifest itself rather differently.

Suppose that the continuous value lies between two discrete approximations N and N+1. It is a little bit closer to N+1, but because the ADC doesn't have enough time, it happens to report N rather than N+1.

Suppose the signal is perfectly flat for some time, and free of noise. But because it is it exactly at the troublesome "in between" value between N and N + 1, the ADC jitters chaotically between reporting N and N + 1 on successive samples, because it has not had enough time to settle on the correct value.

Subsequently, this jitter could be a real problem!

We are not saved by noise either. If the signal has noise in it, you might think it will just nudge the decision to N + 1. But in reality, noise just shifts the problem to a range of lower signal values, which will sill have jitter: sometimes the noise will flip the decision to N + 1, sometimes not.

Mathematically speaking, there is a correct value. In the ideal version of the circuit, this value is obtained by comparing two real numbers. But real numbers are infinitely precise; they are objects which cannot be computed in a finite number of time.

If you have to decide whether X is, say, greater than 1/2, or less than or equal to 1/2, and X is exactly 1/2, you have a problem. If you compute X to one decimal digit, you have 0.5. You do not know whether this is greater than a half. If you compute it to two digits, you have 0.50. You still do not know. No matter how far you compute it, you do not know the answer; even after a trillion zeros, there could be a another zero (you must continue deciding), or a nonzero (you may conclude that X exceeds 1/2). This, I believe, is the essence of Buridan's problem.

Note that you can just stop after a fixed number of digits; but then you risk reporting the wrong answer.

According to Leslie Lamport's paper, if you try to escape the problem by defining a small range around 1/2 (a "gray area") you still have the same problem: that of deciding whether a number is in the range or out.

Suppose that in our ADC, the gray area defaults to an "N+1" indication. Then any hesitation at the boundary between the gray area and N will still result in jitter between N and N+1.

\$\endgroup\$
6
  • \$\begingroup\$ Gray areas are fine for me. The safety proof of my overall system works with either output (N or N+1) in the gray area. I believe that what you are saying is correct and I understand Buridan's principle exactly that way. However, one of my colleagues doesn't buy this argument. He says that arbiters are not guaranteed to terminate, even if we allow non-deterministic output at gray areas. Is there a paper explicitly explicitly showing that we can build ADCs which always finish within finite time in stable states, but are allowed to behave non-deterministically (between N and N+1) in gray areas? \$\endgroup\$ Aug 22 '14 at 15:36
  • \$\begingroup\$ @Abhishek: Suppose each arbiter reports "1" when the input x is greater than 0.505, or "0" when the input is less than 0.495, or 100x-49.5 when the input is between those ranges. If the output of the first arbiter is used directly, the output will be unless input is between 0.495-0.505. If the first arbiter feeds a second arbiter, the output of the second will be clean unless the input is between 0.49995-0.50005. If that second arbiter feeds a third, the output will be clean unless the input is 0.4999995-0.5000005. \$\endgroup\$
    – supercat
    Aug 22 '14 at 15:41
  • 2
    \$\begingroup\$ @Abhishek: Generally, since both time and voltage are potentially continuous, it's best to use cascaded D latches as arbiters. A typical D latch will have many orders of magnitude of gain with respect to both voltage and time, so cascading even two is considered sufficient for most applications; if the application allows cascading three or four, that might not be a bad idea, but once one reaches that level, the probability of metastability occurring by chance will fall below the probability of the apparatus being destroyed by a meteor strike. \$\endgroup\$
    – supercat
    Aug 22 '14 at 15:47
  • 1
    \$\begingroup\$ @supercat "probability of metastability occurring by chance will fall below the probability of the apparatus being destroyed by a meteor strike" . I agree. However I at least have some intellectual interest in finding out whether or not (and why) it can be done with probability exactly 1 \$\endgroup\$ Aug 22 '14 at 17:23
  • \$\begingroup\$ @Abhishek: Assuming time, voltage, and current are continuous quantities, there is no way to guarantee with probability 1 that two or more entities will within any particular bounded time reach a consensus about the state of an object at some particular time. If every component were to have a known finite gain, one could ascertain ranges of input conditions which would cause errant behavior. One can make those ranges very small, but not eliminate them. \$\endgroup\$
    – supercat
    Aug 22 '14 at 17:38
2
\$\begingroup\$

Any sort of digital system whose input is analog or asynchronous will have a possibility of entering a metastable state; there is nothing special about an ADC in that regard. On the other hand, the same general techniques that can be used to deal with asynchronously-changing signals can be used to deal with analog measurements. If a signal is double-synchronized, it will be very unlikely that the output of the second latch will change at any time other than immediately following a clock edge. It if it's triple synchronized, the probability of the second latch's output changing at precisely the moment necessary to cause the third latch to become metastable would be infinitesimal. Adding a fourth synchronizer would reduce the probability even further.

With regard to analog-to-digital converters, it would conceptually be possible to design a successive-approximation ADC which used a "gray-code" architecture internally, so that in the cases where an input was right near the threshold, the voltage processed by the next stage would not depend upon whether the input was above or below the threshold (e.g. if x is input to a stage, the value to be processed by the next stage might be 2x if x is below 0.5, or 1-2x if it's above 0.5; if x is 0.5, then the value to be processed by the next stage will be 1 regardless of whether x was found to be above or below 0.5. I don't know if such designs are used, but they would certainly be possible. Otherwise, I would expect that a typical ADC may have a small but non-zero probability that a particular reading would be totally wacky, but oversampling and using a median-of-three filter should take care of that.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ According to the underlying theory associted with Buridan's Ass problem, as developed by Leslie Lamport, nothing can fix the problem. There will be some in-between values of the signal for which the ADC cannot decide the correct value, and so it will randomly flip between different values on successive samples. \$\endgroup\$
    – Kaz
    Aug 22 '14 at 0:09
  • \$\begingroup\$ @Kaz: An LSB of noise is expected. What's not generally expected, but could occur anyway, would be for a successive-approximation ADC to fail to latch the first (most significant) bit cleanly, such that what should be either 1000 or 0111 ends up as 1111 or 0000. Using gray coding would help avoid that possibility. \$\endgroup\$
    – supercat
    Aug 22 '14 at 3:21
1
\$\begingroup\$

In practice I've never seen an ADC converter that did not produce a result in a bounded length of time. It may not be the optimal result, but it will be a result.

For example, the ADS1271 Delta-Sigma ADC produces exactly one result every 512 clock cycles.

A low end switched-capacitor successive approximation converter as in an MCU has so many clock cycles (11 or something like that for a 10-bit converter) to produce a result. There will be 10 bits in the register at the end of that time.

\$\endgroup\$
3
  • \$\begingroup\$ Thanks. As with the arbiter in [2], it might just be that there is a very small probability of the ADS1271 Delta-Sigma ADC being in a meta-stable state after 512 clock cycles. In a meta-stable state, the voltage at a digital output pin is near the middle of the voltages representing logical 0 and logical 1. \$\endgroup\$ Aug 21 '14 at 21:36
  • 1
    \$\begingroup\$ The result from ADS1271 is actually the output from an FIR digital filter, so any exceedingly rare metastability due to analog functions would have a small effect on the output, I think. \$\endgroup\$ Aug 21 '14 at 21:36
  • 1
    \$\begingroup\$ @SpehroPefhany: A delta-sigma ADC only grabs one bit at a time. If the analog logic were to act as though the bit were "high" but digital logic thought it was "low", or vice versa, that could corrupt the measured value slightly, but I think the feedback loop would pretty quickly sort it out. \$\endgroup\$
    – supercat
    Aug 22 '14 at 15:59
1
\$\begingroup\$

I get the sense this question about finite bound on ADC measurement time, isn't really about ADCs or comparator application circuit design, but rather a concern about metastability and system noise (error voltage), and their impact on life-critical/medical applications.

Although all commercially available ADCs work -- trust me, really they do -- I recognize you're trying to simplify your design for some kind of life-critical product medical design review. It sounds like the real crux of the problem is how to prove that a design has acceptable mitigation against metastability in the digital input synchronizer. This question has seemingly veered in different directions though, first about ADCs and the well-known problems of digital metastability, then 1-bit ADC circuit... I'll try to answer both questions here, but you may get more useful results from this community if you rephrase and ask the question again with a title that references metastability, e.g. "life-critical application proof: metastability and digital input synchronization". Although this kind of question does come up sometimes, I've never seen how the medical/life-critical system proof is normally addressed -- what little I've seen has to do with ensuring that the medical device cannot harm the patient. Must be answerable though.

Mitigating Against the Possibility of Metastability

The remote possibility of metastability cannot ever be completely eliminated in any digital system, because it's physically impossible to switch between logic low and logic high voltages without slewing through the intermediate 'gray zone' that provides the noise immunity, inherent in a digital system. The best defense is to slew as quickly as possible, and use multiple stages of flip-flops when crossing clock domains. This doesn't make digital logic itself impossible or unreliable, it just means careful design is required to ensure correct operation.

The commonly used practice is described several places, such as this related question: Synchronising GPIO transitions to an external clock

Check the medical regulatory standards that your device needs to meet, as this should tell in objective, measurable terms what is an acceptable risk.

Comparator + Voltage Reference = '1-bit ADC'

In the comments, I suggested using a standard comparator + voltage reference as effectively a 1-bit ADC. This is a well-known technique. At the risk of being a shill, here's one of the integrated comparator + voltage reference chips that my employer offers: http://datasheets.maximintegrated.com/en/ds/MAX9025-MAX9028.pdf . See figure 3 for the optional external hysteresis circuit. Not trying to push Maxim parts here, it's just that's what I'm most familiar with.

A comparator is very similar to an operational amplifier, but optimized for low input offset voltage, large differential input signals, fast output rise/fall times, and fast recovery from output saturation, to switch quickly between "logic high" and "logic low" output levels. Most comparators also use open-drain output instead of push-pull. The synchronizer metastability issue doesn't apply to the comparator itself, but obviously does still apply whenever an asynchronous signal enters a synchronous digital clock domain. So the customary digital input synchronization techniques should be used at that point.

The 'finite bound on measurement time' is known as 'propagation delay' (tPD+ and tPD- depending on rising or falling output level). This propagation delay depends on the input overdrive level and the supply voltage. See for example MAX9025 Typical Operating Characteristics graphs at the bottom of page 7 of the data sheet. Since this device has typically 4mV of internal Input-Referred Hysteresis, the input overdrive must exceed this hysteresis level for reliable detection. From the Propagation Delay (VCC+5V) graph (MAX9025toc27) the propagation delay is less than 40us. More importantly, the Rise Time (1.6us typical) and Fall time (0.2us typical) are what determine the fraction of time that the output can spend in the 'gray area' that potentially could trigger a metastable state. These are given in the data sheet as typical values because of the dependency on system capacitance.

Mitigating Noise

This Analog Devices article provides a good general introduction to how to design a hysteresis circuit around any comparator. http://www.analog.com/library/analogdialogue/archives/34-07/comparators/ Note especially the noise shown in figure 1. Without hysteresis, analog noise is captured as digital noise near the switching threshold. Adding hysteresis shifts the effective switching threshold by adding a small amount of positive feedback.

Temperature itself is one source of noise -- Johnson-Nyquist noise affects all electronic components to some degree. Even if your circuit were cryogenically cooled with liquid helium (presumably at high operating cost), there would still be some small amount of thermal noise. How much noise, actually depends on how long you measure it. Sometimes this is specified on op amp data sheets in units of V per square root of Hz. Usually this effect is considered negligible.

Temperature variation is another source of noise, as most every component has a temperature coefficient. Mismatched temperature coefficients cause a system to have some degree of sensitivity to ambient or operating temperature. When the HVAC system turns on and warm or cool air is forced into the room, there can be a small but detectable variation in measurements. Whether or not this matters in your application, I can't determine.

If you haven't already, your next step should be to contact an applications engineer at one or more of the companies that make analog ICs. System-level design review is really the only way to address your concerns about medical regulatory compliance, performance, reliability, and cost trade-offs -- this is beyond the scope of what can be answered here.

I'd suggest you start with (in no particular order) Linear Technology, Analog Devices, Texas Instruments, Maxim Integrated (my day job) -- these are the big analog companies I'm most familiar with, but certainly not the only IC manufacturers that deal in op amps, comparators, and voltage references.

\$\endgroup\$
0
\$\begingroup\$

Introduce a level of hysteresis before the ADC. Now your "life-critical" problem has a solution.

You can't have perfection, it doesn't exist. On the other hand, everything is already perfection, we just refuse to accept it as such.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.