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