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

31–40 of 63 posts

Re: Reed Solomon codes are cool

#31

Post by rando231 »

ignoramous wrote: post #23

You know what? Not just Reed-Solomon codes, but Information Theory is cool. People don't realise how ubiquitous different forms of encoding schemes are (I am leaving out compression/decompression schemes altogether here, but it has always amazed me as to what profound impact Information Theory has, and yet it is so out of the way): Forward error-correction codes (FEC) at L2: IBM's elegant 8b/10b encoding https://en.w…

I am amazed by the brilliant application of 8B/10B encoding to recover clocks: https://en.wikipedia.org/wiki/Clock_recovery

Such a brilliant system.

Re: Reed Solomon codes are cool

#33

Post by jacobolus »

317070 wrote: post #12

If 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 n…

Everything related to the sporadic groups is crazy https://en.wikipedia.org/wiki/Sporadic_group

Re: Reed Solomon codes are cool

#34

Post by akalin »

kragen wrote: post #18
akalin wrote: post #6

I 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.

Thanks! It doesn't explain Gallager codes since I don't know much about them (but will look into them now!). It only briefly mentions RS decoding, since the RS erasure code uses Vandermonde matrices, and Cauchy matrices seem more foolproof for an intro article. I was planning on writing a follow-up article on PAR1 (which uses RS erasure codes, but slightly incorrectly) but alas, my free time isn't what it used to be...

Re: Reed Solomon codes are cool

#35

Post by JadeNB »

aaaaaaaaaaab wrote: post #20
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…

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

#36

Post by JadeNB »

planteen wrote: post #24
_underfl0w_ wrote: post #13

Earlier quoted context omitted.

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.

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

> 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

#37

Post by tempguy9999 »

wlesieutre wrote: post #8
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…

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.

Re: Reed Solomon codes are cool

#38

Post by nayuki »

kragen wrote: post #16
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!

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) time.

Re: Reed Solomon codes are cool

#40

Post by zokier »

pmarreck wrote: post #29
ignoramous wrote: post #23

You know what? Not just Reed-Solomon codes, but Information Theory is cool. People don't realise how ubiquitous different forms of encoding schemes are (I am leaving out compression/decompression schemes altogether here, but it has always amazed me as to what profound impact Information Theory has, and yet it is so out of the way): Forward error-correction codes (FEC) at L2: IBM's elegant 8b/10b encoding https://en.w…

Are any of the ones that are better than Reed-Solomon either open-source or otherwise out of patent protection yet? A library I could play with, perhaps? (would love to get my hands on a Raptor or Turbo implementation)

libraptorq (lgpl3+): https://fenrirproject.org/Luker/libRaptorQ/wikis/home

zfec (gpl2+): https://github.com/tahoe-lafs/zfec (discussion: https://news.ycombinator.com/item?id=12976168)

liberasurecode (bsdesque): https://github.com/openstack/liberasurecode

cm256 (3 clause bsd): https://github.com/catid/cm256

openrq (apache2.0): http://openrq-team.github.io/openrq/

openfec: http://openfec.org/

lt-codes-python: https://github.com/Spriteware/lt-codes-python

Post reply on HN