[nayuki]

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

Using RS for error correction (at initially unknown positions) is quite difficult. I wrote a step-by-step guide on it including demo code, and it doesn't even cover the most efficient decoding algorithm (I used PGZ instead of Berlekamp-Massey): https://www.nayuki.io/page/reed-solomon-error-correcting-cod...

[Hanschri]

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

Hamming codes part 2, the elegance of it all: https://www.youtube.com/watch?v=b3NxrZOu_CE

And any of Ben Eater's five videos on error correction: 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.

[aortega]

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]

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

https://en.wikipedia.org/wiki/Optical_disc#Surface_error_sca...

[nayuki]

By spreading, I think you're referring to interleaving 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 to reduce the chances of many consecutive 0s or 1s which could cause clock desynchronization between the sender and receiver.

[aortega]

>By spreading, I think you're referring to interleaving https://en.wikipedia.org/wiki/Burst_error-correcting_code#In... , which doesn't need randomness.

I stand corrected!

[joshspankit]

> I stand corrected!

Heh

[rogers18445]

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]

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.

[abdullahkhalids]

Is there a resource which lists out different codes and the decoding algorithms that work with them?