What are Reed-Solomon Codes? How computers recover lost data
Vložit
- čas přidán 12. 06. 2024
- An introduction to Modular Arithmetic, Lagrange Interpolation and Reed-Solomon Codes.
Sign up for Brilliant! brilliant.org/vcubingx
Fund future videos on Patreon! / vcubingx
The source code for the animations can be found here:
github.com/vivek3141/videos
Follow me on Twitter for updates/sneak peeks! / vcubingx
Sources for the video: docs.google.com/document/d/1s...
Follow me!
Website: vcubingx.com
Twitter: / vcubingx
Github: github.com/vivek3141
Instagram: / vcubingx
Patreon: / vcubingx
Music, by ChillHop and GameChops (In Order):
Mommy x Philanthrope - Embrace
GameChops - Route 113
Knowmadic - Faces
Idealism - Still
GameChops - Azalea Town
Chapters:
0:00 Introduction
2:02 Modular Arithmetic
6:12 Lagrange Interpolation
11:12 Reed-Solomon Codes, Putting it together
14:50 Outro
15:33 Brilliant Ad
16:33 Outro
Tags: Reed-Solomon Codes, Lagrange Interpolation, Finite Field, Error Correcting Codes, Modular Arithmetic, Polynomial Interpolation, Reed Solomon Codes - Věda a technologie
If you enjoyed the video, please consider subscribing :)
Bhaiya kya mast CZcams channel banaya hai🔥🔥🔥
yes papa!
Missed opportunity to title the video "Learn how to Reed Solomon codes"
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
@@wigglesworthmcgubbins5837 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 ! CZcams/Internet is a mine gold to learn stuff the right way.
@@Amine-gz7gqliar
@@ukissrulez about what ?
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
Wow, this was so well explained. Made it all seem very intuitive. I loved it!
Probably the best video explaining the subject out there. GOATED
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
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 :)
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 CZcams!
Amazingly produced video. Such a cool series of topics. Thank you!!!!
Amazing! Love your videos
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.
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
12:50 Up until this moment I was still confused. Then it hit me like a lightning bolt. Clever thinking!
Beautiful explanation and visualization of the Reed Solomon Code.
Great video, really enjoyed it.
Really good educational material.Thanks !
Beautiful concept lucidity explained.
intuitive Reed-Soloman Codes explanation and Pokemon music, you sir are my hero today
You are very talented. Such a good video
Many thanks for your great videos.
And I suggest making video about non-integer base of numeration.
beautiful explanation!
Great explanation! Thanks a lot
Really great explanation
Magnificent! Thank you for video :)
The teaching is GREAT. The production is GREAT. The art style is *chefs kisses*. 🤌
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...!!
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..
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 .
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. :-)
CZcams 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
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.
This is amazing.
Bruh great video keep it up
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.
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 ;)
To confirm, the receiver also does the interpolation to form the equation, that can then be used to correct the error value?
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.
Nice video
Mathematics insists in being useful. That's kinda beautiful if you ask me.
That's a very elegant way to put it
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
Okay This is pretty epic
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.
Can you do a follow up to show how a bad value is detected and corrected?
I underetood 10% of it.
How high can k (number of last packets) be compared to n (data packets)?
Do you have tutorial about the animation?
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.
This is incredible how old are you?
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.
Erasure that’s cool. Now let’s see Paul Allen’s Error correction
9:20 You should probably mention this proof rests on the fundamental theorem of algebra which is very hard to prove.
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!!!
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 ?
nice! what if you don't know which packet is corrupted?
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!
2+4=6, pls fix thx
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.
THANK YOU 🤕😭😭😭😭
wow its THE tony xin from that super good polish restaurant in berkeley called the hyper house
i've been exposed 😭
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?
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.
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.
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
You covered erasure but here is the case of fixing errors?
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
this is how maths should be taught (langrage polynomials) and not through ugly formulas that mean nothing to the uninitiated
I member many years ago one Chinese boy copy my telephone QR. Than my telephone got twins to me . scared 😳
V cubing X
💖 ρɾσɱσʂɱ
No branch of mathematics is useless. It will have some use, whether after 50 years, 500 or 5000 years.
FIRST
And he name is call solomon
Lmao imagine caring about applications and not doing extremely abstract math without a care in the world
*cringe*
/s
I go to police department i go to kreem Musa office the lady no answer back . .i go to Patrick .no see body.every ..... Belize is big trouble ..thing is 🤥
The legend is back.
When the world needed him the most.