damn. I am brute honest-this is amongst one of the most important topics that is there for CSE Undergrads. And the fact that this channel has taught it to a point that I was ENJOYING the video so much, and was so much engrossed in it! Thanks a lot for making the life of CSE Undergrads less hard and all. Loved the videos :)
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.
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
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.
@@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.
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!
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.
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.
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?
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.
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?
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
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).
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.
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.
@@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.
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.
damn. I am brute honest-this is amongst one of the most important topics that is there for CSE Undergrads. And the fact that this channel has taught it to a point that I was ENJOYING the video so much, and was so much engrossed in it!
Thanks a lot for making the life of CSE Undergrads less hard and all. Loved the videos :)
Thanks Brian for all the work you do to help students :)
You're very welcome!
Absolutely fantastic explanation! The progression and pace of the examples was perfect for me.
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.
How do you take CS class? Like is it in college?
- Just a curious commenter
@@hereigoagain5050 Aw man do you know what a minimum spanning tree is?
Great video, thorough and visuals help a ton
The best video about hamming codes i have ever seen
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
So that's why... Thank you.
But what if an error occurs in a parity beat?
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.
Thank you, you are doing a really great job, keep it up :)
@@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?
@@aenetanthony hamming codes can detect (but not correct) two bit errors
@@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.
I had totally forgoten about this topic. Thanks for refreshing it.
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!
This channel is so underrated and deserving of so much praise!
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.
That's so nice! You guys are the reason I watch youtube!
Great! Bravo!
I really like your videos. Thank you!
Great videos. Sad that I found the channel just now and not earlier.
6:25
I have a question, what if the error occured in the last bit in the right side ?
Can this method detect it ?
The last bit is checked by all three parity bits. Since flipping it wold make all three parity bits wrong, it could be corrected.
@@kasufert thanks, that makes sense now!
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.
Great video, amazing algorithm!
Great video!
does normal ram does this or is it integrated only in ECC ?
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?
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.
Bit 👍
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?
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
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).
was it the rigth MSB & LSB??
Is this TCP/IP layer's responsibilylty?
its like sudoku but with extra steps (?)
What if there are more than one bit flipped? Then the parity bit with wont detect the problem?
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.
@@MichaelDarrow-tr1mn thanx
Parity bits that represent the octals value
Cool video, just found it. What if the parity bit is flipped, would that get corrected?
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.
@@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.
2 bit corruption is very rare guys
like even 1 bit error is stupidly rare
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.
You would have to send out three times, because otherwise you won't know which one is the wrong one
Make more videos
It's like computer cancer
is a parity bit sort of like a chicken mcnugget?
?
What happens if 2 bits are flipped? Does the algorithm handle it gracefully?
It’s aware that there 2 errors, but not where.
@@ninonook677 the one described just erroneously corrects it to a different state.