Hamming codes and error correction

3Blue1Brown

3.59M subscribers

A discovery-oriented introduction to error correction codes.

Part 2: https://youtu.be/b3NxrZOu_CE​

Ben Eater:'s take: https://youtu.be/h0jloehRKas​

Many thanks to these supporters: https://3b1b.co/hamming-thanks​

Heavily related is the chessboard puzzle I did with Matt Parker:

https://youtu.be/as7Gkm7Y7h4​

You can read Hamming's own perspective on his discovery of these codes in chapter 12 of "The Art of Doing Science and Engineering".

https://amzn.to/3lwcnmh​

The viewer Harry Li made an interactive on this topic:

https://harryli0088.github.io/hamming...​

These animations are largely made using manim, a scrappy open-source python library: https://github.com/3b1b/manim​

If you want to check it out, I feel compelled to warn you that it's not the most well-documented tool, and it has many other quirks you might expect in a library someone wrote with only their own use in mind.

Music by Vincent Rubinetti.

Download the music on Bandcamp:

https://vincerubinetti.bandcamp.com/a...​

Stream the music on Spotify:

https://open.spotify.com/album/1dVyjw...​

3blue1brown is a channel about animating math, in all senses of the word animate. And you know the drill with YouTube, if you want to stay posted on new videos, subscribe: http://3b1b.co/subscribe​

Various social media links:

Website: https://www.3blue1brown.com​

Twitter: https://twitter.com/3blue1brown​

Reddit: https://www.reddit.com/r/3blue1brown​

Instagram: https://www.instagram.com/3blue1brown...​

Patreon: https://patreon.com/3blue1brown​

Facebook: https://www.facebook.com/3blue1brown

00:04

Have you ever wondered how it’s possible to scratch a CD or DVD and still have it play

00:08

back whatever it’s storing?

00:10

The scratch really does affect the 1’s and 0’s on the disc, so it reads off different

00:15

data from what was stored, but unless it’s really scratched up, the bits it reads are

00:20

decoded into precisely the same file that was encoded on to it, a bit-for-bit copy,

00:26

despite all those errors.

00:27

There’s a whole pile of mathematical cleverness that allows us to store data, and just as

00:32

importantly to transmit it, in a way that’s resilient to errors.

00:37

Well, actually, it doesn’t take too much cleverness to come up with a way to do this.

00:42

Any file, whether it’s a video, or sound, or text, code, an image, whatever, is ultimately

00:48

stored as a sequence of 1’s and 0’s, and a simple strategy to correct any bit that

00:53

gets flipped would be to store three copies of each bit.

00:57

Then the machine reading the file could compare these three copies and always take the best

01:02

two out of three whenever there’s a discrepancy.

01:07

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

01:11

And even then, for all that space given up, there’s no strong guarantee about what happens

01:15

if more than 1 bit gets flipped.

01:18

The much more interesting question is how to make it so that errors can be corrected

01:21

while giving up as little space as possible.

01:24

For example, using the method you’ll learn about in this video, you could store your

01:28

data in 256-bit blocks, where each block uses nine bits –Nine!– to act as a kind of

01:34

redundancy, the other 247 bits are free to carry whatever meaningful message or data

01:39

you want.

01:40

And it will still be the case that if a bit gets flipped, just by looking at this block

01:45

and nothing more, a machine will be able to identify that there was an error and precisely

01:50

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

01:52

And honestly, that feels like magic.

01:55

And for this particular scheme, if two bits get flipped, the machine will at least be

01:59

able to detect that there were two errors, though it won’t know how to fix them.

02:03

We’ll talk later about how this scales for blocks of a different size.

02:08

Methods that let you correct errors like this are known, reasonably enough, as “Error

02:11

correction code.”

02:13

For the better part of the last century, this field has been a really rich source of surprisingly

02:18

deep math being incorporated into devices we all use every day.

02:22

The goal here is to give you a very thorough understanding of one of the earliest examples,

02:27

known as a Hamming code.

02:29

And by the way, the way I’m thinking about the structure of this video is less about

