64
$\begingroup$

I was listening to Sphere Packing Solved in Higher Dimensions; A Ukrainian mathematician has solved the centuries-old sphere-packing problem in dimensions eight and 24. and reading the transcript there.

Mathematicians have been studying sphere packings since at least 1611, when Johannes Kepler conjectured that the densest way to pack together equal-sized spheres in space is the familiar pyramidal piling of oranges seen in grocery stores. Despite the problem’s seeming simplicity, it was not settled until 1998, when Thomas Hales, now of the University of Pittsburgh, finally proved Kepler’s conjecture in 250 pages of mathematical arguments combined with mammoth computer calculations.

later:

Higher-dimensional sphere packings are hard to visualize, but they are eminently practical objects: Dense sphere packings are intimately related to the error-correcting codes used by cell phones, space probes and the Internet to send signals through noisy channels. A high-dimensional sphere is easy to define — it’s simply the set of points in the high-dimensional space that are a fixed distance away from a given center point.

and later

The Leech lattice is similarly constructed by adding spheres to a less dense packing, and it was discovered almost as an afterthought. In the 1960s, the British mathematician John Leech was studying a 24-dimensional packing that can be constructed from the “Golay” code, an error-correcting code that was later used to transmit the historic photos of Jupiter and Saturn taken by the Voyager probes. Shortly after Leech’s article about this packing went to press, he noticed that there was room to fit additional spheres into the holes in the packing, and that doing so would double the packing density.

Question: How is stacking oranges in 24 dimensions related to receiving and decoding signals from the Voyagers? It it possible to explain in a relatively simple way to the Space SE community, or find a source that does explain the connection suitable for this site?


Thomas Hales, pictured in 1998, used a computer to prove a famous conjecture about the densest way to stack spheres.

Thomas Hales, pictured in 1998, used a computer to prove a famous conjecture about the densest way to stack spheres.

