wire / wire-format / reed-solomon
Reed-Solomon (RS) codes are block-based error-correcting codes. RS(n,k): n total symbols, k data symbols, n-k parity symbols. Can correct up to t = (n-k)/2 errors (or n-k erasures). Used in QR codes, CDs/DVDs, RAID, deep space communication, and digital TV.
aka: Reed-Solomon error correction
spec: Reed-Solomon (1960)
Reed-Solomon (RS) codes are block-based error-correcting codes. RS(n,k): n total symbols, k data symbols, n-k parity symbols. Can correct up to t = (n-k)/2 errors (or n-k erasures). Used in QR codes, CDs/DVDs, RAID, deep space communication, and digital TV.
| field | size | meaning |
|---|---|---|
| Parameters | n, k | n = total codeword length, k = data length, n-k = parity length. Usually n = 2^m - 1 (e.g., 255 for 8-bit symbols). |
| Error correction | t = (n-k)/2 | Can correct up to t symbol errors. Or n-k erasures (known positions). |
| Encoding | O(nk) | Multiply data polynomial by generator polynomial. Or use systematic form: data + parity. |
| Decoding | O(n^2) or O(n log n) | Berlekamp-Massey algorithm for error locator polynomial. Chien search for error positions. Forney algorithm for error values. |
| RS(255,223) | common | 255 total, 223 data, 32 parity. Corrects 16 errors. Used in many systems. |
| RS(255,239) | common | 255 total, 239 data, 16 parity. Corrects 8 errors. Used in QR codes. |
example:
00 00
Reed-Solomon (placeholder)
agent: curl -H 'accept: application/json' wire.phall.io/wire-format/reed-solomon
or /wire-format/reed-solomon.json