Hamming Codes - How Data Corrects Itself

What happens if a mistake happens when data is transferred? With Hamming codes, we give data the ability to correct its own mistakes. Here, we explore how that works.
0:00 Errors in Data
0:56 Parity Bits
2:14 Correcting Errors
3:38 Hamming Code
***
Spanning Tree is an educational video series about computer science and mathematics. See more at spanningtree.me
To be notified when a new video is released, sign up for the Spanning Tree mailing list at spanningtree.substack.com/
Spanning Tree is created by Brian Yu. brianyu.me/
Email me at [e-mail] to suggest a future topic.

[@misiekeloo6114]

But what if an error occurs in a parity beat?

[@SpanningTree]

Hamming Codes handle this case too! If there's an error in a parity bit, then that parity bit won't be correct when the data is received. And since the other parity bits will be correct (assuming at most a 1-bit error), we'll know that the parity bit needs correction.

[@misiekeloo6114]

Thank you, you are doing a really great job, keep it up :)

[@aenetanthony]

@@SpanningTree Is it possible to build a way to detect two or more errors in the data? What is the limit of bits flipped, if it is possible?

[@MichaelDarrow-tr1mn]

@@aenetanthony hamming codes can detect (but not correct) two bit errors

[@reda29100]

@@aenetanthony as mentioned in the vid, an error is likely to be just 1. 1 bit in how many? I would presume 100 in today's hardware. I'm not working with hard facts, pun intended, but O think math and probability can tell what is a reasonable amount of errors an X bytes of data ay hve with a confidence of say 99%.
So technically, there could be 2, 3 and even all bits are mis-transmitted, bit statistically with today's hardware I think that's improbable.

[@vivekagrawal4607]

Thanks Brian for all the work you do to help students :)

[@SpanningTree]

You're very welcome!

[@hereigoagain5050]

I don't need Hamming codes: my wife tells me when I'm wrong :) Excellent video. When you learn this in CS class, it is topic 3 of 4 in a 90 minute lecture to over 100 students.

[@griffinshorts785]

How do you take CS class? Like is it in college?
- Just a curious commenter

[@superspartanman4480]

@@hereigoagain5050 Aw man do you know what a minimum spanning tree is?

[@suikodin2501]

Absolutely fantastic explanation! The progression and pace of the examples was perfect for me.

[@jamesdaus]

Great video, thorough and visuals help a ton

[@matrick1356]

6:18 there should be an addition/correction in phrasing here: "which of the bits was included in both the first bit third parity bits, but not the second bit?" the last data bit is correct since the second bit validates it. The error is in the bit where all of the parity bits is wrong

[@mypaxa003]

So that's why... Thank you.

[@andrekim9223]

The best video about hamming codes i have ever seen

[@rabiaedaylmaz1198]

I was reading The Art of Doing Science and Engineering: Learning to Learn by Richard Hamming. This video helped me a lot to understand how he explained in there, thank you!

[@sid98geek]

This channel is so underrated and deserving of so much praise!

[@edl7176]

That's so nice! You guys are the reason I watch youtube!

[@sulavlalshrestha6683]

Great videos. Sad that I found the channel just now and not earlier.

[@eduardoarteaga8402]

I really like your videos. Thank you!

[@OzanErenBilgen]

Great video, amazing algorithm!

[@sujitkumarsingh3200]

I had totally forgoten about this topic. Thanks for refreshing it.

[@ananyagupta1409]

Great! Bravo!

[@dannywei6933]

Great video!

[@lawrencedoliveiro9104]

6:55 That efficiency comes at a cost, namely less robustness. Assuming the same characteristics storage/transmission medium, a block of 247 bits is 247/7 times more likely to have errors in it than a block of 7 bits. But you only have 8/3 times the parity bits to protect it.

[@ludovicbouchard252]

does normal ram does this or is it integrated only in ECC ?

[@KhmerKhmer-no9cm]

Bit 👍

[@xTasyDotes]

its like sudoku but with extra steps (?)

[@BS-bd4xo]

This is so amazingly cool.
But what about the fact that cosmic rays can change a digit? Veritasium made an entire video about that. Does this not just fix that issue?

[@warriorsabe1792]

