Fifty Shades of Gray Code | Hacker News Reader

Fifty Shades of Gray Code

hackaday.com

127 pointsakeck33 comments

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.

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.

I would say this is a triumph of imposing precision on the real world.

> 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.

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.

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.

I discovered this to my dismay when building a simple cutoff switch for my fish tank's pump. The pump would turn off/on, water would back flow into the reservoir, turning the pump back on. The pump cycling then caused waves to hit the float switch. It would cycle on/off at about 1-2 Hz.

This was built before Arduino's and Raspberry Pi's were around (and the environment is humid), so I devised a fairly simple mechanical solution of just enclosing the float switch inside a pipe that had a small hole in the bottom. The water level inside the pipe would change slower than the real level, providing the needed hysteresis.

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.

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

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?

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.

That sequence has 2^2=4 positions. I don't think rflrob meant "n = number of bits" but "n = number of codes".

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.

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.

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.

Any sequence has 2n codes.

Example with 6:

Proof: Adjacent gray codes have hamming distance 1, so the graph of gray codes is cycle on a hypercube. All cycles on a hypercube graph are even, so every sequence of gray codes is even.

Ah, I was waiting for somebody to point out the wonderful math behind this!

Or rather, I was about to post about hypercubes and cycles myself :D

Check out monotonic grey codes, they are used for situations like this. As far as I understand it is possible to generate a code where each value only differs by one bit no matter the length, but generating them can be difficult

I had a go and worked out a Gray code for 12 positions. There's probably a neater solution, or even some sort of algorithm for generating this, but this seems to work :).

My student, Jessica Fan, and I published a paper in the Allerton Conference in October 2015 on just this question.

You can create a Gray code for exactly the numbers 0 to n-1, for any n, by the following steps: 1. Create the binary reflected Gray code for the next higher power of 2. 2. Take just the first n numbers of that binary reflected Gray code. 3. Bitwise exclusive-or each of these n numbers in the Gray code with the binary representation of floor(n/2) (i.e., n shifted right by one bit).

To create a cyclic Gray code for exactly the numbers 0 to n-1, n must be even. (It's easy to prove that you cannot get a cyclic Gray code for odd n.) 1. Generate the Gray code for 0 to n/2-1, as above. 2. Concatenate the reflection of that Gray code to itself. 3. Shift each of the n numbers you now have left by one bit. The first half gives you all the even numbers 0 to n-2, with the Gray-code property. 4. Put a 1 in the least significant bit in the second half The second half gives you all the odd numbers 1 to n-1, again with the Gray-code property.

The whole sequence gives you 0 to n-1, with the Gray-code property, and it's cyclic.

If you'd like a PDF of the paper, email me: thc@cs.dartmouth.edu.

Tom Cormen Professor of Computer Science Dartmouth College

Thank you for you post, and for your fine book on algorithms.

An algorithm that works for any even n is to generate the Gray code for the next highest power of 2 (in this case, 16) then pick the middle n symbols. Eg the 16 position Gray code, with the middle 12 symbols marked:

you can use a constraint solver to very quickly generate gray codes. I did a python example here using python-constraint: http://www.jimblog.net/2017/01/generating-gray-codes-with-py...

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

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?

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_cod...

2: https://en.wikipedia.org/wiki/Gray_code#Position_encoders

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!

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-...

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.

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.

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!

That is seriously cool! How long does it retain data for? In our case we had to assume the operators might power off the machine for a long weekend, so we spec'd a 7-day data retention.

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.

Reply on news.ycombinator.com