Gray Code

Let’s revisit counting in binary. For this example, we will count from 0 to 7 with 3-digit binary numbers.

Decimal	Binary
0	000
1	001
2	010
3	011
4	100
5	101
6	110
7	111

In a mechanical counter, these 0s and 1s could be represented with switches or currents: off to represent “0”, and on to represent “1”. Thus, a number like 5 would be represented with 3 wires in the “on, off, on” positions respectively.

Let’s add 1 to the number 5 to get 6. The second and third wires need to be switched to give the new position of “on, on, off”. However, due to delays in switching, the second and third wires might not switch at the same time. This might give incorrect values of “on, off, off” (4) or “on, on, on” (7) if the wires are to be read at this time.

A solution to this is to come up with a new representation for numbers. We still want to use the binary digits, since each wire still only has 2 states, off and on. Let’s take a look at the following binary representation of the numbers from 0 to 7.

Decimal	Gray code
0	000
1	001
2	011
3	010
4	110
5	111
6	101
7	100

This is the Gray code representation, also called the reflected binary code. In this new representation, there’s only 1 bit of difference between any 2 consecutive numbers. This way, the value read will always be correct, even when the switches are changing. A nice bonus is that “100” (7) is also only 1 bit away from resetting back to “000” (0), forming a cycle.

But does this generalise to bit strings of other lengths? Yes! Let’s take a look at the construction. First, we start with the values 0 and 1, represented with the bits 0 and 1.

To construct the Gray code of length 2, we perform the following steps:

1. Take the Gray code sequence, reverse it, then place it below the original order

2. Append the digit 0 to the front of the first half of the sequence, and 1 to the second half of the sequence (the one we just copied).

And we’re done! Reading the codes in order, we get 0 → 00, 1 → 01, 2 → 11, and 3 → 10. Let’s perform this operation one more time to get all Gray codes of length 3.

1. Take the Gray code sequence, reverse it, then place it below the original order

2. Append the digit 0 to the front of the first half of the sequence, and 1 to the second half of the sequence.

We’ve just reconstructed the Gray code we saw earlier. We can continue repeating this process to get the Gray codes of any arbitrary length.

While Gray codes are helpful in a few specialised applications in engineering, you won’t actually find them in most devices because of its weaknesses. Gray codes are great when you need to increment a counter by 1, but that’s about it. Adding 2 numbers in Gray code, for instance, is quite computationally messy. That’s why in computers, you’ll see the Two’s Complement—a similar system to binary counting but encodes negative numbers too—being used instead.

For puzzles, look out for situations that involve binary states where adjacent states can only differ by 1 bit.