Hamming codes part 2: The one-line implementation
Vložit
- čas přidán 3. 09. 2020
- A cleaner perspective on Hamming error correction codes
Part 1: • But what are Hamming c...
Watch Ben Eater's video: • What is error correcti...
Help fund future projects: / 3blue1brown
An equally valuable form of support is to simply share some of the videos.
Special thanks to these supporters: 3b1b.co/hamming-thanks
You can read Hamming's own perspective on his discovery of these codes in chapter 12 of "The Art of Doing Science and Engineering".
amzn.to/3lwcnmh
Heavily related is the chessboard puzzle I did with Matt Parker:
• The almost impossible ...
If you're curious to learn a bit about Shannon, the father of information theory, take a look at this documentary.
amzn.to/2RHK5HL
Thanks to these viewers for their contributions to translations
Hebrew: Omer Tuchfeld
Hungarian: FaboBence
------------------
These animations are largely made using manim, a scrappy open-source python library: 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:
vincerubinetti.bandcamp.com/a...
Stream the music on Spotify:
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 CZcams, if you want to stay posted on new videos, subscribe: 3b1b.co/subscribe
Various social media links:
Website: www.3blue1brown.com
Twitter: / 3blue1brown
Reddit: / 3blue1brown
Instagram: / 3blue1brown_animations
Patreon: / 3blue1brown
Facebook: / 3blue1brown
14:55
Grant: "Clever ideas often look deceptively simple in hindsight, which makes them easy to under-appreciate."
Me: *still can't fathom how anyone could ever figure out something so clever and elegant*
This is how I feel after finishing any of his videos. They are truly magical
My thoughts exactly, just standing in awe. So many brilliant people...
My mind was absolutely blown when it was shown how turning the results from the parity checks into binary-booleans gave you the exact location of the error and it just clicked for me why you placed the redundancy bits at powers of two! Dear god I love this channel and please please please don't stop producing content.
honestly. the guys and gals who worked in comuting and hardware at the start of the field are absolute geniuses. I am always left speechless when learning about the tricks they used, the methods they developed, the brilliance of it all
We have some smart tech people now too, but the people who started the field from nothing will always be amazing to me
I noticed that too, our brain is well created by God.
@@mohammedsamir5142 If you think Hamming Codes are beautiful, wait till you learn about biological evolution.
I know! I audibly yelled "Of course!" when he pointed that out. I can't believe I didn't see it sooner.
he just started off with a banger. I was just mind blown at the start...
When you learn about this kind of clever things, it's genuinely impressive how often it ends up having been invented at Bell Labs ...
Bell Labs deserves a documentary series of its own. How it was funded, what they let their people do. So, so much of what we all depend on had foundations laid down there.
Its not that incredible when you think about it. Most of these fundamentals were designed in the early era of computers when there simply weren't that many players involved -- a couple of major companies like Bell and IBM and a handful of the most technical universities like MIT and that was about it. If you wanted to work on an actual computer, you had to be at one of those places -- the devices simply didn't exist elsewhere.
Its kind of like being surprised that advances in rocket tech have mostly come out of Space-X, Blue Origin and Virgin Galactic in the past 5 years or so. Even NASA isn't really working on rocket tech these days (they seem to focus more on satellites now and farm the lift out to private industry.) Maybe 50 years from now rocketing will be so cheap and commonplace that there are hundreds or thousands of competing companies employing smart people, but right now there's only a fairly small group of employers so its not too unusual for most work in the field to come from people working for one of those employers.
@@altrag This does make a lot of sense!
@@thealienrobotanthropologist NASA was chartered under the 1958 Space Act to develop space technology and transfer it to US industry. That Act forbids NASA to compete with private companies. NASA's serious engineering focuses on making the impossible, possible. Do it first, document the lessons, and teach industry. Then get out of the business and engineer something harder.
Sadly the organization's funding is a shadow ( about 10%) of its former level.
That's the response to your comment, by an old friend and co-worker still working at JPL.
@@TinkerAssist_ Not really the point. The point is simply that there are few places doing the research, so research related to the subject necessarily comes from those places.
Whether that research is "fundamental" or "leveraging a convergence of technologies" is kind of beside the point.
I really love what you said at the end. Too often we learn the end results from textbooks without any indication of how insanely clever their discoverers were. This channel is great at telling the story of that discovery process for us.
This is something I've always tried to describe to teachers and people designing curriculum (most of my family is involved in education, so this isn't super weird): I used to phrase it like "we need to teach math, but like the *history* of math." I probably should have found a better way to describe it lol. But it was the same as this point you're talking about.
@@delphicdescant When tutoring students in the STEM field at my college, I always re-derive it for the students. Often times the students don't entirely understand the significance of a derivation or the professor doesn't have the time to explain it to the students (class pacing is brutal). Sometimes all a student needs is a different perspective than the one they're given.
The video actually does NOT tell the story of that discovery process. (It's a very long story!) That's the point he was trying to make at the end of the video, that we under appreciate the amount of effort put into the process because we only see the result, i.e. what is explained in these two videos.
@@delphicdescant I think sciences like chemistry and physics should be the same way. It makes it much more interesting to hear the story of how things developed the way they did, what problems the minds of the time were facing and how they solved them, especially when you get to late 19th and early 20th century. (@mike) 3b1b might not have told the full story, but he at least set up the problem at hand with the punch cards, and showed the book where you can read all about it.
This is so true, Grant is truly a god-tier STEM communicator
"It can be done in python in 1 line of code"
import HammingCode
i get it i get it!
by the way, a huge shovel of schite to those who count "lines of code per hour"
Two lines
import HammingCode
HammingCode.findError(bits)
@@ultimatedude5686 If you use a semicolon, you can do it in one line.
David L. Q. So everything can be considered as "one line of code"
David L. Q. Isn’t that kind of cheating though?
Can we dig into Reed-Solomon error correction next? (Multiple-bit and burst error correction used for CD’s, DVD’s, QR codes, RAID-6, etc.)
Yes Plesse 😁
Its to complicated dude
Or maybe cyclic redundancy checks (CRCs).
Ikr wf
And NASA space probes, don't forget those!
I kid you not. I'm sitting at the airport, I pull out my phone. I think, "It'd be awesome if there were a new 3B1B video"
So yeah, you're the best
have an "errorless" journey ;P
It's pretty unlikely that exact situation would happen to you or anyone specifically, but given how often he uploads and how many people are excited for the uploads and say "It'd be awesome if", it's pretty likely to happen to someone eventually. I bet there's a 3B1B video on that idea lol
@@PianoMastR64 Lol way to math away the excitement 😆
@@PianoMastR64 I guess it's not surprising that someone wins the lottery every now and then, but it's pretty exciting if it happens to you lol
I was bored sitting in hospital bed after playing tons of Earthbound and Final Fantasy , I pulled out the phone and watched Computerphile, Numberphile and 3B1B videos. Don't regret it at all, time well spent
The interesting thing about the error correcting idea is that it was used as a card trick people may have seen before (I know I saw it when young). Each card has a list of numbers written on them, and another person is asked to pick a number between 1-60 and pick out each card with that number printed on it. The cards each were a binary class as shown in this video, so all you had to do to guess their number was sum the top left number on each card.
I did this as a Maths teacher a few years ago to teach binary arithmetic to kids :)
@jalel @3blue1brown thanks to your comment i grabbed a pack of cards and realized one trick i remembered from childhood functioned was exactly this. i knew this algorithm when i was like 9 or 10 or 11? but i did never connect math with it. this makes it even more beautiful- and to shows me complex stuff can be thought and learned way earlier. you two together invoked beautiful childhoodmemories, thank you guys =)
Yeah I had that when I was younger, and I thought it was so amazing that I saved it from the magic set it came with. I found them again a few weeks ago and figured out the trick, and I gotta say figuring out the solution to something I know baffled young me was a really nice experience.
Any video on this card trick 👀 asking to increase my repertoire of party tricks...
@@jaishkhan7442 you'll have to print out certain cards. First one for example will have 1,3,5,...,59 (only odd numbers). Second will have 2,3,6,7,... (2 or 3 mod 4). And so on. Your last card will be 32, 33, ...
I'm studying Geology. I have NOTHING to do with this sort of things but I'm still here for those beautiful videos and ideas/ concepts :)
Divided by Different streams, united by Curiosity.
The true essence of Science , :)
does 1 + 1 = 0 surprised to you?
I am very very ignorant in geology but I'm pretty sure data processing plays a huge part in this field. Like idk when reading height data from satellites or measuring seismic activity :)
Geology is good, but be careful of the political brainwashing and follow the money. Stick with the good science and when new information comes, be ready to change your indoctrinated beliefs in geology. this is a youtube guy who is brilliant at predicting earthquakes with science. /user/dutchsinse
Luck favours the prepared mind.
3B1B in a nutshell: Takes "Impossible" topic, blindfolds you for a second, removes the blindfolds, shows beauty.
Btw I reeeeeally love your work.
Oh, _hey there!_
I agree, this is wonderful.
This reminds me of the following riddle:
The King of a small country invites 1000 senators to his annual party. As a tradition, each senator brings the King a bottle of wine. Soon after, the Queen discovers that one of the senators is trying to assassinate the King by giving him a bottle of poisoned wine. Unfortunately, they do not know which senator, nor which bottle of wine is poisoned, and the poison is completely indiscernible. However, the King has 10 prisoners he plans to execute. He decides to use them as taste testers to determine which bottle of wine contains the poison. The poison when taken has no effect on the prisoner until exactly 24 hours later when the infected prisoner suddenly dies. The King needs to determine which bottle of wine is poisoned by tomorrow so that the festivities can continue as planned. Hence he only has time for one round of testing. How can the King administer the wine to the prisoners to ensure that 24 hours from now he is guaranteed to have found the poisoned wine bottle?
Exactly!
I remember this riddle from my childhood -
and during the video it immediately sprang to mind.
It's kind of shocking to realize that an important concept as this, only discovered in the 50' -
can still be compacted into a riddle for school children.
I'd never heard this riddle! There's my solution below for those who don't want to get spoiled.
It turns out that 999 in binary has 10 digits: 1111100111
So the king just has to label the bottles in binary, from 0000000000 to 1111100111.
Then he gives the first prisoner a glass filled from all the bottles starting with a 1, the second prisoner all the bottles which second digit is a 1, etc. until the 10th prisoner who's given all the odd labelled bottles.
24 hours later, the king writes 1 if the first prisoner died, or 0 if he's alive. To the right of that digit, he writes 1 if the second prisoner died, and 0 if he's alive, and so on to the tenth prisoner.
At the end of this process, the king has written the label of the bottle containing the poison.
@@Ricocossa1 Don't you actually have to take out a bottle, and have that one be the poison if no prisoner dies?
@@maxsnts Well, how do you know which bottle to take out? You can only have them drink once.
Edit: I see what you mean. The bottle you take out is actually the one labelled 0000000000. That one will be in none of the prisoners' glasses.
Incidentally you could also have them drink that bottle. The trick works with up to 1024 bottles. If you have just one more, you'll need 11 prisoners.
I was reminded of a whole family of puzzles involving, say, 100 coins, one of which is counterfeit and weighs less than the rest, and all you have is a balance scale. The most efficient way of weighing them is with a clever grouping which is effectively the same thing as your puzzle's solution
This feels almost too elegant. I mean that I would never expect it to work out this nicely so I would not even put my effort into it and I would never discover all these last tricks.
Seeing a brilliant mind at work (like Hamming in this case) is astonishingly beautiful
The feeling when some problem that you thought was terribly complex, simplifies down to something so concise, is pretty special. It's almost like you've discovered something fundamental about the universe, the first explorer gazing at a new continent. I'm no Hamming, but I've had a few moments like that writing code, where some long block reduces down to a simple formula and you're just like, "aw yeah" hehe
It’s elegant, but very pedestrian. The single bit flip assumption is rather weak. There are much stronger codes in terms of error correction and detection capacities. They involve harder math as well.
Hamming codes were good for the time and a nice intro to coding theory.
Woah realized 'the why' of the relation between the binary bisection and the fact that it actually spells out the position of the cell in binary just before you explained it, that has never happened to me before in one of these videos.
*dopamine boost intensifies*
addiction to math complete.
it's a great feeling.
My "naive" implementation started from the top to keep all possible error locations within a solid interval:
"Error is somewhere between 0 (included) and 16 (excluded). Now is the error in the 2nd half? If not, the new endpoint becomes (0+16)/2 = 8. If it is, the new starting point becomes 8. Then, in which quarter of the array (i.e. which half of the interval) is the error? Halve the interval again, etc. until you have an endpoint that's 1 more than the starting point, and the error is pinned down. But the solution in the video is even more elegant.
For hardware, one could run the data through a circuit where you have 4 XOR gates, and you'd use the index of the bit to turn the gates on/off, so that each gate XORs only half the data. In software, one would XOR the indices of all bits which are 1. Essentially, that's two ways to XOR, by column in hardware and by row in software.
The Haskell programmer in me loved the "one line" reduction (though wanted to write it pointfree), but the C++ programmer in me hated it and wanted to write the 32-bit version as a fixed series of operations in the most efficient manner possible.
Blubwrun
You can rewrite the program in Haskell as a hylomorphism. Making use of the Recursion Schemes library, we can write it as the following;
hammingAlgebra :: ListF Int Int -> Int
hammingAlgebra Nil = 0
hammingAlgebra (Cons i1 i2) = xor i1 i2
hammingCoalgebra :: (Int, [Bool]) -> ListF Int (Int, [Bool])
hammingCoalgebra (_, []) = Nil
hammingCoalgebra (i, (b : r)) = Cons (if b then i else 0) (i + 1, r)
hamming :: [Bool] -> Int
hamming = hylo hammingAlgebra hammingCoalgebra . (0,)
This rendition is also, in some ways, more efficient than the one given in the video, as it avoids using the linear space required to store the enumeration list, only using constant space instead. We can turn this into a point-free implementation, but it won't look too good as the position (i) needs to be copied for both keeping track of position and being fed into xor.
I personally hate list comprehension syntax as it obscures the algebraic structure of what's going on behind seemingly clear but in-fact obscuring syntax sugar.
I have been raised on C-similar languages since 5th grade so anything that isn't completely efficient ticks me off
@@shershahdrimighdelih I've been using Scratch for a few years, and yes, *everything* must be as efficient as possible. Because else it just won't work or will be too slow or non-scalable...:)
xor is a single clock cycle operation, I'm not sure how something like this could possibly be written inefficiently with something that compiles natively. unless you'd do memory allocations in a loop while checksumming something large
I used to play a game called Mastermind where I had to guess the location and colours of 4 pegs using a series of guesses. My method for winning looks a lot like using parity bits.
Ah I remember this game. I think the game is winnable in at most 4 moves
I only know that game because of a minecraft youtuber known as Ethoslab XD
@@shantanunene4389 Depends on the version. I had a version with 8 colors and 5 spaces; I don't know what the number of moves is for that version, but I doubt it's 4
@@Hi_Brien He is a master
Thankyou
I think that the best part about your videos is that you won't understand something completely unless you pause and work on it yourself. I've seen comments asking you to slow down but I think your pace is perfect for telling me that something is going beyond my head. Then, when I pause and figure it out myself, I'm never going to forget it. Keep up the great content :D
Exactly!
reduce() will raise an exception if the list of values to reduce is empty (i.e. all bits were 0 in the Hamming-encoded message). So technically, you should pass 0 (the identity for XOR) as an additional argument:
reduce(ops.xor, (i for i, bit in enumerate(bits) if bit), 0)
That's what I was thinking too.
This is the perfect example of a perfectly right, but definitely unnecessary comment
@@hidroman1993 how ist it unnecessary? It points out a bug in the code and povides a bugfix. The video didn't state the precondition of the message not being all 0
Wow thank you code nazi, maybe the purpose of the video is other than showing a screen full of code
@@hidroman1993 I don't understand why you're upset. Even if the point of a video is to communicate the concept and to induce curiosity.
The comment wasn't rude or condescending, it just presented the facts.
Even if the simplified version is in the video on purpose there's nothing useless about posting the fully correct version.
Beautiful.
However, I'm still waiting for part 3 of "probability of probabilities"
Yeaaah me too...
@@gaeb-hd4lf i wish there were black, lgbt and women programning
Hugo Daniel javascript isn’t racist
No programming language should be racist
@@masonhunter2748 I’m sure we can all agree that if any programming language was racist, it would probably be javascript
I swear the explanations that you make are impossibly elegant, just like some of the things you explain. kinda crazy as I consider myself to be a very slow person and I can absolutely understand the flow of your videos w/o having to rewind. the videos always seem to have immensely powerful lessons as well, where we not only learn about a fun fact but also how it was thought of, how amazing it was, and a separate takeaway other than the thing we're learning. honestly amazing, it's so appreciated, and I absolutely love this channel for it.
Although I studied electrical engineering with focus on communications and most of this is really familiar, it's still fascinating to see it explained and visualized so beautifully. I wish this channel already existed during my studies, that would have made thing so much easier.
you have 3.14 million subscribers as of right now, that is milestone goals...
Oh good lord. I remember learning this in the 90s. Looking forward to the Reed-Solomon encoding, I don't think we ever covered that.
CZcams-recommended had me watch part 2 first
maybe because youtube algorithm prefers more recent video
Maybe CZcams algorithm did not correct its code ;)
@@rohitsrao or maybe its complete GARBAGE
@@j.hawkins8779 yea probably
@@Sohlstyce no, DEFINITELY
Learning about Hamming Codes was such a cool moment in my computer science education along with learning about compression and learning about encryption.
They were so intuitive when someone shows you but mindblowing when you think about it.
5:45 the yellow boxes aren't aligned. I cried when I saw this
That's because of the difference in the number of zeros and ones before those boxes!
TIHI
The money quote of the video: "Ironically the ideas that most profoundly shape the ways that a future generation thinks will end up looking, to that future generation, simpler than they really are."
I was inspired during a liners algebra class to write all binary logic functions as a composition of just xor and and.
In the early 1970's, Hamming spent a year at U C Irvine, working on the second edition of his book. He also taught a class. I'm one of the survivors of that year-long experience. I remember Hamming talking about being forced to invent error correcting codes so he could do (reliable) computation on unreliable hardware. He was brilliant, and a curmudgeon who did not suffer fools well -- I also remember his rant one morning in class when he discovered that some of us had not had a class in complex variable... And then proceeded to give us poor folks an amazingly lucid explanation (that astounded those in the class that had completed complex variable). Hamming's year-long class was one of the highlights of my time at UCI.
I love to see how clever people can be. Just imagine you standing in front of such a problem and trying to find such an elegant solution!
Great video! The clear and eloquent way you explain it is admirable! The very process of learning give an incredible sense of pleasure, giving another different perspective of the way of thinking and to see the result! Bravo!
Im a mathematician and I'm high. This is pure gold.
Y e s
"a mathematician and high" ... There is a lot of redundancy there ;)
Same
@@travcollier i wish there were more were black, women and lgbt in mathematics
@@hugodaniel8975 Used to be a lot of women in high-level maths. Never been a lack of talent there. Sexism is stupid :(
On race, Europeans never had a monopoly, but there's a very strong cultural component (which is why Inida and Persia were way more advanced on maths than Europe for most of history.) Most of the great work comes from ideas someone has when they are pretty young, so it really helps to grow up around maths. It isn't common anywhere, but in some places there are sort of math-is-cool subcultures. Black nerds sort of 'coming out' these days is promising on that front, but it is a generation timescale thing.
LGBT... Yeah, no reason not. Actually, thinking about it, LGBT might already be fairly or even over-represented. It's more of a case of them always being there, just not being obvious. The norms have shifted really quickly, and the majority of folks in the maths and sciences react to LGBTQ with a sort of shrug... So Jim became Joan, ok, they are still an expert on using differential equations to model ecosystem dynamics (that's a real example BTW).
this channel makes so many complicated or high-level topics easily accessible for no cost; you've helped me really *understand* topics that daunted me just reading the video titles. you're fighting the good fight of information accessibility!
Amazing! I love how you built it up in two videos, one the long, but intuitive way, and then the other one just breaking it down into literally two operations.
XOR is an "addition mod 2"
whaaaat, and only know, after 2 years of eletronics AND half of the course of Computer Scientist i know that ??????
I figured it out and I haven't gone to college yet...... It's more important we figured it out. Most people never will.
That's a very elegant way to say it
Yep! If you've studied digital logic circuits at all, here are two more ways to think about it:
1. XOR is the output of a half adder.
2. Hamming codes work on the same principle as using Karnaugh maps to create boolean algebra expressions from bit tables.
Exceedingly cool to see these connecting points between things I think!
also, AND is multiplication. 1*1=1, 1*0=0, 0*1=0, 0*0=0
Easier to consider it a toggle by mask.
Hey. I tried to visualize a (7, 4) bit problem as a 2x2x2 cube, then expandable to higher dimensions, and not a 2x4 rectangle. Instead of the band patterns I get cool half cube divisions in each dimension. It is basically the same, but it is a cool visualization. In case I wasn't clear I can try explaining it better :)
3b1b did mention that idea in the Chessboard video as "a really satisfying way of coloring a hypercube", which is analogous to the (15, 11) Hamming block.
Yep, and visualising a (255,247) Hamming Block is as simple as visualising halves of an 8-dimensional hypercube. It's simple, I really don't get what all the fuss is about.
We do that in school.
I mean, university of Informatics.
i see you watched the computerphile video too
Truly fascinating-I’ve found my way to the Shannon paper before through your mention in a previous video, and that paper has transformed a lot about how I think about basically everything, not just math or science either literally everything
Wow. Oh my goodness. I don't know if I have ever been as blown away by the simplicity and elegance of an explanation of any topic on CZcams. Thank you so much for this video! I understand Hamming codes, and error detection and correction as a whole, far better than I ever have before. I will definitely be "liking and subscribing"!
"Number of bits required is the log base 2 of the bit size." Claude Shannon entered the chat 😂
I think I dropped a tear when I saw the blue line crossing the whole maze of paths at the end, as I only got where you were going with that animation when you actually finished stating your last message... That's very true to me, and the way you so simply represented it is so simple yet beautiful ; with all those little pi-searchers going into wrong/forgotten directions, and this only pi-stein which is remembered as the big hero of a simplified story.
Hey 3b1b, I just wanted to say thank you for these videos. I was suggesting your work and as I explained why it worked for me, being a visual learner, the more I realized it is because of people like you, who give visual form to the data, that I have had any improvement. Thank you so much!
just went through 2 of the videos, and i just wanna say you're AWESOME!
Awesome easy-understand explanations!
Awesome animations!
Thank you!
I'm a simple man, whenever I see "Lambda" or "reduce" I click.
> using fold in Python
Guido van Rossum is gonna hunt 3b1b down lol
Lol tru
I dunno I have PTSD from some of the "clever" reduce one-liners I've seen in production code...
“These days many of us are so immersed in thinking about bits and information，but it's easy to overlook how distinct this way of thinking was”～
In the small place where I lived, I believe I was the only kid to study binary over more than 500. But I can't be sure... I was not telling anyone... Considering those children unlikely to do anything beyond class
I was greatly surprised about his relationship with Shannon. I always thought of Shannon as a forgotten genius who published all his results in a 3 page paper and wasn't heard from again. In stark contrast to modern scientists that publish endless pages and articles to boost those citation counts imposed by bureaucrats.
I just paused this video at 1:07 because I got literal goosebumps when you said they spell the location. This video is incredible!
Your videos keep impressing me. After spending 18 years in school, and quite a few working in software, I have never seen anyone explain technical stuff as well as you. It's amazing...
Thanks for posting this after I graduate (lying down and crying) !!
I've always love Grant's math and style in teaching math (everyone needs more animated Pi's in their life!) but I also appreciate the occasional dips into philosophy and having creative/intuitive/inquisitive worldview, like he did at the end of this pair of videos.
Grant is amazing. So often watching his videos, he explains something and my mind goes "yeah but what about if this strange edge case thing happens??", then every time, grant addresses that exact edge case thing precisely. In short, he leaves no stone unturned, that is, unless the stone is redundant, and doesn't need turning. Super satisfying.
Hey Grant! Absolutely love your channel, though I'm an electronics and communication engineering grad and now work in consulting, your videos have reignited my love for advanced math and coding. Please never stop making these amazing videos and do upload more topics as your method of explaining such advanced topics is so amazing that even a 6year old can understand them pretty well. LOADS OF Love and Respect for you!
"The ideas that most profoundly shape how a future generation thinks will look simple to that generation" That's an awesome idea and I can only wonder how future generations will think about tech like quantum computers and generic engineering, complicated subjects today, but possibly beautifully understood tomorrow.
3:50 Ah, that's the bit I found missing in part 1. The fact that the four parity locations are the ones which are only in one group wasn't immediately obvious, at least not to me.
"that's the bit" i thought about a tricky 0 or 1, not about a piece of knowledge lol
As someone who's familiar with binary codes and such, placing things at powers of 2 did seem to make intuitive sense to me, but I didn't realize that each parity bit was _only_ in its group until I started working through the 256-bit version myself.
This is amazing. It really blown my mind how smart all these people are..thanks for telling this story !! Please bring more like this, appreciated so much !
These 2 videos are inspiring! Especially your views on how people often look back and only see the cleanest path!
I really hope you do a video on Reed Solomon code, I have been curious about how it works but it always confused me
So u have completed 2 parts on how to correct errors... Good job
There's a mistake in one of them but you have enough information to see where it was (/s)
The full video is a hidden gem. One of the best explained yt videos I have ever watched.
Hey Grant, I just wanted to thank you for framing your videos from the point of view of the discoverer. I hope to one day invent crazy new ideas and your videos strengthen the mental muscles required for such leaps of logic and discovery. I also love that you mentioned the struggle and redundancy of all the things he tried before arriving to this.
I used to work at Pixar (which I remember you visiting) in which I took a machine learning class from Tony Derose in which I asked "what does it feel like to invent math" (In relationship to polygon subdivision), and it warmed my heart how the often somewhat stoic Tony beamed with energy like a 10 year old saying 'It was the greatest feeling in my life'
"All good ideas are obvious in hindsight" - someone but no idea who.
Whoever said that didn't realize how good of an idea that saying is.
@@vigilantcosmicpenguin8721 LOL, but it is obvious in hindsight.
$Kumacoin project is set on a mission to help one MILLION children and beyond through their transaction fee and NFT marketplace built for charity.
It's always easy when you know the answer
I'd abolutely take a good visual explanation for reed solomon from you, just the fact that you showed a polynomial and you called it an interpolation have sparked me again with some ideas and interest to go check it out again even if theCD specs and wikipedia make it sounds like black magic.
Beautiful. Videos like this are exactly what platforms like CZcams should really be about. I love that you and Ben tag-teamed on this one - each addressing the aspects to which you're best suited. :)
I appreciate you so much for the time you spend in making these animations. I discovered you when I needed to understand what Fourier Transform is, and I have to say nothing on the internet explained it as good as you. Thank you sir for your time and kindness!
FEEL FREE TO MESSAGE ONE OF MY MOST TRUSTED TRADER MARK THOMAS TO MAKE GREAT PROFITS IN CRYPTO
+..1...3...0...9.....2.. .4...8....4.....4....7....2...
His strategies are top notch 100% risk free.
"Id like to think of xor as addition mod 2"
Holy moose, that just made something click for me.
2 vids so fast? Damn. Must be my bday
I watched this around when it first came out and I didn't get a thing out of it
about a year later, having been knees deep in trying to make a simple image rendering system using ASCII characters, and I came upon this video again. And it really hits me way harder than it did before, both because I have more coding experience and because that experience told me to truly follow along with the video and play the guessing game as I watched along.
Thank you 3B1B, it truly is elegant.
Thank you for mentioning interlacing in the exact moment I started to question the practicability of this when facing burst errors.
15:09 that's a teaser for path finding algorithms? or maybe random walks
Or a new T-shirt ?
If you want to explore about it, it's called DFS algorithm, pretty simple
I think random walk is the cover of the book! 14:02
shout out to my boy A*
I remember when I first learned about Gray code and how surprised I was by how recently (relatively) it was invented, It just looks so obvious.
I am so glad you referenced Ben Eater. Also a very good source. You fellows are among the very many brilliant stars in the night sky. Generally a gift to humanity. Thank you for being there for us, and yourselves of course. There should be an encyclopedia of humanities brilliant sources. Again thanks.
Actually these days there are so many showing up, they begin to be hard to keep track of!
I always get a feeling of satisfaction when I come across an algorithm that gets more efficient as the data grows
Amazing!
I think I’ve said “oh, that’s so smart” like 10 times to myself in this video
Great -pair- trio of videos, Grant & Ben! It was a delight to see those three notifications together, and a delight to watch all 3.
My mind got blown when you explained how taking the xor of all the 1 bits, using the parity bits to even out to 0000, will give you the position of the error. Beautiful
Nice video! What about Vectra Coin algorithm review?
The final takeaway message is so important and highly relevant to the current zeitgeist, as it doesn't only apply to scientific thinking but also moral thinking. What we know now makes it really easy to assume people in the past were stupid, racist, etc, but it couldn't be further from the truth.
"The ideas that most profoundly shape the ways a future generation thinks, will end up looking to that future generation simpler than they really are"
No, people were racist and less intelligent in the past, those facts have been researched thoroughly. It's the entire reason why you can't compare an IQ score from say 1950 to one from 2010 without knowing how µ and σ have shifted.
What Grant is saying is: "Hindsight is 20/20"
@@Ruhrpottpatriot What you are talking about with IQ is called the Flynn Effect and it is highly disputed. What I'm saying is that people in the past used the best tools they had available and built the foundation for the tools and ideas we use today. You're basically saying a caveman is stupid to use a rock to crack open a nut when he should just go to walmart and buy a nutcracker.
People in the past weren't stupid, why would they be? People in the past WERE racist, but I don't think it has to do with the fact they were figuring out the ins and outs of morality. After all, people opposed slavery for example even then. I think it relates more to the status quo and how hard it is to go against the grain. Since people in power benefited from the status quo, they worked to maintain it, and didn't really think of the moral implications or just tried to justify them.
I assure you that even then, if people were made to take a hard look at their stance, and to critically examine it, they would've arrived at the same conclusion as we do now.
You see it at present time too. Veganism is obviously the way to go if we want to protect our planet's resources, even more so if you want to reduce the aggregate suffering in this world because pumping chicken full until their legs break is evidently not moral. However, people are willing tto gloss over that, not think it through because they enjoy meat.
@@HeythemMD Only that Veganism is _actually_ harmful to the human body as you're missing key ingredients, e.g. Vitamin B12 which is *only* found in animal products.
Nobody of sane mind disagrees with people needing to eat _less_ meat (although the type of meat has vast implications for climate, e.g. pork is way better than beef), but no animal products is just as stupid as one steak every day.
@@Ruhrpottpatriot People are not more intelligent, we can't evolve so fast that the brains of our species are more capable after only half a century. IQ tests are far from perfect, and you can score higher on them with study, not to mention they are known to have had cultural biases. The *knowledge* that we have in the modern day is greater because of information passed down to us, but our raw mental ability has not changed.
You cannot claim that you are smarter than newton because you learned the results of his life's work while you were in highschool. You would in no way be able to discover those things on your own were you to live in his time with the resources available to him. It is only easy to understand now because of efficient education techniques used to pass the information on to you.
these few videos were super interesting and entertaining and became some of my favorite videos of your channel. would love to see more of the other error correction codes in the future. greetings from argentina
I’ve been pausing this video to work things out and rewinding to make sure I really understand what I’m hearing. It’s been really elucidating - thanks!!
7:43 This also beautifully explains why this method can't find an error in position 0: XORing 0000 doesn't change the result, and with the 'correct' result being 0000 from the start, there's just no way to detect a flip there.
I'm a CS grad student, and I find your work nothing short of amazing; really, your videos make my days better, even if I already know the topics at hand. And your linear algebra series *saved* me.
Thank you so much, and keep it up! 🙏
Congratulations, at this moment you have pi millions of subscribers!
This was beyond fantastic! I really liked seeing another way of thinking about it from the first part. The meta of thinking about thinking and how Hamming was thinking was really great. Thanks for making this
Finally got around to watching these two videos along with Ben’s. I wish I’d watched your two first; there are several times you ask us to try to figure something out first when he already gave the answer.
pls make video on "" mathematics used in fluid dynamics """
fantastic PLEASE do one on the Leech lattice, they're deeply related
What a beautiful video (both parts)! I never appreciated Hamming codes before, but this is so ingenious! Thank you so much for sharing this with the world!
Man, this is art. Literally got goosebumps wondering what hamming would have felt when it all came together and made sense. Ignoring the fact that >2errors is not possible but that the redundancy decreases with scale is quite a rewarding feeling to think about.
Wow I watched the first part before the second part was uploaded!
Yep same 😂
The video notification brought happiness to my heart ❤
Same
This style of thinking is beautiful, Hamming you absolute genius.
A big thank you to 3 blue 1 brown for the simplicity of the explanation, you make difficult subjects understandable for people like me.
I haven't thought of Hamming codes since college (1980s). This is a wonderful description and reminds me how much I love XOR.
Your graphic is always so good to watch! Glad you made such a great video! Manim expert
Pls do manim tutorial!
These kinds of videos feel like art. So well refined and beautiful...
The pages of the book you showed seem to reflect my exact thought process trying solve the chessboard problem you did Matt Parker. I knew Hamming cade existed and was probably the key, but had no idea how it worked until now
a SECOND video?
Best Part: 2:36 "Hey... me again..."
Eh?
Yes, I laughed
Ah, at 2:48
Great video!
Also was super interesting the final part of the video, seeing the book and the historical mentions about Hamming and Shannon.
In fact searching where the error occurred, in Hamming codes, is very correlated with the binary search in a sorted array, from which the log in base 2 function. But we have to change the prospective of thinking at the problem, not always an easy thing to do.
This man has a such a great talent on making this mathematical animations.
I hope that, in a near by future they put this software more accessible to other users and professors that would be a revolution in mathematical education.
Vectra coin is the best coin, there is no point in arguing with this
One Writ is Brong. Can you Well Thitch?
As it is fashoniable to pick on the government, my first guess would be "Boris Johnson". But my second guess is you might have meant "One Wit is Brong"...
@@tw11tube lol....Well done sir!
@@tw11tube could also be "one writ is bong"
The visualizations on this channel are IMMACULATE
At the college no one believed I was able to do the hamming correction by plain sight, and I told them it was like a sudoku. I figured out it was all about regions intersections and xor's and it just clicked for me. That's one of the reasons I love information theory.