$\endgroup$
13
  • 18
    $\begingroup$ Better suited for the math SE. The question simplifies to "what is the connection between 24-dimensional sphere packing and Golay code?" $\endgroup$ Jul 7 at 16:10
  • 8
    $\begingroup$ I agree this should go to either math SE or signal processing SE - there are the experts for this. $\endgroup$
    – asdfex
    Jul 7 at 16:15
  • 4
    $\begingroup$ @asdfex the experts there will write answers I can't understand. I've asked here to gain an explanation from the point of view of the Voyager hardware and algorithms. Those folks will not go back and look at 1970's NASA technology and write from that perspective. In the future, once I understand better, I might (or might not) venture a more in-depth 21st century question there. That's why I wrote "Is it possible to explain in a relatively simple way to the Space SE community, or find a source that does explain the connection suitable for this site?" FYI I did post a link in DSP SE chat room. $\endgroup$
    – uhoh
    Jul 7 at 16:35
  • 2
    $\begingroup$ @uhoh But as the quote says, this technology is also used in cell phones and the Internet, although not as commonly. $\endgroup$
    – Barmar
    Jul 8 at 20:56
  • 2
    $\begingroup$ @uhoh (&Barmar), the mind-blowing thing is indeed how these men and women made the connections between so-distant fields (that I still can't comprehend). These error codes, as "perfect" as they are (in their sphere-packing performance) are quite weak by today's standard (see the survey by Costello The road to Channel Capacity). Thanks to uhoh, I discovered another facet of Kepler's brilliance. I learned that he conjectured and calculated the sphere-packing limit (for dimension 3) while trying to explain the shape of snowflakes. Exquisite! $\endgroup$
    – Ng Ph
    Jul 9 at 18:57
131
$\begingroup$

All the different data words a transmitter can send and a receiver can detect can be imagined as dots arranged in a large space.

Selecting a data encoding for error detection and correction is about keeping valid code words at a certain distance from each other. As a result, a slight change ("movement") of a valid word doesn't make it look like another valid word.

As I'm not going to make any drawings of 24 dimensional spheres and hypercubes, I'm going to restrict this answer to three dimensions.

3-bit example

Imagine a data word consisting of three binary digits. We can arrange them in the form of a cube by treating each digit as the coordinate in one dimension:

Each transmission error, that is a bit that is a '0' mistaken for a '1' or vice versa, corresponds to moving one step along one of the edges of this cube.

In normal, everyday communication with sufficiently low error rates, we can treat all code points as valid:

But, every flipped bit leads to another valid word. So, if we remove every second valid word, we get this:

Now, all the valid words are two edges apart. One flipped bit gets us to an invalid word and we know there was an error, but we are not able to correct it, because there are three possible bits that could have flipped. This is called a "0 error correcting, 1 error detecting" code.

To improve robustness, remove another two valid code words:

Now, all valid words are three edges apart. If one bit flips we get to an invalid word, but we still can tell where we came from. If two bits flipped we can't correct the word, because another valid word is closer to the wrong code than the correct word. Hence, this code is called "1 error correcting, 2 bit detecting"[*]. This is the best we can get with our simple 3-bit code words.

4 bit code extension

If you add another bit to have 4-bit code words, you can increase the distance between valid points to three edges of the then 4-dimensional cube. This gives another level of error mitigation: If two bits flip, you reach a invalid word right "in the middle" of several valid words. You can't decide which one might be the correct one, but at least you know that two bits flipped. This type of code is called "1 error correcting, 3 error detecting".

Voyager

In the case of Voyager, this wouldn't be enough, so they went for a 24 bit long code word. From the total of 16 million code words, they only defined 4096 as valid. I.e. 12 Bits carry actual information and another 12 are used for error correction. This resulted in a "3 error correcting, 7 error detecting" code. I.e., if in any word 3 bit were wrongly received, it could still be corrected properly and if up to 7 bits flipped; at least it would be known something is wrong. This code could be represented in the same way I did above as the corners of a 24-dimensional hypercube.

Now, how does this relate to packing of spheres? In fact, the three images show the densest possible packing of spheres with diameters of $\sqrt 1$, $\sqrt 2$ and $\sqrt 3$, respectively, under the constraint that their centers need to be located on corners of the cube.[**]

Obviously, this doesn't look too spectacular, but it gets a lot more challenging if we're not looking at digital, binary data, but use a transmitter that also supports values in between, e.g., by using not a simple on/off modulation, but add amplitude modulation on top. By adding one more step (e.g., power off/low/high) for each of the three digits in our example, we don't have eight valid code words, but actually $3^3 = 27$ - start packing your spheres onto that grid!


[*] Note that "detecting" doesn't mean that you will be able to tell how many bit errors there are exactly. It refers to the number of bit errors that can occur before you end up with another valid code word.

[**] Strictly speaking, we don't deal with spheres in a regular Euclidean space here, but Hamming spheres - these are defined by the set of corners that are a given number of edges away from their center. This accounts for the fact that in a binary world only the corners of the cube represent valid points while any other point would have fractional coordinates and just doesn't exist. Practically, there is no difference between the two in the examples given here.

$\endgroup$
29
  • 8
    $\begingroup$ In the cube example, how can you error correct? You don't know whether one bit or two bits got flipped. Ie receiving 101 could be 100 with a bit flipped, but it could also be 011 with two bits flipped. Even if the first is more likely it's still ambiguous. I can't see how any error correction can be performed here, only detected. $\endgroup$
    – Innovine
    Jul 7 at 21:16
  • 9
    $\begingroup$ @Innovine I believe you can correct any one-bit errors in this example, but you cannot detect two-bit errors. All two bit errors are indistinguishable from a one-bit error of the opposing word. So a two-bit error will be "corrected" to the opposite word of what was sent. $\endgroup$ Jul 7 at 21:49
  • 2
    $\begingroup$ By having all zeros and all ones as an invalid code (as shown above), this approach also detects that big error. $\endgroup$ Jul 7 at 23:00
  • 22
    $\begingroup$ The answer illustrates a 3,1 Hamming code, which is capable of detecting up to 2 error bits, or correcting 1 error bit, but not both. Adding an additional parity bit allows it to correct 1-bit errors and detect 2-bit errors, but at the cost of an additional bit. en.wikipedia.org/wiki/… $\endgroup$ Jul 8 at 5:50
  • 2
    $\begingroup$ @LawnmowerMan Yes. Similarly, the binary Golay code can correct 3 errors or detect up to 6 errors, but not both. (This is a code with words of 23 bits.) The extended binary Golay code (with 24 bit words) can correct 3 errors and detect 4 errors. If you want only error detection, the extended code can detect up to 7 errors. $\endgroup$ Jul 8 at 6:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.