02:32

explaining it as directly as possible, and more a matter of prompting you to invent it

02:37

yourself, with some a little gentle guidance here and there.

02:40

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

02:43

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

02:47

Also, if you want that understanding to get down to the hardware level, Ben Eater has

02:51

made a video in conjunction with this one showing you how to actually implement Hamming

02:55

codes on breadboards, which is extremely satisfying.

02:58

Now, you should know, Hamming codes are not as widely used as more modern codes, like

03:02

the Reed Solomon algorithm.

03:04

But there is a certain magic to the contrast between just how impossible the task feels

03:08

at the start, and how utterly reasonable it is once you learn about Hamming.

03:14

The basic principle of error correction is that in a vast space of all possible messages,

03:19

only some subset are going to be considered valid messages.

03:22

As an analogy, think of correctly spelled words vs incorrectly spelled words.

03:29

Whenever a valid message gets altered, the receiver is responsible for correcting what

03:33

they see back to the nearest valid neighbor, as you might do with a typo.

03:38

Coming up with a concrete algorithm to efficiently categorize messages like this, though, take

03:43

a certain cleverness.

03:47

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

03:51

and some of his work involved using a very big very expensive punchcard computer that

03:55

he had only limited access to.

03:57

And the programs he kept putting through it kept failing because every now and then a

04:01

bit would get misread.

04:03

Frustration being the crucible for invention, he got so fed up that he invented error correction

04:08

codes.

04:09

There are many different ways to frame Hamming codes, but as a first pass, we're going to

04:13

go through it the way that Hamming himself thought about them.

04:15

Let’s use an example that’s simple, but not too simple: A block of 16 bits.

04:21

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

04:25

The actual data we want to store is only going to make up 12 of these bits, while 4 of the

04:30

positions will be reserved as a kind of redundancy.

04:33

The word “redundant” here doesn’t simply mean copy, after all those four bits don’t

04:38

give us enough room to blindly copy the data.

04:40

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

04:45

any new information, but adding resilience.

04:48

You might expect these four special bits to come nicely packaged together, maybe at the

04:52

end or something like that, but as you’ll see, having them sit in positions which are

04:56

powers of 2 allows for something that's really elegant by the end.

04:59

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

05:04

Also, technically it ends up being only 11 bits of data; you’ll find there’s a mild

05:09

nuance for what goes on with position 0, but don’t worry about that for now.

05:14

Like any error correction algorithm, this will involve two players: A sender who is

05:18

responsible for setting these four special bits, and then a receiver who is responsible

05:22

for performing some checks and correcting any errors.

05:26

Of course, the words “sender” and “receiver” really refer to machines or software that's

05:29

doing all these checks, and the idea of a message is meant really broadly, to include

05:33

things like storage.

05:35

After all, storing data is the thing as sending a message, just from the past to the future

05:40

instead of from one place to another.

05:42

So that’s the setup, but before we can dive in, we need to talk about a related idea which

05:46

was fresh on Hamming’s mind in the time of his discovery, a method which lets you

05:51

detect any single-bit error, but not to correct them, known in the business as a “parity

05:56

check”.

05:57

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

06:01

for tuning, and the rest are free to carry a message.

06:04

The only job of this special bit is to make sure the total number of 1’s in the message

06:10

is an even number.

06:12

For example, right now that total number of 1’s is 7, that's odd, so the sender needs

06:16

to flip that special bit to be a 1, making the count even.

06:20

But if the block had already started off with an even number of 1’s, then this special

06:25

bit would have been kept at a 0.

06:27

This is pretty simple, deceptively simple, but it’s an incredibly elegant way to distill

06:31

the idea of change anywhere in a message to be reflected in a single bit of information.

06:37

Notice, if any bit of this message gets flipped, either from 0 to 1 or 1 to 0, it changes the

06:43

total count of 1’s from being even to being odd.

06:48

So if you're the receiver, you look at this message, and you see an odd number of 1’s,

06:51

you can know, for sure, that some error occurred, even though you might have no idea where it

06:57

was.

