Name: But what are Hamming codes? The origin of error correction
Uploaded: 2026-01-07T04:42:38.000Z
Duration: 20 min 5 s
Description: Thousands of YouTube videos with English-Chinese subtitles! Now you can learn to understand native speakers, expand your vocabulary, and improve your pronunciation...

Have you ever wondered how it's possible to scratch a CD or a DVD and still have it play back whatever it's storing?

Adverbs of degree

The scratch really does affect the ones and zeros on the disc, so it reads off different data from what was stored.

Basic passive voice

But unless it's really scratched up, the bits that it reads off are decoded into precisely the same file that was encoded onto it, a bit for bit copy.

Despite all of those errors, there is a whole pile of mathematical cleverness that allows us to store data and just as importantly, to transmit data in a way that's resilient to errors.

Actually, it doesn't take that much cleverness to come up with a way to do this.

Any file, whether it's a video or sound or text, some code, an image, whatever, is ultimately some sequence of ones and zeros.

And a simple strategy to correct any bit that gets flipped and would be to store three copies of each bit.

Then the machine reading this file could compare these three copies and always take the best two out of three whenever there's a discrepancy.

But what that means is using two thirds of your space for redundancy.

And even then, for all of that space given up, there's no strong guarantee about what happens if more than one bit gets flipped.

The much more interesting question is how to make it so that errors can be corrected when, while giving up as little space as possible.

For example, using the method that you'll learn about this video, you could store your data in 256 bit blocks, where each block uses 9 bits, 9 to act as a kind of redundancy.

And the other 247 bits are free to carry whatever meaningful message or data that you want.

And it will still be the case that if any bit gets flipped here, just by looking at this block and nothing more, a machine will be able to identify that there was an error and, and

precisely where it was, so that it knows how to correct it.

And for this particular scheme, if two bits get flipped, the machine will at least be able to detect that there were two errors, though it won't know how to fix them.

We'll talk a little bit later about how this scales for blocks with different sizes.

Methods that let you correct errors like this are known, reasonably enough, as error correction codes.

For the better part of the last century, this field has been a really rich source of surprisingly deep math that gets incorporated into devices we use every day.

The goal here is to give you a very thorough understanding of one of the Earliest examples known as a hamming code.

And by the way, the way I'm thinking about the structure of this video is less about explaining it as directly as possible, and

more a matter of prompting you to invent it for yourself with a little gentle guidance here and there.

So when you feel like you see where it's going at some point, take that moment to pause.

Actively predict what the scheme is going to be before I tell you.

Also, if you want your understanding to get down to the hardware level, Ben Eater has made a video in conjunction with this one showing you how to actually implement hamming codes on breadboards, which is extremely satisfying.

Now, you should know hamming codes are not as widely used as more modern codes like the Reed Solomon algorithm.

But there is a certain magic to the contrast between just how impossible this task feels at the start and how utterly reasonable it seems once you learn about Hamming.

The basic principle of error correction is that in a vast space of all possible messages, only some subset are going to be considered valid messages.

As an analogy, think about correctly spelled words versus incorrectly spelled words.

Whenever a valid message gets altered, the receiver is responsible for correcting what they see back to the nearest valid neighbor, as you might do with a typo.

Coming up with a concrete algorithm to efficiently categorize messages like this, though, takes a certain cleverness.

The story begins in the 1940s, when a young Richard Hamming was working for Bell Labs, and

some of his work involved using a very big, expensive punch card computer that he had only limited access to.

And the programs he kept putting through it kept failing because every now and then, a bit would get misread.

Frustration being the crucible of invention, he got so fed up that he invented the world's first error correction code.

There are many different ways to frame hamming codes, but

as a first pass, we're going to go through it the way that Hamming himself thought about them.

Let's use an example that's simple, but not too simple.

We'll number the positions of these bits from 0 up to 15.

The actual data that we want to store is only going to make up 12 of these bits, while four of the positions are going to be reserved as a kind of redundancy.

The word redundant here doesn't simply mean copyright.

