Home Creators Posts Import Register Favorites Logout
haven't archived this post yet. have a subscription? use the importer!

Content

Following up on the last post, here’s a draft of part 2 to the error correction project.

(Edit: swapping out video link for the finalized version)

Files

Previews only

Hamming codes part 2, the elegance of it all

Part 1: https://youtu.be/X8jsijhllIA Watch Ben Eater's video: https://youtu.be/h0jloehRKas Viewer-supported: https://3b1b.co/hamming-thanks A cleaner perspective on Hamming error correction codes. 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 Heavily related is the chessboard puzzle I did with Matt Parker: https://youtu.be/as7Gkm7Y7h4 ------------------ 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/album/the-music-of-3blue1brown Stream the music on Spotify: https://open.spotify.com/album/1dVyjwS8FBqXhRunaG5W5u ------------------ 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_animations/ Patreon: https://patreon.com/3blue1brown Facebook: https://www.facebook.com/3blue1brown

Comments

Anonymous

Awesome! I love the message at the end.

Anonymous

Fascinating! If you ever want to do a full explainer of Reed-Solomon codes, I would enjoy watching that as well.

Jan Prummel

Wait but ... When you do the example, why start with 16 useful data bits? You need to sacrifice the five parity bits at positions 0, 1, 2, 4 and 8, so why are they part of the starting point of 16 random data bits?

Anonymous

Awesome work Grant! I just happen to be reading Hamming’s book after hearing Bret Victor mention his influence so it’s quite lucky that my favorite math channel is putting out related content...must be some of that luck Pasteur was talking about.

Daniel Armesto

The parity bits could also be altered in transmission (or storage, or whatever). Maybe you could think of a system where you start with 16 information bits, and you add four parity bits. Then you would need two parity bits to check those initial four parity bits. And then one parity bit to check these two second order parity bits. You would end up with 16 information bits and seven parity bits, which is a ratio similar to 11/16. And you would still need to check for this third order parity bit, and then for the fourth order parity bit, and so on ... Part of the beauty of the Hamming code is that it also checks the parity bits. In other words, the parity bits take care of themselves.

Kevin

At 13:47, the words you say do not match the title of the book.

Gabe

I think you go through the code section really well. Doing it out "by hand" with the xor and then replacing that with the functions was very clear. I think the jump at 6:05 from explain the binary location of the bits to the "all you need to do is xor the location of each point in the message with a 1" is extremely abrupt. It might be better to list the message itself with the position bits along side (like you do in the code later) and then take out the lines where the message is turned off. That's can also be seen as a multiplication followed by an xor to get rid of the if statement.

Tom Hawking

i found this absolutely fascinating. fwiw, i don't have any sort of computer science background, and i 100% agree with your statement at 11:20 that the first method does a better job of instilling the core intuition about how and why this works. i'm sure i could have followed it if you'd started with the XOR method, but it would have felt more like a fait accompli: here's this method, here's how it works, and see how elegant it is? i'm sure i would have been impressed with the elegance of it, but i would have had no idea how or why anyone arrived at it -- whereas this way, the revelation that the four parity bits spell out the location of the error elicited a "whaaaaaat?! that's awesome" that woke the cat :)

Mike Jarvis

Great! Love both of these videos. I had managed to get pretty close to the single line of python conceptually trying to solve the chess board puzzle, but hadn't quite gotten all the way there. Mostly because I didn't quite appreciate how xor worked for a list of more than 2 numbers. That was very nice to see wrapped up so simply with reduce.

3blue1brown

Hmm, good point. Do you think it would fix it to simply state upfront that this move might look very weird and different at first, but will be explained shortly?

Anonymous

Great! I really like this stuff, and using python to demonstrate the theory is a very, VERY useful tool. Love this videos!

Anonymous

I am glad that you included the bit about larger blocks having a higher chance of containing more errors. I was thinking about that during the efficiency section, so it was really well timed.

Rion Boom Crabhands Keon

At 1:37 there is a frame linking to Ben Eater's video, but you don't talk about that.

Anonymous

Great video pair, goes without saying! Truly minor nitpick: I just noticed that the pi creature at 2:15 doesn't transition to the fadeout position smoothly, but skips instead.

Scroaty Ball Sac

Thanks... I'm in your Pateron bucket from this video.. This has given me so many helpful ideas 💡