Error Correcting Curves - Numberphile 

I thought they used binary and not decimal encoding. would it not be untwoable?

@@TaohRihze Reed-Solomon in binary is simpler to understand and implement

@@TaohRihzeBa-dum tish!

@@TaohRihze You have to account for inflationary language. Without that things would be twoderful.

@@allanolley4874 That's a deep cut from the 1940s.

Funny seeing you here

I'm a fan.

@@aidanhennessey5586haha i was wondering if this would happen

What class was it?

Also, the extra numbers need to be float instead of integers, no? I can't see how it can be done with only integer y's.

@@tinglin6121 Unfortunately the end of the explanation is rushed. I think you're right, you construct a polynomial using the sent data as coefficients - these can be integers, because it's the input, you're not trying to achieve any particular curve on a graph, whatever you get is fine. Then you pick a point or two (or more) on the graph, and at that part it could be challenging to pick a point which both x and y are integers. This brings the question of precision and I imagine as many things in life, the actual error correction is full of complex nuances like finding the most optimal precision and number of points. Also there was no example on how it actually looks when you detect a mismatch: you got your 16 values + 2 additional points, but those 2 additional points don't lie on the curve drawn by the polynomial defined by the 16 points - so how do you find which is the offending point, and then how do you use the 2nd value to correct the error? There might be some smart math behind that, but it wasn't presented.

*His questions

Yeah. In this case he asked a very on-point question -- he asked whether the maximum number of random points that a curve interpolates is also the minimum number of points that defines the curve. The answer is yes, as explained later in the video, but unfortunately it seems like the prof misunderstood his question :(

The real magic is the interleaving. Reed Solomon can't help you if the whole code is unreadable

thank you.

I can't imagine why you'd use forward error correction for a credit card number when you could just detect an error and ask the sender to resend that packet. It's typically only used for very low latency requirements like live video, or for situations like storage or digital TV broadcasts where it's impossible to request a resend. But I guess it's just an example.

@@gdclemo Yes it is just an example, however asking the sender to send again isn't always an option even ignoring latency demands. For example, imagine archival. There, your primary struggle is against temporal corruption: if your archival solution survives longer than the original work's medium, you don't get to ask for the original work again when corruption occurs.

@@mark.panghyUzcard does, it is from Uzbekistan. Also, some credit cards from the communications industry or used in healthcare may start with 8.

@@gdclemo Well, the website asking for the number might not explicitly do it, but all of the communication between both ends is error-corrected at various levels of he networking stack.

Do any of those correct for *missing* bits? As in, let's say I send 50 bits of real message encoded in 100 total bits, and a chunk of 10 bits in the middle just never arrives at the destination, can one of these codes allow the receiver to reconstruct the 50 bit real message from the 90 that did arrive?

@@maxbaugh9372 Replace the missing bits with random ones at the receiver and you are back to the original situation. This is not the most efficient way, because by using the information the bits have been "erased" you can optimize the error correcting code and the receiver, but it would still work. You can research about Information Theory to find out all the mathematical limits and awesome stuff you can do.

@@maxbaugh9372 if I am not wrong, they can, since bits comes in packages, also, missing bits are registered as bits with 0 value. but I am not sure

​@@maxbaugh9372usually you know how many bits the message is, so you would add the missing bits as zeroes. But that probably works only if you know where the bits are missing.

This is generally not a problem because signals are clocked, if a link is functioning at all the both sides will agree completely about how many bits were sent.

And ata disks and fpgas have a niche for finite fields calculations

QR codes also use Reed-Solomon.

this seems like a very easy crossover with computerphile to look at the actual implementation of these codes and what kind of algorithms they're using

Tq

MORE MATH.

you should pin this

Glad I checked the comments. Is there a reason to post this here and not in the description?

this seems like a comment that traveled through time as the comment is from 1 day ago, but the video got published 13 hours ago

Yeah it's okay

Nah

I think you use xor to make (and check) whether an array is odd or even (one of the easiest to understand [and therefore to implement] error checking [and potentially self correcting, if you make it two dimensional] methods.)

You can mitigate against this problem by the sender doing 1) encode 2) permute the coded bits 3) send. The receiver must thus do 1) receive 2) unpermute the received bits 3) decode. One sort of permutation is called interleaving. But permuting bits is independent of encoding...

Do you know of any books that explain the theory in your last paragraph? I learned this from a book about computer networking, and if I recall I was annoyed that this leap was made. In fact, I had this type of annoyance several times during my engineering degree.

