Math is beautiful – it’s a sheer magic to me, but now and then some good people publish approachable articles that allow me get a tiny dash of understanding of how things work.
There’s one such article today – https://innovation.vivint.com/introduction-to-reed-solomon-bc264d0794f8 (and complimentary https://medium.com/@jtolds/joseph-louis-lagrange-and-the-polynomials-499cf0742b39) that I could highly recommend. It’s a fairly simplified overview that provides just a basic idea of a particular error correction technique, but it’s simple yet comprehensive.
In fact it was so fascinating I couldn’t stop myself from giving it a (very short and simple) try. I won’t repeat the articles in any way, just post a code with some comments.
Let’s say we have this code in Python (minor comments inline):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | xs = [ 1.0, # float format to make suure calculation precision is not impacted - it fails badly otherwise 2.0, 3.0, 4.0, ] ys = [ 10, # the values here are random - like in "I made them up". But this is about "any numbers", right? 42, 74, 111, ] # it's a direct representation of what's described in the https://medium.com/@jtolds/joseph-louis-lagrange-and-the-polynomials-499cf0742b39 article def l0(x): return ( (x-xs[1]) * (x-xs[2]) * (x-xs[3]) ) / ( (xs[0] - xs[1]) * (xs[0] - xs[2]) * (xs[0] - xs[3]) ) def l1(x): return ( (x-xs[0]) * (x-xs[2]) * (x-xs[3]) ) / ( (xs[1] - xs[0]) * (xs[1] - xs[2]) * (xs[1] - xs[3]) ) def l2(x): return ( (x-xs[0]) * (x-xs[1]) * (x-xs[3]) ) / ( (xs[2] - xs[0]) * (xs[2] - xs[1]) * (xs[2] - xs[3]) ) def l3(x): return ( (x-xs[0]) * (x-xs[1]) * (x-xs[2]) ) / ( (xs[3] - xs[0]) * (xs[3] - xs[1]) * (xs[3] - xs[2]) ) # as well as this def f(num): return ys[0] * l0(num) + ys[1] * l1(num) + ys[2] * l2(num) + ys[3] * l3(num) for x in range(0, 10): fx = f(x) print "{}: {}".format(x, fx) |
And we run it and we get this:
0: -27.0 1: 10.0 2: 42.0 3: 74.0 4: 111.0 5: 158.0 6: 220.0 7: 302.0 8: 409.0 9: 546.0
(you can add more point; you could also use matplotlib to plot them)
So as you can see it reflected the pre-defined 4 points (10, 42, 74 and 111), but also calculated other points on a curve. So let’s say we sent 6 point, but client received only points 1,2,5 and 6 (10, 42, 158, 220).
If we adjust the input values to look like this:
xs = [ 1.0, 2.0, 5.0, 6.0, ] ys = [ 10, 42, 158, 220, ] |
and run it again, we’d still get all the values, because 4 values are enough to define the cubic function curve, and these were taken from that very curve:
0: -27.0 1: 10.0 2: 42.0 3: 74.0 4: 111.0 5: 158.0 6: 220.0 7: 302.0 8: 409.0 9: 546.0
Magic, right?
Some extra calculations around it are also available at http://mathonline.wikidot.com/linear-lagrange-interpolating-polynomials