06:58

In the jargon, whether a group of bits has an even or odd number of 1’s is known as

07:02

its “parity”.

07:04

You could also use numbers and say that the parity is 0 or 1, which is typically more

07:08

helpful once you start doing math with the idea.

07:11

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

07:16

bit”.

07:17

And actually, we should be clear, if the receiver sees an odd parity, it doesn't necessarily

07:22

mean there was just 1 error.

07:23

There might have been 3 errors, or 5, or any other odd number, but they can know for sure

07:28

that it wasn’t 0.

07:29

On the other hand, if there had been 2 errors, or any even number of errors, that final count

07:35

of 1’s would still be even, so the receiver can’t have full confidence that an even

07:39

count necessarily means the message is error-free.

07:43

You might complain that a method which gets messed up by only two bit flips is pretty

07:47

weak, and you would be absolutely right!

07:49

Keep in mind, though, there is no method for error detection, or correction, that could

07:54

give you 100% confidence that the message you receive is the one the sender intended.

07:59

After all, enough random noise can always change one valid message into another valid

08:03

message just by pure chance.

08:05

Instead, the goal is to come up with a scheme that's robust up to a certain maximum number

08:10

of errors or maybe to reduce the probability of a false positive like this.

08:16

Parity checks on their own are weak, but by distilling the idea of change across a full

08:21

message down to a single bit, what they give us is a powerful building block for more sophisticated

08:26

schemes.

08:27

For example, as Hamming was searching for a way to identify where an error happened,

08:32

not just that it happened, his key insight was that if you apply some parity checks,

08:37

not to the full message, but to certain carefully selected subsets, you can ask a more refined

08:42

series of questions that pin down the location of any single-bit error.

08:46

The overall feeling is a bit like playing a game of 20 questions, asking yes or no queries

08:51

that chop the space of possibilities in half.

08:54

For example, let's say we do a parity check on just these 8 bits, all the odd-numbered

08:59

positions.

09:00

Then if an error is detected, it gives the receiver a little more information about where

09:04

specifically the error is; namely that it’s in an odd position.

09:09

If no error is detected among those 8 bits, it either means there's no error at all, or

09:14

it sits somewhere in the even position.

09:17

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

09:21

but when it’s done in conjunction with other well-chosen parity checks, it counterintuitively

09:25

gives us something more powerful.

09:28

To actually set up that parity check, remember, it requires earmarking some special bit that

09:34

has control for the parity of that full group.

09:37

Here let's just choose position number 1.

09:39

So for the example shown, the parity of these 8 bits is currently odd, so the sender is

09:43

responsible for toggling that parity bit, and now it's even.

09:48

This is only one out of four parity checks we’ll do.

09:51

The second check is going to be among the 8 bits on the right half of the grid, at least

09:55

as we've drawn it here.

09:56

This time, we might use position number 2 as a parity bit.

09:59

So these 8 bits already have an even parity, and the sender can feel good leaving that

10:04

bit number 2 unchanged.

10:06

Then, on the other end, if the receiver checks the parity of this group and they find that

10:11

it’s odd, they’ll know that the error is somewhere among these 8 bits on the right.

10:15

Otherwise, it means either there's no error, or the error is somewhere on the left half.

10:20

Or I guess there could have been two errors, but for right now we’re going to assume

10:24

that there’s at most one error in the entire block; things break down completely for more

10:28

than that.

10:29

Here, before looking at the next two checks, take a moment to think about what these first

10:32

two allow us to do when you consider them together.

10:35

Let's say you detect an error among the odd columns, and among the right half.

10:40

It necessarily means the error is somewhere in the last column.

10:43

If there was no error in the odd column, but there was one in the right half, well that

10:48

tells you it's in the second to last column.

10:50

Likewise, if there is an error in the odd columns but not the right half, you know that

10:54

it's somewhere in the second column.

10:56

And then, if neither of those two parity checks detects anything, it means the only place

11:00

an error could be is in that leftmost column, but it also might simply mean there’s no

11:05

error at all.

11:06

