COMPUTING SCIENCE

# How to Count

# Shades of Gray

The main hazards to correct binary counting are those perilous Hamming cliffs. A tiny misstep—if it happens to come as a string of 1s rolls over to 0s—can put you over the edge. Engineers long ago confronted this problem in other contexts. For example, when encoding the angular position of a shaft as a binary number, the slightest misalignment can cause large uncertainty at a Hamming cliff. The standard remedy is an alternative to the ordinary binary numbers called a Gray code, which replaces the cliffs with gentler slopes.

Gray codes are named for Frank Gray, who was a physicist at Bell Telephone Laboratories in the 1950s and '60s, but the idea actually goes back to Emile Baudot, the French pioneer of the telegraph. The basic principle is to arrange the counting numbers in a sequence where each transition alters only one bit. For example, here is a three-bit Gray code: 000, 001, 011, 010, 110, 111, 101, 100. Note that all eight three-bit patterns appear in the sequence, and that each number differs from its neighbors at just one bit position. Many such codes exist, although the one shown here—called the reflected Gray code—is the most common.

Could Gray codes improve the accuracy of counting? At first, the idea seems promising: A missed event would set the count back by only one step, as in the unary Peano counter. But it's important to look at the internal details of a Gray-code counter. How does the counter generate the correct permutation of the binary numerals? For a shaft encoder, the sequence would be calculated in advance and permanently engraved in the hardware, but that's not a realistic option for a counter of larger capacity.

As it turns out, the obvious way to generate the reflected Gray code is to use an ordinary binary counter as an auxiliary. The position of the rightmost 1 bit in the auxiliary marks which bit should change next in the Gray code. But this implementation of the counter can hardly improve its error performance. At best, the Gray-code counter will inherit all the flaws of the binary counter. What's worse, when the binary and the Gray-code patterns get out of synch, the counter tends to go off on wild zigzag or crenelated trajectories. It can even start counting backwards. The behavior of the machine is fascinating, but it has little to do with the concept of counting.

I have looked for other ways to implement a reflected Gray-code counter, but the schemes I have tried turn out to be functionally equivalent to the auxiliary-counter method, and they suffer from the same error catastrophes. Of course it's entirely possible there's a clever method I've missed, or perhaps some Gray code other than the reflected one solves the problem.

Coding theory offers many other strategies for reducing error. The simplest device is a "parity bit," an extra bit that keeps track of whether the number of 1s in a binary number is odd or even. A parity check would combine particularly well with a Gray-code counter, because the number of 1s in a Gray code must alternate between odd and even. A 1990 report prepared for the Federal Election Commission recommends that ballot-counting machines be equipped with parity bits or other error-detecting devices.

EMAIL TO A FRIEND :

**Of Possible Interest**

**Computing Science**: Clarity in Climate Modeling

**Feature Article**: Candy Crush's Puzzling Mathematics

**Computing Science**: Belles lettres Meets Big Data