It significantly reduces the impact, but if, say, two cosmic rays hit and flipped two bits, it would not be guaranteed to help anymore. Plus, hamming codes can't be used constantly - you can't actually use the protected data as-is for a lot of things because the parity bits get in the way, meaning if one hits while the data is being used for something and unprotected, it's also vulnerable there. Luckily, it's a lot less likely for an externally triggered error such as from a cosmic ray to happen during the short window of it being used versus the longer periods of storage or transmission where the codes are employed, just as it's much less likely for multiple bits to get flipped in the same data unit.
And one thing you can do to protect more is to break down your data into smaller such units, so that if multiple bits get flipped, they're more likely to be in separate chunks that can separately detect the single error, though that does cost you in the fact that the codes are less size-efficient for said smaller chunks.

[@axiomfinity]

Parity bits that represent the octals value

[@a10netmedtv]

6:25
I have a question, what if the error occured in the last bit in the right side ?
Can this method detect it ?

[@kasufert]

The last bit is checked by all three parity bits. Since flipping it wold make all three parity bits wrong, it could be corrected.

[@a10netmedtv]

@@kasufert thanks, that makes sense now!

[@danielfarfudinov3193]

This method only works for a single flipped bit, and the parity bits together can be read as a binary id of the erroneous flipped bit. In the big example at the end, you can see that the parity bits are in those specific places because all of them only have a single "1" in its' binary "spot" in the sequence - [1: 10000000, 2: 01000000, 3: 00100000, 4: 00010000, 5: 00001000, 6: 00000100, 7: 00000010, 8: 00000001]. After that, you can override 00000000 with every erroneous parity bit, and achieve for example an error in the seventh position: 11100000, if the first 3 parity bits are erroneous.
This property also helps when the parity bit itself is incorrect, since the result from the combination would lead to the parity bit itself: 01000000.

[@oldbadname3633]

Hamming code relies on the assumption that there are only two possible states: entirely correct or with one error, but increasing bit package size also increases likelihood of error, so isnt there a limit to how effective Hamming Code can possibly be?

[@Joe_Payne]

My assumption is that since for large numbers you only need a small % for error correction that you would also implement similar error correction bits designed for detecting two bit errors

[@zanfur]

This video was a simplification; hamming codes can be created that will correct up to N flipped bits (and, in general, detect 2N errors even if it can't fix them).

[@Labib_1453]

was it the rigth MSB & LSB??

[@josephsalviaii9183]

Cool video, just found it. What if the parity bit is flipped, would that get corrected?

[@SunnySingh-ry4qs]

For that you'll need parity parity bits to correct parity bits, and to keep a check on those parity parity bits you'll need parity parity parity bits. Therefore i work as construction worker and not in an IT field.

[@danielfarfudinov3193]

@@SunnySingh-ry4qs The channel owner explained it above. If a parity bit is flipped, and therefore shows an error, every other parity bit will still be correct, therefore we can conclude that the error is not in the used data, but in the parity bit that shows an error
Edit: This whole thing works because if the data has an error in it, there is always more than a single parity bit that will show an error.

[@franchello1105]

Is this TCP/IP layer's responsibilylty?

[@icheckedavailability]

I also wonder this

[@dhruvo100]

What if there are more than one bit flipped? Then the parity bit with wont detect the problem?

[@MichaelDarrow-tr1mn]

let's take the example 0110011.
both bits 6 and 7 are flipped. we see 0110000.
if we try to correct it we end up erroneously believing the correct result is 1110000, which encodes the data [1000] instead of [1011] that is originally encoded.

[@dhruvo100]

@@MichaelDarrow-tr1mn thanx

[@poglin_or_smh]

2 bit corruption is very rare guys
like even 1 bit error is stupidly rare

[@tinypileofpolydimethylsiloxane]

At what point does it become more efficient to send the 4 data bits twice? This method only saves 1 bit, but i bet all this checking takes some computing power. I bet the extra electricity cost will more expensive then sending 4 correction bits every 4 data bits as opposed to 3.

[@nicospadoni5328]

You would have to send out three times, because otherwise you won't know which one is the wrong one

[@Last-Tap]

Make more videos

[@crelos3549]

It's like computer cancer

[@PlaylistsM]

?

[@roymallard]

is a parity bit sort of like a chicken mcnugget?

[@hitarthk]

What happens if 2 bits are flipped? Does the algorithm handle it gracefully?

[@ninonook677]

It’s aware that there 2 errors, but not where.

[@MichaelDarrow-tr1mn]

@@ninonook677 the one described just erroneously corrects it to a different state.