Which is all a rather belabored way to say that two parity checks let us pin down the

11:10

column.

11:11

From here, you can probably guess what follows.

11:13

We do basically the same thing, but for the rows.

11:16

There’s going to be a parity check on the odd rows, using position 4 as a parity bit.

11:21

So in this example, that group already has even parity, so bit 4 would be set to a 0.

11:26

And finally there's a parity check on the bottom two rows, using position 8 as a parity

11:31

bit.

11:32

In this case, it looks like the sender needs to turn on bit 8 on in order to give that

11:35

group an even parity.

11:37

Just as the first two checks let us pin down the column, these next two let you pin down

11:41

the row.

11:42

As an example, imagine that during transmission there’s an error at, say position 3.

11:47

Well, this affects the first parity group, and it also affects the second parity group,

11:52

so the receiver knows that there's an error somewhere in that right column.

11:56

But it doesn’t affect the third group, and it doesn't affect the fourth group.

12:01

And that lets the receiver pinpoint the error up to the first row, which necessarily means

12:05

position 3, so they can fix the error.

12:08

You might enjoy taking a moment to convince yourself that the answers to these four questions

12:12

really will always let you pin down a specific location, no matter where they turn out to

12:16

be.

12:17

In fact, the astute among you might even notice a connection between these questions and binary

12:22

counting.

12:23

And if you do, again let me emphasize, pause, try for yourself to draw the connection before

12:27

I spoil it.

12:30

If you’re wondering what happens if a parity bit itself gets affected…well you can just

12:35

try it.

12:36

Take a moment to think about how any error among these four special bits is going to

12:40

be tracked down just like any other, with the same game of 4 questions.

12:47

It doesn’t really matter, since at the end of the day what we want is to protect the

12:50

message bits, the error correction bits are just riding along, but protecting those bits

12:54

as well is something that naturally falls out of this scheme as a byproduct.

12:59

You might also enjoy anticipating how this scales.

13:02

If we used a block of size 256 bits, for example, in order to pin down a location, you need

13:08

only 8 yes or no questions to binary search your way down to some specific spot.

13:15

And remember, each question requires giving up only a single bit to set the appropriate

13:19

parity check.

13:23

Some of you may already see it, but we’ll talk later about the systematic way to find

13:26

what these questions are in just a minute or two.

13:29

Hopefully, this sketch is enough to appreciate the efficiency of what we’re developing

13:33

here.

13:34

Everything except for those 8 highlighted parity bits, can be whatever you want it to

13:38

be, carrying whatever message or data you want.

13:41

The 8 bits are “redundant” in the sense that they’re completely determined by the

13:45

rest of the message, but it’s in a much smarter way than simply copying the message

13:49

as a whole.

13:53

And still, for so little given up, you would be able to identify and fix any single bit

13:59

error.

14:00

Well...almost.

14:01

Okay, so, the one problem here is that if none of the four parity checks detect an error,

14:05

meaning that the specially selected subsets of eights bits all have even parities just

14:10

like the sender intended, then it either means there was no error at all, or it narrows us

14:15

down into position 0.

14:17

You see, with four yes or no questions, we have 16 possible outcomes for our parity checks.

14:22

And at first, that feels perfect for pinpointing 1 of the 16 positions in the block.

14:27

But you also need to communicate a 17th outcome, the “no error” condition.

14:33

The solution here is actually pretty simple: Just forget about 0th bit entirely.

14:37

So when we do our four parity checks, and we see that they're all even, it unambiguously

14:41

means that there is no error.

14:44

What that means, is that rather than working with a 16-bit block, work with a 15-bit block,

14:49

where 11 of the bits are free to carry a message, and 4 of them are there for redundancy.

14:54

And with that, we now have what people in the business would refer to as a “(15, 11)

14:58

Hamming code”.

14:59

That said, it is nice to have block size that's a clean power of 2, and there’s a clever

15:04

way that we can keep that 0th bit around and get it to do a little extra work for us.

15:08

If we use it as a parity bit across the whole block, it lets us actually detect, even though

15:13

