Practical Reed-Solomon for Programmers - Bert Hubert's writings
a day ago
- Reed-Solomon (R-S) adds t parity symbols to a message, allowing recovery from t/2 corrupted symbols in unknown locations, or t corrupted/missing symbols in known locations, as well as detecting up to t corruptions without recovery.
- Common R-S configuration uses 8-bit symbols with a block size of 255 bytes—you choose how many parity symbols (t) and the payload becomes 255-t bytes.
- To be interoperable, you must specify not only (N,K) but also the Galois field generator polynomial, primitive element, and first consecutive root; for 8-bit symbols, two standard polynomials exist and typical primitive elements include 8, 11, or 14.
- R-S excels at correcting bursts of errors and can be used for erasure coding—combining with sequence numbers to recover from packet loss or disk failures, as in RAID6 or streaming resilience.
- Padding allows using smaller payloads by treating leading symbols as zero and not transmitting them, but a separate integrity check for length fields is needed.
- R-S is not a substitute for cryptographic integrity checks and is rarely needed for protecting data against single-byte errors in RAM or network transmission, which are better handled by retransmission or cryptography.
- Modern soft-decision codes (Turbo, LDPC, Polar) are not applicable for hard-decision correction of concrete bits and bytes; R-S remains appropriate for such scenarios.
- The article provides a practical command-line tool (rscmd) for experimenting with R-S parameters and demonstrates recovery examples.