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

51–60 of 63 posts

Re: Reed Solomon codes are cool

#51

Post by MereInterest »

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…

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

#52

Post by jwerle »

MereInterest wrote: post #51
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…

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

I believe they both use Lagrange interpolation

Re: Reed Solomon codes are cool

#54

Post by philsnow »

My favorite class of error correcting codes is one I haven't seen mentioned here: rateless / "fountain" codes. https://en.wikipedia.org/wiki/Fountain_code

You take any message and can generate any amount of coding symbols from the message, and a receiver that gathers _any_ K of those coding symbols can decode the message.

The mental image I have is using these to send messages into space -- a receiver could pick up at any point and just wait until they have any K coding symbols and they'll be able to decode the message.

My understanding of all this stuff comes from USENET and par/par2/yenc (where, IIRC, the message gets packaged up in plaintext blocks and if your local server is missing N blocks you have to collect N parity blocks and you can recover from there, but my recollection is probably fuzzy), and I imagine rateless codes would be quite useful for USENET binaries.

Re: Reed Solomon codes are cool

#55

Post by Waterluvian »

So is the idea basically that you can recover any missing n% of a dataset by using an extra n% of disk space to store specially calculated data, rather than 100% extra disk space (because you don't know which pieces are going to go missing)?

Re: Reed Solomon codes are cool

#56

Post by userbinator »

This is a very practical explanation of how to actually implement RS codes with a focus on QR codes, and one of the best ones I've come across that doesn't immediately go into the deep theoretical maths of it: https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_f...

It's very enlightening to see finite-field arithmetic implemented in a few lines of Python --- it gives something concrete to look at and think about.

Re: Reed Solomon codes are cool

#57

Post by beachy »

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

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

#58

Post by FR10 »

major wrote: post #26

After learning about Hamming code (the predecessor of Reed-Solomon), I wrote a tutorial that explains Hamming code and how to implement it in a simple simulator. https://manuelfi.com/blog/hamming-code-simulator/

Hi major, I just read your post and its great, thank you, it really has inspired me to learn more on erasure codes. I only have one doubt: in the Example Problem, I understand the 4th parity bit should be the 8th position (starting the first at 1), however you placed it in the 9th position, and I think this is the reason why (according to me) in the 2nd parity check the bit should be 1 instead of 0, however your answer was still right, so could you tell me what is the correct place for the 4th parity bit?

Re: Reed Solomon codes are cool

#59

Post by ithkuil »

rurban wrote: post #11

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.

When you have tons of disks you notice how often you have whole disk failures

Re: Reed Solomon codes are cool

#60

Post by sliken »

filipo wrote: post #48

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…

Or both. Much like encryption, to avoid various attacks you need to add a checksum and then encrypt.
Post reply on HN