we can't correct, 2-bit errors.

15:15

Here’s how it works.

15:17

After setting those four special error-correcting bits, we set that 0th bit so that the parity

15:21

of the full block is even, just like a normal parity check.

15:25

Now if there’s a single-bit error, then the parity of the full block toggles to be

15:29

odd, but we would catch that anyway thanks to our four error-correcting checks.

15:33

However, if there are two errors, then the overall parity is going to toggle back to

15:38

being even, but the receiver will still see that there’s been at least some error because

15:42

of what's going on with the four usual parity checks.

15:45

So if they notice an even parity overall, but something nonzero happening with the other

15:50

checks, it tells them there were at least two errors.

15:52

Isn’t that clever?

15:54

Even though we can’t correct those two-bit errors, just by putting that one little bothersome

15:58

0th bit to work, it lets us detect them.

16:02

This is pretty standard, it's known as an “extended” hamming code.

16:06

Technically speaking, you now have a full description of what a Hamming code does, at

16:10

least for the example of a 16-bit block.

16:13

But I think you'll find it more satisfying to check your understanding and solidify everything

16:17

up to this point by doing one full example from start to finish yourself.

16:21

I’ll step through it with you, though, so you can check yourself.

16:24

To set up a message, whether that’s a literal message that you’re transmitting over space,

16:29

or some data that you want to store over time, the first step is to divide it up into 11-bit

16:34

chunks.

16:35

Each chunk is going to get packaged into an error-resistant 16-bit block, so let’s take

16:40

this one as an example and actually work it out.

16:43

Go ahead, actually do it, pause and try putting together this block

16:46

....okay, you ready?

16:51

Remember, position 0 along with all the powers of 2 are reserved for error-correction duty,

16:59

so you start by placing the message bits in all of the remaining spots, in order.

17:05

You need this group to have even parity, which it already does, so you should have set the

17:10

parity bit in position 1 to be a 0.

17:13

The next group starts off with odd parity, so you should have set its parity bit to 1.

17:19

The group after that starts with odd parity, so again you should have set it’s parity

17:23

bit to 1.

17:24

And the final group also has odd parity, meaning we set that bit in position 8 to be a 1.

17:31

And then, as the final step, the full block now has even parity, meaning that you can

17:36

set that bit number 0, the overarching parity bit, to be 0.

17:41

So as this block is sent off, the parity of the four special subsets, and the block as

17:45

a whole, will all be even, or zero.

17:48

As the second part of the exercise, let’s have you play the role of the receiver.

17:53

Of course, that would mean you don’t already know what this message is; maybe some of you

17:57

memorized it but, let’s assume that you haven’t.

18:00

What I’m going to do is change either zero, one or two of the bits in that block, and

18:05

then ask you to figure out what it is that I did.

18:08

So, again, pause and try working it out.

18:15

...okay, so you as the receiver now check the first parity group and you can see that

18:23

it’s even, so any error that exists would have to be in an even column.

18:29

The next check gives us an odd number, telling us both that there’s at least one error,

18:34

and narrowing us down into this specific column.

18:38

The third check is even, chopping down the possibilities even further.

18:41

And the last parity check is odd, telling us there’s an error somewhere in the bottom,

18:46

which by now we can see must be in position number 10.

18:50

What’s more, the parity of the whole block is odd, giving us confidence that there was

18:56

one flip and not two (if it’s three or more, all bets are off).

19:01

After correcting that bit number 10, pulling out the 11 bits that were not used for correction

19:06

gives us the relevant segment of the original message, which if you rewind and compare,

19:11

is indeed exactly what we started the example with.

19:16

And now that you know how to do all this by hand, I’d like to show you how you can carry

19:19

out the core part of all of this logic with a single line of python code.

19:23

You see, what I haven’t told you yet is just how elegant this algorithm really is,

19:28

how simple it is to get a machine to point to the position of an error, how to systematically

19:32

scale it, and how we can frame all of this as one single operation rather than multiple

19:37

separate checks.

19:39

To see what I mean, come join me in part 2.