Gray Code
datagenetics.com
Gray Code
1–10 of 30 posts
Re: Gray Code
#2A great example of a useful article that keeps me reading HN.
Re: Gray Code
#3This 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.
Re: Gray Code
#4Great 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.
Re: Gray Code
#5There 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!
Re: Gray Code
#6If you liked this, google "single track gray codes".
Re: Gray Code
#7This 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.
Re: Gray Code
#8I 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).
Re: Gray Code
#9If 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 -> ...
Re: Gray Code
#10This 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.
Not only that, it is a standard within absolute encoders since years.