Thank you so much for explaining the reasoning behind the equations I was taught this in way that was basically forcing me to memorize . I truly believe that the best way to learn is by understanding the reasoning behind what your doing as it makes it easier to memorize and more enjoyable
Glad to see you back. Code theory has very interesting ties with field theory and algebraic geometry, and it's not easy to find instructional videos about it. Keep up the great work!
interesring to compare this explanation of Hamming code with 3blue1brown's one I guess I like 3b1b's version more, because it shows "set intersection" aspect visually, but pure "make equations do the work" approach deserves respect and I guess that "one can mix what error states correspond to which error bits" idea is eye-opening, but probably just corresponds to taking different bits in 3b1b rectangle...
Absolutely amazing ! I was eagerly awaiting the upcoming series on GR which I thought would be the end of your production. But instead, a totally unexpected series on error correction coding, which I also am very interested in. So excited, I wrote this comment even before I began watching the lecture. The first screen seems to relate linear algebra to error correction ... How is the tip jar coming along ? I hope I don't have to use an intermediary to process a credit card transaction.
I'm preparing the final 3 videos I have planned for that series on Torsion, the Riemann Tensor, and the Ricci Tensor. I'm still learning about them, and I'll be uploading ECC videos in the meantime until my understanding of the tensor calc stuff is better.
Your videos seem to be the best ones to understand ECC by far. Its a shame the series isn't finished but I was wondering if you have made any notes on the rest of the topic that I could buy?
I try to explain the proces for getti g the equations in the last 30% or so of this video. It's not totally random, but the 3 variables chosen in each case are arbitrary and can be switched around.
Error Correcting Codes 1: Introduction + Hamming (7,4) Code Decoding Problems Stages In the field of data transmission and storage, error-correcting codes play a crucial role in ensuring the reliable transfer of information. The Hamming (7,4) code is a specific example of an error-correcting code that can detect and correct errors in a data transmission. Let's break down the stages involved in understanding and solving problems related to this code. 1. Introduction to Error Correcting Codes: Error-correcting codes are mathematical algorithms that encode digital data in a way that allows the receiver to detect and, in some cases, correct errors that may occur during transmission. These codes work by adding redundant information to the original data, which helps the receiver identify and correct errors without the need for retransmission. 2. Understanding Hamming (7,4) Code: The Hamming (7,4) code is a popular example of an error-correcting code. It is a linear code that can correct a single error in the transmitted data. The code is named after its inventor, Richard Hamming. This code uses 7-bit blocks to encode 4-bit information, with the remaining 3 bits serving as parity checks for error detection and correction. 3. Decoding Problems: Decoding problems in error-correcting codes involve determining the original data from the received data, which may contain errors. In the case of the Hamming (7,4) code, the decoding process involves the following steps: a. Syndrome Calculation: The receiver calculates the syndrome, which is the sum of the product of the received bits and a set of fixed coefficients. This syndrome helps determine the location and type of error(s) in the received data. b. Error Location: Using the syndrome, the receiver identifies the location(s) of the error(s) in the received data. c. Error Correction: Once the location of the error(s) is known, the receiver can correct the error(s) by flipping the bit(s) at the identified location(s). 4. Stages in Solving Decoding Problems: To solve decoding problems related to the Hamming (7,4) code, you can follow these stages: a. Understand the code structure and its ability to correct errors. b. Learn how to calculate the syndrome for a given set of received data. c. Develop strategies to identify the location of errors based on the syndrome. d. Implement methods to correct the errors by flipping the appropriate bits in the received data. By mastering these stages, you will be well-equipped to understand and solve problems related to the Hamming (7,4) code and other error-correcting codes.
2:02 Will you go through CRC(Cyclic Redundancy Check) as well? Perhaps that's what Polynomial Codes are? If you will go through it then I'd love to hear why one polynomial is better than another polynomial, because I've so far never heard or seen any... reasonable explanation.
I haven't studied CRCs directly, but it looks like the theory is very similar to error correcting codes. When you are asking abouy the "polynomial", are you talking about the "generator polynomial"? The one that's used as the multiplier? The anser in general is that you want a polynomial that "spreads" out the valid binary strings as much as possible. This is related to the idea of "minimum distance" which you can google. I know Reed Solomom codes have generator polynomials that are designed to have the highest possible minimum distance for a given string length, so in a sense they are "optimal". I'm not sure I can give a more specific amswer than that yet. Maybe future videos will clear things up.
@@eigenchris Well CRC's are very similar to checksums, but yeah when I said "polynomial" I meant "generator polynomial", in this case it's actually division, not multiplication. en.wikipedia.org/wiki/Computation_of_cyclic_redundancy_checks It's not the same as a generator matrix, for say Hadamard code or Hamming code (I believe). If I'm not incorrect, CRC's are just shift registers where all bits in the register can be inputs and fed from xor gates and then fed back into the input with yet another xor gate. So a fancy checksum, yet not exactly a "sum", it's long division in some sense (according to wiki). I don't understand it 100%, but I'm fairly certain that you can't find out where an error has appeared in a CRC, just that some error has appeared and therefor the receiver can ask for another message. Fun info: CRC has been used multiple times in order for you to read this very text that I've written for you. Imagine losing packets on wi-fi/cable, instead of correcting some packet it just asks for the packet again and says that it has lost a packet. For forward error correcting codes, as you were describing in the video, then yeah I can understand how some generator matrices spread out messages and increase the hamming distances among all codes than other generator matrices. But the CRC polynomial is still... I can read that wiki article several times but it just doesn't go into my head. Or I can read some other wiki article... en.wikipedia.org/wiki/Cyclic_redundancy_check#Designing_polynomials It's still just... I think it's either so ridiculously simple that I'm just overlooking it, or it's so advanced that I can't understand it. So the thing I don't understand regarding CRC in particular is why one polynomial is better than another, or how you would say "this polynomial is better than this one because of ???". But yeah, maybe some future video will mention CRC, or checksums, or maybe not, I love your videos either way ;)
So after a bit of reading, I've concluded CRCs are basically equivalent to Cyclic Polynonial Error Correcting Codes. I am working on the video for these right now and it should be out by early May. Although generator polynomials and generator matrices seem different, every generator polynomial can be converted into a generator matrix, so the idea behind them is more or less the same: take raw messages and encode them into a longer string, where the encoded strings are "spread out" as much as possible to maximize error detection. Every generator polynomial/matrix has a number associated wity it called the "minimum distance", usually denoted by the letter d. And if you want to detect/correct more errors, you basically need to choose a generator polynomial/matrix with the highest d possible. While I am not sure how to get d from the generator, I will eventually show how to go the other way around: how to create a generator with a given d. This is ultimately what reed solomon codes and BCH codes allow: we can pick a d of our choice and get most efficient generator with that d. When I say "most efficient", I mean d meets the "singleton bound", which is an inequality you can google that places constraints on the relationship between d and the message length. The following page, in section 7, says that choosing good generator polynomials is a "dark art", and says we generally use "tried and true" polynomials. however I think this might be untrue... the wikipedia page you linked me to mentions BCH codes and this leads me to believe what I said above is correct and that you can design a polynonial which has a given d that you want. I am guessing by the end of this series your question will be answered, but you can always ask me again later if things are unclear. www.ross.net/crc/download/crc_v3.txt
@@eigenchris Thanks for that txt file. It really helped. It's fun to know at least someone else has also thought of it as "black arts". But now I see that different polynomials can find different kind of errors (1 bit error, 2 consecutive errors, 2 errors randomly spaced, burst, etc). And I also believe that long division (mod 2) is the same thing as multiplication, with the caveat that the operand slides the opposite way in multiplication vs division. And this is because addition and subtraction is the same. So with CRC I thought it was only long division, but it's also multiplication in some sense. It's weird to even talk about multiplication/division in mod 2 when there's no carries. Oh well. So yeah, looking forward to the next couple of videos ;) Good stuff man!
I'm defining an "error" as a "flipped bit" here. Maybe when you're artificially generating errors, you can assign probabilities like that for whether or not they happen.
As I said in another comment, I'm preparing the final 3 videos I have planned for that series on Torsion, the Riemann Tensor, and the Ricci Tensor. I'm still learning about them, and I'll be uploading ECC videos in the meantime until my understanding of the Tensor Calc stuff is better.
The check bits validated that all the equations for checking for errors are satisfied. If there's a "1", it means one of the expected check-equations has been violated. Does that make sense or do you need more explanation?
Ok, so if you made videos on differential geometry and you made videos on information theory, why not cover the marriage of two: "information geometry". This is a topic that can really benefit your style of presentation.
I didn't know that information geometry existed until now. :P Unfortunately I know nothing about it and it doesn't really catch my interest much. My main plan for the rest of the year is general relativity videos.
@@eigenchris yes, I guessed. Information geometry is not very popular, especially if you compare with GR. But information theory is quite deep and general, give it a tiny chance ;)
I'm so happy. I came for your tensor calculus series and now I'm addicted
Thank you so much for explaining the reasoning behind the equations I was taught this in way that was basically forcing me to memorize . I truly believe that the best way to learn is by understanding the reasoning behind what your doing as it makes it easier to memorize and more enjoyable
Glad to see you back. Code theory has very interesting ties with field theory and algebraic geometry, and it's not easy to find instructional videos about it. Keep up the great work!
I study media engineering in Germany. Since there are no good videos in my language about this topic, you are my hero. Thank you! :D
Repetition Code - 2:30
Hamming Code - 6:55
Syndromes - 17:03
Check-bit states and Error States - 17:10
Thank you very much for explaining clearly and not including too many unnecessary and complex words!
good to see you back!
interesring to compare this explanation of Hamming code with 3blue1brown's one
I guess I like 3b1b's version more, because it shows "set intersection" aspect visually, but pure "make equations do the work" approach deserves respect
and I guess that "one can mix what error states correspond to which error bits" idea is eye-opening, but probably just corresponds to taking different bits in 3b1b rectangle...
Great video! I already love this channel!
Absolutely amazing !
I was eagerly awaiting the upcoming series on GR which I thought would be the end of your production. But instead, a totally unexpected series on error correction coding, which I also am very interested in. So excited, I wrote this comment even before I began watching the lecture. The first screen seems to relate linear algebra to error correction ...
How is the tip jar coming along ? I hope I don't have to use an intermediary to process a credit card transaction.
it's a vary good video so easily explained, good work.
Hello eigen why dont you upload video on tensor analysis.. We are waiting to go for General theory of Relativity
I'm preparing the final 3 videos I have planned for that series on Torsion, the Riemann Tensor, and the Ricci Tensor. I'm still learning about them, and I'll be uploading ECC videos in the meantime until my understanding of the tensor calc stuff is better.
Your videos seem to be the best ones to understand ECC by far. Its a shame the series isn't finished but I was wondering if you have made any notes on the rest of the topic that I could buy?
Thanks a lot. Your lecture is very awesome and helps me understand hamming codes!!!
I would like to know the reason why we have those exact equations for x, y and z. It's it a random selection?
I try to explain the proces for getti g the equations in the last 30% or so of this video. It's not totally random, but the 3 variables chosen in each case are arbitrary and can be switched around.
@@eigenchris Thanks a lot
New serie 🙌🏼😃
Life saving lecture 🙂
Lovely series. Great video.
I'm so glad you are still alive
Excellent video thank you so much for this!
Students are liberated after seeing this !
You are one amazing teacher !
waiting for next video in series.
Is that we can use Hamming(5,4) or Hamming(6,4) code
Error Correcting Codes 1: Introduction + Hamming (7,4) Code Decoding Problems Stages
In the field of data transmission and storage, error-correcting codes play a crucial role in ensuring the reliable transfer of information. The Hamming (7,4) code is a specific example of an error-correcting code that can detect and correct errors in a data transmission. Let's break down the stages involved in understanding and solving problems related to this code.
1. Introduction to Error Correcting Codes:
Error-correcting codes are mathematical algorithms that encode digital data in a way that allows the receiver to detect and, in some cases, correct errors that may occur during transmission. These codes work by adding redundant information to the original data, which helps the receiver identify and correct errors without the need for retransmission.
2. Understanding Hamming (7,4) Code:
The Hamming (7,4) code is a popular example of an error-correcting code. It is a linear code that can correct a single error in the transmitted data. The code is named after its inventor, Richard Hamming. This code uses 7-bit blocks to encode 4-bit information, with the remaining 3 bits serving as parity checks for error detection and correction.
3. Decoding Problems:
Decoding problems in error-correcting codes involve determining the original data from the received data, which may contain errors. In the case of the Hamming (7,4) code, the decoding process involves the following steps:
a. Syndrome Calculation: The receiver calculates the syndrome, which is the sum of the product of the received bits and a set of fixed coefficients. This syndrome helps determine the location and type of error(s) in the received data.
b. Error Location: Using the syndrome, the receiver identifies the location(s) of the error(s) in the received data.
c. Error Correction: Once the location of the error(s) is known, the receiver can correct the error(s) by flipping the bit(s) at the identified location(s).
4. Stages in Solving Decoding Problems:
To solve decoding problems related to the Hamming (7,4) code, you can follow these stages:
a. Understand the code structure and its ability to correct errors.
b. Learn how to calculate the syndrome for a given set of received data.
c. Develop strategies to identify the location of errors based on the syndrome.
d. Implement methods to correct the errors by flipping the appropriate bits in the received data.
By mastering these stages, you will be well-equipped to understand and solve problems related to the Hamming (7,4) code and other error-correcting codes.
Where I can get the ppt you used here
I see eigenchris, i click!
2:02
Will you go through CRC(Cyclic Redundancy Check) as well? Perhaps that's what Polynomial Codes are?
If you will go through it then I'd love to hear why one polynomial is better than another polynomial, because I've so far never heard or seen any... reasonable explanation.
I haven't studied CRCs directly, but it looks like the theory is very similar to error correcting codes. When you are asking abouy the "polynomial", are you talking about the "generator polynomial"? The one that's used as the multiplier?
The anser in general is that you want a polynomial that "spreads" out the valid binary strings as much as possible. This is related to the idea of "minimum distance" which you can google. I know Reed Solomom codes have generator polynomials that are designed to have the highest possible minimum distance for a given string length, so in a sense they are "optimal". I'm not sure I can give a more specific amswer than that yet. Maybe future videos will clear things up.
@@eigenchris Well CRC's are very similar to checksums, but yeah when I said "polynomial" I meant "generator polynomial", in this case it's actually division, not multiplication.
en.wikipedia.org/wiki/Computation_of_cyclic_redundancy_checks
It's not the same as a generator matrix, for say Hadamard code or Hamming code (I believe). If I'm not incorrect, CRC's are just shift registers where all bits in the register can be inputs and fed from xor gates and then fed back into the input with yet another xor gate. So a fancy checksum, yet not exactly a "sum", it's long division in some sense (according to wiki). I don't understand it 100%, but I'm fairly certain that you can't find out where an error has appeared in a CRC, just that some error has appeared and therefor the receiver can ask for another message. Fun info: CRC has been used multiple times in order for you to read this very text that I've written for you. Imagine losing packets on wi-fi/cable, instead of correcting some packet it just asks for the packet again and says that it has lost a packet.
For forward error correcting codes, as you were describing in the video, then yeah I can understand how some generator matrices spread out messages and increase the hamming distances among all codes than other generator matrices.
But the CRC polynomial is still... I can read that wiki article several times but it just doesn't go into my head. Or I can read some other wiki article...
en.wikipedia.org/wiki/Cyclic_redundancy_check#Designing_polynomials
It's still just... I think it's either so ridiculously simple that I'm just overlooking it, or it's so advanced that I can't understand it. So the thing I don't understand regarding CRC in particular is why one polynomial is better than another, or how you would say "this polynomial is better than this one because of ???".
But yeah, maybe some future video will mention CRC, or checksums, or maybe not, I love your videos either way ;)
So after a bit of reading, I've concluded CRCs are basically equivalent to Cyclic Polynonial Error Correcting Codes. I am working on the video for these right now and it should be out by early May.
Although generator polynomials and generator matrices seem different, every generator polynomial can be converted into a generator matrix, so the idea behind them is more or less the same: take raw messages and encode them into a longer string, where the encoded strings are "spread out" as much as possible to maximize error detection.
Every generator polynomial/matrix has a number associated wity it called the "minimum distance", usually denoted by the letter d. And if you want to detect/correct more errors, you basically need to choose a generator polynomial/matrix with the highest d possible.
While I am not sure how to get d from the generator, I will eventually show how to go the other way around: how to create a generator with a given d. This is ultimately what reed solomon codes and BCH codes allow: we can pick a d of our choice and get most efficient generator with that d. When I say "most efficient", I mean d meets the "singleton bound", which is an inequality you can google that places constraints on the relationship between d and the message length.
The following page, in section 7, says that choosing good generator polynomials is a "dark art", and says we generally use "tried and true" polynomials. however I think this might be untrue... the wikipedia page you linked me to mentions BCH codes and this leads me to believe what I said above is correct and that you can design a polynonial which has a given d that you want. I am guessing by the end of this series your question will be answered, but you can always ask me again later if things are unclear.
www.ross.net/crc/download/crc_v3.txt
@@eigenchris Thanks for that txt file. It really helped.
It's fun to know at least someone else has also thought of it as "black arts". But now I see that different polynomials can find different kind of errors (1 bit error, 2 consecutive errors, 2 errors randomly spaced, burst, etc).
And I also believe that long division (mod 2) is the same thing as multiplication, with the caveat that the operand slides the opposite way in multiplication vs division. And this is because addition and subtraction is the same. So with CRC I thought it was only long division, but it's also multiplication in some sense.
It's weird to even talk about multiplication/division in mod 2 when there's no carries. Oh well.
So yeah, looking forward to the next couple of videos ;) Good stuff man!
Do errors here neccesarily flip a bit, or do they have a 50 chance of flipping a bit given the error?
I'm defining an "error" as a "flipped bit" here. Maybe when you're artificially generating errors, you can assign probabilities like that for whether or not they happen.
good job chris!
Hi Chris not wanting to sound like a broken record, and this new series is great... but when will we get the final videos on Tensor Calculus?
As I said in another comment, I'm preparing the final 3 videos I have planned for that series on Torsion, the Riemann Tensor, and the Ricci Tensor. I'm still learning about them, and I'll be uploading ECC videos in the meantime until my understanding of the Tensor Calc stuff is better.
@@eigenchris thanks!
Really good and informative video
Hey I googled ricci to know how to pronounce it and saw some of your videos. Good stuff
Great video! Thank you
Why should all the check bits be 0?
The check bits validated that all the equations for checking for errors are satisfied. If there's a "1", it means one of the expected check-equations has been violated. Does that make sense or do you need more explanation?
Excellent. Thank you.
Thank you, you've helped a lot.
omg, this is gold
your amazing!
You explain really well...should be a teacher.
god bless you.
u saved my life thanky ou
A bit little rush, but overall well explain!
Ok, so if you made videos on differential geometry and you made videos on information theory, why not cover the marriage of two: "information geometry". This is a topic that can really benefit your style of presentation.
I didn't know that information geometry existed until now. :P Unfortunately I know nothing about it and it doesn't really catch my interest much. My main plan for the rest of the year is general relativity videos.
@@eigenchris yes, I guessed. Information geometry is not very popular, especially if you compare with GR. But information theory is quite deep and general, give it a tiny chance ;)
thank you
so cool!!!! thanks a lot
thanks
Oh wow i felt asleep
thanks