Building the map

OK, OK, so it is just a matter of moving my truth table onto that map, right?

Hmm, yes, partly. Each cell of the map is one row of your truth table, and inside it you write the output of that row (0, 1, or - if you don't care or it is a case that will never happen). What matters is the order of the rows and columns: they are not numbered 00, 01, 10, 11 as you would expect, but following the Gray code. So let's take it one step at a time.

# The Gray code

The Gray code (or reflected binary code) is a way of counting in binary with a very simple rule: from one number to the next, a single bit changes. Just one. That includes the wrap from the last to the first (from 15 back to 0 a single bit changes too), which is why it is called a cyclic code.

Frank Gray, also at Bell Labs, patented it in 1947 (the patent was granted in 1953) for a pulse code modulation system built with vacuum tubes. The idea is older, though: Émile Baudot was already using it in the telegraph in the 1870s.

Its best-known use is in rotary encoders: a disk with tracks that a few sensors read to know the angle of a shaft.

And what is wrong with plain binary there?

In the real world the sensors are never perfectly aligned, so the bits that should change at the same time do not change at exactly the same instant. If several bits change in a transition, for an instant you read a mix of the old value and the new one, which can be anything. Between 7 (0111) and 8 (1000) all four bits change: a sensor that is a little ahead can make you read 15 or 0 for a moment. With Gray that does not happen: since a single bit changes, the worst you can read is the previous value or the next one. Compare the two disks: the wrong-reading counter of the binary one goes up and the Gray one stays at zero.

Converting binary to Gray is almost free: a shift and an XOR. Going back takes a little longer:

def binary_to_gray(n: int) -> int:
    return n ^ (n >> 1)

def gray_to_binary(g: int) -> int:
    n = 0
    while g:
        n ^= g
        g >>= 1
    return n

For 4 bits it looks like this:

Notice two things. In binary, going from 1 to 2 changes two bits, from 3 to 4 three, and from 7 to 8 all four; in Gray it is always one, even on the wrap from 15 back to 0 (the last row). And compare rows 8 to 15 with rows 7 to 0: the three bits on the right are the top half mirrored, with a 1 in front. That is where reflected comes from, and it is the easiest way to build it by hand: copy the list, mirror it, and put a 0 in front of the top ones and a 1 in front of the bottom ones.

# Curiosities

The solution of the Tower of Hanoi follows the Gray code: the bit that changes at each step tells you which disk to move.

In hardware, Gray counters are used to pass pointers between different clock domains (asynchronous FIFOs): if the other side reads right during a change, it is off by one at most.

In digital communications the symbols of a QAM constellation are labelled in Gray, so that mistaking a symbol for its neighbour costs a single wrong bit.

# From the Gray code to the map

In a Karnaugh map the rows and the columns are labelled in Gray code, and that guarantees that two neighbouring cells differ in a single variable. Each cell stands for one combination of inputs (a minterm) and holds the output of the function for that combination; the number of the cell is the row of the truth table. For 4 variables, AB (the most significant) go on the columns and CD (the least significant) on the rows.

What about a 5-variable map? Is that possible?

Of course. Each extra variable doubles the size of the map, and from 5 variables on there are neighbours that are no longer next to each other (the thick lines mark the mirror axes; more on that later). There are strategies for many variables, such as splitting the map into 4-variable sub-maps, and we will get to them. For now, move the slider and see how the values are laid out.

# The edges touch: the map as a torus

Before grouping there is a curious detail: the map does not end at its edges. The left column is a neighbour of the right one, and the top row is a neighbour of the bottom one, because the Gray code is cyclic. If you roll the map joining top and bottom you get a tube; if you then join the ends of the tube, you get a torus.

What about the corners? All four are neighbours of each other: on the torus they end up together.