Fifty Shades of Gray Code

Some years back, a museum asked me to help them with an exhibit a contractor had built for them. It was a wheel like the one on Wheel of Fortune, but smaller and mounted on the wall instead of the floor. You would spin the wheel, it would stop on some item, and a computer would play a short video about the item. Physically and mechanically, it was a beautifully built exhibit. The electronics, though, left something to be desired.

In principle, this is pretty simple computer task. Measure the position of the wheel, and when it stops moving, play a video based on the position. The problem was the folks who created the artistic mechanics didn’t think hard about the electronics behind it. Sometimes–but not often–the wheel would play the wrong video. Sometimes it wouldn’t play at all.

The Prime Suspect

My immediate suspicion turned out to be correct. I took the wheel off its mount to discover copper foil tape on the back of it. Each pie wedge had foil in different areas and there were two brushes in each area. When the wheel stopped, two of the brushes would be shorted together and the rest were open. The way they detected that was bizarre, but that wasn’t the problem. (It involved a cannibalized PS/2 keyboard.)

There were quite a few pie wedges, so the device had multiple foil strips per wedge forming a 4-bit binary number. That is, each wedge encoded a number from 1 to 12 by using the presence of foil to denote a one and the absence, a zero. For example, the figure below shows a similar wheel with three bits. Moving clockwise from the top, the black mark on the outer track represents foil that forms a number 001. Then the foil forms 010, 011, and finally 100, which covers most of the wheel.

There were two problems. First, if the wheel was almost exactly half way between two zones, it was possible for two sets of brushes to make contact, even when only one should have made contact. The brushes were close together, not totally secure, and the foil wasn’t very precisely aligned. On the example wheel above, if you were right at the top, you could have the case where the brushes read 101, which isn’t even a legal combination on this simple wheel.The other problem was when the foil was on

The other glitch occurred when the foil was on one half of a brush pair but not the other. This usually meant another brush was also half activated. The closer the brushes were on one track, the less likely this was, but there was always some probability that the wheel would stop just wrong.

The Answer

I made a few changes to the device. First, I changed the foil tape to paint and used an IR emitter and detector pair. I didn’t think the brushes were that reliable. But that alone wasn’t going to fix the problem. The entire system is basically a big homemade rotary position encoder. Real rotary position encoders use Gray code to prevent slight misalignments and border cases from being a problem. For some people, the term Gray code (named after [Frank Gray], the inventor) isn’t fancy enough. So they call it a binary reflected code. Do yourself a favor, and call it a Gray code. You don’t want to be like my old professor who talked about “maximizing the Boolean variable” when he meant “setting the bit to 1.”

Unlike, say, the ASCII code, there isn’t a single Gray code. The term refers to any sequence of binary numbers where each item has only one bit difference between itself and adjacent items. In academic-speak, the Hamming distance between each item is one.

Hamming Distance

The original wheel used sequential coding:

0000
0001 
0010
0011
...

The Hamming distance between the first two items is one, but the next two items have a hamming distance of two because you have to flip two bits to go from one to the next. So this isn’t a Gray code. And don’t forget that when the sequence wraps around, the last entry and the first are also adjacent.

Consider this three-bit code with 4 items:

000
001
011
111

This isn’t a Gray code because the distance between the last item (111) and the first item (000) is three. One possible proper Gray code would be:

000
001
101
100

Of course, the code doesn’t have to start with 000, so an equally valid code is:

110
010
011
111

Common Sense

Because each adjacent item differs by only one bit, the edge cases work better with physical items like brushes or optical sensors. Assume you have two pie wedges on the wheel, C and D. If C is 011 and D is 100 (not Gray code), then it is possible at the edge to get 111 which would be some other item. But if C is 011 and D is 111 (as in the last example), moving from C to D will cleanly switch to D at some point. There won’t be any time when a 111 (or any other code) is possible.

If you look closely at a rotary encoder disk, you can see the pattern. The wheel has eight pie slices. If you consider the three concentric rings, you’ll notice that on each slice a ring is either white or black and, looking at a neighbor slice, only one ring will be different. The image makes it clear why the first and last items on the list are logically adjacent. Since each neighbor differs only in one bit, it doesn’t matter if the disk spins clockwise or anticlockwise.

Why Gray? Why Reflected?

[Frank Gray] devised this coding scheme at Bell Labs and the patent dates to 1947 — the original circuit used vacuum tubes and a CRT. He didn’t call it a Gray code, but other patents dubbed it Gray code and the name stuck. The reflected name comes from one method of constructing a Gray code, and it appears in the original patent. Gray would later become semi-famous for working with [Herber Ives] to devise a scheme for color television that was compatible with black and white sets.

The reflection is part of a recursive algorithm for making a Gray code of any length. Start with the simplest Gray code: {0, 1}. Sure, it is just one bit, but the distance between each entry is one, so it is a Gray code. Now reverse (reflect) the list: {1, 0}. Still a Gray code. The next step is to put a zero in front of the first list numbers, put a one in front of the second list items, and then interleave the lists: { 00, 01, 11, 10 }.

You can repeat that to get as many bits as you want. Three bits would start with the list {00, 01, 11, 10} and its reflection {10, 11, 01, 00}. The final code, then is: { 000, 001, 011, 010, 110, 111, 101, 100 }.

Of course, that’s just one possible Gray code. There are other useful variations with names ranging from monotonic Gray code to a “snake-in-the-box” code. You can’t make this stuff up.

We’ve seen a number of custom encoders over the years, and going with a full Gray code is often overkill. For instance, if you just care about direction and distance, you usually use a rotary encoder with quadrature output. If you just want to see how to read that type of encoder with an ARM processor, we just did one of those. But when the absolute position matters, and you care about keeping the transitions from becoming too messy, a Gray code is what you need.

Filed under: Engineering

from Hackaday http://ift.tt/2jfndMk
via IFTTT