A Practical Application of Gray Codes

Gray codes are a way of encoding a a sequence of integers {0, 1, 2, …, n} so that the binary representation of adjacent integers differs by only 1 bit. For example, the¹ Gray encoding for the sequence {0, 1, 2, 3, 4, 5, 6, 7} is {000, 001, 011, 010, 110, 111, 101, 100}.

It’s easy to calculate the Gray code for any integer, j: it’s simply j ⊕ _⌊ j/2 _⌋. We can express this in Scheme as

(define d->g
  (lambda (j)
    (number->string (logxor j (quotient j 2)) 2)))

When we evaluate d->g with 4 we get 110 as expected.

Going from a Gray Code back to its binary equivalent is a little harder. The binary number equivalent to the Gray code k is k ⊕ _⌊ k/2 _⌋ ⊕ _⌊ k/4 _⌋ ⊕ … where the zero terms are dropped. Since _⌊ k/2ⁿ _⌋ is 0 for large enough n, the sequence terminates.

We can implement this in Scheme as

(define g->d
  (lambda (k)
    (let loop ((k (quotient k 2)) (result k))
      (if (zero? k)
          result
          (loop (quotient k 2) (logxor k result))))))

Why do this? Gray codes are useful in situations where analog information is being converted to digital information or vice versa. It often happens that there are ambiguities where, say, an analog value changes from one value to the next. In section 7.2.1.1 of AOCP V. 4A, Knuth gives the example of a disk divided into 16 sectors with concentric colored bands marking the bit values of each sector. At the sector boundaries it’s unclear what the correct values are and encoding them in the normal binary encoding can lead to large errors. With the Gray coding, the errors are always localized to one bit so that the values are never more than one off. That explanation is a little hard to follow without Knuth’s diagram and is, in any event, not a real application (although one can imagine the same basic scheme being used in one).

Mark Dominus over at The Universe of Discourse has a nice post from 2009 that shows a perfect real-world application of Gray codes. It’s a stadiometer, a device used in medical settings to measure a person’s height. Commonly they are attached to a scale and consist of a slider that can be moved up and down a column marked with the heights and a piece that sticks out and rests on the top of the patient’s head. We’ve all been measured by one of these and usually the doctor or nurse just reads off the number from the column. In Dominus’ example, the stadiometer was digital and worked by a photosensor reading a pattern from the column. That pattern turns out to be a Gray code and, as Dominus illustrates, is used precisely to avoid measurement errors when the slider is between two possible height values.

Follow the link to see a picture of the column with its Gray codes and a worked example of how large the measurement error can be if normal binary encoding were used.