gray code

While working on this year’s advent of code, I was reminded of gray code, something I hadn’t thought about for a few years. Gray code is a cool invention with some interesting uses.

From Wikipedia:

The reflected binary code (RBC), also known just as reflected binary (RB) or Gray code after Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit). The reflected binary code was originally designed to prevent spurious output from electromechanical switches. Today, Gray codes are widely used to facilitate error correction in digital communications such as digital terrestrial television and some cable TV systems.

The first (and only other) time I came across gray code I was learning how to integrate a rotary encoder into my Arduino project. The encoder I had reported its absolute position as a 5-bit value on 5 pins. I checked out the spec sheet to figure out how to convert these values to an angle and encountered a description of gray code for the first time.

Gray code is an alternate way of representing integers in binary notation such that each number differs from the previous by only a single digit. The following table compares gray code with traditional binary notation:

You can see the difference in the transition from 1 to 2. Traditional binary notation represents 1 as 01 and 2 as 10, which means that to transition from 1 to 2, both digits must be flipped. In gray code, however, moving from 1 to 2 means flipping one digit (01 to 11).

Some rotary encoders (like mine) use a “code disk” (3-bit example pictured below) containing binary “words” representing each position of the encoder. This disk is usually made from clear plastic screen-printed with opaque black ink so that an array of photo sensors (1 per bit of the output) are partially blocked by the ink. The sensors are arranged in a line along the diameter of the disk. As the knob on the encoder turns, the disk blocks the light from hitting certain sensors, creating a unique combination of outputs for each angle. From this signal we can reconstruct the actual angle of the knob at any time.

Most rotary encoders represent angles using gray code. Since gray code orders values such that each one is only a 1-bit change from the previous, this eliminates problems of ambiguous outputs since we avoid cases where multiple bits change simultaneously.

Like many integer sequences, generating gray code has a nice recursive solution. For each bit-length n, use the resulting sequence produced by n-1 and create a new sequence twice as long. Each value in the sequence becomes two new values: i << 1 and (i << 1) | 1. Here’s how that looks in go:

package main

import (
	"fmt"
	"math"
)

func main() {
	fmt.Printf("%010b", gray(10)) // print all 10-bit gray codes as binary values
}

func gray(n int) []int {
	if n == 0 {
		return []int{}
	}
	if n == 1 {
		return []int{0b0, 0b1}
	}
	prev := gray(n-1)
	left, right := make([]int, pow2(n-1)), make([]int, pow2(n-1))
	for i, c := range prev {
		left[i] = c << 1
		right[len(right)-i-1] = left[i] | 0b1
	}
	return append(left, right...)
}

func pow2(n int) int {
	return int(math.Exp2(float64(n)))
}