7 ms·

Fifty Shades of Gray Code

127 points by akeck 10y ago

entee 10y ago
Didn't know anything about this, really interesting! One question: when you need to know exact angle of something, say a steering wheel, if you used a grey code you'd need a really fine grained code with a huge set of numbers if you used this approach. Is that how it's done? Or is there a different way?
- wrigby 10y ago
  Sometimes yes! Wikipedia has a cool picture[1] of a 13-track (and hence 13-bit) Gray code encoder in the Gray Code article[2], which would have a resolution of ~.05 degrees. 1: https://upload.wikimedia.org/wikipedia/commons/a/a8/Gray_code_rotary_encoder_13-track_opened.jpg https://upload.wikimedia.org/wikipedia/commons/a/a8/Gray_cod... 2: https://en.wikipedia.org/wiki/Gray_code#Position_encoders https://en.wikipedia.org/wiki/Gray_code#Position_encoders
  - Ericson2314 10y ago
    So the grey code itself has a graph analog (cycle in hypercube) and as the 1st picture would leave one to believe there's also some tree structure going on. Graphs on multiple levels!
- azdle 10y ago
  You would end up with a very large grey code if you tried to do that. You could solve that by gearing it down (or repeating the code) and count revolutions, but more likely these days you'd use something like a hall-effect angle-position sensor [1]. The ones linked will give you an angle with 2^12 bits, or ~0.09° just by rotating a magnet next to the IC. [1] http://www.allegromicro.com/en/Products/Magnetic-Linear-And-Angular-Position-Sensor-ICs/Angular-Position-Sensor-ICs.aspx http://www.allegromicro.com/en/Products/Magnetic-Linear-And-...
- HeyLaughingBoy 10y ago
  Yes and no. It depends. Maybe. A Gray code, as the article states, is only referenced by the Hamming distance between codes, not the bit size of the encoding. If you repeat the two-bit code: 00,01,11,10 90 times, you'll get a one-degree resolution around a circle, which is plenty for a steering wheel and usually works just as well as a 9-bit encoding (512 states). The problem becomes "how do I know where the wheel is at any arbitrary time?" The answer is: you continuously monitor the wheel by counting up or down on each code transition, and have a Home sensor to set the initial position. But now you have to remember the position when you power it off, and perhaps make sure no one can move the wheel while you're not monitoring it. Is that sufficient for your application? (hint: it is for 90% of such applications) If so, problem solved. If not, then we need to get more complex. More complex can mean: Non-Volatile Memory so we can power off and remember the last position[1], continuous battery-backup so even if main power is off, we track the wheel position, or ta-da: a 9-bit encoding so even with power off, we can encode 512 discrete states. Historically, that last solution was by far the most expensive. 1: I've worked with such a system where the position of a critical gantry was updated while it was running, then when power was off, the last (X,Y) position of the gantry encoders was remembered. Battery-powered electronics then monitored the state of an access door. If the door was opened, then the X,Y position was invalidated (someone could have moved the gantry while the encoders weren't being read) and the software would not allow the system to restart until a manual alignment procedure was done to reset the gantry to a known position and clear the "lockdown" bit. The alternative would have required two 10-bit absolute encoders that cost more than the electronics to do what I described.
  - Ericson2314 10y ago
    Cool to note that either the additional gray codes bit or the circuit (be it regs, NVRO, etc) is tracking the exact same extra information.
  - Gracana 10y ago
    RE: non volatile position storage Some of the industrial equipment I've designed at work uses Omron servos with encoders that use their own motion to provide power to the position tracking electronics, so you can disconnect the cable or otherwise lose power and not lose your zero, even if the machine is moved in the interim. No batteries required. Very cool product!
- stonemetal 10y ago
  I worked in industrial automation controls for a while. There they used a concept called quadrature to determine servo movement precisely. Quadrature is basically a grey code of [00, 01, 11, 10] that is repeated. You know what direction you are going by where you are and what comes next. If you are on 01 and see 00 you know you are going left. If you are on 01 and see 11 then you are going right. With a tad bit of math involving the gear box attached to the servo you know that one tick is real world distance X. From there it is a matter of establishing a "home" position, and counting your ticks as you move.
