3 ms·

Using Reed-Solomon coding to recover from erasures (at known positions) is relatively straightforward. It can be understood with a basic knowledge of linear alg

• Hanschri 4y ago
  To understand how error correction works and to learn more about Hamming codes & Reed-Solomon, 3Blue1Brown and Ben Eater were invaluable. 3Blue1Brown and Ben Eater are by far some of the best educational content creators within their fields, mathematics and computer engineering respectively. I would strongly recommend anyone interested in the topic to check out any of these videos: How to send a self-correcting message (Hamming codes): https://www.youtube.com/watch?v=X8jsijhllIA https://www.youtube.com/watch?v=X8jsijhllIA Hamming codes part 2, the elegance of it all: https://www.youtube.com/watch?v=b3NxrZOu_CE https://www.youtube.com/watch?v=b3NxrZOu_CE And any of Ben Eater's five videos on error correction: https://eater.net/crc https://eater.net/crc As an aside, Ben Eater does all of his videos and demonstrations using an 8-bit computer he has built step by step in videos on a breadboard. Very impressive and inspiring.
• abdullahkhalids 4y ago
  Is there a resource which lists out different codes and the decoding algorithms that work with them?
• rogers18445 4y ago
  Usually, you would see RS used in a setting where any error is going to be erasure (non erasure error -> failed checksum -> erasure error). Then you use something like LDPC codes for in-packet ECC. RS for multi-packet ECC.
  • less_less 4y ago
    RS codes are also good for contexts where you don't know where the errors are. The codes are always maximum distance separable, and the algorithms to locate the errors are quite efficient. In my experience, LDPC is usually better for soft-decision decoding, where you have information about how reliable each bit is. RS is usually better for hard-decision where you don't know anything about the error locations. Also LDPC is usually bit-oriented, and RS is always a symbol-oriented code, so RS works well for burst errors.
• aortega 4y ago
  One important stage of error correction is spreading, that use a pseudo-random function to 'spread' the damaged data over several blocks that can be then completely recovered, instead of concentrating the damage in a single block (like often happen in erasures) that cannot be recovered.
  • userbinator 4y ago
    Optical media like CDs and DVDs use a similar interleaving scheme, allowing for large amounts of errors to be corrected; in fact, even during normal operation with what appears to be a completely clean and perfect disc and drive, read errors are always occurring but corrected silently so there is no loss of data: https://en.wikipedia.org/wiki/Cross-interleaved_Reed%E2%80%93Solomon_coding https://en.wikipedia.org/wiki/Cross-interleaved_Reed%E2%80%9... https://en.wikipedia.org/wiki/Optical_disc#Surface_error_scanning https://en.wikipedia.org/wiki/Optical_disc#Surface_error_sca...
  • nayuki 4y ago
    By spreading, I think you're referring to interleaving https://en.wikipedia.org/wiki/Burst_error-correcting_code#Interleaved_codes https://en.wikipedia.org/wiki/Burst_error-correcting_code#In... , which doesn't need randomness. Pseudo-random scrambling is used in places like https://en.wikipedia.org/wiki/64b/66b_encoding https://en.wikipedia.org/wiki/64b/66b_encoding to reduce the chances of many consecutive 0s or 1s which could cause clock desynchronization between the sender and receiver.
    • aortega 4y ago
      >By spreading, I think you're referring to interleaving https://en.wikipedia.org/wiki/Burst_error-correcting_code#In https://en.wikipedia.org/wiki/Burst_error-correcting_code#In... , which doesn't need randomness. I stand corrected!
      • joshspankit 4y ago
        > I stand corrected! Heh