From what I've seen (on my own course and others) they're typically reserved for Numerical Analysis classes due to having pretty strong applications there (Newton-Coates Quadrature Rules come to mind off the top of my head). It's a huge shame that they get left out elsewhere though, such a simple and elegant solution to a problem
yeah it's mind blowing, I learned how to create a polynomial whose curve passes through n points thanks to this video ! TH-cam/Internet is a mine gold to learn stuff the right way.
Was about to spend an entire night to understand how it worked, but did it in 15 minutes. Has got to be one of the most elegant explanations of this topic if not the most elegant.
What a wonderful video! Came here from 3B1B's Hamming codes video, and this video blew my mind. Never realized how elegant Lagrange polynomials are! I wonder if Reed-Solomon can not only correct known errors, but detect them. i.e. what happens if you do receive all the packets, but one of them changed value unexpectedly? 🤔
Yes they can and that's a great question! What I've presented here is so-called "Erasure" error correction. "General" error correction requires a slight modification. If you're interested, see the link: www.eecs70.org/assets/pdf/notes/n9.pdf section 1.3
I've read about Reed Solomon before but everyone either just talks about the polynomials or just talks about the matrix algebra, this is the only explanation I've seen that elegantly bridges that gap. This should be taught in college!
This is why I love mathematics. There’s all this “useless” stuff you learn in high school but when you look into the environment around you, it’s EVERYWHERE! I hope I can put math to better use in my own code
I have just recently learned about lagrange polynomials and stumbled across this video. The way you explained it makes the work seems so beatifully done and simple. Great work!
This introduction to Reed-Solomon codes was extraordinarily put together, and was presented beautifully and elegantly. Thank you, I had a lot of fun watching.
Absolutely beautiful my friend. I remember my information theory teacher put some students to investigate and teach the subject and of course I did not learn a thing, until now thanks to this vid! You’ve got a new subscriber :)
Oh man, I love You! Tried to understand Reed-Solomon for AGES. Others simply >suck< at explaining this topic. I would love to see more details of practical implementation, e.g. space probes communications.
Great question! These are for "erasure errors" as they're called, where the packets get dropped. For bit flipping, it's actually the same algorithm, but a slight modification en.wikipedia.org/wiki/Berlekamp%E2%80%93Welch_algorithm
Gao's extended Euclid decoder is the most efficient one so far: en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#Gao_decoder. However, using BCH type encoding with a fixed generator polynomial results in much faster decoders, that operate on n-k syndromes, instead of n symbols.
Great video, really like how you explained it! Just a remark on the final example - using 5 as an input in a mod 5 example shouldn't be done as it is the same as using 0 as an input - so if you didn't have the luck to loose the package 0, you'd end up with only 2 points (one being the superposition of input 0 and 5 which didn't get lost) and wouldn't be able to reconstruct the rest.
I also came from 3b1b's Hamming video. What a time to be alive when there are resources like these available essentially putting some college lectures to a shame. Deducing ideas intuitively ourselves is a much better form of learning. How many times have I heard on QM or electrodynamics classes: "let's assume the solution is of this form" and indeed it works out in the end, but the magic is getting the feeling of that assumption in the first place, which is not really thaught. Even for someone who is well versed with math and IT jargon, these approaches give rise to great new perspectives.
Hi! I like your video very much. I think you did a great job explaining the method. I see a small issue about how the prime number is chosen, which in turn also depends on how the Lagrange interpolant is calculated. I see two options: either it is calculated directly in the field Fp (which I believe this is what you are doing), or it is calculated in the field of rationals numbers and then "converted" to have coefficients in the field Fp. It seems to me that the first option is the best one. But in that case, the prime p should be chosen to be larger than number of packets too. This is to ensure that the extra packets don't contain redundant information. If you look at your final example, f(0) = f(5) = 2 mod 5, because 0 = 5 mod 5. Thus, if we lose say packets 2 and 3, the points to interpolate are (0,2), (3,1), (4,0), (5,2) = (0,2). Thus, there are really only 3 points, not 4, and we cannot recover the original interpolant. If, on the other hand, the interpolant is calculated in Q and then converted to Fp, then we should have some justification that the denominators of the coefficients won't be multiples of p, as well as the numerator of the leading coefficient. But, maybe I'm missing something... :-)
Most erasure codes are based on GF(2^n), where n is the number of bits per symbol. One exception for error correcting codes is PDF417, which is based on GF(929). As for your question, the prime p is normally larger than the number of packets, but it can be the same as the number of packets if the data points include 0: 0, 1, 2, 3, ... , p-1. However, most implementations of erasure codes are similar to Raid 6, which is based on an alternate encoding scheme, where encoding is based on a fixed generator polynomial, rather than a fixed set of data points.
I think in practice p will almost certainly be bigger than the number of packets, based just on the size of the packets. For example, if you have 256 byte packets, p will need to be greater than 2^2048, and you're not likely to want to send that many packets. :-)
I really wish I could have somebody teach me how to apply this to, say, a qr code. What would it take to generate the error correction bits by hand? Seeing it done in video form like this makes it actually not seem too difficult, but applying the knowledge somewhere else is pretty difficult.
I may be misreading your comment, but QR codes already do use Reed-Solomon error correction. The bits next to the bottom left alignment square specify how much.
at 13:00 I don't understand how the receiver can construct the Lagrangian polynomial constructed by the sender from 6 points whereas the receiver has only 4 points available ?
ah! i was looking into RS for the sake of QR codes. but recently, i was using LPs to implement OR logic on secret keys. ie: 1 of 4 possible secrets suffice, by supplying 3 random values to pin down the curve when 1 value is supplied. this is really similar. if you have an array of 13 values, then sending 3 more allows you to send 3 more values on the polynomial. this is good if scratch locality doesn't have scratches longer than 3 values. thanks! this is very helpful. LPs have lots of crypto applications as well. you can even implement this inside of Elliptic Curves, to do this arithmetic on encrypted values.
Reed Solomon is a magic for me. I secured my photo album of 30 photos totalling 60 Megabytes, each photo is 2 Megabytes average. It created a 4.4 Megabytes of rescue data. now, even if I delete a photo, the rescure software (QuickPar) recovers that photo by using Reed Solomon algorithm. storing medias we use today are mostly flash memories, like SSDs or USB disks. bit rots may happen on those hardwares. your JPG photo file won't get unreadable when some of it's bits rotten, but your RAR archieve file would. so Reed Solomon is a life-saver assitant for reliably save files on long term..
A data problem that comes up is how to tell if your backed up files have been corrupted. The standard way is to hash the file, then later, hash the backed up version to see if they match. However, one problem that comes up is that when the new and old hashes don't match, it's hard to tell if the file went bad or the saved hash went bad. One answer is to keep three copies of everything, so hopefully two always agree. Another is to use error correcting codes. Using par2/parchive, we can create hash-like objects that store redundant data from the source file so that errors can not only be detected, but in some cases repaired. We can tell if the generated objects are valid or not, allowing easy distinctions between source files vs generated files suffering bitrot.
TH-cam seems to be joking There was never a notification for the video and I thought you just stopped creating these :c Glad to stumble upon it at least now tho
Hey great vid! Do you know if Reed-Solomon codes can detects errors? For example, when you send a message to your friend but the message is corrupted and you don’t know where it is corrupted, is there a way to know the location of this corrupted data? Thank you!!
Yep! Great question, they actually require a slight modification to do that, but the idea is similar: en.wikipedia.org/wiki/Berlekamp%E2%80%93Welch_algorithm
Gao's extended Euclid algorithm (time complexity O(n^2)) is more efficient than Berlekamp Welch (time complexity O(n^3)), en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#Gao_decoder . Using BCH style encoding, where a fixed generator polynomial is used to encode is much faster, as the two most common decoders will have time complexity O((n-k)^2): en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#Berlekamp%E2%80%93Massey_decoder and en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#Euclidean_decoder.
Thank you so much for this video. It's amazing, seriously. One thing I wonder is how would this be applied for a value that was changed instead of missed. For an original message [1, 2, 3, 4, 5, 6] how would we at the other end fix it back if we got [1, 2, 3, 3, 5, 6], since we wouldn't know which packet was lost.
Thankyou greatly! I have no CS background but a reasonable grasp of pure maths. I had studied several other presentations of Reed-Solomon that were confusing and opaque. Your use and explanation of LaGrange interpolation was clear, elegant and easy to follow. I will be watching more!
For an erasure only code, Raid 6 is more efficient, since a single erasure (or the first parity packet) can be corrected with XOR. For error correcting code, using the alternative BCH type encoding scheme (fixed generator polynomial known to both encoder and decoder) is more efficient. The most efficient original view decoder is Gao's extended Euclid decoder with O(n^2) time complexity, while the two most common BCH view decoders, Berlekamp-Massey and Sugyama's extended Euclid decoders have O((n-k)^2) time complexity. The Wikipedia article covers both original and BCH type encoders and decoders: en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction .
I'm confused at 7:57. U were looking for x such that f(x) = 1, okay but then u plotted a graph for f(x) = 2 and why u were looking for f(1)=1 when the first point is (1,2), it makes sense to me search for f(1)=2... Shouldn't the l_1(x) be (x-3)(x-4)/3 then ?
I think what you're trying to get at is if I lose more than k packets, then is the data recoverable? The answer is mostly no, since we can no longer uniquely define a polynomial with the remaining packets. As such, you need to choose k wisely - too large, and you have too much data to send, too little, and you have a higher chance of losing all the data.
Thanks for the video! You keep referring to packets beging 'lost' which suits this methodology of restoring data. What happens if all packets make it through but some of the data gets corrupted? How is the original message recovered from the corrupted received data? Thanks!
This video explains it for if the packets go missing entirely, but what if they're just corrupted? How does the receiver tell which packets are bad and which ones it should use for the polynomial?
One thing I notice: this can't actually correct _errors_, on its own, can it? Just known-missing values. If you have e.g. 4 messages with 1 corrective message and one of your messages is wrong, then any combination of 4 messages yields a (likely different) valid polynomial, I think. (It's possible that having extra spare messages solves the problem, basically by group vote.)
In your example, you need to go at least mod 7, to use 6 carrier packets. When you go mod 5, zero and five are equivalent, so f(0) and f(5) are automatically the same.
It is mentioned in the video that information is received on the other end as in the order in which it has been sent and on the place of the numbers that has been lost shows error. Then, machine uses polynomial to find it.
8 years after completing my engineering in Computers, I came to this video because i randomly got interested in how error correcting codes work. Then i saw the part about Lagrange theorem, and i swear to God,i do remember the word and equations i was supposed to crunch but in college nobody told us what we are doing or why. We were just supposed to write the final equation and multiply it and mark the equation as answer if Lagrange was written in the question. Gosh, I wish i had seen this video back then 😅 at least i would have known what i am studying.
This is a common problem of a lot of instructors teaching different subjects. I faced it too. Instructors will tell you the steps to get the answer on the board, but don't really tell at the beginning of the lecture about what we're trying to achieve in the class, i.e. what does doing those steps help us achieve. Idkw instructors dont bother explaining the concepts first before writing a bunch of equations and steps on the board.
@@thjamy Exactly. It is as if we are some machine. We take numbers and keywords as inputs and perform some fixed calculation on them and spit out an output number.
Thanks a lot for your informative video. I just don't get one passage. From Lagrange to function with mod. Doing the calculation for the lagrangian polynomial the results will be: f(x)=(2x^3 -15x^2 +25x+12)/6. How Do you obtain f(x)=2x^3 +2 (mod 5) ? Thanks in advance
Do it mod 5! f(x) = (2x^3 -15x^2 +25x+12)/6, like you said. Now, 6^-1 = 1 mod 5 (since 6 * 1 = 1 mod 5), so f(x) = 2x^3 -15x^2 +25x+12 mod 5. Then, 2 = 2 mod 5 15 = 0 mod 5 25 = 0 mod 5 12 = 2 mod 5 So, f(x) = 2x^3 + 2 mod 5
Good question. Since the setup for lagrange interpolation involves division, we need every number to have a multiplicative inverse mod p. a^-1 mod m exists iff gcd(m, a)=1. If m is a prime p, then a^-1 always exists, since gcd(a, p) = 1 for all a.
there's also a famous extension of this by Galois to prime powers p^n (where p is a prime and n is a positive integer) but you have to add some more structure
Ok, it was bit complex and became boring in the middle but in the end, it put a sudden smile in face to realize how simple the basic behind reed-solomon is and the history comes from long way..! I was working with video and was amazed by hearing reed-solomon that it can retrieve even burst packets.. and now I understand why..! Thanks for great explanation...!!
Your videos are quite interesting! I suggest speaking a little louder cause other voice in my house disturbs this other than that, this is interesting!!!
When I interpolate the points of (0,2) (1,4) (2,3) (3,1) with Lagrange polynomial, I get this equation: f(x) = (x^3)/3 - 5(x^2)/2 + 25x/6 + 2, which is not the same as your f(x)= 2(x^3) + 2. Am I missing some reduction part?
Your interpolation is right, what I think has not been mentioned in the video is that when you are interpolating mod n you no longer have only one correct answer e.g. you can add n to any polynomial which would not change its value mod n.
2 ปีที่แล้ว
When doing the Lagrange interpolation, you should use modular arithmetic (mod 5). Then 3^-1 becomes 2 (modular multiplicative inverse under modulo 5), and x^2 and x are always multiples of 5 so they disappear.
Yeah, but you didn't tell us how exactly they know those were the packets that were lost, because you say "let's assume", but what if we don't assume? And what if instead of losing, the data is modified? how do you know that packet was modified, because you said that is used on qr and barcode. where a single white pixels group could be shaded by a spot or a black pixels group could be over lightened
please sir tell me do I need to know Python before starting manim. if yes than how much would be suffice. I want to use little bit animation for my physics lectures, how much would it take me to learn how to make basic stuff. is there any other better alternative of manim for my kind of work.
I think more education shall be like this. Instead of purely starting from Abstract, start from actual usage of it and decode it to present the theory. That way you hook interest and connect math to real world easier.
There is the easiest way to solve quadratics .....it surpasses even po-shen loh's method .....and this can lay foundation to solve cubic and quartic..... I can make a video on it if you all want.....lemme know
If you enjoyed the video, please consider subscribing :)
Bhaiya kya mast TH-cam channel banaya hai🔥🔥🔥
yes papa!
How have I never come across Lagrange polynomials?! That was one of the most beautiful pieces of maths I've ever seen!
From what I've seen (on my own course and others) they're typically reserved for Numerical Analysis classes due to having pretty strong applications there (Newton-Coates Quadrature Rules come to mind off the top of my head). It's a huge shame that they get left out elsewhere though, such a simple and elegant solution to a problem
@@ThomasCartwrightLancs Absolutely! If only I'd studied Numerical Analysis (all those years ago!)
yeah it's mind blowing, I learned how to create a polynomial whose curve passes through n points thanks to this video ! TH-cam/Internet is a mine gold to learn stuff the right way.
@@Amine-gz7gqliar
@@ukissrulez about what ?
Missed opportunity to title the video "Learn how to Reed Solomon codes"
Was about to spend an entire night to understand how it worked, but did it in 15 minutes. Has got to be one of the most elegant explanations of this topic if not the most elegant.
Same!!
What a wonderful video! Came here from 3B1B's Hamming codes video, and this video blew my mind. Never realized how elegant Lagrange polynomials are!
I wonder if Reed-Solomon can not only correct known errors, but detect them. i.e. what happens if you do receive all the packets, but one of them changed value unexpectedly? 🤔
Yes they can and that's a great question!
What I've presented here is so-called "Erasure" error correction. "General" error correction requires a slight modification. If you're interested, see the link: www.eecs70.org/assets/pdf/notes/n9.pdf section 1.3
I've read about Reed Solomon before but everyone either just talks about the polynomials or just talks about the matrix algebra, this is the only explanation I've seen that elegantly bridges that gap. This should be taught in college!
This is why I love mathematics. There’s all this “useless” stuff you learn in high school but when you look into the environment around you, it’s EVERYWHERE! I hope I can put math to better use in my own code
I have just recently learned about lagrange polynomials and stumbled across this video. The way you explained it makes the work seems so beatifully done and simple. Great work!
Wow, this was so well explained. Made it all seem very intuitive. I loved it!
This introduction to Reed-Solomon codes was extraordinarily put together, and was presented beautifully and elegantly. Thank you, I had a lot of fun watching.
12:50 this moment was so satisfying and elegant that my heart skipped a beat
Thank you SO much! I have been trying to wrap my head around Reed Solomon for literal years and now I fully understand it!
Easily the best explanation of the topic of Reed-Solomon coding on TH-cam!
12:50 Up until this moment I was still confused. Then it hit me like a lightning bolt. Clever thinking!
Absolutely beautiful my friend. I remember my information theory teacher put some students to investigate and teach the subject and of course I did not learn a thing, until now thanks to this vid! You’ve got a new subscriber :)
The legend is back.
When the world needed him the most.
The Lagrange polynomial bit was so neat, absolutely loved it.
Beautiful explanation and visualization of the Reed Solomon Code.
Amazing! Love your videos
intuitive Reed-Soloman Codes explanation and Pokemon music, you sir are my hero today
Thank you so much for the visual explanation. Seeing all the equations on wikipedia didn't help much but this did!
Oh man, I love You! Tried to understand Reed-Solomon for AGES. Others simply >suck< at explaining this topic. I would love to see more details of practical implementation, e.g. space probes communications.
How does it deal with bit flips, so if a number is changed instead of dropped?
Great question! These are for "erasure errors" as they're called, where the packets get dropped. For bit flipping, it's actually the same algorithm, but a slight modification en.wikipedia.org/wiki/Berlekamp%E2%80%93Welch_algorithm
@@vcubingx An addendum video on that would be awesome! As someone casually studying error correction codes, this video was invaluable, thanks
Gao's extended Euclid decoder is the most efficient one so far: en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#Gao_decoder. However, using BCH type encoding with a fixed generator polynomial results in much faster decoders, that operate on n-k syndromes, instead of n symbols.
Great video, really like how you explained it! Just a remark on the final example - using 5 as an input in a mod 5 example shouldn't be done as it is the same as using 0 as an input - so if you didn't have the luck to loose the package 0, you'd end up with only 2 points (one being the superposition of input 0 and 5 which didn't get lost) and wouldn't be able to reconstruct the rest.
its super magnificent to me as I saw how the function is built based on 3 points, damn
I also came from 3b1b's Hamming video. What a time to be alive when there are resources like these available essentially putting some college lectures to a shame. Deducing ideas intuitively ourselves is a much better form of learning. How many times have I heard on QM or electrodynamics classes: "let's assume the solution is of this form" and indeed it works out in the end, but the magic is getting the feeling of that assumption in the first place, which is not really thaught. Even for someone who is well versed with math and IT jargon, these approaches give rise to great new perspectives.
Hi! I like your video very much. I think you did a great job explaining the method. I see a small issue about how the prime number is chosen, which in turn also depends on how the Lagrange interpolant is calculated. I see two options: either it is calculated directly in the field Fp (which I believe this is what you are doing), or it is calculated in the field of rationals numbers and then "converted" to have coefficients in the field Fp.
It seems to me that the first option is the best one. But in that case, the prime p should be chosen to be larger than number of packets too. This is to ensure that the extra packets don't contain redundant information. If you look at your final example, f(0) = f(5) = 2 mod 5, because 0 = 5 mod 5. Thus, if we lose say packets 2 and 3, the points to interpolate are (0,2), (3,1), (4,0), (5,2) = (0,2). Thus, there are really only 3 points, not 4, and we cannot recover the original interpolant.
If, on the other hand, the interpolant is calculated in Q and then converted to Fp, then we should have some justification that the denominators of the coefficients won't be multiples of p, as well as the numerator of the leading coefficient.
But, maybe I'm missing something... :-)
Most erasure codes are based on GF(2^n), where n is the number of bits per symbol. One exception for error correcting codes is PDF417, which is based on GF(929). As for your question, the prime p is normally larger than the number of packets, but it can be the same as the number of packets if the data points include 0: 0, 1, 2, 3, ... , p-1. However, most implementations of erasure codes are similar to Raid 6, which is based on an alternate encoding scheme, where encoding is based on a fixed generator polynomial, rather than a fixed set of data points.
I think in practice p will almost certainly be bigger than the number of packets, based just on the size of the packets. For example, if you have 256 byte packets, p will need to be greater than 2^2048, and you're not likely to want to send that many packets. :-)
I really wish I could have somebody teach me how to apply this to, say, a qr code. What would it take to generate the error correction bits by hand? Seeing it done in video form like this makes it actually not seem too difficult, but applying the knowledge somewhere else is pretty difficult.
I may be misreading your comment, but QR codes already do use Reed-Solomon error correction. The bits next to the bottom left alignment square specify how much.
at 13:00 I don't understand how the receiver can construct the Lagrangian polynomial constructed by the sender from 6 points whereas the receiver has only 4 points available ?
Remember, that the polynomial was actually constructed by the sender from 4 points, and the other 2 were added after the polynomial was constructed
@@antonionio7977 ha yes ! I missed this information so that is actually a polynomial of degree 4 ! Thanks ;)
ah! i was looking into RS for the sake of QR codes. but recently, i was using LPs to implement OR logic on secret keys. ie: 1 of 4 possible secrets suffice, by supplying 3 random values to pin down the curve when 1 value is supplied. this is really similar. if you have an array of 13 values, then sending 3 more allows you to send 3 more values on the polynomial. this is good if scratch locality doesn't have scratches longer than 3 values. thanks! this is very helpful.
LPs have lots of crypto applications as well. you can even implement this inside of Elliptic Curves, to do this arithmetic on encrypted values.
Amazingly produced video. Such a cool series of topics. Thank you!!!!
Great video, really enjoyed it.
Absolutely amazing video, thanks a lot!
Reed Solomon is a magic for me. I secured my photo album of 30 photos totalling 60 Megabytes, each photo is 2 Megabytes average. It created a 4.4 Megabytes of rescue data. now, even if I delete a photo, the rescure software (QuickPar) recovers that photo by using Reed Solomon algorithm. storing medias we use today are mostly flash memories, like SSDs or USB disks. bit rots may happen on those hardwares. your JPG photo file won't get unreadable when some of it's bits rotten, but your RAR archieve file would. so Reed Solomon is a life-saver assitant for reliably save files on long term..
A data problem that comes up is how to tell if your backed up files have been corrupted. The standard way is to hash the file, then later, hash the backed up version to see if they match. However, one problem that comes up is that when the new and old hashes don't match, it's hard to tell if the file went bad or the saved hash went bad. One answer is to keep three copies of everything, so hopefully two always agree. Another is to use error correcting codes. Using par2/parchive, we can create hash-like objects that store redundant data from the source file so that errors can not only be detected, but in some cases repaired. We can tell if the generated objects are valid or not, allowing easy distinctions between source files vs generated files suffering bitrot.
TH-cam seems to be joking
There was never a notification for the video and I thought you just stopped creating these :c
Glad to stumble upon it at least now tho
I think a good application of Reed-Solomon is used within TCP (OSI layer 4 ) or may be a parallel !
Beautiful concept lucidity explained.
The teaching is GREAT. The production is GREAT. The art style is *chefs kisses*. 🤌
Hey great vid!
Do you know if Reed-Solomon codes can detects errors? For example, when you send a message to your friend but the message is corrupted and you don’t know where it is corrupted, is there a way to know the location of this corrupted data?
Thank you!!
Yep! Great question, they actually require a slight modification to do that, but the idea is similar: en.wikipedia.org/wiki/Berlekamp%E2%80%93Welch_algorithm
Gao's extended Euclid algorithm (time complexity O(n^2)) is more efficient than Berlekamp Welch (time complexity O(n^3)), en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#Gao_decoder . Using BCH style encoding, where a fixed generator polynomial is used to encode is much faster, as the two most common decoders will have time complexity O((n-k)^2): en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#Berlekamp%E2%80%93Massey_decoder and en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#Euclidean_decoder.
Thank you so much for this video. It's amazing, seriously.
One thing I wonder is how would this be applied for a value that was changed instead of missed.
For an original message [1, 2, 3, 4, 5, 6] how would we at the other end fix it back if we got [1, 2, 3, 3, 5, 6], since we wouldn't know which packet was lost.
You are very talented. Such a good video
Thankyou greatly! I have no CS background but a reasonable grasp of pure maths. I had studied several other presentations of Reed-Solomon that were confusing and opaque. Your use and explanation of LaGrange interpolation was clear, elegant and easy to follow. I will be watching more!
this is the most beautiful thing I've seen in math
For an erasure only code, Raid 6 is more efficient, since a single erasure (or the first parity packet) can be corrected with XOR. For error correcting code, using the alternative BCH type encoding scheme (fixed generator polynomial known to both encoder and decoder) is more efficient. The most efficient original view decoder is Gao's extended Euclid decoder with O(n^2) time complexity, while the two most common BCH view decoders, Berlekamp-Massey and Sugyama's extended Euclid decoders have O((n-k)^2) time complexity. The Wikipedia article covers both original and BCH type encoders and decoders: en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction .
Really good educational material.Thanks !
I'm confused at 7:57. U were looking for x such that f(x) = 1, okay but then u plotted a graph for f(x) = 2 and why u were looking for f(1)=1 when the first point is (1,2), it makes sense to me search for f(1)=2... Shouldn't the l_1(x) be (x-3)(x-4)/3 then ?
Really great explanation
I don't understand if k=2 and we lost 3 packets, what is the problem ? In general if the number of packet lost is superior of k what is the problem ?
I think what you're trying to get at is if I lose more than k packets, then is the data recoverable?
The answer is mostly no, since we can no longer uniquely define a polynomial with the remaining packets. As such, you need to choose k wisely - too large, and you have too much data to send, too little, and you have a higher chance of losing all the data.
Thanks for the video!
You keep referring to packets beging 'lost' which suits this methodology of restoring data.
What happens if all packets make it through but some of the data gets corrupted? How is the original message recovered from the corrupted received data? Thanks!
This video explains it for if the packets go missing entirely, but what if they're just corrupted? How does the receiver tell which packets are bad and which ones it should use for the polynomial?
Many thanks for your great videos.
And I suggest making video about non-integer base of numeration.
One thing I notice: this can't actually correct _errors_, on its own, can it? Just known-missing values. If you have e.g. 4 messages with 1 corrective message and one of your messages is wrong, then any combination of 4 messages yields a (likely different) valid polynomial, I think. (It's possible that having extra spare messages solves the problem, basically by group vote.)
How high can k (number of last packets) be compared to n (data packets)?
Can you do a follow up to show how a bad value is detected and corrected?
Small thing at 6:12. If p is prime, then it forms a field. Otherwise it’s just a ring.
To confirm, the receiver also does the interpolation to form the equation, that can then be used to correct the error value?
Magnificent! Thank you for video :)
Great explanation! Thanks a lot
In your example, you need to go at least mod 7, to use 6 carrier packets. When you go mod 5, zero and five are equivalent, so f(0) and f(5) are automatically the same.
14:09 How do we know what numbered packets (you said packet 1 and 6 are lost) were lost? Is there some other method to find that?
It is mentioned in the video that information is received on the other end as in the order in which it has been sent and on the place of the numbers that has been lost shows error. Then, machine uses polynomial to find it.
Wow great video!!!
Do you have tutorial about the animation?
8 years after completing my engineering in Computers, I came to this video because i randomly got interested in how error correcting codes work.
Then i saw the part about Lagrange theorem, and i swear to God,i do remember the word and equations i was supposed to crunch but in college nobody told us what we are doing or why.
We were just supposed to write the final equation and multiply it and mark the equation as answer if Lagrange was written in the question.
Gosh, I wish i had seen this video back then 😅 at least i would have known what i am studying.
This is a common problem of a lot of instructors teaching different subjects. I faced it too. Instructors will tell you the steps to get the answer on the board, but don't really tell at the beginning of the lecture about what we're trying to achieve in the class, i.e. what does doing those steps help us achieve. Idkw instructors dont bother explaining the concepts first before writing a bunch of equations and steps on the board.
@@thjamy Exactly. It is as if we are some machine. We take numbers and keywords as inputs and perform some fixed calculation on them and spit out an output number.
Thanks a lot for your informative video. I just don't get one passage. From Lagrange to function with mod. Doing the calculation for the lagrangian polynomial the results will be: f(x)=(2x^3 -15x^2 +25x+12)/6. How Do you obtain f(x)=2x^3 +2 (mod 5) ? Thanks in advance
Do it mod 5!
f(x) = (2x^3 -15x^2 +25x+12)/6, like you said. Now,
6^-1 = 1 mod 5 (since 6 * 1 = 1 mod 5), so f(x) = 2x^3 -15x^2 +25x+12 mod 5. Then,
2 = 2 mod 5
15 = 0 mod 5
25 = 0 mod 5
12 = 2 mod 5
So, f(x) = 2x^3 + 2 mod 5
@@vcubingx thanks a lot!
beautiful explanation!
nice! what if you don't know which packet is corrupted?
Probably the best video explaining the subject out there. GOATED
9:20 You should probably mention this proof rests on the fundamental theorem of algebra which is very hard to prove.
Bruh great video keep it up
Why can you assume f(4) and f(5) are integers?
This is amazing.
why does p at 12:01 have to be prime?
Good question. Since the setup for lagrange interpolation involves division, we need every number to have a multiplicative inverse mod p. a^-1 mod m exists iff gcd(m, a)=1. If m is a prime p, then a^-1 always exists, since gcd(a, p) = 1 for all a.
there's also a famous extension of this by Galois to prime powers p^n (where p is a prime and n is a positive integer) but you have to add some more structure
Ok, it was bit complex and became boring in the middle but in the end, it put a sudden smile in face to realize how simple the basic behind reed-solomon is and the history comes from long way..!
I was working with video and was amazed by hearing reed-solomon that it can retrieve even burst packets.. and now I understand why..! Thanks for great explanation...!!
Your videos are quite interesting! I suggest speaking a little louder cause other voice in my house disturbs this other than that, this is interesting!!!
Mathematics insists in being useful. That's kinda beautiful if you ask me.
That's a very elegant way to put it
When I interpolate the points of (0,2) (1,4) (2,3) (3,1) with Lagrange polynomial, I get this equation: f(x) = (x^3)/3 - 5(x^2)/2 + 25x/6 + 2, which is not the same as your f(x)= 2(x^3) + 2. Am I missing some reduction part?
Your interpolation is right, what I think has not been mentioned in the video is that when you are interpolating mod n you no longer have only one correct answer e.g. you can add n to any polynomial which would not change its value mod n.
When doing the Lagrange interpolation, you should use modular arithmetic (mod 5). Then 3^-1 becomes 2 (modular multiplicative inverse under modulo 5), and x^2 and x are always multiples of 5 so they disappear.
This is incredible how old are you?
Erasure that’s cool. Now let’s see Paul Allen’s Error correction
Okay This is pretty epic
Nice video
The fact this actually works still feels like black magic
I dont know anything about coding but I’m curious why cyberpunk 2077 named an important character Solomon Reed?
Yeah, but you didn't tell us how exactly they know those were the packets that were lost, because you say "let's assume", but what if we don't assume?
And what if instead of losing, the data is modified? how do you know that packet was modified, because you said that is used on qr and barcode. where a single white pixels group could be shaded by a spot or a black pixels group could be over lightened
I underetood 10% of it.
THANK YOU 🤕😭😭😭😭
Thank you
wow its THE tony xin from that super good polish restaurant in berkeley called the hyper house
i've been exposed 😭
cool video
please sir tell me do I need to know Python before starting manim.
if yes than how much would be suffice.
I want to use little bit animation for my physics lectures, how much would it take me to learn how to make basic stuff.
is there any other better alternative of manim for my kind of work.
You covered erasure but here is the case of fixing errors?
I think more education shall be like this. Instead of purely starting from Abstract, start from actual usage of it and decode it to present the theory. That way you hook interest and connect math to real world easier.
2+4=6, pls fix thx
this is how maths should be taught (langrage polynomials) and not through ugly formulas that mean nothing to the uninitiated
I have a project where i need to do a Reed-Solomon encoder and decoder, im so cooked i dont understand any of this shit
Sooooo...who was Reed Solomon? :P
There is the easiest way to solve quadratics .....it surpasses even po-shen loh's method .....and this can lay foundation to solve cubic and quartic.....
I can make a video on it if you all want.....lemme know
Here because of Veritasium’s QR video
No branch of mathematics is useless. It will have some use, whether after 50 years, 500 or 5000 years.
I member many years ago one Chinese boy copy my telephone QR. Than my telephone got twins to me . scared 😳