deleted 10y ago
[deleted]
throwawayish 10y ago
Fun-fact: the digital rotary knobs on most equipment (given name: rotary encoder) are pretty much built like this - a disc with conductive patterning read by brushes (well, bent contacts). Only the far more expensive rotary encoders are optical with an etched or printed glass disc, like typically found in industrial incremental encoders. These optical encoders typically cost 10-15 EUR a pop. Btw. using keyboard controllers to poll many switches isn't actually that unusual, but definitely a nice hack.
rflrob 10y ago
Am I missing something here, or is it only possible to easily generate Gray codes (or a similar Hamming distance 1 code if Gray refers specifically to a reflection generated code) for 2^n positions? Is there a way to do it for 12 positions like the article seems to mention? Or an odd number?
- stonemetal 10y ago
  As long as the code has adjacent entries vary by only one bit it is unnecessary to use them all. The author gives the example [110, 010, 011, 111] of a code that is valid but doesn't use all 2^n possibilities.
  - tantalor 10y ago
    That sequence has 2^2=4 positions. I don't think rflrob meant "n = number of bits" but "n = number of codes".
    - stonemetal 10y ago
      Ah, I see what you mean. [000, 001, 011, 111, 101, 100] is a grey code of length 6, so not power of two is possible. However trying to come up with an odd length code is a real head scratcher. It may not be possible in binary, but is easily accomplished in higher bases.
      - bryondowd 10y ago
        You couldn't do an odd number of codes, but if you have an odd number of positions, I suppose you could have one position represented by two adjacent codes. So, you could have a wheel with 5 equal pie slices, but on the reverse, one of those slices is divided in half, with a different encoding on each, that both resolve to the same value/result.
- default-kramer 10y ago
  An odd number of positions is impossible because if your first position has an even number of 1's then your last position must have an odd number of 1's. All even numbers should be possible though. For example, here is 6 positions: 000, 001, 011, 111, 110, 100 - and this strategy can generalize to any even number.
gregmac 10y ago
I love when the reality of the physical world crashes into the precision of the software world like this. Many years ago I was working with ultrasonic distance sensors to measure water levels in cisterns. These things had a pretty good resolution: something around 2-3mm (cisterns were typically 6' to 12' deep/high). Enough that the waves/splashing during filling could cause the level to fluctuate and so we'd build the software so alarms had a separate 'on' and 'off' level. If you were to just say '<1500L = alarm', it would rapidly trigger on and off, so instead it would turn on at <=1500L and off at >1800L to both account for splashing and reduce repeat/nuisance alarms due to regular fluctuation in use. I regularly use this as my go-to example whenever I'm talking with someone about why you can't directly map the physical world to binary state.
- Ericson2314 10y ago
  I would say this is a triumph of imposing precision on the real world.
- lfowles 10y ago
  > I regularly use this as my go-to example whenever I'm talking with someone about why you can't directly map the physical world to binary state. Just like the classic genies, "be careful what you wish for"! This is also called hysteresis filtering for anyone wondering.
- DigitalJack 10y ago
  I believe this is an example of hysteresis. Often used to avoid the exact situation you describe of rapid state changes. You will see it in web page menus, or rather the easier to use web page menus, where when your mouse leaves briefly the menu does not instantly disappear.
  - __jal 10y ago
    Hysteresis also has to be taken into account in systems monitoring - if an alert on, say, IO wait > 5% or whatever is desired, it generally needs to enter an "OK" state at some value under .05 for the same reason.
- deleted 10y ago
DigitalJack 10y ago
Gray codes are useful to eliminate race conditions. We use them in chip design for FIFO pointers, for example where one end of the FIFO is in clock domain A, and the other is in clock domain B. By using a gray code, only one signal toggles when a word is added or removed. A normal binary code would have a race between multiple signals toggling and when they showed up on across the boundary. You can convert between normal binary and gray codes with a tree of XOR gates.
swordswinger12 10y ago
Cool article! Gray codes are used in cryptography sometimes too; the most well-known example is probably the Offset Codebook (OCB) authenticated encryption scheme, which uses a Gray code to compute tweaks: http://web.cs.ucdavis.edu/~rogaway/papers/ocb-full.pdf http://web.cs.ucdavis.edu/~rogaway/papers/ocb-full.pdf
sciyoshi 10y ago
There's a type of Gray code which is particularly useful for small-scale rotary encoders: a single-track Gray code. The idea is to find a code where the sequences for each position are cyclic shifts of each other. Then you can use a single "track" with arms at different angles, rather than multiple tracks with a single arm. http://sciyoshi.com/2010/12/gray-codes/#single-track http://sciyoshi.com/2010/12/gray-codes/#single-track

