Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Reed Solomon codes are cool

djhworld.github.io

Post reply on HN
Print view View original

41–50 of 63 posts

Re: Reed Solomon codes are cool

#41

Post by kragen »

nayuki wrote: post #38
kragen wrote: post #16

Earlier quoted context omitted.

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…

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)…

Oh, that's wonderful! Your explanations are always the best. Thank you, magical girl Nayuki!

Re: Reed Solomon codes are cool

#42

Post by dfox »

gwbas1c wrote: post #28

One of the things that I miss about analog electronics is how the signal degrades nicely. For example, with FM, if I drive under a bridge the radio gets a little fuzzy or switches to mono. With newer digital satellite radio, the playback just stops. Evan back with old analog TV broadcasts, if there was a signal issue, the picture would just get fuzzy. Now with HDTV, the picture goes away completely. I know a lot of t…

I distinctly remember that one of the marketing features of DVB-T was "perfect picture or none at all" while I haven't seen any consumer grade DVB-T receiver that actually behaves that way and instead marginal signal results in various ugly MPEG artifacts.

Re: Reed Solomon codes are cool

#43

Post by aaaaaaaaaaab »

JadeNB wrote: post #35
aaaaaaaaaaab wrote: post #20

Earlier quoted context omitted.

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 poly…

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 spe…

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

#44

Post by scottlocklin »

subjoriented wrote: post #4

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…

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

#47

Post by toast0 »

dfox wrote: post #42
gwbas1c wrote: post #28

One of the things that I miss about analog electronics is how the signal degrades nicely. For example, with FM, if I drive under a bridge the radio gets a little fuzzy or switches to mono. With newer digital satellite radio, the playback just stops. Evan back with old analog TV broadcasts, if there was a signal issue, the picture would just get fuzzy. Now with HDTV, the picture goes away completely. I know a lot of t…

I distinctly remember that one of the marketing features of DVB-T was "perfect picture or none at all" while I haven't seen any consumer grade DVB-T receiver that actually behaves that way and instead marginal signal results in various ugly MPEG artifacts.

I've not used DVB-T, but ATSC (which on Linux uses the DVB-T subsystem); the range of conditions where you can get perfect picture is much larger than from analog broadcast TV, but the experience with marginal signals is indeed much less watchable. If you've got nothing else to watch, you can watch an analog broadcast that's more snow than picture, as long as you're getting the sync signals well enough.

Re: Reed Solomon codes are cool

#48

Post by filipo »

Last month I tried to use Reed Solomon ECC in order to do error correction. I stopped using it, the moment I understand that error correction does not necessarily mean "error detection". If one does not exactly know the number of possible errors within encoded data, RS-ECC may "correct" to a wrong result (if the data contains more errors than the ECC is able to correct). So checksums might be the better approach (in certain scenarios) if data integrity has the highest priority... I wish, Reed-Solomon would handle that.

Re: Reed Solomon codes are cool

#49

Post by quink »

gwbas1c wrote: post #28

One of the things that I miss about analog electronics is how the signal degrades nicely. For example, with FM, if I drive under a bridge the radio gets a little fuzzy or switches to mono. With newer digital satellite radio, the playback just stops. Evan back with old analog TV broadcasts, if there was a signal issue, the picture would just get fuzzy. Now with HDTV, the picture goes away completely. I know a lot of t…

Hierarchical Modulation. It’s in the standard, but essentially nobody used or used it.

In fact, Europe (or rather large parts of) seems to be on the verge of shutting down terrestrial TV entirely.

Re: Reed Solomon codes are cool

#50

Post by philsnow »

tempguy9999 wrote: post #37
wlesieutre wrote: post #8

Earlier 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!

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.

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.
Post reply on HN