Linear Codes
A linear algebraic introduction
This article is the first in a series of posts that will seek to explain, both rigorously and intuitively, concepts from quantum computing.1
Let’s start by understanding linear codes — a key notion in classical error correction — and use it to set the stage for quantum error correction.
The usual presentation of linear codes begins with the 3-bit repetition code, then considers a general [n, k, d] code and its rate k/n, and so on, all from the engineer’s perspective of building practical codes. But as any math major at UChicago would ask, “that’s all well and good in practice... but how does it work in theory?”
In this post, I want to present linear codes from the abstract, pure math perspective of linear algebra.
Consider the space of n-bit strings, denoted {0, 1}n. Notice that {0, 1} = F2, so the space of n-bit strings is exactly {0, 1}n = F2n.
Just as ℝn is a vector space over the field ℝ, we might guess that F2n is a vector space over F2. Before we can evaluate this guess, we must define an addition operator on the space of n-bit strings.2
So, how can we add n-bit strings? Here are a few ideas one might think of:
Convert the n-bit strings into decimal numbers, add them in decimal, and convert back to binary.
For example, if I want to add the 2-bit strings 10 and 11, I look at their decimal representations, 2 and 3 respectively, add them in decimal to get 2 + 3 = 5, then convert 5 back into binary to get 101.
But clearly, this doesn’t work, because we added 2-bit strings (10 and 11) and got a 3-bit string (101), so the space is not closed under addition!
To resolve this, one can do the same thing — convert to decimal, add in decimal and convert back — but this time do the decimal addition modulo n.
For example, if I want to add the 3-bit strings 101 and 110, I look at their decimal representations, 5 and 6 respectively, add them in decimal to get 5 + 6 = 11, take modulo 3 to get 2, then convert 2 back into binary to get 010. So under this definition of the addition operator, we get 101 + 110 = 010.
The space is now closed under addition, but intuitively, this feels strange. To see why, think about what possible answers we can get when we add modulo n: we can only get the remainders 0, 1, …, n-1. So, adding any 3-bit strings can never give an output greater than 010 (i.e., 2). Isn’t this strange?
More rigorously, the addition map is not surjective onto {0, 1}n, which means that the space under this addition operator has no identity element. (Exercise: think about how failure of surjectivity implies lack of identity element. Suppose there was an identity element e, and try adding it to the 3-bit string 111 — what happens?)
To fix this, we repeat the same procedure, but we add modulo 2n instead of n. (Exercise: think about why this fixes the problem of the identity element!)
Alas, we are not yet done. Think about what we originally set out to do: we wanted to construct a vector space over the field F2. Observe that on F2, 1 + 1 = 0, so any vector v added to itself must give 1 v + 1 v = (1 + 1) v = 0. But with our modulo 2n definition, 011 + 011 = 110 ≠ 0.
Let us think back to the analogy with ℝn that we began with. How does ℝn avoid this problem? Well, addition on ℝn is coordinate-wise, i.e., (u + v)j depends only on uj and vj.
If we generalised such a notion of coordinate-wise addition to our space, we naturally get addition of n-bit strings defined as a bitwise modulo 2 addition (i.e., a bitwise XOR).
Finally, we have an addition operator under which {0, 1}n is a genuine vector space over F2. (Exercise: convince yourself that with the addition operator defined as bitwise XOR, this satisfies all the vector space axioms).
Whew! All that work was just to define an addition operator?! Let’s take a breather.
In pure mathematics, one often encounters the idea of a space — metric space, vector space, topological space, etc. — and one wonders what this means. After all, this is not the same space as one thinks of in the astronomical sense of the word.
An abstract space in mathematics is simply a set endowed with some structure. For example, a metric space is a set equipped with a notion of distance between points. A topological space is a set equipped with a collection of open subsets. A vector space is a set associated with a field, equipped with addition and scalar multiplication operators.
Given two spaces X and Y of the same kind, it is a natural question to ponder “which functions f: X → Y preserve the structure of the space?” For example, if X and Y are both metric spaces, then it is natural to study the functions that preserve distance. In the general case, given a space, we would like to consider the functions that preserve the essential structure of the space. The general name for such a function is homomorphism.
(Exercise: Considering the structure of vector spaces — namely, the operations they are equipped with — think about and write down the conditions required for a function to be a vector space homomorphism. Concretely, what properties would a function between two vector spaces f: V → W need to satisfy, in order to preserve the essential structure of a vector space?)
Spoiler: these requirements are exactly the definition of a linear transformation between vector spaces. In other words, a vector space homomorphism is precisely a linear transformation. This explains why we care so much about linear transformations: they preserve the essential structure of vector spaces.
Back to our study of {0, 1}n.
Note that this space has an additional structure: we can think of the “weight” of an n-bit string vector as the number of 1’s in it. For example, the weight of 10010 is 2, and the weight of 10111 is 4. We call this the Hamming weight of the vector.
And observe that our choice of the bitwise XOR as addition operator naturally gives a metric: given two n-bit string vectors, simply add them to get a new vector, and look at the Hamming weight of that vector to get the distance between the original two vectors:
So we actually have not just a vector space, but also a metric space! We call this the n-dimensional Hamming space. (Exercise: check that this is a valid metric: it is symmetric, non-negative, d(x, y) = 0 iff x = y, and satisfies the triangle inequality).
Going forward, we can think about Hamming space both as a vector space and as a metric space.
Now, what does one do when handed vector spaces? One thinks about maps between them, of course! So let us consider k-dimensional Hamming space Hk and n-dimensional Hamming space Hn and a map T: Hk → Hn between them. (For now, this can be any arbitrary map — we will impose constraints on it soon).
Our linear algebra intuition already tells us that imposing the constraint that T be a linear transformation might somehow make it interesting, though we don’t know exactly how just yet. Hold onto this intuition; it will come up soon!
Now, finally, let us turn to the application of all this theory.3
I posit the following for your consideration: if we wish to reliably send a k-bit message to a friend, across a noisy channel that may introduce errors in our message, then it is necessary to transmit more than k bits. (Exercise: think about why we need strictly more bits — what would happen if we sent exactly k bits and an error occurred?)
Let n and k be integers representing the number of transmitted bits and the number of bits in the message, respectively. Clearly, then, n > k.
Let us revisit the map T: Hk → Hn. We may think of this map as encoding our k-bit message as an n-bit string.
For example, if k = 3 and n = 5 and if our message is 101, then T might, for instance, map this to T(101) = 10111. Or some other choice of the map might give us, say, T(101) = 01101. For now, T is arbitrary and all that matters is that it is converting a k-bit message into an encoded n-bit codeword.
Let us think about what extra properties we desire T should have. For one thing, it would be strange if two different messages got encoded into the same codeword — e.g., if T(101) = T(111) — for how would our friend decode the codeword to extract our intended message? So we require T to be injective.
What is the cardinality of the image of T? Well, the domain has 2k elements and T is injective, so |Image(T)| = 2k. So the image of T is a 2k-element subset of the 2n-element set {0, 1}n. By the way, we refer to Image(T) by C, the set of codewords.
Now, just for fun, how about we force T to be linear and see what happens?4
If T: Hk → Hn is a linear transformation, then the image of T is a linear subspace of the codomain Hn. When this is the case, we call the code a linear code.
What does this mean? It means that adding any two codewords always produces another codeword. Peculiar! How could this possibly be of use to us? Stow this question and we’ll return to it.
In what scenario is an error correctable? Suppose, with k = 3 and n = 5, that my message is 101 and the corresponding codeword — the thing that I transmit through the channel — is T(101) = 11101. If no errors occur, then we are done, because T is injective so the recipient can simply invert to get T -1(11101) = 101.
If errors do occur, however, then the recipient will receive something different from 11101; for example, they may receive 11000. Therefore, note that the recipient flags an error when the received string is not a codeword.
In this case, we need to supply a decoding mechanism: a way to interpret the received, faulty n-bit string to extract the original k-bit message. Even without specifying the particular decoding mechanism, it is easy to imagine a case in which it fails: if so many errors occur that the received, faulty n-bit string is a codeword, then the situation is hopeless. For example, if 11000 is itself a codeword, then how can the recipient possibly know that the true message is not T -1(11000)?
Observe that there are two ways in which the recipient can receive a codeword: either no errors occurred, or so many errors occurred that another codeword was received.
So the operative question is: how many errors must occur to turn one codeword into another? But the codewords need not be evenly spaced apart, so what matters is, in the set of all 2k codewords, what is the minimum distance over all pairs of distinct codewords? We call this the distance d of the code, because it quantifies the code’s robustness: the larger the distance d, the more errors that can be detected.5
How does one compute the distance of a code? A priori, one would need to compute (2k choose 2)-many pairwise Hamming distances and find the minimum. But recall that for a linear T, the set of codewords is closed under addition. So we may simply find the minimum Hamming weight over non-zero codewords and we’re done!
For a linear code, the code distance is equal to the minimum, over all non-zero codewords, of the Hamming weights of the codewords.
This is the first indication of our vindication — we already see that forcing T to be a linear transformation, in line our with linear-algebraic intuition, made it much easier for us to compute d.6
We said earlier that the larger the code distance d, the more errors that can be detected. It is natural to ask, then, how exactly does the code distance d relate to the number of errors that can be corrected, call it t — what equation relates them?
Firstly, we must distinguish the number of detectable errors from the number of correctable errors — a priori, they may or may not be the same.
We defined the code distance d as the minimum number of bits that need to be flipped to go from one codeword to another. Clearly, this means that if d errors occur, then our code cannot detect them. But if fewer than d errors occur, then no matter what the original codeword was, it cannot have been distorted into another codeword — so it now sits somewhere in Hamming space, between codewords.
Recall that the recipient flags an error whenever the received string is not a codeword. This tells us that if fewer than d errors occur, then we know for sure that our code can detect them — so upto d-1 are guaranteed detectable.
What about correctable errors? In order to correct an error, we must construct a decoder function D: Hn → C that reads the received n-bit string and outputs the codeword that was transmitted.
We say that D corrects t errors if D(c + e) = c for every n-bit-error-string e that has Hamming weight ≤ t. This is a condition that an arbitrary function may or may not satisfy; what we are interested in is whether there exists a particular decoder function D that satisfies it. (Exercise: prove that such a D exists if and only if d ≥ 2t + 1).
So, detection works with guarantee up to d-1 errors, correction only up to (d-1)/2 errors. To detect, the error need only be visible; to correct, it must be unambiguous, and ambiguity sets in at the midpoint between codewords.
Having used an abstract path to getting here, let us reflect on the intuition it provides us.
Our linear algebra intuition told us that we should pick T to be a vector space homomorphism, namely a linear transformation, and this worked out well, giving us the concept of linear codes.
Seeing as Hamming space is also a metric space, we may very well have the idea of making T a metric space homomorphism too, namely a distance-preserving map, also called an isometry.
But in fact, an isometric T is the worst possible encoder, for it means that the code has d = 1 (exercise: why?), meaning that no errors can be detected, let alone corrected! The very nature of a useful code is that any two distinct k-bit messages — no matter how far apart in Hk — get mapped to codewords that are Hamming distance ≥ d apart in Hn — namely, the fact that T is not an isometry!
Clearly, we have an asymmetry that begs to be resolved: why are vector space homomorphisms ‘good’ but metric space homomorphisms ‘bad’? The answer lies in revisiting the notion of homomorphism as a map that preserves essential structure. But the question is, what is essential?
In this case, the message — the k-bit string vector — is essential. The notion of Hamming distance as a metric is used only as an evaluation criteria to gauge how good the code is — how many errors it can correct — and is not essential.
Put differently, a structure can come up as a constraint defining which maps are admissible, or as an objective that measures which admissible maps are good. Here, the vector space structure plays the first role, and the metric space structure plays the second.
We are only just scratching the surface of error correction theory (pun intended), and future posts will expand on further topics.
Feedback and reading recommendations are invited at malhar.manek@gmail.com
Some resources I found useful and would recommend:
This video on Hamming codes by 3blue1brown
This blog article on classical error correction by Arthur Pesah
I will try to use the discovery fiction approach suggested by Michael Nielsen, where one presents a plausible line of reasoning through which the reader, with some thought, might have discovered the ideas on their own.
As the aphorism goes, “good mathematicians prove theorems, great mathematicians come up with conjectures, and the greatest mathematicians come up with definitions.”
I deliberately chose to present an abstract explanation of linear codes. The standard presentation begins with the 3-bit repetition code and then generalises from it, but I find it worth at least exploring an alternative presentation, because:
The n-bit repetition code, while easy to grasp, has a rate k/n that tends to 0 as n goes to infinity, i.e., it is an inefficient code.
Personally, I love abstract linear algebra (and pure math more generally) and thought it would be worthwhile to approach linear codes from a linear algebraic perspective.
Generally, it is always good to have multiple different expositions of the same topic, and consider how each one illuminates a different facet of the idea.
Often in math, we have an intuition for something — e.g., our intuition might tell us that linear maps are vector space isomorphisms, so maybe, just maybe, something special might happen if T is linear? — and we test it out, and course-correct accordingly. When one solves many problems of a certain nature, one starts to develop an intuition for what might work.
Notice that we now have the [n, k, d] notation for a generic classical error correcting code.
Searching through the list of 2k codewords rather than computing (2k choose 2)-many pairwise Hamming distances. (Linear codes have several other nice properties, that we will explore in future posts).