You can do a lot with a D20, pencil and paper. Including, it turns out, designing a code that helps bring pictures from space.

That was one of the (admittedly unstated) conclusions from a talk by Dr Julia Wolf at the University of Bristol this week to mark Ada Lovelace Day. She describes her work as focusing on “arithmetic structures in dense sets of integers and combines Fourier analytic, combinatorial and probabilistic methods” but fortunately chose to start in more simple terms for those of us in the audience who are not mathematicians. (My apologies in advance to Dr Wolf and our more mathematically-oriented readers for any errors or oversimplifications in this article.)

The talk centered on the challenge of creating binary codes that can cope with errors introduced by noise during transmission. To illustrate, these are some limitations with some possible ways of transmitting a code with two possible messages (such as “Yes” or “No”).

• A single-digit of either 0 or 1 is no use at all as there’s no way to tell if you’ve got an error (a 1 appearing in place of 0 or vice versa).
• Repeating the digit (so sending 0-0 or 1-1) makes it possible to spot if one digit has been mistranscribed (because 0-1 or 1-0 is not a valid message) but doesn’t let you know what the correct message was, so the code requires a resend.
• Repeating the digit ten times (eg 0-0-0-0-0-0-0-0-0-0) means you can not only spot an error in almost every case (the only exception being if all 10 digits were mistranscribed) but will also give a good clue as to what the correct message was: 0-0-0-0-0-0-0-1-0-0 was almost certainly meant to be a message of 0, while even 0-0-1-0-1-0-1-0-1-0 is more likely to be a message of 0 with four errors than a message of 1 with six errors. The downside is that it’s inefficient to transmit ten digits to distinguish between just two possible message options.

The trick therefore is to find something that best achieves three aims: error detection (showing when there’s a mistake), error correction (indicating what the correct message likely was), and efficiency in having as few digits as possible cover as many different message options as possible.

If you keep things simple, you can develop such a solution manually. For example, with three digits, you can figure out a combination of four message options, for example 000, 011, 101 and 110, with the other four possible combinations (in this case 001, 010, 100 and 111) serving as errors.

Using this set-up, if you mistranscribe one digit in a valid message option, you get an error rather than another valid option. That means we get error detection but unfortunately no error correction because we can’t deduce what the original message was (001 could have been either 000 or 101). We’ve also improved the efficiency: we now have a three-digit string carrying four different message options.

The ideal solution would be where each valid message option is a string of 0s and 1s of a given length and where every other possible string of the same length differs from one valid message option — and only one option — by a single digit. In other words, if one digit in the code is wrong, you not only know there was a transmission error, but you can tell exactly what the correct message option was meant to be.

It turns out that while algebra is one way to find such a solution, geometry will also do the trick. The three digit example above is demonstrable on a cube:

In the search for ideal solutions (known as perfect codes), it turns out another geometric shape known as a Fano plane is a useful tool:

The shape has seven points connected by lines (including the circular line.) Looking at the shape lets us construct a matrix with each digit based on whether each of the seven points lies on each of the seven lines (1 if it does, 0 if it doesn’t):

And it turns out that this gives us seven rows of numbers which can serve as seven message options where not only will a mistranscribed digit produce a clearly invalid option (an error) but also make it certain what the intended message was.

Even better, it’s possible to add seven more message options by producing a mirror matrix (with every 0 replaced by a 1 and vice versa), and then two more in the form of a string of all 0s and a string of all 1s. So not only do we have a code that works even with a mistranscribed digit, but we’re now getting a much more efficient 16 message options from a string of seven digits.

This code was actually used in early space telescopes to transmit images and cope with errors. However, it wasn’t efficient enough to cope with color images. Fortunately there’s one more ‘perfect’ code that again derives from a geometric shape, namely the regular icosahedron — aka a D20.

To be strictly fair, this technique doesn’t involve numbered faces but rather the 12 points (vertices). In a similar way to with the fanoplane, we can construct a matrix based on whether a particular pair of points are connected by a single line. Even without adding any new techniques, that gives us 26 possible message options (12 rows in the matrix, another 12 by reversing each digit, and the strings of all 0s and all 1s).

Not only is that particularly neat as it means each string can correlate to a letter in the English alphabet, but it also increases efficiency. It was the basis of an error-correcting code that could detect and correct up to three errors in a string of 24 digits (a 24-bit block) and used on Voyager to send back pictures of Saturn and Jupiter.

To be fair there’s no evidence at all that this Golay code was inspired by an actual 20-sided die (it seems unlikely given Marcel Golay wrote about the code in 1949), but it’s certainly neat to think that two such iconically geeky objects as the D20 and Voyager have a mathematical connection.

[Post Header Picture Source: Scott Ogle (CC BY 2.0)]