Gray Code(datagenetics.com)
datagenetics.com
Gray Code
http://www.datagenetics.com/blog/november32014/index.html
12 comments
Hah! I remember learning about K-Maps in my Digital Logic class and it blew my mind. Gotta love them.
This is such a beautiful explanation! And I love the shaft orientation detector example.
The biggest effect that Gray code had on my life was when it helped me pass an entrance exam to a math camp when I was pretty young (younger than most other students), because one of the questions on the entrance exam was "can you prove that there is or isn't a Hamiltonian circuit on any n-dimensional hypercube?".
The Hamiltonian path is a path that visits every node once, and a Hamiltonian circuit does this and also returns to the starting point.
https://en.wikipedia.org/wiki/Hamiltonian_path
Well, I knew about the binary Gray code from Martin Gardner (in his book Knotted Doughnuts and Other Mathematical Entertainments), and I realized that if you think of an n-bit number as a coordinate in n-dimensional space (like 10101110 is the coordinate (1, 0, 1, 0, 1, 1, 1, 0)), then the n-bit binary Gray code is already a description of a Hamiltonian cycle on the unit n-dimensional hypercube.
It tells you how to trace the path, because it tells you which vertices to go to in which order. Every transition from one number to the next is an edge of the cube because it involves changing exactly one bit (so, exactly one dimension), which is exactly what defines the edge of a cube (it's a movement in exactly one dimension). You visit every vertex because the Gray code includes every number, and as this linked article says, the default Gray code is cyclic and comes back to the original starting point at the end.
We know that there's a Gray code for any number of bits because there is a recursive reflective procedure for constructing them to any length (as described in this article): take the (n-1)-bit Gray code, write it forwards prefixed with 0 and then backwards prefixed with 1, and you have an n-bit Gray code. This also has a nice geometric interpretation, which is that given a Hamiltonian circuit on an (n-1)-dimensional hypercube, you can do it on the "lower" hypercube, go "up", do it backwards, and then come "down", and now you've created a Hamiltonian circuit on the larger n-dimensional hypercube.
This answer let me pass the test and get into the math camp, but I found it pretty difficult when I actually went, I think because I didn't exactly come up with this answer "on my own": Martin Gardner did a ton of the work for me in teaching me about Gray codes, and I had already been thinking about the isomorphism between binary numbers and hypercubes before for some reason.
The biggest effect that Gray code had on my life was when it helped me pass an entrance exam to a math camp when I was pretty young (younger than most other students), because one of the questions on the entrance exam was "can you prove that there is or isn't a Hamiltonian circuit on any n-dimensional hypercube?".
The Hamiltonian path is a path that visits every node once, and a Hamiltonian circuit does this and also returns to the starting point.
https://en.wikipedia.org/wiki/Hamiltonian_path
Well, I knew about the binary Gray code from Martin Gardner (in his book Knotted Doughnuts and Other Mathematical Entertainments), and I realized that if you think of an n-bit number as a coordinate in n-dimensional space (like 10101110 is the coordinate (1, 0, 1, 0, 1, 1, 1, 0)), then the n-bit binary Gray code is already a description of a Hamiltonian cycle on the unit n-dimensional hypercube.
It tells you how to trace the path, because it tells you which vertices to go to in which order. Every transition from one number to the next is an edge of the cube because it involves changing exactly one bit (so, exactly one dimension), which is exactly what defines the edge of a cube (it's a movement in exactly one dimension). You visit every vertex because the Gray code includes every number, and as this linked article says, the default Gray code is cyclic and comes back to the original starting point at the end.
We know that there's a Gray code for any number of bits because there is a recursive reflective procedure for constructing them to any length (as described in this article): take the (n-1)-bit Gray code, write it forwards prefixed with 0 and then backwards prefixed with 1, and you have an n-bit Gray code. This also has a nice geometric interpretation, which is that given a Hamiltonian circuit on an (n-1)-dimensional hypercube, you can do it on the "lower" hypercube, go "up", do it backwards, and then come "down", and now you've created a Hamiltonian circuit on the larger n-dimensional hypercube.
This answer let me pass the test and get into the math camp, but I found it pretty difficult when I actually went, I think because I didn't exactly come up with this answer "on my own": Martin Gardner did a ton of the work for me in teaching me about Gray codes, and I had already been thinking about the isomorphism between binary numbers and hypercubes before for some reason.
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). Does anyone remember where this observation appeared, and is anyone's familiarity with metastability enough to clarify how accurate or inaccurate this description is?
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.
Pressing a key on the keyboard would never do that because there's a little microprocessor built in that actually handles getting keypresses and transmitting them to the real computer. Could you crash that computer by pressing a key at exactly the right time? No. Because they've designed it so that even in the metastable state it handles things correctly. A key defaults to off. If there is enough evidence over a sample period that a key was pressed then report on. If there's not enough evidence, it's off. Switch debouncing is a well established and practiced discipline. http://www.ganssle.com/debouncing.htm
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.
Pressing a key on the keyboard would never do that because there's a little microprocessor built in that actually handles getting keypresses and transmitting them to the real computer. Could you crash that computer by pressing a key at exactly the right time? No. Because they've designed it so that even in the metastable state it handles things correctly. A key defaults to off. If there is enough evidence over a sample period that a key was pressed then report on. If there's not enough evidence, it's off. Switch debouncing is a well established and practiced discipline. http://www.ganssle.com/debouncing.htm
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.
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.
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.
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.
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.
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.
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...
[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.
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.
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.
I think it's possible, but it becomes less and less likely with the depth of the latches.
Supposing your keyboard key input was latched by a flop and you pressed the key at the exact right moment you could violate the timings of the flop and have it end up in a metastable state.
That's why you usually put a bunch of delay flops when sampling such a signal in the hope that you'll manage to have a stable signal down the line, however that doesn't remove the problem altogether, it just makes the probability of the problem happening very low.
Supposing your keyboard key input was latched by a flop and you pressed the key at the exact right moment you could violate the timings of the flop and have it end up in a metastable state.
That's why you usually put a bunch of delay flops when sampling such a signal in the hope that you'll manage to have a stable signal down the line, however that doesn't remove the problem altogether, it just makes the probability of the problem happening very low.
Huh, sounds kind of like probabilistic primality testing! (We can specify the probability of getting a false positive in the primality test and make it as low as we want, though it's still always formally possible to have false positives.)
Not only that, it is a standard within absolute encoders since years.
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.
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?
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 | 222The 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.)
I still think the most interesting thing about gray codes is the relationship to hilbert curves. It's really useful for figuring out locality with a cheap calculation (axes to/from transpose).
I use gray code to generate sobol sequences, which are psuedo random number sequences that help you approximate a distribution more quickly than purely random sequences.
A great example of a useful article that keeps me reading HN.
If you liked this, google "single track gray codes".
I've used it once making a DRAM refresh controller. That was almost forty years ago before DRAMs came with refresh circuitry build in and before you could get dedicated chips for it.
I made this 6-state sequencer
ABC -> A'B'C'
000 -> 100 -> 110 -> 111 -> 011 -> 001 -> 000 -> ...
A' = not(C) B' = A C' = B
000 = not(A) & not(C)
100 = A & not(B)
110 = B & not(C)
etc.
010 -> 101 -> 010 -> 101 -> 010 -> 101 -> ...
There was an article about computers optimizing a card trick earlier this week, and it was using Gray code.
What about to add control digits?
There are many, many, other cool articles on the site.
http://www.datagenetics.com/blog.html
Once you start reading, you'll spend the rest of the day!
http://www.datagenetics.com/blog.html
Once you start reading, you'll spend the rest of the day!
Imagine a set of deeply nested if-then-else conditions that are dependent upon a fixed set of boolean flags - this is pretty common in a state machine. Reducing those conditions to a formula that calculates a boolean value is often far less taxing on a small uC.
So I brought out one of my Electrical Engineering books (The Art of Electronics by Horowitz and Hill), let them each read the section on Karnaugh Maps [1] and then ran through some examples using their decision networks. Watching those light bulbs come on was one of the favorite events in my career.
[1] https://en.wikipedia.org/wiki/Karnaugh_map