Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Gray Code

datagenetics.com

Post reply on HN
Print view View original

21–30 of 30 posts

Re: Gray Code

#21

Post by bkirwi »

schoen wrote: post #13
Marcus10110 wrote: post #3

This is a fundamental in FPGAs. The mode where the bit is unstable is called metastability. Most FPGA tools can automatically infer gray code for state machine states, and pretty much all cross clock domain FIFOs will use grey code to indicate where the read and write pointers are located.

I remember someone (but not whom or where: maybe on HN or maybe a blog post) saying that all digital systems that accept and quantize analog input will have some analog input conditions with consequences that persist and extend arbitrarily far into the digital part of the system (so that theoretically you could cause an OS on a digital computer to crash just by pressing a key on the keyboard at the exact right time).…

There you go.[0] I believe it's called the 'arbiter problem' in that context, and your description seems basically correct.

[0]: http://research.microsoft.com/en-us/um/people/lamport/pubs/b...

Re: Gray Code

#22

Post by schoen »

msandford wrote: post #20
schoen wrote: post #13

Earlier quoted context omitted.

I remember someone (but not whom or where: maybe on HN or maybe a blog post) saying that all digital systems that accept and quantize analog input will have some analog input conditions with consequences that persist and extend arbitrarily far into the digital part of the system (so that theoretically you could cause an OS on a digital computer to crash just by pressing a key on the keyboard at the exact right time).…

It's theoretically possible but not practically so. Computers are actually analog, not digital. There's a lot of effort that goes into making sure that the analog signals behave enough like the ideal digital ones, but they're still analog. So we've got very, very good at the engineering analysis to make sure that even though it's actually analog we can have a meaningful conversation about things and pretend it's not.…

In this context I'm wondering about the theoretical possibilities rather than the practical risk; I think the analysis that I'm referring to assumed the probability was negligible in practice (or can be made negligible in practice), so the question is whether it is still true that there is some analog input (even from a key on the keyboard) that in principle makes the machine misbehave even though no physically realistic process can typically actually generate that input.

The debouncing examples in the article you linked to don't seem to eliminate the risk in a theoretical sense. The RC circuit is taking an analog function of an analog function to apply some smoothing and significantly decrease the effects of transients on the observed voltage at the ADC, increasing the proportion of the time it will spend in a well-defined range if driven by a noisy switch. There must still be some set of analog inputs that would keep the voltage in an ambiguous range, though. The SR latch can itself experience metastability. (And the software solution should be right out, because it starts from the assumption that each individual digital measurement of the switch state has produced a well-defined binary value that can be safely used as input to expressions and functions at the software level.)

Wikipedia says that chaining latches together merely (dramatically) reduces the probability of this behavior, rather than actually eliminating it, because each latch could in principle (though with ever-decreasing probability) introduce and maintain metastability in the latch following it.

https://en.wikipedia.org/wiki/Flip-flop_%28electronics%29#Se...

Wikipedia cites to this article

http://ibm-1401.info/AnomalousSynchronizer_ChaneyMolnar_IEEE...

which seems to say that it was understood in the 1960s that every interface between digital circuits with no common clock (as well as every interface from an analog to a digital circuit) presented a theoretically "fundamentally inescapable" risk of introducing metastability which could propagate into the digital system, and that this was thought to be a source of some practical errors in computing systems in the early 1970s.

Re: Gray Code

#23

Post by schoen »

bkirwi wrote: post #21
schoen wrote: post #13

Earlier quoted context omitted.

I remember someone (but not whom or where: maybe on HN or maybe a blog post) saying that all digital systems that accept and quantize analog input will have some analog input conditions with consequences that persist and extend arbitrarily far into the digital part of the system (so that theoretically you could cause an OS on a digital computer to crash just by pressing a key on the keyboard at the exact right time).…

There you go.[0] I believe it's called the 'arbiter problem' in that context, and your description seems basically correct. [0]: http://research.microsoft.com/en-us/um/people/lamport/pubs/b...

Whoa, that paper is fascinating!

I'm trying to improve my intuition for why the physical exmaples in it are right. I found the examples of inevitable crashes and collisions disconcerting.

Re: Gray Code

#24

Post by Animats »

bkirwi wrote: post #21
schoen wrote: post #13

Earlier quoted context omitted.

I remember someone (but not whom or where: maybe on HN or maybe a blog post) saying that all digital systems that accept and quantize analog input will have some analog input conditions with consequences that persist and extend arbitrarily far into the digital part of the system (so that theoretically you could cause an OS on a digital computer to crash just by pressing a key on the keyboard at the exact right time).…

There you go.[0] I believe it's called the 'arbiter problem' in that context, and your description seems basically correct. [0]: http://research.microsoft.com/en-us/um/people/lamport/pubs/b...