@@DF-ss5ep Discrete mathematics, usually a required course for computer science, "Discrete Mathematics with Applications", is the book I would recommend, Will give you an intro to things like fields, especially in the section about encryption, it should give you enough info to actually gain some intuition. The more rigorous Abstract Algebra stuff is a bit above my knowledge.

It's linked in the description.

I think technically no, you still need two extra, but I’m not sure it’s terribly important. See, the 16th digit is only non-random if you enter your credit card number correctly. If you make a mistake, it potentially becomes 16 random numbers. Those 16 numbers when transmitted electronically could have further errors, so you still need two extra digits on top to catch and fix. However, if you entered an invalid credit card number in the first place, I’m not sure how important it is to catch any errors that happen afterwards, but from a coding regulation perspective you probably want to just to catch the edge cases.

Depends on implementation. The credit-card code catches any single-digit error, but might fail to catch that there are two errors. So if you get 17 digits that you detect as wrong, there will likely be 2 combinations of 16 digits subsets that produce legal credit card number, so it is likely not enough to be self-repairing, but using it might still be useful with some other tricks.

Audio CDs also use Reed-Solomon for error detection and correction. The 'filtering' happens when there are errors that the Reed-Solomon code can't correct.

@@edwardfanboy oh, okay. but there's definitely a difference in data they contain. maybe a CD for computers contains even more correction methods. but you definitely lose some storage capabilities. (and no, I'm not talking about discs that store more then 650 megabytes which just use more if the available area.) I mean, that's all aside this other encoding method where way more physical "pits" get used to represent digital bits. I think you need fourteen to represent eight. that's because you need to constantly focus the laser (it's about a square millimeter when it hits the surface to be insensitive towards scratches) and can't just have eight consecutive zeros. it *must* change after two spots or the laser will lose focus and alignment. this kinda like provides the same function as the punched sides of analog film, so to speak.

@@HxTurtle CD's, Barcodes, QR codes, even ASDL all have encoding schemes that prevent the continuous zero issue, But we usually don't call that data, it's something extra from the data payload that's being sent and it's below the EC. The PCM audio stream coming out of the CD is identical to the master copy used to make the CD, If the data can be repaired with EC, the issue is most shitty CD rippers put the CD drive in audio playback mode which just ignores errors and keeps playing to maintain tempo, and not data read mode which will try reading the data sector again. Remember Audio CD's were designed in the 80s to be played on affordable hardware with kB of RAM, you don't have 10s of buffering to go back and attempt to reread the data like we do with RU-vid, or can wait a few extra seconds for the game to load like on the PS1.

If I remember right, audio CDs have just enough error detection to detect a bad sample and recreate it from its neighbours, and only protect the most significant bits of the sample. Data CDs need much more error correction to recreate every bit perfectly.

The more you learn about data mechanisms, the more wonderful it is that all of it can be stored so flawlessly.

Knowing Lagrange's Interpolation and working out a few programming examples may help in understanding the original problem.

@@abhijitborah If someone is completely lost it might be a bit much to expect them to be able to jump straight to understanding and applying the maths here, no?

If you also look at the second video, you have two new pieces of data, and can correct the error between your neurons. :)

All you need to do is add another connection of neurons

​@@abhijitborahI think that was a joke, fyi

Of what? Is numberphile aimed at cognoscenti or ordinary curious people? If the second we need more explanation

@@jeremykeens3905in my case it's admittedly closer to the former. I'm a software developer for the airline industry, the hardware I work with uses error correction codes for all sorts of things like passport barcode scans and so on. I've known for a long time that polynomials are used for error detection and recovery but I've never really intuitively understood why.

You should be the guest

And also because sending 48 bytes instead of 16 bytes would make no noticeable difference to the transmission time. It was a pretty bad choice of example.

@@RFC3514Perhaps, but this isn't computerphile.

