from Hacker News

Practical Reed-Solomon for Programmers

by heydenberk on 6/13/21, 9:51 AM with 43 comments

  • by h2odragon on 6/14/21, 3:41 PM

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

  • by coder543 on 6/14/21, 3:20 PM

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

  • by boredprograming on 6/14/21, 10:09 PM

    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

  • by conductor on 6/14/21, 4:15 PM

    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.

  • by ithkuil on 6/14/21, 8:24 PM

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

  • by xrd on 6/14/21, 3:52 PM

    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

  • by crazygringo on 6/14/21, 4:50 PM

    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.

  • by sparc24 on 6/14/21, 5:11 PM

  • by moreati on 6/14/21, 5:03 PM

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

  • by nayuki on 6/14/21, 6:48 PM

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

  • by Tcepsa on 6/14/21, 9:21 PM

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

  • by IAmLiterallyAB on 6/14/21, 4:24 PM

    What is the difference between RS and Hamming codes?

  • by alessandroetc on 6/14/21, 11:53 PM

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

  • by mrfusion on 6/14/21, 3:09 PM

    Is this what tcp/ip uses?