7 ms·

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 nee

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.

djhworld 8y ago
I'm sure there are simpler ways to explain it, I'm new to the topic, sorry if you didn't like it.
- subjoriented 8y ago
  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.
  - kragen 8y ago
    Do you want to give it a try? I just attempted to explain RS in https://news.ycombinator.com/item?id=19248444 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?
- isoprophlex 8y ago
  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.
  - dnautics 8y ago
    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 https://www.youtube.com/watch?v=x1v2tX4_dkQ
- _underfl0w_ 8y ago
  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.
  - planteen 8y ago
    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.
    - JadeNB 8y ago
      > 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.
wlesieutre 8y ago
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!
- choochootrain 8y ago
  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
- kragen 8y ago
  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.
dicroce 8y ago
This reminds me of DCT's...
scottlocklin 8y ago
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?
MereInterest 8y ago
Conceptually, that sounds the same as Shamir's Secret Sharing. Do these have similar implementations as well as similar underlying concepts?
- jwerle 8y ago
  I believe they both use Lagrange interpolation

djhworld 8y ago

I'm sure there are simpler ways to explain it, I'm new to the topic, sorry if you didn't like it.

subjoriented 8y ago
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.
- kragen 8y ago
  Do you want to give it a try? I just attempted to explain RS in https://news.ycombinator.com/item?id=19248444 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?
isoprophlex 8y ago
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.
- dnautics 8y ago
  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 https://www.youtube.com/watch?v=x1v2tX4_dkQ
_underfl0w_ 8y ago
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.
- planteen 8y ago
  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.
  - JadeNB 8y ago
    > 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.

wlesieutre 8y ago

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!

choochootrain 8y ago
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
kragen 8y ago
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.

dicroce 8y ago

This reminds me of DCT's...

scottlocklin 8y ago

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?

MereInterest 8y ago

Conceptually, that sounds the same as Shamir's Secret Sharing. Do these have similar implementations as well as similar underlying concepts?

jwerle 8y ago
I believe they both use Lagrange interpolation