title

But what are Hamming codes? The origin of error correction

description

A discovery-oriented introduction to error correction codes.
Part 2: https://youtu.be/b3NxrZOu_CE
Ben Eater:'s take: https://youtu.be/h0jloehRKas
Help fund future projects: https://www.patreon.com/3blue1brown
An equally valuable form of support is to simply share some of the videos.
Special 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-code/
------------------
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

detail

{'title': 'But what are Hamming codes? The origin of error correction', 'heatmap': [{'end': 952.654, 'start': 939.327, 'weight': 0.723}, {'end': 1121.692, 'start': 1100.023, 'weight': 1}], 'summary': "Explores error correction in data storage, showcasing methods using 256-bit blocks with 9 bits of redundancy and the hamming code's contrast to modern codes like reed-solomon algorithm. it discusses storing 12 bits with 4 bits for redundancy and explains the concept of parity checks. additionally, it explains the concept of hamming codes, their efficiency in detecting and correcting errors, and implementation in 16-bit blocks, while covering the process of error correction.", 'chapters': [{'end': 255.178, 'segs': [{'end': 33.336, 'src': 'embed', 'start': 4.025, 'weight': 3, 'content': [{'end': 10.067, 'text': "Have you ever wondered how it's possible to scratch a CD or a DVD and still have it play back, whatever it's storing?", 'start': 4.025, 'duration': 6.042}, {'end': 13.789, 'text': 'The scratch really does affect the ones and zeros on the disc.', 'start': 10.828, 'duration': 2.961}, {'end': 16.99, 'text': 'so it reads off different data from what was stored.', 'start': 13.789, 'duration': 3.201}, {'end': 25.993, 'text': "but unless it's really scratched up, the bits that it reads off are decoded into precisely the same file that was encoded onto it a bit-for-bit copy,", 'start': 16.99, 'duration': 9.003}, {'end': 27.354, 'text': 'despite all of those errors.', 'start': 25.993, 'duration': 1.361}, {'end': 33.336, 'text': 'There is a whole pile of mathematical cleverness that allows us to store data and, just as importantly,', 'start': 28.254, 'duration': 5.082}], 'summary': 'Scratches may affect cd/dvd data, but clever math ensures playback accuracy.', 'duration': 29.311, 'max_score': 4.025, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/X8jsijhllIA/pics/X8jsijhllIA4025.jpg'}, {'end': 141.708, 'src': 'embed', 'start': 84.658, 'weight': 0, 'content': [{'end': 90.584, 'text': "For example, using the method that you'll learn about this video, you could store your data in 256-bit blocks,", 'start': 84.658, 'duration': 5.926}, {'end': 100.213, 'text': 'where each block uses 9 bits to act as a kind of redundancy and the other 247 bits are free to carry whatever meaningful message or data that you want.', 'start': 90.584, 'duration': 9.629}, {'end': 106.478, 'text': 'And it will still be the case that if any bit gets flipped here, just by looking at this block and nothing more,', 'start': 100.894, 'duration': 5.584}, {'end': 112.482, 'text': 'a machine will be able to identify that there was an error, and precisely where it was, so that it knows how to correct it.', 'start': 106.478, 'duration': 6.004}, {'end': 114.644, 'text': 'And honestly, that feels like magic.', 'start': 113.023, 'duration': 1.621}, {'end': 121.469, 'text': 'And for this particular scheme, if two bits get flipped, the machine will at least be able to detect that there were two errors,', 'start': 115.444, 'duration': 6.025}, {'end': 122.75, 'text': "though it won't know how to fix them.", 'start': 121.469, 'duration': 1.281}, {'end': 126.813, 'text': "We'll talk a little bit later about how this scales for blocks with different sizes.", 'start': 123.47, 'duration': 3.343}, {'end': 132.839, 'text': 'Methods that let you correct errors like this are known, reasonably enough, as error correction codes.', 'start': 127.814, 'duration': 5.025}, {'end': 135.502, 'text': 'For the better part of the last century,', 'start': 133.68, 'duration': 1.822}, {'end': 141.708, 'text': 'this field has been a really rich source of surprisingly deep math that gets incorporated into devices we use every day.', 'start': 135.502, 'duration': 6.206}], 'summary': 'Using error correction codes, data can be stored in 256-bit blocks with 9 bits for redundancy, enabling error detection and correction.', 'duration': 57.05, 'max_score': 84.658, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/X8jsijhllIA/pics/X8jsijhllIA84658.jpg'}, {'end': 206.774, 'src': 'embed', 'start': 179.181, 'weight': 5, 'content': [{'end': 184.684, 'text': 'Now you should know, Hamming codes are not as widely used as more modern codes like the Reed-Solomon algorithm.', 'start': 179.181, 'duration': 5.503}, {'end': 192.907, 'text': 'but there is a certain magic to the contrast between just how impossible this task feels at the start and how utterly reasonable it seems once you learn about Hamming.', 'start': 184.684, 'duration': 8.223}, {'end': 202.152, 'text': 'The basic principle of error correction is that in a vast space of all possible messages, only some subset are going to be considered valid messages.', 'start': 194.168, 'duration': 7.984}, {'end': 206.774, 'text': 'As an analogy, think about correctly spelled words versus incorrectly spelled words.', 'start': 202.772, 'duration': 4.002}], 'summary': 'Hamming codes are less used than reed-solomon algorithm, but offer a contrasting magic in error correction principle.', 'duration': 27.593, 'max_score': 179.181, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/X8jsijhllIA/pics/X8jsijhllIA179181.jpg'}, {'end': 265.618, 'src': 'embed', 'start': 237.768, 'weight': 2, 'content': [{'end': 242.391, 'text': 'And the programs he kept putting through it kept failing, because every now and then a bit would get misread.', 'start': 237.768, 'duration': 4.623}, {'end': 248.334, 'text': "Frustration being the crucible of invention, he got so fed up that he invented the world's first error correction code.", 'start': 243.071, 'duration': 5.263}, {'end': 251.676, 'text': 'There are many different ways to frame Hamming codes,', 'start': 249.154, 'duration': 2.522}, {'end': 255.178, 'text': "but as a first pass we're going to go through it the way that Hamming himself thought about them.", 'start': 251.676, 'duration': 3.502}, {'end': 259.129, 'text': "Let's use an example that's simple, but not too simple.", 'start': 256.464, 'duration': 2.665}, {'end': 260.851, 'text': 'A block of 16 bits.', 'start': 259.589, 'duration': 1.262}, {'end': 265.618, 'text': "We'll number the positions of these bits from 0 up to 15.", 'start': 261.772, 'duration': 3.846}], 'summary': "Frustrated by errors, hamming invented world's first error correction code.", 'duration': 27.85, 'max_score': 237.768, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/X8jsijhllIA/pics/X8jsijhllIA237768.jpg'}], 'start': 4.025, 'title': 'Error correction in data storage', 'summary': 'Explores error correction in data storage, showcasing a method using 256-bit blocks with 9 bits of redundancy, enabling correction of flipped bits. it also discusses the significance of error correction codes in everyday devices and introduces the hamming code with its contrast to modern codes like the reed-solomon algorithm, while recounting its invention by richard hamming in the 1940s.', 'chapters': [{'end': 106.478, 'start': 4.025, 'title': 'Error correction in data storage', 'summary': 'Explains how data is stored and transmitted resiliently to errors, leveraging mathematical cleverness and minimal space usage, as exemplified by a method using 256-bit blocks with 9 bits of redundancy, enabling correction of flipped bits.', 'duration': 102.453, 'highlights': ['The method discussed in the video uses 256-bit blocks with 9 bits of redundancy, allowing correction of flipped bits while minimizing space usage.', "Storing three copies of each bit would enable the machine to compare and take the best two out of three whenever there's a discrepancy, but this approach requires using two-thirds of the space for redundancy.", 'The scratch on a CD or DVD affects the ones and zeros on the disc, but despite errors, the data can still be decoded into the same file that was encoded onto it, showcasing the resilience to errors in data storage and retrieval.']}, {'end': 141.708, 'start': 106.478, 'title': 'Error correction codes: magic of machines', 'summary': 'Explains how machines can identify and correct errors, with the ability to detect two errors in a particular scheme, and discusses the significance of error correction codes in incorporating deep math into everyday devices.', 'duration': 35.23, 'highlights': ['Error correction codes enable machines to identify and correct errors, with the capability to detect two errors in a particular scheme.', 'The field of error correction codes has been a rich source of deep math that is incorporated into everyday devices.', 'Machines can precisely identify the location of errors and know how to correct them, akin to magic.', 'Methods for error correction codes have been developed over the last century, contributing to the advancement of error detection and correction in various devices.']}, {'end': 255.178, 'start': 142.915, 'title': 'Understanding hamming code', 'summary': "Introduces the hamming code, prompting viewers to predict the scheme, highlighting its implementation on breadboards, and emphasizing its contrast with modern codes like the reed-solomon algorithm, while recounting the frustration-driven invention of the world's first error correction code by richard hamming in the 1940s.", 'duration': 112.263, 'highlights': ["Richard Hamming's frustration with the failure of programs due to misreads led to the invention of the world's first error correction code, the Hamming Code.", 'Viewers are encouraged to predict the Hamming Code scheme and actively engage in understanding its implementation, fostering a thorough grasp of the concept.', 'The chapter contrasts the limited usage of Hamming codes with more modern codes like the Reed-Solomon algorithm, highlighting the magic in the transition from an impossible task to an understandable concept.', 'The chapter emphasizes the importance of error correction in categorizing valid messages and the cleverness required to efficiently develop concrete algorithms for this purpose.', "The chapter mentions Ben Eder's video demonstrating the implementation of Hamming codes on breadboards, emphasizing the satisfaction derived from this practical application."]}], 'duration': 251.153, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/X8jsijhllIA/pics/X8jsijhllIA4025.jpg', 'highlights': ['The method uses 256-bit blocks with 9 bits of redundancy for error correction.', 'Error correction codes enable machines to identify and correct errors.', "Richard Hamming invented the world's first error correction code, the Hamming Code.", 'The scratch on a CD or DVD affects the ones and zeros, but the data can still be decoded.', 'The field of error correction codes has been a rich source of deep math in everyday devices.', 'The chapter contrasts the limited usage of Hamming codes with modern codes like Reed-Solomon algorithm.']}, {'end': 727.427, 'segs': [{'end': 312.928, 'src': 'embed', 'start': 256.464, 'weight': 0, 'content': [{'end': 259.129, 'text': "Let's use an example that's simple, but not too simple.", 'start': 256.464, 'duration': 2.665}, {'end': 260.851, 'text': 'A block of 16 bits.', 'start': 259.589, 'duration': 1.262}, {'end': 265.618, 'text': "We'll number the positions of these bits from 0 up to 15.", 'start': 261.772, 'duration': 3.846}, {'end': 269.743, 'text': 'The actual data that we want to store is only going to make up 12 of these bits,', 'start': 265.618, 'duration': 4.125}, {'end': 273.068, 'text': 'while 4 of the positions are going to be reserved as a kind of redundancy.', 'start': 269.743, 'duration': 3.325}, {'end': 280.015, 'text': "The word redundant here doesn't simply mean copy, after all, those four bits don't give us enough room to blindly copy the data.", 'start': 273.854, 'duration': 6.161}, {'end': 287.397, 'text': "Instead, they'll need to be a much more nuanced and clever kind of redundancy, not adding any new information, but adding resilience.", 'start': 280.695, 'duration': 6.702}, {'end': 294.658, 'text': "You might expect these four special bits to come nicely packaged together, maybe at the end or something like that, but, as you'll see,", 'start': 288.637, 'duration': 6.021}, {'end': 299.499, 'text': "having them sit in positions which are powers of two allows for something that's really elegant by the end.", 'start': 294.658, 'duration': 4.841}, {'end': 303.44, 'text': 'It also might give you a little hint about how this scales for larger blocks.', 'start': 300.259, 'duration': 3.181}, {'end': 308.004, 'text': 'Also, technically it ends up being only 11 bits of data.', 'start': 305.222, 'duration': 2.782}, {'end': 312.928, 'text': "You'll find there's a mild nuance for what goes on at position zero, but don't worry about that for now.", 'start': 308.344, 'duration': 4.584}], 'summary': 'Using 16 bits to store 12 data bits with 4 reserved for redundancy, positioned at powers of 2, adding resilience.', 'duration': 56.464, 'max_score': 256.464, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/X8jsijhllIA/pics/X8jsijhllIA256464.jpg'}, {'end': 520.811, 'src': 'embed', 'start': 496.155, 'weight': 4, 'content': [{'end': 503.5, 'text': 'Parity checks on their own are pretty weak, but by distilling the idea of change across a full message down to a single bit,', 'start': 496.155, 'duration': 7.345}, {'end': 507.122, 'text': 'what they give us is a powerful building block for more sophisticated schemes.', 'start': 503.5, 'duration': 3.622}, {'end': 512.765, 'text': 'For example, as Hamming was searching for a way to identify where an error happened.', 'start': 507.923, 'duration': 4.842}, {'end': 514.107, 'text': 'not just that it happened.', 'start': 512.765, 'duration': 1.342}, {'end': 520.811, 'text': 'his key insight was that if you apply some parity checks, not to the full message but to certain carefully selected subsets,', 'start': 514.107, 'duration': 6.704}], 'summary': 'Parity checks offer a powerful building block for error identification and correction.', 'duration': 24.656, 'max_score': 496.155, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/X8jsijhllIA/pics/X8jsijhllIA496155.jpg'}, {'end': 696.847, 'src': 'embed', 'start': 666.366, 'weight': 6, 'content': [{'end': 670.81, 'text': 'Which is all a rather belabored way to say that two parity checks let us pin down the column.', 'start': 666.366, 'duration': 4.444}, {'end': 673.592, 'text': 'From here, you can probably guess what follows.', 'start': 671.511, 'duration': 2.081}, {'end': 676.094, 'text': 'We do basically the same thing, but for the rows.', 'start': 673.912, 'duration': 2.182}, {'end': 680.816, 'text': "There's going to be a parity check on the odd rows, using position 4 as a parity bit.", 'start': 676.494, 'duration': 4.322}, {'end': 686.519, 'text': 'So in this example, that group already has an even parity, so bit 4 would be set to a 0.', 'start': 681.456, 'duration': 5.063}, {'end': 691.482, 'text': "And finally, there's a parity check on the bottom two rows, using position 8 as a parity bit.", 'start': 686.519, 'duration': 4.963}, {'end': 696.847, 'text': 'In this case, it looks like the sender needs to turn that bit 8 on in order to give the group even parity.', 'start': 692.082, 'duration': 4.765}], 'summary': 'Using parity checks to determine and correct errors in data transmission.', 'duration': 30.481, 'max_score': 666.366, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/X8jsijhllIA/pics/X8jsijhllIA666366.jpg'}], 'start': 256.464, 'title': 'Data storage and error correction', 'summary': "Delves into storing 12 bits with 4 bits for redundancy, resulting in technically 11 bits, hinting at scalability. it also explains the concept of parity checks, their limitations in correcting errors, and their role in sophisticated error correction schemes, illustrated using hamming's approach to identifying error locations.", 'chapters': [{'end': 312.928, 'start': 256.464, 'title': 'Block of 16 bits redundancy', 'summary': 'Discusses the storage of 12 bits of data with 4 bits reserved for redundancy, positioned as powers of two to add resilience, resulting in technically only 11 bits of data and hinting at scalability for larger blocks.', 'duration': 56.464, 'highlights': ['The storage of 12 bits of data with 4 bits reserved for redundancy is discussed, indicating a 12:4 ratio of data to redundancy.', 'The positioning of the redundant bits as powers of two is mentioned to add resilience to the data.', 'It is noted that technically only 11 bits of data are stored due to the redundancy.', 'The hint about scalability for larger blocks is provided, suggesting the potential application of the discussed concept on a larger scale.']}, {'end': 727.427, 'start': 314.129, 'title': 'Error correction and parity checks', 'summary': "Explains the concept of parity checks, which can detect single-bit errors but not correct them, and how they serve as a powerful building block for more sophisticated error correction schemes, as demonstrated by hamming's approach to identifying error locations.", 'duration': 413.298, 'highlights': ['Parity checks serve as a powerful building block for more sophisticated error correction schemes', "Hamming's approach using parity checks to identify error locations", 'Explanation of how two parity checks allow pinning down the column and then the rows to identify error locations']}], 'duration': 470.963, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/X8jsijhllIA/pics/X8jsijhllIA256464.jpg', 'highlights': ['The storage of 12 bits of data with 4 bits reserved for redundancy is discussed, indicating a 12:4 ratio of data to redundancy.', 'The positioning of the redundant bits as powers of two is mentioned to add resilience to the data.', 'Technically only 11 bits of data are stored due to the redundancy.', 'The hint about scalability for larger blocks is provided, suggesting the potential application of the discussed concept on a larger scale.', 'Parity checks serve as a powerful building block for more sophisticated error correction schemes', "Hamming's approach using parity checks to identify error locations", 'Explanation of how two parity checks allow pinning down the column and then the rows to identify error locations']}, {'end': 1181.484, 'segs': [{'end': 809.209, 'src': 'embed', 'start': 782.32, 'weight': 0, 'content': [{'end': 790.686, 'text': 'If we used a block of size 256 bits, for example, in order to pin down a location, you need only eight yes or no questions to binary.', 'start': 782.32, 'duration': 8.366}, {'end': 792.687, 'text': 'search your way down to some specific spot.', 'start': 790.686, 'duration': 2.001}, {'end': 800.332, 'text': 'And remember, each question requires giving up only a single bit to set the appropriate parity check.', 'start': 795.629, 'duration': 4.703}, {'end': 809.209, 'text': "Some of you may already see it, but we'll talk later about the systematic way to find what these questions are in just a minute or two.", 'start': 803.228, 'duration': 5.981}], 'summary': 'Using 256-bit blocks, only 8 yes/no questions are needed to locate a specific spot.', 'duration': 26.889, 'max_score': 782.32, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/X8jsijhllIA/pics/X8jsijhllIA782320.jpg'}, {'end': 915.466, 'src': 'embed', 'start': 887.422, 'weight': 2, 'content': [{'end': 893.227, 'text': 'we work with a 15-bit block where 11 of the bits are free to carry a message and four of them are there for redundancy.', 'start': 887.422, 'duration': 5.805}, {'end': 898.712, 'text': 'And with that, we now have what people in the business would refer to as a 1511 Hamming code.', 'start': 893.968, 'duration': 4.744}, {'end': 901.995, 'text': 'That said, it is nice to have a block size.', 'start': 899.813, 'duration': 2.182}, {'end': 908.02, 'text': "that's a clean power of two, and there's a clever way that we can keep that zeroth bit around and get it to do a little extra work for us.", 'start': 901.995, 'duration': 6.025}, {'end': 915.466, 'text': "If we use it as a parity bit across the whole block, it lets us actually detect, even though we can't correct, two-bit errors.", 'start': 908.821, 'duration': 6.645}], 'summary': 'A 1511 hamming code uses a 15-bit block with 11 bits for message and 4 for redundancy, allowing detection of two-bit errors.', 'duration': 28.044, 'max_score': 887.422, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/X8jsijhllIA/pics/X8jsijhllIA887422.jpg'}, {'end': 965.144, 'src': 'heatmap', 'start': 939.327, 'weight': 1, 'content': [{'end': 945.09, 'text': "but the receiver would still see that there's been at least some error because of what's going on with those four usual parity checks.", 'start': 939.327, 'duration': 5.763}, {'end': 952.654, 'text': 'So if they notice an even parity overall, but something non-zero happening with the other checks, it tells them there were at least two errors.', 'start': 945.73, 'duration': 6.924}, {'end': 953.991, 'text': "Isn't that clever?", 'start': 953.43, 'duration': 0.561}, {'end': 961.139, 'text': "Even though we can't correct those two-bit errors just by putting that one little bothersome zeroth bit back to work, it, lets us detect them.", 'start': 954.271, 'duration': 6.868}, {'end': 963.262, 'text': 'This is pretty standard.', 'start': 962.22, 'duration': 1.042}, {'end': 965.144, 'text': "It's known as an extended Hamming code.", 'start': 963.402, 'duration': 1.742}], 'summary': 'Extended hamming code detects at least two errors, cleverly using parity checks.', 'duration': 34.541, 'max_score': 939.327, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/X8jsijhllIA/pics/X8jsijhllIA939327.jpg'}, {'end': 1018.707, 'src': 'embed', 'start': 985.051, 'weight': 3, 'content': [{'end': 991.835, 'text': "To set up a message, whether that's a literal message that you're translating over space or some data that you want to store over time.", 'start': 985.051, 'duration': 6.784}, {'end': 994.557, 'text': 'the first step is to divide it up into 11-bit chunks.', 'start': 991.835, 'duration': 2.722}, {'end': 999.68, 'text': 'Each chunk is going to get packaged into an error-resistant 16-bit block.', 'start': 995.618, 'duration': 4.062}, {'end': 1003.002, 'text': "So let's take this one as an example and actually work it out.", 'start': 1000.281, 'duration': 2.721}, {'end': 1004.804, 'text': 'Go ahead, actually do it.', 'start': 1003.683, 'duration': 1.121}, {'end': 1006.805, 'text': 'Pause and try putting together this block.', 'start': 1005.104, 'duration': 1.701}, {'end': 1018.707, 'text': 'Okay, you ready? Remember, position 0 along with the other powers of 2 are reserved for error correction duty.', 'start': 1013.041, 'duration': 5.666}], 'summary': 'Data is divided into 11-bit chunks and packaged into 16-bit blocks for error resistance.', 'duration': 33.656, 'max_score': 985.051, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/X8jsijhllIA/pics/X8jsijhllIA985051.jpg'}, {'end': 1131.564, 'src': 'heatmap', 'start': 1100.023, 'weight': 1, 'content': [{'end': 1104.345, 'text': "Okay, so U is the receiver, now check the first parity group, and you can see that it's even.", 'start': 1100.023, 'duration': 4.322}, {'end': 1107.826, 'text': 'So any error that exists would have to be in an even column.', 'start': 1104.705, 'duration': 3.121}, {'end': 1116.97, 'text': "The next check gives us an odd number, telling us both that there's at least one error, and narrowing us down into this specific column.", 'start': 1109.747, 'duration': 7.223}, {'end': 1121.692, 'text': 'The third check is even, chopping down the possibilities even further.', 'start': 1118.671, 'duration': 3.021}, {'end': 1131.564, 'text': "And the last parity check is odd, telling us there's an error somewhere in the bottom, which by now we can see must be in position number 10.", 'start': 1122.792, 'duration': 8.772}], 'summary': 'Using parity checks, identified error in position 10.', 'duration': 31.541, 'max_score': 1100.023, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/X8jsijhllIA/pics/X8jsijhllIA1100023.jpg'}, {'end': 1181.484, 'src': 'embed', 'start': 1168.314, 'weight': 4, 'content': [{'end': 1171.596, 'text': 'how simple it is to get a machine to point to the position of an error,', 'start': 1168.314, 'duration': 3.282}, {'end': 1178.702, 'text': 'how to systematically scale it and how we can frame all of this as one single operation rather than multiple separate parity checks.', 'start': 1171.596, 'duration': 7.106}, {'end': 1181.484, 'text': 'To see what I mean, come join me in part two.', 'start': 1179.522, 'duration': 1.962}], 'summary': 'Learn how to efficiently locate errors and streamline operations in part two.', 'duration': 13.17, 'max_score': 1168.314, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/X8jsijhllIA/pics/X8jsijhllIA1168314.jpg'}], 'start': 728.567, 'title': 'Hamming codes and data error correction', 'summary': "Explains the concept of hamming codes, their efficiency in detecting and correcting errors, implementation in 16-bit blocks, and extended hamming code's capability to detect two-bit errors. it also covers the process of dividing a message into 11-bit chunks, packaging them into error-resistant 16-bit blocks, and demonstrating the error correction process.", 'chapters': [{'end': 984.115, 'start': 728.567, 'title': 'Understanding hamming codes', 'summary': "Explains the concept of hamming codes, highlighting their efficiency in detecting and correcting errors, with examples of how they can be implemented in 16-bit blocks, as well as the extended hamming code's capability to detect two-bit errors.", 'duration': 255.548, 'highlights': ['Hamming codes efficiently pinpoint specific locations in a block by using a minimal number of yes or no questions, with only eight such questions needed to locate a specific spot in a 256-bit block.', 'The 1511 Hamming code is developed by working with a 15-bit block, with 11 bits free for carrying a message and four bits serving as redundancy, achieved by omitting the zeroth bit and effectively detecting, but not correcting, two-bit errors.', 'The extended Hamming code detects two-bit errors by using the zeroth bit as a parity bit across the entire block, allowing the identification of such errors even though they cannot be corrected.']}, {'end': 1181.484, 'start': 985.051, 'title': 'Data error correction', 'summary': 'Explains the process of dividing a message into 11-bit chunks and packaging them into error-resistant 16-bit blocks, demonstrating the error correction process and highlighting the efficiency and elegance of the algorithm.', 'duration': 196.433, 'highlights': ['The process of dividing a message into 11-bit chunks and packaging them into error-resistant 16-bit blocks is explained.', 'The error correction process is demonstrated, showing how errors are identified and corrected using parity checks.', 'The efficiency and elegance of the error correction algorithm are highlighted, emphasizing its simplicity and systematic scalability.']}], 'duration': 452.917, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/X8jsijhllIA/pics/X8jsijhllIA728567.jpg', 'highlights': ['Hamming codes efficiently pinpoint specific locations in a block with minimal yes or no questions, requiring only eight questions for a 256-bit block.', 'The extended Hamming code detects two-bit errors using the zeroth bit as a parity bit across the entire block, enabling the identification of uncorrectable errors.', 'The 1511 Hamming code utilizes 11 bits for carrying a message and four bits for redundancy, effectively detecting but not correcting two-bit errors.', 'The process of dividing a message into 11-bit chunks and packaging them into error-resistant 16-bit blocks is explained.', 'The efficiency and elegance of the error correction algorithm are highlighted, emphasizing its simplicity and systematic scalability.', 'The error correction process is demonstrated, illustrating how errors are identified and corrected using parity checks.']}], 'highlights': ['The method uses 256-bit blocks with 9 bits of redundancy for error correction.', 'Hamming codes efficiently pinpoint specific locations in a block with minimal yes or no questions, requiring only eight questions for a 256-bit block.', 'The storage of 12 bits of data with 4 bits reserved for redundancy is discussed, indicating a 12:4 ratio of data to redundancy.', 'The extended Hamming code detects two-bit errors using the zeroth bit as a parity bit across the entire block, enabling the identification of uncorrectable errors.', 'Error correction codes enable machines to identify and correct errors.', 'The scratch on a CD or DVD affects the ones and zeros, but the data can still be decoded.', 'The field of error correction codes has been a rich source of deep math in everyday devices.', 'The chapter contrasts the limited usage of Hamming codes with modern codes like Reed-Solomon algorithm.', 'The efficiency and elegance of the error correction algorithm are highlighted, emphasizing its simplicity and systematic scalability.', "Richard Hamming invented the world's first error correction code, the Hamming Code.", 'The process of dividing a message into 11-bit chunks and packaging them into error-resistant 16-bit blocks is explained.', 'Parity checks serve as a powerful building block for more sophisticated error correction schemes', 'The hint about scalability for larger blocks is provided, suggesting the potential application of the discussed concept on a larger scale.', 'The explanation of how two parity checks allow pinning down the column and then the rows to identify error locations', 'The 1511 Hamming code utilizes 11 bits for carrying a message and four bits for redundancy, effectively detecting but not correcting two-bit errors.', 'Technically only 11 bits of data are stored due to the redundancy.']}