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

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.

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

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

Yeah it's okay

Nah

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

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.

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 UKposts, 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

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.

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.

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

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

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.

Curious analogy. 😐

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

It's linked in the description.

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

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

CD's actually use this exact mathematics.

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

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!

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.

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.

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.

The original number is what get sent, the credit card number (in truth it would be encrypted but that's another whole level of complexity that's not necessaryto know about for error correction). This is an error correction technique, it is determining what was received is what was sent, it is not trying to fix what was sent in the first place if the person entered the wrong credit card number, it's just fixing if there has been an error in transmission (I.e. if noise had messed up the message somehow along the way). If the sender typed in a wrong number as part of the credit card number, then there is no way the receiver can know this. However, if in the sending of the credit card number a digit got messed up, then this technique could hello you determine what value was out of place. It is an error correction technique, not an original number verifier. Perhaps this might help as an explanation If someone is saying MY DOG HAS FLEAS out loud but because of the wind, the receiver hears MY DOG HAD FLEAS this error correction technique would help you determine that the word HAD should have been HAS If the original person had accidentally said MY DOGS HAD FLEAS you would not know they said something wrong and this technique cannot fix the wrong original intended message because this is error correction, not original message verification. You need to do other things to verify the original message before the message was ever sent If you want original message verification. Hopefully my crude attempt at explaining things helped

@@stultuses Thank you for trying, but this does not address my confusion. In the original discussion about how to check the credit card number, the naive solution was to double each number. So I understand exactly what was transmitted. Two 8's, two 4's, two 3's, and so on, until you have sent 32 total digits. Then triple-send in case one of a double-sent pair is corrupted. Sent 48 digits. Fine. Then we discuss Reed-Solomon and the functions and all of that. What *actual values* need to be sent for that to work? The credit card number plus _what else?_ A few extra digits? A binary code? Something else?

Yes!

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.

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.

It seems like that would work, but it turns out that including a wrong point messes up all the coefficients, so none of them agree with the correct answer or each other at all.

If you have one errored number, then each set of 16 points will give a different curve with different coefficients - for a toy example, consider sending three points on a line: changing one point gives you a triangle rather than a line, with three different slopes for the three different lines, and, unless one of the points sent is on the y-axis, three different y-intercepts too. So you wouldn't get coefficients repeating, let alone the correct values.

I recently experimented with Reed-Solomon error correction, and to be fair it's a beautiful solution and less complicated than it seems. The first case is for error detection, and as said in the answer above, a single wrong number will make a completely differente curve. So if redundant values are also in the same curve, you can procede without worries. In the other hand, if the redundant values doesn't match the curve, you must test for errors. This is where things can get tricky and some implementations may differ, but a simple first step is to just try skip one value and check if it "fixes" the interpolation. You can also test for bits flipped, and so on. If you really need to recover the data, you can try harder and harder until it fits, and this is where more redundancy can help. A nice property of reed-solomon is also this possibility to simply add more redundancy, or change how it is interleaved between data, without any change in the base algorithm. For computer files, for example, additional redundancy can be stored in another filesystem as a backup. In the end, you are just interpolating points on a curve :o

@@iabervon That makes perfect sense! My 'optimisation' seemed a little too trivial to be original or correct (in this case correct). I would really like to find out though how sensitive these coefficients are to the points. If a single point shifts some dx (or dy) away from its original position what is the corresponding change da1, da2, ....dan in the value of the coefficients. I lack the mathematical tools to really get into this question (and the topic in general) but thank you though! Much appreciations from all the way in South Africa.

@@rmsgrey hey. Thank you for your response. I accidently attended an electrical engineering lecture a few weeks ago (I study Chemical Engineering here in South Africa and I sort of got lost on campus and found my way somehow to that lecture! ) Anyway, they were discussing transferring data and such and I have a vague memory of some of the things you mention being part of that discussion, albeit in a more technical setting. It's interesting how life works!

Then your code can't compensate. For your specific example, you'd get the same coefficients except for the constant term, which would be one higher. Fortunately, credit card numbers have their own error-detection built in, so you'd still be able to tell something went wrong in this example. In general, error detection and correction can only go so far - there's always a chance of random noise happening to produce a valid signal, and the best anyone can do is reduce the chances of that happening to an acceptable level. If you have a perfectly noisy channel - one where what's received is totally random, with no relationship to what was sent - then no possible code could ever help.

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