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) |
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,
] |
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
