Hamming codes, part 1 (early view)

Looking forward to this series! I have a couple of students who have chosen error correcring codes and matrices as their final project. This series should give them a better introduction than any regular textbook!

Glenn Wo

Great video! Just one technical thing: I’m not sure if it’s something weird with Manim, but it seems like there are elements of the video that are visible before you want them to be. Basically, there are pieces of text that are set up to fade in, but they are visible (with a very low opacity) long before their animation actually starts. Not sure if this is something you already know about, but I thought I would mention it since I didn’t see anyone else comment on it.

That's amazing.

3blue1brown

I'm not sure I understand the suggestion, are you suggesting adding on a 2005 label for Bacon and remove the '92 label for Shor? To have both? The spirit of the timeline is to just pinpoint the handful of most significant error correction contributions, where I thought it'd be fun to mention the very first version for quantum computation, which as I understand it was just from Peter Shor in the early 90s.

3blue1brown

Hmm, I'll look over that section and see if I can be clearer.

3blue1brown

I tried the exercises myself and it was really satisfying!

Great stuff as usual!

SomePoint

Love the 'DIY' parts ... made it interactive ... :)

Tristan Ursell

In the introduction, you show a CD. They use Reed-Solomon coding, no doubt following in part 2. It may be nice to add that Bluetooth (LE Coded PHY) uses Hamming codes.

Jan Prummel

Thanks Grant, another concept moved from the complex to the easy column. The video frames of Ben Eater were ‘empty’ (black screen). Not sure if that was intended. I was expecting a YouTube thumbnail. Also, I picked up on your use of ‘sender’ and receiver, rather than ‘transmitter’. I think it would make for more common terminology, but maybe less accessible to the larger audience.

Jan Prummel

Great video. With a little bit of guidance, my 6 year-old daughter was able to work through the example.

Shaeeyaa

This was a great watch! It ties in so nicely with the chessboard problem from a few videos back, and i really appreciate the gaps you put in for us to pause and 'discover' these things for ourselves 😄

Dan Kinch

Interesting question (both are, but on the topic of the first question specifically:), which probably would be interesting if it was covered in the video. I do think however that you could actually answer the question with the information in the video. If you look at the 'ranges' that each parity bit covers, those actually include the parity bits themselves. As you can identify 15 individual locations with this 4 bit encoding, you would also be able to uniquely identify the error if it was located inside the parity bit location itself. In that sense, since the whole encoding system only involves making a whole 'range' even or odd, there is actually nothing special about the parity bits themselves, every bit has the same "weight" so to speak. The only thing that makes them different is that we can freely adjust them, without altering the content that we care about. Or anyway, that is my understanding of it, based on just this video and some tinkering afterwards. I'll leave it to Grant to correct me if I'm wrong ;)

Nice! Can't wait to see Ben's video too!

jason black

It's maybe worth emphasizing that "assuming the best" in the way you describe is a given here. After all, there's always the possibility that a message gets so manipulated by the noise that it coincidentally equals another valid message, so when you see a message with a bunch of valid parity checks, to take it at face value is to assume the best.

3blue1brown

Well, keep in mind that we actually want this to be carried out by machines, and preferably as quickly as possible. It quickly gets very non-obvious how to extend to be robust to more bit errors. For example, an example of something a bit more robust which came shortly after Hamming codes, known as Golay codes, end up relating to the study of finite simple groups that I talked about in the monster video.

3blue1brown

I actually talk about this book in part 2

3blue1brown

Highly recommend reading Hamming's book The Art of Doing Science and Engineering. It covers thisAs and example, and gives his view on the process of developing engineering and science solutions. Well worth a look.

Question in my mind (that might be outside the scope of these videos) - is it reasonable with multiple errors to narrow down somewhat what the possibilities are, and then either have that covered by bigger-scale checker bits (wouldn't be surprised if this is a thing), or if necessary, test the options (such as visually displaying two possible photo reconstructions to the user) to see which is most likely?

C.J. Smith

I do think this could be worth a quick mention, wouldn't have to be long

C.J. Smith

I agree with Kevin's comment. There was a tendency on my part to reject the whole data block because the "overall" parity didn't work. But it only means that 1 or 3 ... errors occurred. This is clear from the following explanation, where the error is corrected and we assume the best!

Nice! It might be useful to discuss what happens if the error correction bits are in error. Is the system resilient against that or is an ECC level for the ECC needed?

Thank you so much for this! - One thing I'd recommend for better UI/UX is to change the reference to Shor codes as Bacon-Shor Codes because that's at least the first thing Google provides.. if you're mainly talking about another current standard - I'd be a little more specific. No need to change the audio.. They're just Shor codes, but especially upon first glance, the text near ~2:20 (first mention) I'd expand slightly to the whatever is the current best research you prefer. All the best,

I like it! Your explanation at 14:36 was a bit confusing, however. It sounds as if you're saying the whole-block parity bit is only telling us "that there was an error," which (as you point out) we already knew from the other blocks. I think it would be helpful to specifically say that it tells us there were an even number of errors, and to show what would have happened if the whole-block parity bit were not used (i.e. we would have misidentified it as a single-bit error and "corrected" it).

Kevin

I found the example very helpful. I thought I was completely following you and hadn't missed a thing, but when I paused for the example, I realized there were a few details I couldn't reproduce without a reminder. My brain thanks you for the reinforcement.

Jacob Mirra

The video leaves me with a couple of questions: 1. What if the parity bits are corrupted? 2. What is the best message size? For 2, since the ratio of parity bits to message bits is ~log2(n) / n, clearly bigger chunks are more efficient but you need to keep the size small enough that you don't expect to have more than one bit flipped... so you have to do statistics on acceptable error rates and volatility of your medium.

Alexis Olson

Amazing stuff! Seems like a great intro CS lecture to share with friends and teachers

Kyle Begovich

Should you make a comment that the error might actually be in one of the parity bits and not the message itself yet the hamming code handles that situation correctly too?

William Smith

Really beautiful work, I love how elegantly you presented it. The collab with Ben Eater is also really exciting! You both are really great educators!

Tyler Wolfe

This is incredible! I was expecting some kind of connection to the impossible chessboard puzzle, but wow I did not expect it'd be so similar!

Fantastic video! I always love the way you make us feel like we've "discovered" the topic on our own.

By the way, that podcast with Lex Fridman was quite enjoyable to listen to!

Vincent Zalzal

I’m so happy this is happening, thank you Grant!