Hamming codes part 2, the elegance of it all

Video Statistics and Information

Video
Captions Word Cloud
Reddit Comments

Ben Eater also released a video about Error Correction & Hamming Codes.

YouTube-Link

👍︎︎ 27 👤︎︎ u/madpata 📅︎︎ Sep 05 2020 đź—«︎ replies

Very fun video. Here's my attempt at the same code in Haskell

import Data.Bits (xor)
import Data.List (elemIndices)

hamming = foldr xor 0 . elemIndices 0
👍︎︎ 11 👤︎︎ u/mode_2 📅︎︎ Sep 05 2020 đź—«︎ replies

Very elegant indeed. Thanks for sharing.

👍︎︎ 2 👤︎︎ u/rinconrex 📅︎︎ Sep 05 2020 đź—«︎ replies
Captions
I’m assuming that everybody here is coming in from part 1. We were talking about Hamming codes, a way to create a block of data where most of the bits carry a meaningful message, while a few others act as a kind of redundancy in such a way that if any bit gets flipped, either a message bit or a redundancy bit, anything in this block, a receiver is going to be able to identify that there was an error and how to fix it. The basic idea presented there was how to use multiple parity checks to binary search your way down to the error. Now, in that video the goal was to make Hamming codes feel as hands-on and re-discoverable as possible, but as you start to think about actually implementing this, either in software or hardware, that framing may actually undersell how elegant these codes really are. You might think that you need to write an algorithm that keeps track of all possible error locations and cuts that group in half with each check, but it’s actually way, way simpler than that. If you read out the answers to the four parity checks from we did in the last video all as 1’s and 0’s, instead of as yesses and nos, it literally spells out the position of the error in binary For example, the number 7 in binary looks like 0111, essentially saying it’s 4+2+1. And notice where the position 7 sits: It does affect the first of our parity groups, and the second, and the third, but not the last. So reading the results of those four checks from bottom to top indeed does spell out the position of the error. There’s nothing special about the example 7, this works in general, and this makes the logic for implementing the whole scheme in hardware shockingly simple. Now if you want to see why this magic happens, take these 16 index labels for our positions but instead of writing them in base 10, let's write them all in binary running from 0000 up to 1111. As we put these binary labels back into their boxes, let me emphasize that they are distinct from the data that's actually being sent; they’re nothing more than a conceptual label to help you and me understand where the four parity groups came from. The elegance of having everything that we’re looking at being described in binary is maybe undercut by the confusion of having everything we’re looking at being described in binary. It’s worth it, though. Focus your attention just on that last bit of all of these labels, and then highlight the positions where that final bit is a 1. What we get is the first of our four parity groups, which means you can interpret that check as asking: “hey, if there’s an error, is the final bit in the position of that error a 1?”. Similarly, if you focus on the second to last bit and highlight all the positions where that's a 1, you get the second parity group from our scheme. In other words, that second check is asking: “Hey, me again, if there’s an error, is the second to last bit in its position a 1?”. And so on, the third parity check covers every position whose third to last bit is turned on... and the last one covers the last 8 positions, those ones whose highest order bit is a 1. Everything we did earlier is the same as answering these four questions, which in turn is the same as spelling out a position in binary. I hope this makes two things clearer: The first is how to systematically generalize to block sizes that are bigger powers of 2. If it takes more bits to describe each position, like 6 bits to describe 64 spots, then each of those bits gives you one of the parity groups that we need to check. Those of you who watched the chessboard puzzle I did with Matt Parker might find all this exceedingly familiar. It’s the same core logic, but solving a different problem, and applied to a 64 square chessboard. The second thing I hope this makes clear is why our parity bits are sitting in positions that are powers of two, for example, 1, 2, 4, and 8. These are the positions whose binary representation has just a single bit turned on. What that means, is that each of those parity bits sits inside one and only one of the four parity groups. You can also see this in larger examples, where no matter how big you get, each parity bit conveniently touches only one of the groups. Once you understand that these parity checks that we’ve focused so much of our time on are nothing more than a clever way to spell out the position of an error in binary, well then we can draw a connection with a different way to think about Hamming codes, one that is arguably a lot simpler and more elegant, and which can basically be written down with a single line of code. It’s based on the xor function. Xor, for those of you who don’t know, stands for “exclusive or”; when you take the xor of two bits, it's going to return a 1 if either one of those bits is turned on, but not if both are turned on or if both are turned off. Phrased differently, it’s the parity of these two bits. As a math person, I prefer to think about it as addition mod 2. We also commonly talk about the xor of two different bit strings, which basically does this component-by-component; it’s like addition but where you never carry. Again, the more mathematically inclined might prefer to think of this as adding two vectors and reducing mod 2. If you open up some python right now and you apply the carat operation between two integers, this is what it’s doing but to the bit representations of those numbers under the hood. The key point for you and me is that taking the xor of many different bit strings is effectively a way to compute the parities of a bunch of separate groups, like so with the columns, all in one fell swoop. This gives us a rather snazzy way to think about the multiple parity checks from our Hamming code algorithm as all being packaged together into one single operation. Though at first glance it does look very different. Specifically, write down the 16 positions in binary, like we had before, and now highlight only the positions where the message bit is turned on to a 1. And then collect these positions into one big column and take the xor. You can probably guess that the four bits sitting at the bottom, as a result, are the same as the four parity checks that we’ve come to know and love, but take a moment to think about why, exactly. This last column, for example, is counting all of the positions whose last bit is a 1, but we're already limited only to the highlighted positions, so it’s effectively counting how many highlighted positions came from the first parity group. Does that make sense? Likewise, the next column counts how many positions are in the second parity group, the positions whose second to last bit is a 1, and which are also highlighted. And so on, it’s really a small shift in perspective on the same thing that we’ve been doing. And so you know where it goes from here, the sender is responsible for toggling some of the special parity bits to make sure this sum works out to be 0000. Now once we have it like this, this gives a really nice way to think about why these four resulting bits at the bottom directly spell out the position of an error. Let's say some bit in this block gets toggled from a 0 to a 1, what that means is that the position of that bit is now going to be included in the total xor, which changes the sum from being 0 to instead being this newly included value, the position of the error. Slightly less obviously, the same is true if there’s an error that changes a 1 to a 0. You see, if you add bit string together twice, it’s the same as not having it there at all, basically because in this world 1+1=0. So adding a copy of this position to the total sum has the same effect as removing it, and that effect again is that the total result at the bottom here spells out the position of the error. To illustrate how elegant this is, let me show that one line of python code I referenced before, which will capture almost all of the logic on the receiver’s end. We'll start by creating a random array of 16 1’s and 0’s to simulate the data block, and I'll go ahead and give it the name "bits". But of course, in practice, this would be something that we’re receiving from a sender. And instead of being random, it would be carrying 11 data bits together with 5 parity bits. If I call the function “enumerate(bits)”, what it does is pair together each of those bits with a corresponding index, in this case from 0 up to 15. So if we then create a list that loops over all of these pairs, pairs that look like (i, bit), and then we pull out just the i value, just the index....well it’s not that exciting, we just get back those indices 0 through 15. But if we add on the condition to only do this “if bit”, meaning if that bit is a 1 and not a 0, then it pulls out only the positions where the corresponding bit is turned on. In this case it looks like those positions are at 0, 4, 6, 9, etc. Remember, we want to collect together all of those positions, the positions of the bits that are turned on, and then xor them together. To do this in python, let me first import a couple helpful functions...that way we can call “reduce” on this list and use the xor function to reduce it. This basically eats its way through the list, taking xors along the way. If you prefer, you can explicitly write out that xor function without importing from anywhere. So at the moment it looks like if we do this on our random block of 16 bits, it returns "9", which has the binary representation 1001. We won’t do it here, but you could write a function where the sender uses that binary representation to set the four parity bits as needed, ultimately getting this block to a state where running this line of code on the full list of bits returns a 0. This would be considered a well-prepared block. Now what’s cool is that if we toggle any one of the bits in this list, simulating a random error from noise, then if you run this same line of code what it does is it prints out that error. Isn’t that neat? You could get this block from out of the blue, run this single line on it, and what it'll do is automatically spit out the position of an error, or a 0 if there wasn't any. And there’s nothing special about the size 16 here, this same line of code would work if you had a list of, say, 256 bits. Needless to say, there is more code to write here, like doing the meta-parity check to detect two-bit errors, but the idea is that almost all of the core logic from our scheme comes down to a single xor reduction. Now, depending on your comfort with binary, and xors, and software in general, you may either find this perspective a little bit confusing or so much more elegant and simple that you’re wondering why we didn’t just start with it from the get-go. Loosely speaking, the multiple parity check perspective is easier to think about when implementing Hamming codes in hardware, and the xor perspective is easiest to think about when doing it in software, from kind of a higher level. The first one is easiest to actually carry out by hand, and I think it does a better job instilling the core intuition behind underlying all of this, which is that the information required to locate a single error is related to the log of the size of the block, or in other words, it grows one bit at a time as the block size doubles. The relevant fact here is that that information directly corresponds to how much redundancy we need. That’s really what runs against most people knee jerk reactions when they first think about making a message resilient to errors, where usually copying the whole message is the first instinct that comes to mind. And then, by the way, there’s this whole other way that you sometimes see Hamming codes presented where you multiply the message by one big matrix, it's kind of nice because it relates it to the broader family of "linear codes", but I think that gives almost no intuition for where it comes from or how it scales. And speaking of scaling, you might notice that the efficiency of this scheme only gets better as we increase the block size. For example, we saw that with 256 bits, you're using only 3% of that space for redundancy. And it just keeps getting better from there. As the number of parity bits grows one-by-one, the block size keeps doubling. And if you take that to an extreme, you could have a block with, say, a million bits, where you would quite literally be playing 20 questions with your parity checks, and it uses only 21 parity bits. And if you step back to think about looking at a million bits and locating a single error, that genuinely feels crazy. The problem, of course, is that with a larger block, the probability of seeing more than one or two bit errors goes up, and Hamming codes do not handle anything beyond that. So in practice, what you’d want is to find the right size so that the probability of too many bit flips isn’t too high. Also, in practice errors tend to come in little bursts, which would totally ruin a single block, so one common tactic to help spread out a burst of errors over across many different blocks is to interlace those blocks, like this, before they're sent out or stored. Then again, a lot of this is rendered completely moot by more modern codes, like the much more commonly used Reed-Solomon algorithm, which handles burst errors particularly well, and it can be tuned to be resilient to a larger number of errors per block. But that’s a topic for another time. In his book “The Art of doing Science and Engineering”, Hamming is wonderfully candid about just how meandering his discovery of this code was. He first tried all sorts of different schemes involving organizing the bits into parts of a higher dimensional lattice and strange things like this. The idea that it might be possible to get parity checks to conspire in a way that spells out the position of the error only came to Hamming when he stepped back after a bunch of other analysis and asked: “okay, what is the most efficient I could conceivably be about this?” He was also candid about how important it was parity checks were already on his mind, which would have been way less common back in the 1940s than it is today. There are like half a dozen times throughout this book that he references the Louis Pasteur quote “luck favors a prepared mind." Clever ideas often look deceptively simple in hindsight, which makes them easy to underappreciate. Right now my honest hope is that Hamming codes, or at least the possibility of such codes, feels almost obvious to you. But you shouldn’t fool yourself into thinking that they actually are obvious, because they definitely aren’t. Part of the reason that clever ideas look deceptively easy is that we only ever see the final result, cleaning up what was messy, never mentioning all the wrong turns, underselling just how vast the space of explorable possibilities is at the start of the problem-solving process, all of that. But this is true in general, I think for some special inventions, I think there’s a second, deeper reason that we underappreciate them. Thinking of information in terms of bits had only really been coalesced into a full theory by 1948, with Claude Shannon’s seminal paper on information theory. This was essentially concurrent with when Hamming developed his algorithm. This was the same foundational paper that showed, in a certain sense, that efficient error correction is always possible, no matter how high the probability of bit flips, at least in theory. Shannon and Hamming, by the way, shared an office in Bell Labs, despite working on very different things, which hardly seems coincidental here. Fast forward several decades, and these days many of us are so immersed in thinking about bits and information that it's easy to overlook just how distinct this way of thinking was. Ironically the ideas that most profoundly shape the ways that a future generation thinks will end up looking, to that future generation, well, simpler than they really are.
Info
Channel: 3Blue1Brown
Views: 522,627
Rating: 4.9818707 out of 5
Keywords: Mathematics, three blue one brown, 3 blue 1 brown, 3b1b, 3brown1blue, 3 brown 1 blue, three brown one blue
Id: b3NxrZOu_CE
Channel Id: undefined
Length: 16min 50sec (1010 seconds)
Published: Fri Sep 04 2020
Related Videos
Note
Please note that this website is currently a work in progress! Lots of interesting data and statistics to come.