Yes. This is a well known problem. See (https://en.wikipedia.org/wiki/Arbiter_[electronics]). It's not possible to build an arbiter which will reliably decide who wins in a fixed time. It is, however, possible to design one which can detect that the arbiter hasn't stabilized yet and delays until it has. All multiprocessor shared-memory systems need this.

Re: Gray Code

#25

Post by apitheia »

With ternary grey code, only one digit is changed at a time, but sometimes that change can be more than one value, why isn't ternary ordered so that each digit only changes by at most 1 number? for example:

   0 → 000 | 000
   1 → 001 | 001
   2 → 002 | 002
  10 → 012 | 012
  11 → 010 | 011
  12 → 011 | 010
  20 → 021 | 020
  21 → 022 | 021
  22 → 020 | 022
 100 → 120 | 122
 101 → 121 | 121
 102 → 122 | 120
 110 → 102 | 110
 111 → 100 | 111
 112 → 101 | 112
 120 → 111 | 102
 121 → 112 | 101
 122 → 110 | 100
 200 → 210 | 200
 201 → 211 | 201
 202 → 212 | 202
 210 → 222 | 212
 211 → 220 | 211
 212 → 221 | 210
 220 → 201 | 220
 221 → 202 | 221
 222 → 200 | 222

Re: Gray Code

#26

Post by a1369209993 »

apitheia wrote: post #25

With ternary grey code, only one digit is changed at a time, but sometimes that change can be more than one value, why isn't ternary ordered so that each digit only changes by at most 1 number? for example: 0 → 000 | 000 1 → 001 | 001 2 → 002 | 002 10 → 012 | 012 11 → 010 | 011 12 → 011 | 010 20 → 021 | 020 21 → 022 | 021 22 → 020 | 022 100 → 120 | 122 101 → 121 | 121 102 → 122 | 120 110 → 102 | 110 111 → 100 | 111 1…

The middle column is changing by at most one number. Furthermore, it's changing by at most one number always in the same direction, a feature not shared by the right column. (The direction thing doesn't matter for binary grey codes, since 1 + 1 = 1 - 1 = 0 and 0 + 1 = 0 - 1 = 1.)

Re: Gray Code

#27

Post by msandford »

schoen wrote: post #22
msandford wrote: post #20

Earlier quoted context omitted.

It's theoretically possible but not practically so. Computers are actually analog, not digital. There's a lot of effort that goes into making sure that the analog signals behave enough like the ideal digital ones, but they're still analog. So we've got very, very good at the engineering analysis to make sure that even though it's actually analog we can have a meaningful conversation about things and pretend it's not.…

In this context I'm wondering about the theoretical possibilities rather than the practical risk; I think the analysis that I'm referring to assumed the probability was negligible in practice (or can be made negligible in practice), so the question is whether it is still true that there is some analog input (even from a key on the keyboard) that in principle makes the machine misbehave even though no physically reali…

On the next page the author talks about ways to bulletproof this by avoiding latches and to use hysteresis to ensure that the debouncing is perfect. Not perfect in the sense that it always gets the state right -- it might register a button press when none is there if there was absolutely horrific EMI, or it might not register a button press that is too short -- but perfect in the sense that there are no undefined states. That's the point of hysteresis; you can't fake it out. If it's in the no-mans-land between decision points, it defaults to whatever it was previously.

You're right that any long chain of latches could end up metastable and screwed up. But this technique doesn't use latches, it uses multiple reads on an analog input which is interpreted digitally (but not an ADC) to preclude the possibility of any kind of undesired behavior.

Re: Gray Code

#28

Post by schoen »

msandford wrote: post #27
schoen wrote: post #22

Earlier quoted context omitted.

In this context I'm wondering about the theoretical possibilities rather than the practical risk; I think the analysis that I'm referring to assumed the probability was negligible in practice (or can be made negligible in practice), so the question is whether it is still true that there is some analog input (even from a key on the keyboard) that in principle makes the machine misbehave even though no physically reali…

On the next page the author talks about ways to bulletproof this by avoiding latches and to use hysteresis to ensure that the debouncing is perfect. Not perfect in the sense that it always gets the state right -- it might register a button press when none is there if there was absolutely horrific EMI, or it might not register a button press that is too short -- but perfect in the sense that there are no undefined sta…

The "reads on an analog input which is interpreted digitally" are effectively a one-bit ADC or comparator, aren't they?

Re: Gray Code

#29

Post by msandford »

schoen wrote: post #28
msandford wrote: post #27

Earlier quoted context omitted.

On the next page the author talks about ways to bulletproof this by avoiding latches and to use hysteresis to ensure that the debouncing is perfect. Not perfect in the sense that it always gets the state right -- it might register a button press when none is there if there was absolutely horrific EMI, or it might not register a button press that is too short -- but perfect in the sense that there are no undefined sta…

The "reads on an analog input which is interpreted digitally" are effectively a one-bit ADC or comparator, aren't they?

Yes, but typically when you're talking about an ADC you're talking multiple bits. These days an 8 bit ADC is "low resolution" and 10-12 bits are nearly free (considering they're built into tons and tons of microcontrollers).

The point was more that it was a single bit, not a 10 bit ADC that's used to make determinations about switches. From a theoretical perspective the idea of a 1 bit ADC makes sense. From an engineering perspective, it doesn't. Since I'm an engineer that's why I said what I did.

Re: Gray Code

#30

Post by ddingus »

asynchronous13 wrote: post #16
ddingus wrote: post #4

Great piece! I enjoyed it. The author comments: It's possible to generate Gray codes without this restriction (though to be honest, I can't understand the value of this, as the step-change on the warp around would experience the exact problem we are trying to solve!) Linear encoders seems to me a perfect application.

But a linear encoder would work with a Gray code that had the restriction AND it would work with a Gray code that did not have the restriction. So there's no benefit for the linear encoder.

What if it's encoded with absolute values, not relative?
Post reply on HN