They pointed it out themselves. Their use of the word "random" is hiding some mathematical details that are too much of a tangent to get into. The tldr is that that those cases are a measure 0 set and so come up with 0 probability so we are mathematically justified in ignoring them (that doesn't say that they are impossible however). If you really want you could say it is a circle with a radius of infinity

s/random/generic/

A straight line is also often considered as a circle with basically infinite radius. Then even if they are on a line, we can fit such a circle

Well, this video provides the thought process, implementation of course need to solve more problems. But still, imagine you need to send milion digits and expect 10% to get lost on the way. With naive solution, you might need grahams number of digits to send, while with this solution, you actually need to send little over 1,2 milion digits to be reasonably sure the code will still fix itself on the other side.

The precise answer might sound strange to you. If the noise is a continuous random variable, the answer is 0 (think gaussian distribution or bell curve). If the distribution has discrete components, or delta functions (think flipping a coin), and they are perfectly placed, it can be non-zero, but this would never happen in practice. Is it POSSIBLE for a random error to produce a new polynomial and evade detection? Yes, it is an event that exists in the event space (in math jargon this is called the sigma field). But it is probability 0. It’s a quirk of probability theory but these don’t mean exactly the same thing. Essentially, it CAN happen, but it WON’T ever happen even if you repeat the random trial an arbitrary number of times.

A variant maybe? Who knows?😂

That way if there was an error in any of the videos we can use the other two videos to correct it

I suppose as you know the polynomial, you just correct this erroneus number to the output of the polynomial at the exact same input

The coordinates are spaced out equally on the x axis. The x value is just the position of the number in the stream of data. There is one unique value generated by the polynomial for each position on the x axis and it is the value of numbers at their chosen x coordinate. To reconstruct the missing number you just put its position in the stream into the polynomial function.

I think you can test each of the 18 points one by one. When testing the i-th point, you take the set of the other 17 points and find their interpolation. If the erroneous point is in this set, then the interpolation will have degree 16. But if the erroneous number isn't included in the set, then the interpolation of the points will be the original polynomial of degree 15. So, when you test the erroneous point, you find that it's in fact errouneous, as well as the original polynomial. From the point you can take its value of x an by evaluating the polynomial you can get the corrected value.

@@Unifrog_ aah thank you! This was the key piece of info I'd missed - that the x value is just the position in the stream!

Curious analogy. 😐

@@warlockpaladin2261 If you'd prefer to substitute a secret chicken or soft drink recipe, that's totally fine.

If you don't have a degree 15 polynomial when you look at the 18 numbers, you can look at the eighteen different sets of 17 numbers. One of them will exclude the error, so will be 17 numbers that all lie on the degree 15 polynomial, while the other seventeen will each be the 1 error and 16 correct values. Since the 16 correct values define the correct degree 15 polynomial, which we know the error is away from, none of them will give a degree 15 polynomial. So if there's at most one error, there will only be one degree 15 polynomial that fits 17 of the points given, and that will be the correct curve.

Adding the 18th point means you now effectively have 17 different sets of 17 different points, each excluding a single point. If there's one error, all the sets except the one that doesn't have the bad value will detect the error. You can then use the set that doesn't have the error to determine the correct value for the corrupted piece of data.

Something does appear to be a bit off in comparison to other Numberphile videos. I am curious to the reason.

Maybe he had explosive diarrhea

In practice, this is usually done over finite fields. So in other words, your polynomial can only take on a very limitied set of values to begin with. For example only the values 0, 1, 2, 3, 4, 5 and 6. No real numbers, no rational numbers, nothing in between, just these seven values. So if there is an error, it may change a 4 to a 6, or something. This is being done because calculating with these limited set of numbers is quicker than with the entire rational numbers.

In real applications the computation is usually done over a finite field rather than the real numbers, which does not have this problem

Yes!

CD's actually use this exact mathematics.

That's where this algorithm gets into the really obscure math. The answer is that instead of real (or rational) numbers, you use something called a finite field, which has addition, subtraction, multiplication, and division like rational numbers, but there are only 256 of them and the answers don't agree in any way with the real numbers. They were discovered as a theoretical exercise, but they have all the necessary properties for Lagrange's Interpolation Theorem to be true. Of course, the graphs really don't look like anything, because there isn't anywhere between two points to draw a line.

If you know the x-co-ordinates of the points you're looking at (and for a method like this, you'll generally pick sensible x values in advance, so most of the work only needs to be done once) you can work out the general form of the polynomial at those points (so at x=1, you have something like a+b+c+d+e+f+g+h+i+j+k+l+m+n+o+p) which, when you substitute in the y values you receive will give you a bunch of simultaneous equations. Because of the added structure of these equations all coming from the same underlying polynomial, you can solve them more efficiently by constructing a "divided difference" table - an inverted triangle where the first row is just the original y values, then in each subsequent row, each entry is the difference between the two entries above (right minus left) divided by the difference between the x values corresponding to the base of that entry's triangle (again, right minus left). So, for example, in the second row, below and between y1 and y2, you'd get y1,2 = (y2 - y1)/(x2 - x1), while in the third row, below and between y1,2 and y2,3 you'd get y1,3 = (y2,3 - y1,2)/(x3 - x1). After filling out the divided difference table, the leading diagonal pretty much lets you read off the coefficients for the polynomial with minimal effort. It seems complicated to describe, but if you try actually doing it a couple of times, it should all make sense :)