127 points by akeck 10y ago

entee 10y ago

Didn't know anything about this, really interesting! One question: when you need to know exact angle of something, say a steering wheel, if you used a grey code you'd need a really fine grained code with a huge set of numbers if you used this approach. Is that how it's done? Or is there a different way?

wrigby 10y ago
Sometimes yes! Wikipedia has a cool picture[1] of a 13-track (and hence 13-bit) Gray code encoder in the Gray Code article[2], which would have a resolution of ~.05 degrees. 1: https://upload.wikimedia.org/wikipedia/commons/a/a8/Gray_code_rotary_encoder_13-track_opened.jpg https://upload.wikimedia.org/wikipedia/commons/a/a8/Gray_cod... 2: https://en.wikipedia.org/wiki/Gray_code#Position_encoders https://en.wikipedia.org/wiki/Gray_code#Position_encoders
- Ericson2314 10y ago
  So the grey code itself has a graph analog (cycle in hypercube) and as the 1st picture would leave one to believe there's also some tree structure going on. Graphs on multiple levels!
azdle 10y ago
You would end up with a very large grey code if you tried to do that. You could solve that by gearing it down (or repeating the code) and count revolutions, but more likely these days you'd use something like a hall-effect angle-position sensor [1]. The ones linked will give you an angle with 2^12 bits, or ~0.09° just by rotating a magnet next to the IC. [1] http://www.allegromicro.com/en/Products/Magnetic-Linear-And-Angular-Position-Sensor-ICs/Angular-Position-Sensor-ICs.aspx http://www.allegromicro.com/en/Products/Magnetic-Linear-And-...
HeyLaughingBoy 10y ago
Yes and no. It depends. Maybe. A Gray code, as the article states, is only referenced by the Hamming distance between codes, not the bit size of the encoding. If you repeat the two-bit code: 00,01,11,10 90 times, you'll get a one-degree resolution around a circle, which is plenty for a steering wheel and usually works just as well as a 9-bit encoding (512 states). The problem becomes "how do I know where the wheel is at any arbitrary time?" The answer is: you continuously monitor the wheel by counting up or down on each code transition, and have a Home sensor to set the initial position. But now you have to remember the position when you power it off, and perhaps make sure no one can move the wheel while you're not monitoring it. Is that sufficient for your application? (hint: it is for 90% of such applications) If so, problem solved. If not, then we need to get more complex. More complex can mean: Non-Volatile Memory so we can power off and remember the last position[1], continuous battery-backup so even if main power is off, we track the wheel position, or ta-da: a 9-bit encoding so even with power off, we can encode 512 discrete states. Historically, that last solution was by far the most expensive. 1: I've worked with such a system where the position of a critical gantry was updated while it was running, then when power was off, the last (X,Y) position of the gantry encoders was remembered. Battery-powered electronics then monitored the state of an access door. If the door was opened, then the X,Y position was invalidated (someone could have moved the gantry while the encoders weren't being read) and the software would not allow the system to restart until a manual alignment procedure was done to reset the gantry to a known position and clear the "lockdown" bit. The alternative would have required two 10-bit absolute encoders that cost more than the electronics to do what I described.
- Ericson2314 10y ago
  Cool to note that either the additional gray codes bit or the circuit (be it regs, NVRO, etc) is tracking the exact same extra information.
- Gracana 10y ago
  RE: non volatile position storage Some of the industrial equipment I've designed at work uses Omron servos with encoders that use their own motion to provide power to the position tracking electronics, so you can disconnect the cable or otherwise lose power and not lose your zero, even if the machine is moved in the interim. No batteries required. Very cool product!
stonemetal 10y ago
I worked in industrial automation controls for a while. There they used a concept called quadrature to determine servo movement precisely. Quadrature is basically a grey code of [00, 01, 11, 10] that is repeated. You know what direction you are going by where you are and what comes next. If you are on 01 and see 00 you know you are going left. If you are on 01 and see 11 then you are going right. With a tad bit of math involving the gear box attached to the servo you know that one tick is real world distance X. From there it is a matter of establishing a "home" position, and counting your ticks as you move.

deleted 10y ago

[deleted]

throwawayish 10y ago

