wire / wire-format / reed-solomon

Reed-Solomon error correction

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.

wire-format kind wire-format status standard verification verified tier B wire-format@1

aka: Reed-Solomon error correction

wire format

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.

fieldsizemeaning
Parametersn, kn = total codeword length, k = data length, n-k = parity length. Usually n = 2^m - 1 (e.g., 255 for 8-bit symbols).
Error correctiont = (n-k)/2Can correct up to t symbol errors. Or n-k erasures (known positions).
EncodingO(nk)Multiply data polynomial by generator polynomial. Or use systematic form: data + parity.
DecodingO(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)common255 total, 223 data, 32 parity. Corrects 16 errors. Used in many systems.
RS(255,239)common255 total, 239 data, 16 parity. Corrects 8 errors. Used in QR codes.

example:

00 00

Reed-Solomon (placeholder)


provenance

agent: curl -H 'accept: application/json' wire.phall.io/wire-format/reed-solomon or /wire-format/reed-solomon.json