What Happens When Projective Geometry Meets Information Theory? (II) - An illustration of a mars drone on the left. On the right, there is an illustration of a Fano plane.

In my previous essay on what happens when projective geometry meets information theory, I covered the notion of error detecting codes and error correcting codes. After landing your space vehicle on Mars, you were trying to transmit error corrective signal to course correct your misguided Mars drone.

We were trying to make sense of how the Hamming code and the Fano plane are related. At the same time, as your drone was hurtling towards a Martian rock, I ended the essay on a cliffhanger.

In this essay, I aim to set things straight. Not only will we be answering the question of how the Hamming code and Fano plane are related, but we will also figure out a way to save your Mars drone.

In case you haven’t read the first essay yet, I urge you to do so now, as we will building upon those concepts in this essay. Without any further ado, let us begin.

This essay is supported by Generatebg

A product with a beautiful background featuring the sponsor: Generatebg - a service that generates high-resolution backgrounds in just one click. The description says "No more costly photographers" and displays a "Get Started" button beneath the description.

Analysing the Fano Plane

Let us strip the Fano plane first and study its individual components. As I had explained in the previous essay, the Fano plane consists of seven points and seven lines (including the curved line).

In the following image, you will see that I have numbered the points starting from 1 to 7:

What Happens When Projective Geometry Meets Information Theory? — An illustration of the Fano plane. The plane consits of an equilateral triangle with an inscribed circle. The vertices of the triangle and the contact points of the circle and the trinagle generate points. Each vertex is joined by a line segment with the centre of the opposite vertex, such that these are also the contact points between the circle and the triangle. Each point is numbered from 1 through 7.
The Fano Plane — Illustration created by the author

Based on this numbering, you will also notice that any Fano line can be represented using 3 points. Consequently, the following is the list of all the lines in the Fano plane:

124

135

167

257

347

236

456

With this list of lines in our books, let us shift our focus now toward the Hamming code.

Comparing the Fano Plane with the Hamming Code

In my previous essay, I covered how Richard Hamming (Shannon’s Bell Labs colleague) invented the Hamming code. Furthermore, I listed the Hamming code’s combination for any three-digit (binary) combination as follows:

000 → 0000000

001 → 0010111

010 → 0101011

011 → 0111100

101 → 1011010

110 → 1100110

100 → 1001101

111 → 1110001

Now, let us say that we are interested in transforming the list of the Fano lines we just saw into binary code as well. Instead of converting the numbers directly into binary, I’m going to use simple yet specific logic.

Let “xxxxxxx” be the generic binary code for any line in the Fano plane. The ‘x’ on the left-most end represents the point number ‘1’ and the ‘x’ on the right-most end represents point number ‘7’. On any given line, if a point ‘x’ is present, we replace ‘x’ with zero. If not, we replace it with a ‘1’.

Consequently, the list of Fano lines gets transformed into binary code as follows:

124 → 0010111

135 → 0101011

167 → 0111100

257 → 1011010

347 → 1100110

236 → 1001101

456 → 1110001

Do you see what is going on here? Except for the missing point (0000000), this list is the same as the Hamming code. So, why did Hamming specifically choose these numbers? And why is the list of lines in Fano’s plane the same? Let us find out.

Projective Geometry Meets Information Theory

Just as a reminder, Richard Hamming was trying to scratch his own itch with the hamming code. His goal was to design an information transmission system that self-corrects any corruption/errors/bit-flips in the input.

Let us say that you transmit your course-corrective signal to your mars drone using the Hamming code as follows:

10101 → 010 101 → 0101011 1011010

Hamming’s worst nightmare is a situation where a bit flip would transform one of his codes into another. In your corrective signal, you have two of Hamming’s code blocks side by side. How many bits would you need to flip to transform one code block into another?

The answer is 4. Herein lies the genius of Richard Hamming. While others could not see geometry in binary signals, he could. He came up with the notion of the Hamming distance.