Yes, if your symbol error rate is constant you get more errors as you send more data. To counter this, the data is split into chunks and the codes are applied chunkwise to get reasonable error rates.

As I understand it, the numbers you want at the end are the coefficients, not the points. That's the data you're trying to send. When the receiver looks at the points, and sees one is wrong, they can just discount that one because they will still have the coefficients derived from the other 17 points. There's no need to calculate what the false point should've been.

You'd have an agreed set of x co-ordinates, and just send the y values.

In the (very artificial) example used here, the "x" values are the position of the digit. So, always 1, 2, 3, ... ,15, 16. That''s how you can recalculate the correct digit if one of them doesn't fall on the curve (otherwise you would only have error detection, but not correction).

Some of the basic ideas are the same, but the details of Hamming Codes are different enough that they'll be strictly limited in their utility.

likely the switches pre-date the bookcases. you would think just relocate the switches, but there might not be a more suitable location. the most likely answer is that doing so requires union labor and significant cost. it is less expensive and more efficient simply to cut holes in a bookcase. I've heard stories very similar to this.

Yeah sure it's like quite similar but also different in some aspects and a lot smaller

Though for me too especially starting minute 12:00, it goes quickly ^^ My understanding is same as yours except that receiver does not find f(x) based on polynomial. He finds polynomial based on f(x) that he received. Basically sender sends f(x), not polynomial. Receiver tries to create polynomial based on all f(x) received and if not possible, he tries one by one with all f(x) minus one different f(x) for each try. When he succeeded, he sees which f(x) has to be removed to success and this f(x) is the error. If somebody more knowledgeable than me could confirm or (more probably) correct my understanding, it would much appreciated :)

@@OldFreeman I still don't understand...so you would need to send x AND f(x) right? or am I missing something, when you send a point dont you need to send (x, f(x))? So what is actually being send it n+2 points where every point is 2 numbers (one for x, and one for f(x))?

@@some1rational thank you for your question. Thanks to you I rewatched video (I did not remember) but this time I understood better. You are correct, you need to send the whole points so you need to send x and f(x) of each point. However, for each customer sending his credit card number, you can use the same x… only the f(x) will vary. Therefore you can consider that the x are fixed for all credit cards sent so you don’t need to send x each time, only the f(x). This applies for the 2 extra points too, you can use x fixed and just send n+2 different f(x). In case one f(x) does not lie on the polynomial, you know there is a mistake, you know where AND you calculate the correct f(x) because x is fixed and you have the polynomial formula to calculate the correct f(x). I hope that it makes sense (and that I am right… not entirely sure 😂👍)

@@OldFreeman haha no worries, thanks for the input! I think I'm starting to grok the idea now, it appears (as you say) that the "x-coordinates" are fixed/agreed-upon between client and server; thus the client needs only to send the "f(x)"s. It sounds like from other resources I'm reading online (mainly wikipedia) though, that this method of error correction is mostly used for error correction on data storage systems (like scratches on CDs or DVDs, showing my age here). I wish there was a more in-depth applied example of how/where this is used for error correction when transmitting data over the internet, but I have yet to find a resource that meets that criteria 😓(guess I could ask ChatGPT haha...)

Yes, just 2 extra would be insufficient for larger numbers, and the polynomials would become too unwieldy as well. Generally, the message will be broken into smaller chunks, and each chunk would then get the +2 extra numbers. Additionally, adding more extra numbers lets the code correct more errors. Adding 4 extra numbers to each chunk would let us correct 2 errors instead of just 1. When these codes are implemented, there's a balance between choosing the size of the chunk and how many extra values each chunk gets. Making smaller chunks and adding more extra values to each chunk allows the message to survive more errors, but eventually starts adding more and more bloat to the value.

You can literally just choose any different point.

Wouldn't happen with random points just like 3 lying on the same line or 4 on the same parabola cause lines and curves have 0 density in 2 dimensions

for lagrange interpolation, the points need to be different. However given a point x with values f(x) and f‘(x) (the derivatve at the point x) we can also find curves. This is called Hermite Interpolation.

to encode data with the reed solomon code, every point gets assigned different x values. if thats not the case, no curve of any function can cover all points. every x value in a funcion has exactly 1 value, or no value if its something like the root of a negative number for negative x values.

(1) Geometrically, that's fine. You just use a vertical line. If you're requiring y = f(x) then indeed it's a problem. Fortunately, (2) since the points are random, the probability of that happening is extremely small (actually 0).