Fun-fact: the digital rotary knobs on most equipment (given name: rotary encoder) are pretty much built like this - a disc with conductive patterning read by brushes (well, bent contacts). Only the far more expensive rotary encoders are optical with an etched or printed glass disc, like typically found in industrial incremental encoders. These optical encoders typically cost 10-15 EUR a pop. Btw. using keyboard controllers to poll many switches isn't actually that unusual, but definitely a nice hack.

rflrob 10y ago

Am I missing something here, or is it only possible to easily generate Gray codes (or a similar Hamming distance 1 code if Gray refers specifically to a reflection generated code) for 2^n positions? Is there a way to do it for 12 positions like the article seems to mention? Or an odd number?

stonemetal 10y ago
As long as the code has adjacent entries vary by only one bit it is unnecessary to use them all. The author gives the example [110, 010, 011, 111] of a code that is valid but doesn't use all 2^n possibilities.
- tantalor 10y ago
  That sequence has 2^2=4 positions. I don't think rflrob meant "n = number of bits" but "n = number of codes".
  - stonemetal 10y ago
    Ah, I see what you mean. [000, 001, 011, 111, 101, 100] is a grey code of length 6, so not power of two is possible. However trying to come up with an odd length code is a real head scratcher. It may not be possible in binary, but is easily accomplished in higher bases.
    - bryondowd 10y ago
      You couldn't do an odd number of codes, but if you have an odd number of positions, I suppose you could have one position represented by two adjacent codes. So, you could have a wheel with 5 equal pie slices, but on the reverse, one of those slices is divided in half, with a different encoding on each, that both resolve to the same value/result.
default-kramer 10y ago
An odd number of positions is impossible because if your first position has an even number of 1's then your last position must have an odd number of 1's. All even numbers should be possible though. For example, here is 6 positions: 000, 001, 011, 111, 110, 100 - and this strategy can generalize to any even number.

gregmac 10y ago

I love when the reality of the physical world crashes into the precision of the software world like this. Many years ago I was working with ultrasonic distance sensors to measure water levels in cisterns. These things had a pretty good resolution: something around 2-3mm (cisterns were typically 6' to 12' deep/high). Enough that the waves/splashing during filling could cause the level to fluctuate and so we'd build the software so alarms had a separate 'on' and 'off' level. If you were to just say '<1500L = alarm', it would rapidly trigger on and off, so instead it would turn on at <=1500L and off at >1800L to both account for splashing and reduce repeat/nuisance alarms due to regular fluctuation in use. I regularly use this as my go-to example whenever I'm talking with someone about why you can't directly map the physical world to binary state.

Ericson2314 10y ago
I would say this is a triumph of imposing precision on the real world.
lfowles 10y ago
> I regularly use this as my go-to example whenever I'm talking with someone about why you can't directly map the physical world to binary state. Just like the classic genies, "be careful what you wish for"! This is also called hysteresis filtering for anyone wondering.
DigitalJack 10y ago
I believe this is an example of hysteresis. Often used to avoid the exact situation you describe of rapid state changes. You will see it in web page menus, or rather the easier to use web page menus, where when your mouse leaves briefly the menu does not instantly disappear.
- __jal 10y ago
  Hysteresis also has to be taken into account in systems monitoring - if an alert on, say, IO wait > 5% or whatever is desired, it generally needs to enter an "OK" state at some value under .05 for the same reason.
deleted 10y ago

DigitalJack 10y ago

Gray codes are useful to eliminate race conditions. We use them in chip design for FIFO pointers, for example where one end of the FIFO is in clock domain A, and the other is in clock domain B. By using a gray code, only one signal toggles when a word is added or removed. A normal binary code would have a race between multiple signals toggling and when they showed up on across the boundary. You can convert between normal binary and gray codes with a tree of XOR gates.

swordswinger12 10y ago

Cool article! Gray codes are used in cryptography sometimes too; the most well-known example is probably the Offset Codebook (OCB) authenticated encryption scheme, which uses a Gray code to compute tweaks: http://web.cs.ucdavis.edu/~rogaway/papers/ocb-full.pdf http://web.cs.ucdavis.edu/~rogaway/papers/ocb-full.pdf

sciyoshi 10y ago

There's a type of Gray code which is particularly useful for small-scale rotary encoders: a single-track Gray code. The idea is to find a code where the sequences for each position are cyclic shifts of each other. Then you can use a single "track" with arms at different angles, rather than multiple tracks with a single arm. http://sciyoshi.com/2010/12/gray-codes/#single-track http://sciyoshi.com/2010/12/gray-codes/#single-track