After all, those four bits don't give us enough room to blindly copy the data.

Instead, they'll need to be a much more nuanced and clever kind of redundancy, not adding any new information, but

You might expect these four special bits to come nicely packaged together, maybe at the end or something like that.

But as you'll see, having them sit in positions which are powers of two allows for something that's really elegant by the end.

It also might give you a little hint about how this scales for larger blocks.

Also, technically, it ends up being only 11 bits of data.

You'll find there's a mild nuance for what goes on at position zero.

Like any error correction algorithm, this will involve two.

A sender who's responsible for setting these four special bits, and

then a receiver who's responsible for performing some kind of check and then correcting the errors.

Of course, the words sender and receiver really refer to machines or software that's doing all the checks.

And the idea of a message is meant really broadly to include things like storage.

After all, storing data is the same thing as sending a message just from the past to the future, instead of from one place to another.

But before we can dive in, we need to talk about a related idea which was fresh on Hamming's mind in the time of his discovery.

A method which lets you detect any single bit errors, but

not to correct them, known in the business as a parity check.

For a parity check, we separate out only one single bit that the sender is responsible for tuning, and

The only job of this special bit is to make sure that the total number of ones in the message is an even number.

So, for example, right now, that total number of ones is seven.

So the sender needs to flip that special bit to be a one, making the count even.

But if the block had already started off with an even number of ones, and

then this special bit would have been kept at a zero.

This is pretty simple, deceptively simple.

But it's an incredibly elegant way to distill the idea of change anywhere in a message to be reflected in a single bit of information.

Notice if any bit of this message gets flipped either from 0 to 1 or 1 to 0, it changes the total count of ones from being even to being odd.

So if you're the receiver, you look at this message and you see an odd number of ones, you can know for sure that some error has occurred, even though you might have no idea where it was.

In the jargon, whether a group of bits has an even or an odd number of ones is known as its parity.

You could also Use numbers and say the parity is 0 or 1, which is typically more helpful once you start doing math with the idea.

And this special bit that the sender uses to control the parity is called the parity.

And actually we should be if the receiver sees an odd parity, it doesn't necessarily mean there was just one error.

There might have been three errors or five or any other odd number, but

they can know for sure that it wasn't zero.

On the other hand, if there had been two errors or any even number of errors, that final count of ones would still be even.

So the receiver can't have full confidence that an even count necessarily means the message is error free.

You might complain that a message which gets messed up by only two bit flips is pretty weak, and

Keep in mind though, there is no method for error detection or correction that could give you 100% confidence that the message you receive is the one that the sender intended.

After all, enough random noise could always change one valid message into another valid message just by pure chance.

Instead, the goal is to come up with a scheme that's robust up to a certain maximum number of errors, or maybe to reduce the probability of a false positive like this.

Parity checks on their own are pretty weak.

But by distilling the idea of change across a full message down to a single bit, what they give us is a powerful building block for more sophisticated schemes.

For example, as Hamming was searching for a way to identify where an error happened, not just that it happened, his key insight was that if you apply some parity checks not to the full message and but to certain carefully selected subsets, you can ask a more refined series of questions that pin down the location of any single bit error.

The overall feeling is a bit like playing a game of 20 questions, asking yes or no queries that chop the space of possibilities in half.

For example, let's say we do a parity check just on these eight bits, all of the odd numbered positions.

Then if an error is detected, it gives the perceiver a little more information about where specifically the error is, namely that it's in an odd position.

If no error is detected among those eight bits, it either means there's no error at all, or it sits somewhere in the even positions.

You might think that limiting a parity check to half the bits makes it less effective, but

when it's done in conjunction with other well chosen checks, it counterintuitively gives us something a lot more powerful to actually set up that parity Check.

Remember, it requires earmarking some special bit that has control for the parity of that full group.

Here, let's just choose position number one.

So, for the example shown, the parity of these eight bits is currently odd.

Subtitles ListPlay Video

But what are Hamming codes? The origin of error correction

specific

assume

matter

flip