Over the past year or so, I’ve been transitioning my research to a more applied area, Algebraic Coding Theory; as a youngish PhD staring down the barrel of another job search, this was partially strategic. Another part of it was that this area just seems interesting; in school I had a few graduate classes in the area, so I thought I’d give it a try. It lets me flex my linear algebra muscles, but in a more applied direction. I’ve heard potential employers love that.

I’ll give a quick overview of the area, but this will just be a sketch. If you want to dive deeper, check out this book by Guruswami, Rudra, and Sudan. Essentially coding theory deals with the problem of communicating information over what’s called a “noisy channel”, where there is a significant, but hopefully small, chance that the message will be corrupted in some way. These are a familiar occurrence to anybody who’s had a dropped call on a cell phone, or if you try to play a Playstation game, but have a CD which has a few scratches on it, or if you’re an engineer who wants to communicate with the Voyager satellites as they travel further and further form the solar system. In all of these cases, some of the information is lost in transmission.

For example, if you wish to send the message the noisy channel might corrupt it to where . The game then becomes to pad the original message with a sufficient amount of excess information so that we can recover the original message. In this case let us think about each as an element of the field . This is what is called the “alphabet” of our code. Then we can construct 16 “codewords” by selecting either a or for each of the entries in . However, if we try to send but the noisy channel intervenes and instead the receiver gets , we have no way to tell even if there’s been an error, much less where the error occurred. So we need to pack it with enough redundant information to survive.

Among the first (and certainly the most famous) of the codes that could correct any one error that occurred during transmission is the Hamming code, named after Richard Hamming. Here’s a link to a playlist of his lectures about Information Theory (of which coding theory is one of the sub-fields). Lets think about the following picture.

We will think about the ‘s as our information bits, while the three are our “parity bits” which change value based on the values of the ‘s. The rule for choosing the values for the parity bit is that every circle must have an even number of ‘s. So for the message that you wanted to send, you would incorporate the parity bits at the end of the message to get the “codeword” based on the parity rule.

Now say that we had an error occur in the first place and our friend received . Then the friend could put those values into the diagram and then see that the circles containing and both have an odd number of ‘s, but the third circle didn’t have an issue. Hence the error occurred in the overlap of the first and second circles which is not contained in the third circle. Hence is the location of the error. This works no matter the message you choose and the location of the error. This “decoding algorithm,” however, can only handle a maximum of one error.

For those of us with some knowledge of linear algebra, this can be re-formulated as a vector space over . The rule that every circle needs to have an even number of zeros can be written as a system of homogeneous linear equations in .

Then the codewords that follow the ‘even circle rule’, the “valid codewords are precisely the kernel of this matrix

As the set of valid codewords is the kernel of , it must be a subspace of the vector space .

Alternatively we can also think about the following set of equations that we get by moving the message bits to the right hand side (remember that we are doing addition mod 2, so “” is the same as ““)

Then the set of valid codewords is the row-space of this matrix

.

In my research I look at “linear” codes, by which we mean that they are vector spaces. So we can use techniques from linear algebra to define them. The next post will be a bit more of a deep dive into some of the more technical aspects. But remember, if your mind starts swimming, go back to this post to just get a reminder of what the point is for all of this.

Until next time, and I promise it won’t be a year before the next post.