What are Reed-Solomon Codes? How computers recover lost data

An introduction to Modular Arithmetic, Lagrange Interpolation and Reed-Solomon Codes.

The source code for the animations can be found here:

Follow me!

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

[vcubingx]

If you enjoyed the video, please consider subscribing :)

[dylanparker]

How have I never come across Lagrange polynomials?! That was one of the most beautiful pieces of maths I've ever seen!

[roy]

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.

[narayanbandodker]

Missed opportunity to title the video "Learn how to Reed Solomon codes"

[nycki]

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!

[glitchy_weasel]

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? 🤔

[vesk]

Wow, this was so well explained. Made it all seem very intuitive. I loved it!

[Amara]

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

[bernardoramirez]

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 :)

[nadavshemesh]

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.

[JonathanKayne]

Thank you SO much! I have been trying to wrap my head around Reed Solomon for literal years and now I fully understand it!

[fyu]

12:50 this moment was so satisfying and elegant that my heart skipped a beat

[prometheus]

12:50 Up until this moment I was still confused. Then it hit me like a lightning bolt. Clever thinking!

[omarsweidan]

Easily the best explanation of the topic of Reed-Solomon coding on Youtube!

[martingeorgiev]

The Lagrange polynomial bit was so neat, absolutely loved it.

[cycv]

Beautiful explanation and visualization of the Reed Solomon Code.

[jgilferez]

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... :-)

[ThbopCoder]

Thank you so much for the visual explanation. Seeing all the equations on wikipedia didn't help much but this did!

[yasam]

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..

[riku]

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.