If you enjoyed the video, please consider subscribing :)
@harsh8899
2 жыл бұрын
Bhaiya kya mast KZitem channel banaya hai🔥🔥🔥
@tonyxin4186
8 ай бұрын
yes papa!
@narayanbandodker5482
2 жыл бұрын
Missed opportunity to title the video "Learn how to Reed Solomon codes"
@nycki93
Ай бұрын
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!
@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!
@ThbopCoder
3 ай бұрын
Thank you so much for the visual explanation. Seeing all the equations on wikipedia didn't help much but this did!
@jgilferez
2 жыл бұрын
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... :-)
@rcgldr
2 жыл бұрын
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.
@gcewing
Жыл бұрын
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. :-)
@augustus6660
Жыл бұрын
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.
@nerses2654
Жыл бұрын
Really good educational material.Thanks !
@alexhooper27
3 ай бұрын
Small thing at 6:12. If p is prime, then it forms a field. Otherwise it’s just a ring.
@fujinafiul6044
11 ай бұрын
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...!!
@paulofelipe2780
2 ай бұрын
Wow great video!!!
@cossibility7019
2 жыл бұрын
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!!
@vcubingx
2 жыл бұрын
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
@rcgldr
2 жыл бұрын
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.
@christophercrawford641
4 ай бұрын
nice! what if you don't know which packet is corrupted?
@josephang9927
10 ай бұрын
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.
@alexyangfox
Жыл бұрын
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?
@qqtrol1774
Жыл бұрын
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.
@Crazytesseract
Жыл бұрын
No branch of mathematics is useless. It will have some use, whether after 50 years, 500 or 5000 years.
@mastershooter64
2 жыл бұрын
Lmao imagine caring about applications and not doing extremely abstract math without a care in the world *cringe* /s
@1XxDoubleshotxX1
2 жыл бұрын
FIRST
@amelaamelajiang493
Жыл бұрын
And he name is call solomon
@amelaamelajiang493
Жыл бұрын
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 🤥
@dylanparker130
2 жыл бұрын
How have I never come across Lagrange polynomials?! That was one of the most beautiful pieces of maths I've ever seen!
@wigglesworthmcgubbins
2 жыл бұрын
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
@dylanparker130
2 жыл бұрын
@@wigglesworthmcgubbins Absolutely! If only I'd studied Numerical Analysis (all those years ago!)
@Amine-gz7gq
2 жыл бұрын
yeah it's mind blowing, I learned how to create a polynomial whose curve passes through n points thanks to this video ! KZitem/Internet is a mine gold to learn stuff the right way.
@ukissrulez
Жыл бұрын
@@Amine-gz7gqliar
@Amine-gz7gq
Жыл бұрын
@@ukissrulez about what ?
@glitchy_weasel
11 ай бұрын
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? 🤔
@vcubingx
9 ай бұрын
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
@riku5543
2 жыл бұрын
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.
@cadekachelmeier7251
9 ай бұрын
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.
@roy04
4 ай бұрын
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.
@tigranrostomyan9231
3 ай бұрын
Same!!
@arnavvirmani8688
2 жыл бұрын
2+4=6, pls fix thx
@vesk4000
Жыл бұрын
Wow, this was so well explained. Made it all seem very intuitive. I loved it!
@Kaepsele337
2 жыл бұрын
How does it deal with bit flips, so if a number is changed instead of dropped?
@vcubingx
2 жыл бұрын
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
@ivolol
2 жыл бұрын
@@vcubingx An addendum video on that would be awesome! As someone casually studying error correction codes, this video was invaluable, thanks
@rcgldr
2 жыл бұрын
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.
@victorscarpes
2 жыл бұрын
Mathematics insists in being useful. That's kinda beautiful if you ask me.
@tenix6698
2 жыл бұрын
That's a very elegant way to put it
@Amara87387
Жыл бұрын
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
@ethanthiebaut2596
2 жыл бұрын
Amazing! Love your videos
@bernardoramirez1759
2 жыл бұрын
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 :)
@amelaamelajiang493
Жыл бұрын
I member many years ago one Chinese boy copy my telephone QR. Than my telephone got twins to me . scared 😳
@WaarDoz57
Жыл бұрын
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 ?
@vcubingx
9 ай бұрын
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.
@Kong9901
2 жыл бұрын
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 ?
@antonionio7977
2 жыл бұрын
Remember, that the polynomial was actually constructed by the sender from 4 points, and the other 2 were added after the polynomial was constructed
@Kong9901
2 жыл бұрын
@@antonionio7977 ha yes ! I missed this information so that is actually a polynomial of degree 4 ! Thanks ;)
@rcgldr
2 жыл бұрын
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 .
@prometheus7387
2 жыл бұрын
12:50 Up until this moment I was still confused. Then it hit me like a lightning bolt. Clever thinking!
@yasam9311
Жыл бұрын
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..
@PvblivsAelivs
Ай бұрын
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.
@vladimirpezo3734
2 ай бұрын
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.
@nomionz4150
9 ай бұрын
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 ?
@comeycallate9959
3 ай бұрын
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
@cutwir3317
11 ай бұрын
I dont know anything about coding but I’m curious why cyberpunk 2077 named an important character Solomon Reed?
@sporefergieboy10
7 ай бұрын
9:20 You should probably mention this proof rests on the fundamental theorem of algebra which is very hard to prove.
@fyu1945
2 жыл бұрын
12:50 this moment was so satisfying and elegant that my heart skipped a beat
@segganew
12 күн бұрын
Why can you assume f(4) and f(5) are integers?
@thisisrr1
2 жыл бұрын
Great video, really enjoyed it.
@Amine-gz7gq
Жыл бұрын
this is how maths should be taught (langrage polynomials) and not through ugly formulas that mean nothing to the uninitiated
@kennethng8346
9 ай бұрын
Can you do a follow up to show how a bad value is detected and corrected?
@sporefergieboy10
7 ай бұрын
Erasure that’s cool. Now let’s see Paul Allen’s Error correction
@vinidugeevaratne6008
2 ай бұрын
this is the most beautiful thing I've seen in math
@hashhoomy
Жыл бұрын
You covered erasure but here is the case of fixing errors?
@nuwanda923
8 ай бұрын
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
@vcubingx
8 ай бұрын
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
@nuwanda923
8 ай бұрын
@@vcubingx thanks a lot!
@chebmaster1791
5 ай бұрын
You are very talented. Such a good video
@jupa7166
9 ай бұрын
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.
@kodirovsshik
2 жыл бұрын
KZitem 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
@pi-meson7677
2 жыл бұрын
The legend is back. When the world needed him the most.
@rahulshah1593
2 жыл бұрын
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
@TomHutchinson5
Жыл бұрын
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.
@Vynnsounnet
4 ай бұрын
Probably the best video explaining the subject out there. GOATED
@theeternal6890
Жыл бұрын
I underetood 10% of it.
@martingeorgiev999
Ай бұрын
The Lagrange polynomial bit was so neat, absolutely loved it.
@xsup_8137
3 ай бұрын
THANK YOU 🤕😭😭😭😭
@nadavshemesh1231
9 ай бұрын
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.
@youtuber_nr3504
Жыл бұрын
How high can k (number of last packets) be compared to n (data packets)?
@GoddamnAxl
Жыл бұрын
intuitive Reed-Soloman Codes explanation and Pokemon music, you sir are my hero today
@cycv5881
6 ай бұрын
Beautiful explanation and visualization of the Reed Solomon Code.
@nahzor
2 жыл бұрын
To confirm, the receiver also does the interpolation to form the equation, that can then be used to correct the error value?
@bat_man1138
9 ай бұрын
Nice video
@omarsweidan4550
Жыл бұрын
Easily the best explanation of the topic of Reed-Solomon coding on KZitem!
@mahmoudalbahar1641
2 жыл бұрын
Many thanks for your great videos. And I suggest making video about non-integer base of numeration.
@darwinschuppan8624
Жыл бұрын
The fact this actually works still feels like black magic
@mbabb
2 жыл бұрын
Amazingly produced video. Such a cool series of topics. Thank you!!!!
@pilot615
2 жыл бұрын
Magnificent! Thank you for video :)
@aashsyed1277
2 жыл бұрын
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!!!
@annielee3035
Жыл бұрын
wow its THE tony xin from that super good polish restaurant in berkeley called the hyper house
@vcubingx
Жыл бұрын
i've been exposed 😭
@sumitprajapati821
2 жыл бұрын
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?
@sniper6233
2 жыл бұрын
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.
@FelipeMontealegreS
Жыл бұрын
This is incredible how old are you?
@naaahini3799
Жыл бұрын
Do you have tutorial about the animation?
@santanusaikia8848
Жыл бұрын
Beautiful concept lucidity explained.
@Manu-lc4ob
11 ай бұрын
Great explanation! Thanks a lot
@antonionio7977
2 жыл бұрын
why does p at 12:01 have to be prime?
@vcubingx
2 жыл бұрын
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.
@firebrain2991
2 жыл бұрын
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
@shans2408
Жыл бұрын
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.
@thjamy
Жыл бұрын
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.
@shans2408
Жыл бұрын
@@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.
@felixma5731
2 жыл бұрын
Bruh great video keep it up
@shaswatabanik7673
Жыл бұрын
Really great explanation
@johndwolynetz6495
2 жыл бұрын
Okay This is pretty epic
@yousefawad57
Жыл бұрын
Thank you
@mathsciencefancier
2 жыл бұрын
V cubing X
@michaelvanstraten4390
2 жыл бұрын
This is amazing.
@andremuller3497
2 жыл бұрын
beautiful explanation!
@porter105
2 жыл бұрын
💖 ρɾσɱσʂɱ
@yashnarvariya4725
2 жыл бұрын
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.
@gaganpardhi0111
Жыл бұрын
The teaching is GREAT. The production is GREAT. The art style is *chefs kisses*. 🤌
Пікірлер: 124