I do use it in LibreDWG, but I don't find it cool or useful enough. For CD's or WiFi with lossy transports yes, but for harddiscs (bitflips don't happen) not needed and not so easy to plug in.
Reed Solomon codes are cool
11–20 of 63 posts
Re: Reed Solomon codes are cool
#12If this interests you, make sure to look into Golay codes: https://en.wikipedia.org/wiki/Binary_Golay_code
This code is a mathematical miracle. Apparently, number theory comes together exactly such as to allow you to code 12 bits into 23 bits. Such that you can correct all possible 3 bit errors, but none of the possible 4 bit errors (which means it is efficient). AND it detects all of the possible 7 bit errors, but none of the possible 8 bit errors.
That is very efficient. So in exchange for storing all your data about twice, you can detect all errors where ~30% of the bits are flipped. You can even _correct_ all errors where only 12% of the bits were flipped!
I still consider it magic that such an efficient and 'perfect' code exists. There is unfortunately a proof that is the best one, and that there is no bigger perfect one.
Re: Reed Solomon codes are cool
#13Wow. 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…
I'm sure there are simpler ways to explain it, I'm new to the topic, sorry if you didn't like it.
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
#14Wow. 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…
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!
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
#15Wow. 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…
This reminds me of DCT's...
Re: Reed Solomon codes are cool
#16Wow. 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…
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!
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
#17Earlier quoted context omitted.
I'm sure there are simpler ways to explain it, I'm new to the topic, sorry if you didn't like it.
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.
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
#18I got excited about erasure codes a while ago and tried my best to give an accessible intro at https://www.akalin.com/intro-erasure-codes (with HN discussion at https://news.ycombinator.com/item?id=18702843 ). Glad to see other people getting excited by them too!
This looks great! I haven't finished reading it, but does it explain Gallager decoding or RS decoding? At a first skim, it doesn't seem to, but that might be my lack of knowledge of the topic.
Re: Reed Solomon codes are cool
#19I do use it in LibreDWG, but I don't find it cool or useful enough. For CD's or WiFi with lossy transports yes, but for harddiscs (bitflips don't happen) not needed and not so easy to plug in.
Actually it does happen all the time for hard discs, but the disk itself uses error correcting codes so that it's rare to see an error exposed. The bigger use is in the Backblaze example where you have multiple discs and one may get flakey or fail entirely.
Re: Reed Solomon codes are cool
#20Earlier quoted context omitted.
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!
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 w…
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...