News for hackers. Stuff that matters.
Re:Reed Solomon codes are cool by subjoriented on Monday February 25, 2019 @01:38PM (#19248110)
Wow. I love explaining Reed Solomon codes and this didn't do it justice.

The basic concept is that if I give you five points all on the same line, you only need any two of them to reconstruct the line.

Reed Solomon doesn't use lines (it isn't optimal) and the geometry they use isn't the Cartesian plane (this requires infinite precision) - but this is what the codes do!

Just like it requires two points to reconstruct a line, three points are required to reconstruct a simple polynomial (degree 2). Reed Solomon uses "high degree polynomials" which require n+1 points to reconstruct the degree-n polynomial.

The codes take data, make a polynomial out of it, and then send points from the polynomial to the other side, which can interpolate it as soon as enough points are gathered!

All of this looks like impenetrable discretization and matrix operations if you just get a description of the algorithms, which makes it seem a lot less approachable than it is.

Re:Reed Solomon codes are cool by wlesieutre on Monday February 25, 2019 @01:47PM (#19248199)
I remember playing a computer game in math class where you were presented with a XY plane and had to "hit" points (really circles, didn't need to be exact) by plotting equations through them. With some trial and error you could make a polynomial go through basically as many as you wanted, it's neat to see this applied to a real problem!
Re:Reed Solomon codes are cool by kragen on Monday February 25, 2019 @02:14PM (#19248444)
Doing this kind of thing was my first introduction to Lagrange interpolation, too, but it turns out that you can do Lagrange interpolation without trial and error; you can just use linear algebra, since the points are a linear function of the coefficients, regardless of the degree of the polynomial.

This was in fact the first decoding algorithm for Reed–Solomon codes, but it's not very efficient when you don't know which of your points are the ones with the corrupted data; you kind of have to guess, which gets expensive fast when you're trying to tolerate more than one or two errors.

Although it turns out that there are better algorithms for that, the most commonly used RS codes don't actually encode a series of points on a polynomial, as subjoriented's comment at the root of this thread suggests; instead they are so-called "BCH codes", where you consider the data you transmit (both the original data and the "parity" symbols) to be actually a sequence of coefficients. So where does the redundancy come from? After all, any set of numbers is valid as the coefficients of a polynomial.

BCH codes require the polynomial to be divisible by a known generator polynomial, and that's where you get the redundancy you need to correct errors. Gorenstein and Zierler published an efficient error-correction ("decoding") algorithm for BCH codes in 1960; the first efficient decoding algorithm for original-view RS codes (where you transmit a series of points) wasn't found until 1986, and even today, BCH-code decoding algorithms are more efficient than original-view decoding algorithms.

The Gorenstein–Zierler algorithm works by evaluating the received polynomial at the roots of the generator polynomial. Since it's supposed to be a multiple of the generator, it should be zero at those roots, as the generator is; if it's nonzero, the values at those roots are due to some "error polynomial" that's been conceptually added to your message in transit. If you suppose that it has only a few nonzero coefficients, there's a clever way to compute the error polynomial from those values that should have been zero. This allows you to subtract it from the received message to correct the errors.

At least, I think that's how it works. I haven't implemented an RS decoder yet, so I might be getting some of this wrong.

But something like that was what I was actually hoping to read at the above link.

Re:Reed Solomon codes are cool by nayuki on Monday February 25, 2019 @04:35PM (#19249678)
I explained all the linear algebra involved in the Peterson-Gorenstein-Zierler decoder and offer a working implementation in https://www.nayuki.io/page/reed-solomon-error-correcting-cod... ; https://news.ycombinator.com/item?id=13565939

It runs in O(n^3) time, and unfortunately is not the state of the art. What actual Reed-Solomon implementations use are the Berlekamp-Massey and Forney algorithms, which run in O(n^2) time.

Re:Reed Solomon codes are cool by abraae on Tuesday February 26, 2019 @03:14AM (#19252769)
Incredible. This is the sort of thing my non-programmer friends think that my work entails. Thank god it doesn't.
Re:Reed Solomon codes are cool by kragen on Monday February 25, 2019 @04:57PM (#19249858)
Oh, that's wonderful! Your explanations are always the best. Thank you, magical girl Nayuki!
Re:Reed Solomon codes are cool by aaaaaaaaaaab on Monday February 25, 2019 @02:49PM (#19248754)
That’s an interesting duality between the coefficient and pointwise representation. I wonder whether this connects to the discrete Fourier transform, which can be viewed as the evaluation of a polynomial at the complex n-th roots of unity. (and the inverse DFT must be equivalent to Lagrange interpolation I guess - insert some handwaving here)

Also, the BCH encoder multiplies the input sequence with the generator polynomial, which is a convolution of their coefficients. Fourier-type transforms (i.e. number theoretic transform) relate convolution and pointwise multiplication, so I feel there’s an underlying connection here, but I don’t have enough experience with finite fields to connect the dots...

Re:Reed Solomon codes are cool by JadeNB on Monday February 25, 2019 @04:26PM (#19249602)
You seem to have answered your own question! For any set of `n + 1` sample values for degree-at-most-`n` polynomials, there's a map from the coefficient representation to the pointwise representation (obvious), and one going the other way (Lagrange interpolation). The DFT is just one instance of this, but a particularly nice one, because the map is essentially involutive, and subject to considerable computational speed-up.

What dots do you want to connect? (Anyway you can connect them with a high-degree polynomial curve. :-) )

Re:Reed Solomon codes are cool by aaaaaaaaaaab on Monday February 25, 2019 @05:29PM (#19250092)
Indeed, the wikipedia article on RS codes [1] mentions this equivalence between the DFT and RS encoding/decoding.

They mention that both procedures are basically a multiplication by a Vandermonde matrix, with the Fourier transform having the additional requirement of using the n-th roots of unity.

https://en.m.wikipedia.org/wiki/Reed–Solomon_error_correctio...

Re:Reed Solomon codes are cool by tempguy9999 on Monday February 25, 2019 @04:30PM (#19249640)
I believe it was Green Globs. I read about it years ago as being a noteworthy pedagogical aid. Wish I'd had it when I was in school.
Re:Reed Solomon codes are cool by philsnow on Monday February 25, 2019 @06:59PM (#19250710)
I played such a game, called Green Globs, in junior high school. I spent probably 20 minutes tweaking an ellipse equation to hit 7 or 8 globs.
Re:Reed Solomon codes are cool by choochootrain on Monday February 25, 2019 @02:05PM (#19248374)
what a blast from the past - i remember this game and it blew my mind when i first realized i had the power to plot a polynomial through all those points with little effort required
Re:Reed Solomon codes are cool by scottlocklin on Monday February 25, 2019 @05:33PM (#19250128)
You win at explaining Reed Solomon codes, forever.

Please do this for Berlekamp-Massey algorithm! Is it EM algorithm for this problem, or am I smoking banana peels?

Re:Reed Solomon codes are cool by djhworld on Monday February 25, 2019 @01:42PM (#19248152)
I'm sure there are simpler ways to explain it, I'm new to the topic, sorry if you didn't like it.
Re:Reed Solomon codes are cool by subjoriented on Monday February 25, 2019 @01:45PM (#19248180)
I don't think anything you wrote is wrong!

I have a background in error codes - hamming, and luby and raptor and, and, and. Reed-Solomon is particularly "beautiful" from a mathematics perspective (more so than Raptor) - something I can usually explain to anyone and get them interested.

Re:Reed Solomon codes are cool by kragen on Monday February 25, 2019 @02:16PM (#19248470)
Do you want to give it a try? I just attempted to explain RS in https://news.ycombinator.com/item?id=19248444 but I am significantly impeded by the fact that I don't actually understand it myself, so I'm sort of summarizing the Wikipedia article. Am I focusing on the right algorithms? Did I explain them correctly, as far as my short explanation goes?
Re:Reed Solomon codes are cool by _underfl0w_ on Monday February 25, 2019 @02:04PM (#19248360)
The explanation from BackBlaze that you linked to goes into more depth.

It looks to be built on matrix algebra. Kinda nifty how simple and elegant the underlying concept is, really. Reminds me of the surprising conceptual simplicity behind Diffie-Hellman.

Re:Reed Solomon codes are cool by planteen on Monday February 25, 2019 @02:57PM (#19248827)
I guess simple is relative, but in my opinion, coding theory is not simple. It requires some high level math to understand what is going on. Many people's eyes will glaze over when you go into Galois (finite) fields. Abstract algebra is not part of the typical undegrad CS/engineering math curriculum. And then the efficient algorithms for the decoding procedure were found much later than Reed & Solomon's original paper by Berlekamp.
Re:Reed Solomon codes are cool by JadeNB on Monday February 25, 2019 @04:28PM (#19249615)
> Abstract algebra is not part of the typical undegrad CS/engineering math curriculum.

It should be (says the mathematician)! That it doesn't probably comes from confusing the elegant theoretical perspective on finite fields to the computational perspective, which (at least from my pure-math point of view) can get pretty hairy.

Re:Reed Solomon codes are cool by isoprophlex on Monday February 25, 2019 @01:53PM (#19248259)
Well it might not be the most in depth explanation, but your enthusiasm is appreciated, and contagious too.

I'm down the Wikipedia rabbit hole too, now.

Re:Reed Solomon codes are cool by dnautics on Monday February 25, 2019 @02:52PM (#19248786)
if you want to learn finite fields somewhat more formally, but not so formally, this is a pretty good introduction (yes, it's for AES, but the principles are the same): https://www.youtube.com/watch?v=x1v2tX4_dkQ
Re:Reed Solomon codes are cool by MereInterest on Monday February 25, 2019 @07:00PM (#19250714)
Conceptually, that sounds the same as Shamir's Secret Sharing. Do these have similar implementations as well as similar underlying concepts?
Re:Reed Solomon codes are cool by jwerle on Monday February 25, 2019 @07:06PM (#19250751)
I believe they both use Lagrange interpolation
Re:Reed Solomon codes are cool by dicroce on Monday February 25, 2019 @02:09PM (#19248407)
This reminds me of DCT's...