Practical Reed-Solomon for Programmers

h2odragon 4 years ago |

Amusing: the linked library page, https://www.ka9q.net/code/fec/ says (from 2007) "The new Intel Macs are not yet supported. Stay tuned."

Ignore an issue for long enough, and it stops being an issue :)

coder543 4 years ago |

If anyone wants to read more about Reed Solomon, this is the article that helped me understand Reed Solomon earlier this year: https://innovation.vivint.com/introduction-to-reed-solomon-b...

ahubert 4 years ago | |

(author here) Nice! Added that to the page, very worthwhile. Thanks.

vmilner 4 years ago | | |

This BBC engineering paper is also useful.

https://downloads.bbc.co.uk/rd/pubs/whp/whp-pdf-files/WHP031...

boredprograming 4 years ago |

Just to add to this topic, usually Reed Solomon codes are interleaved with Turbo codes or LDPC.

The reason is this: Reed Solomon corrects entire symbols, but can only correct so many symbols per block. LDPC and Turbo correct single bit errors. If you have a lot of single bit errors, mixed with completely corrupt blocks, it's best to use both.

Interleaving usually mixes the bits around too, to spread long chains of errors out between symbols.

This setup is used in digital radio, 3G, CD and DVD, DSL, etc

conductor 4 years ago |

Thanks for the article and code.

Also check out https://github.com/Parchive/par2cmdline

I wish something like this was integrated into a modern and free archive format. RAR has it. RAR also got volume recovery: when creating split multi-volume archives you can also create recovery volumes - each recovery volume can replace any other one missing volume. It was a life-saver in floppy-disk times.

dale_glass 4 years ago | |

We're not using floppies anymore, and media is extremely reliable.

On the internet you can just retransmit if something went wrong, and if you're worried about the media specifically then there are media specific measures, like RAID and filesystem level checksums.

macintux 4 years ago | | |

Cosmic rays are a thing, and wasn’t there just a study linked here a few days ago about how unreliable hardware is at scale?

dale_glass 4 years ago | | |

Oh, I'm all for ECC and checksumming and whatnot.

All I'm saying is that adding recovery info to archives is probably not ideal -- we can do it in a task or media specific way that works best for whatever context the data is in.

Redundancy in .RAR made perfect sense back when you were transporting data on floppies, and if the floppy was bad, it was a huge pain. These days we transport over the network and don't need to carry any redundant data at all. All we need is a checksum and to retransmit whatever didn't arrive correctly.

ithkuil 4 years ago |

There are other erasure codes that go beyond RS. For example LRC (Local Reconstruct Codes) is very interesting; it improves on reed Solomon by requiring less bandwidth/IO for repair reads.

https://www.usenix.org/conference/atc12/technical-sessions/p...

xrd 4 years ago |

I loved this article and going down the rabbit hole with the associated links was excited to see a discussion from Russ Cox (golang) about how QR codes rely on RS (and another great article)

https://research.swtch.com/qart

crazygringo 4 years ago |

Are there any uses cases for Reed-Solomon at the application level?

My impression was always that error checking was implemented at the hardware level, or else at the OS/driver level.

But just curious if there are some applications I'm missing.

sparc24 4 years ago |

These 2 papers helped me better understand some more practical aspects of it.

https://mirrors.edge.kernel.org/pub/linux/kernel/people/hpa/... https://www.usenix.org/legacy/event/fast08/tech/full_papers/...

moreati 4 years ago |

A semi-related question/puzzle. Is it possible to reverse engineer parameters of a Reed Solomoon function?

Given one or more known inputs/outputs of a Reed Solomon function with known symbol size, message length, number of parity symbols. Is it possible to calculate the other parameters (polynomial coefficients, primitive element etc)?

I failed to find an answer a few years ago, when trying to interoperate with chirp.io (now gone). https://math.stackexchange.com/questions/663643/discover-par...

xorvoid 4 years ago | |

Doesn’t seem too hard actually, given enough example input. The parity is just a linear combination of the input so you can set up a linear system and solve for those things encoding matrix rows pretty easily. From there you may need to make some assumptions about what type of matrix was used (e.g. vandermonde is popular) and perhaps the field size being used (e.g. GF(2^8), and with those, it should be easy to determine the reducing polynomial. Some of these choices are small enough to be able to brute force (finite fields used for practical problems tend to be small, naturally). If you have a dataset, I might actually toy with it myself.. sounds fun.

moreati 4 years ago | | |

Thanks. I have 30 examples I got from the API, many moons ago https://github.com/moreati/chirppy/blob/master/examples.json. My finite field knowledge is not up to solving it analytically, my attempts to brute force it are in https://github.com/moreati/chirppy/blob/master/trials.py. That includes functions to go between the characters, and integer representations.

nayuki 4 years ago |

Mathematical derivation and runnable code for a Reed-Solomon error-correcting code decoder: https://www.nayuki.io/page/reed-solomon-error-correcting-cod...

Tcepsa 4 years ago |

At the risk of oversimplifying, is there any value in the analogy, "It's like RAID but for data streams"?

frabert 4 years ago | |

Problem with that is, as the article states, RAID6 _can_ use RS as its error correction method, which turns this description into something a bit too circular for my taste

IAmLiterallyAB 4 years ago |

What is the difference between RS and Hamming codes?

rurban 4 years ago | |

Hamming Codes can only recover from 2 wrong bits per byte, with RS it's configurable.

alessandroetc 4 years ago |

what are your thoughts on storj.io? they utilize R-S for all their entire storage platform.

mrfusion 4 years ago |

Is this what tcp/ip uses?

rl1987 4 years ago | |

No. TCP, IP and UDP are all using Internet Checksum (RFC 1071). Ethernet uses CRC.

znpy 4 years ago | | |

I went and skimmed the rfc you're citing and it's fro 1988, it's old enough to have samples in C code where the "register" keyword is still used (afaik nowadays most compilers will ignore it) along with assembly code for motorola 68020, Cray CPUs and the IBM-370.

EDIT: for reference: https://datatracker.ietf.org/doc/html/rfc1071.html

brandmeyer 4 years ago | | |

All of these are techniques for verifying a message. Galileo also uses a 24-bit CRC to verify its messages after performing forward error correction.

jandrese 4 years ago | |

TCP doesn't do forward error correction at all. It uses a retransmission scheme instead. TCP's error correction is not only to insure a consistent datastream, but also to more equitably share limited bandwidth.

stagger87 4 years ago | |

Forward error correction is usually at the PHY layer, not the transport layer. So the more appropriate question is, does 10GbE/100GbE/WLAN/etc use RS coding? (and yes some of them do.)

TonyTrapp 4 years ago | |

No, but Reed-Solomon codes are used on on CDs.

sliken 4 years ago | | |

Indeed, I think there's a 3 layers of encodings to protect against different corruption scenarios. Trick is some equipment only does a partial implementation, thus the need for a tool like cdparanoia to recovery data from corrupted CDs.