There was an article about computers optimizing a card trick earlier this week, and it was using Gray code.
Gray Code
11–20 of 30 posts
Re: Gray Code
#12I 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.
Re: Gray Code
#13This 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?
Re: Gray Code
#14This 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).…
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.
Re: Gray Code
#15Earlier 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).…
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 th…
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.)
Re: Gray Code
#16Great 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.
Re: Gray Code
#17What about to add control digits?
Re: Gray Code
#18Coming from a embedded systems background (mostly in the telecommunications sector), I have a deep love for Gray Code. My fondest memory is teaching a group of software engineers how "us hardware guys" do logic minimization.
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.
Re: Gray Code
#19Coming from a embedded systems background (mostly in the telecommunications sector), I have a deep love for Gray Code. My fondest memory is teaching a group of software engineers how "us hardware guys" do logic minimization. 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…
Hah! I remember learning about K-Maps in my Digital Logic class and it blew my mind. Gotta love them.
Re: Gray Code
#20This 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).…
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