The Hamming distance measures the number of bit flips required to transform one block of Hamming code into another block. If you play around with Hamming’s code list, you will notice that any two blocks are at least 4 units/bits of Hamming distance away from each other.

Neither Gino Fano nor Richard Hamming had intended for these two fields to come together (as far as I could research). But later generations of mathematicians figured out the connection between Hamming codes and projective planes.

Usually, when such connections are established, it leads to a bunch of new innovations. In a plot twist, this connection was used by a bunch of MIT students to game a state lottery, thus netting them millions of dollars.

I know what you must be thinking:

“Why would I be thinking of lotteries when my Mars drone is about to crash and burn?”

I get you. So, let us skip the lottery and focus on your problem.

How to Save Your Mars Drone?

The Hamming Code follows a linear error-correcting algorithm. It can easily detect up to two-bit errors and can correct one-bit errors. This is fine for applications like ECC-RAM (Error Correcting Code — Random Access Memory), but what about your Mars drone?

Without reinventing some of the historically more advanced error correcting codes, here are a couple of options we could consider:

1. The version of the Hamming code we have used so far involves (2^r — 1) bits, where r=3. You could just increase the value of r, thereby increasing redundancy and reducing the probability of signal corruption. But note that signal transmission speed also decreases correspondingly.

2. You could repeat the Hamming code signal thrice and tell the drone to return a copy of the input signal to you. If it matches, you could send a shortened (agreed) confirmation signal for the drone to execute your planned corrective manoeuvre.

With these options, the most important point that I wish to push across is this: with error correcting codes, we may, at best, reduce the probability of signal corruption, but we can never eliminate it completely.

So, depending upon your requirement (say that you wish to send the fastest input signal to your Mars drone), pick your pill and hope for the best.

Projective Geometry Meets Information Theory — II

Here is a simplified version of the nature of the problem we are up against: imagine that you are organising a party. Your challenge is to invite and get as many guests as possible into your party hall. At the same time, your challenge is to make sure that EACH party guest is as far away from EVERY other party guest as possible.

It turns out that the notion of projective geometry is very useful and efficient to solve such a problem. The notion of the Fano plane was useful for us to get to solve the Hamming code.

But in practice, mathematicians/scientists use higher dimensional geometries to solve for more advanced party/error-correcting algorithms.

Closing Comments

Back when Richard Hamming invented the Hamming code, his employer (Bell Labs) perhaps understood the value of the invention more than Hamming himself. Bell Labs resisted Hamming’s attempts to patent the invention.

In an ironic plot twist, Swiss mathematician Marcel Golay heard about Hamming’s ideas from Shanon and discovered his own versions of error-correcting code. And Golay published first, which has led to a lasting controversy about who gets the credit.

In the end, due to an antitrust settlement, Bell Labs lost the right to charge for the license on Hamming codes anyway.

Epilogue

As your drone is hurtling towards the rock, you decide that signal speed is your most important criterium. So, you go for the vanilla 7–4-Hamming code (the one we just covered) and hope for the best.

With just seconds to spare, your drone gets the correct transmission and lives another Martian day as it now travels towards Mount Olympus, the tallest mountain on Mars (its original destination).

What Happens When Projective Geometry Meets Information Theory? (I) — An two-dimensional illustration of a mars drone. It seems to feature 2 rotos on either side. The centre looks like a circular disc with two legs for landing. Below the mars drone, we see the following text in bold: “MISSION SUCCESS”
Mars Drone — Illustrative art created by the author

You breathe a sigh of relief, and realise the role of luck and randomness in all of this! All you could do was minimise the probability of error/corruption, given your requirement for the fastest possible transmission signal.

Reference and credit: Jordon Ellenberg and Patrick Fleming.

If you’d like to get notified when interesting content gets published here, consider subscribing.

Further reading that might interest you:

If you would like to support me as an author, consider contributing on Patreon.

Street Science

Explore humanity's most curious questions!

Sign up to receive more of our awesome content in your inbox!

Select your update frequency:

We don’t spam! Read our privacy policy for more info.