Reed-Solomon codes
The block code that repairs a noisy link by charging per corrupted symbol rather than per corrupted bit. Ubiquitous on space downlinks, and a silent failure the moment your decoder's field does not match the encoder's.
Reed-Solomon is a block code that works on symbols rather than bits. A code written RS(n, k) takes k message symbols and emits n, adding n - k check symbols; a decoder can then repair up to (n - k) / 2 wrong symbols anywhere in the block without being told which ones are wrong. It is what stands between a noisy space link and unreadable telemetry, and it is also inside CDs, DVDs, QR codes, DVB and RAID 6.
What it is
The symbols are elements of a finite field, usually GF(2^8), one field element per octet. That choice is the whole reason the code suits radio. If the channel flips three bits and all three land in the same octet, that is one symbol error, not three. Real radio noise clumps, and Reed-Solomon charges per clump.
The code is systematic: the message appears verbatim at the front of the codeword and the check symbols are appended. That is convenient and misleading, because a corrupted block still looks parseable.
Erasures are the other half of the budget. An error is a wrong symbol at an unknown position and costs two check symbols; an erasure is a symbol you already know is wrong, and costs one. So RS(255,223) fixes 16 unknown errors, or 32 known-bad symbols, or any mix in between.
Why the parameters are part of the code
This is the point that costs people evenings. "Reed-Solomon (255,223)" does not specify a code. To produce check symbols the encoder needs:
- a primitive polynomial defining how octets multiply in GF(2^8),
- a first consecutive root, the power of the primitive element the generator starts at,
- the generator element itself, and the symbol width.
Two encoders that both call themselves RS(255,223) with different values produce completely different check symbols and are, for decoding, different codes. A decoder pointed at the wrong field does not complain. It does its error-location algebra in the wrong arithmetic and either declares the block uncorrectable or "corrects" it into confident garbage.
CCSDS 131.0-B specifies primitive polynomial 0x187 (that is x^8 + x^7 + x^2 + x + 1) and first consecutive root 112. In Python:
import reedsolo
rs = reedsolo.RSCodec(32, nsize=255, fcr=112, prim=0x187)
message, codeword, errata = rs.decode(block) # 223 octets back, plus fixed positions
RSCodec's defaults are fcr=0 and prim=0x11d, a perfectly good field that happens to be the one QR codes and Data Matrix use, and a different one from CCSDS. Letting the defaults ride is the single most common failure.
The dual-basis trap
CCSDS specifies that the symbols are represented in a dual basis (a Berlekamp representation) on the air, not the conventional basis that reedsolo and most textbook implementations work in. Against a real over-the-air CCSDS downlink you must apply the dual-to-conventional transform per symbol before decoding, or every block fails. Against a capture produced by an encoder working directly in the conventional basis, applying the transform is what breaks it.
Phil Karn's libfec exposes exactly this split: decode_rs_ccsds() handles the dual basis, decode_rs_8() is the same field in the conventional basis. The rule to carry away is that your decoder must match the encoder, not the specification in the abstract.
Where it sits in a link
Reed-Solomon is almost always the outer code of a concatenated pair. An inner convolutional or LDPC code cleans up random bit errors but emits bursts when it does fail; an interleaver spreads those bursts across several blocks; Reed-Solomon, charging per symbol, mops them up. CCSDS interleaves several codewords together (depth 5 is the common choice) for exactly this reason. See Wiki: viterbi for the inner half.
Pitfalls
- Do not slice, decode. Dropping the last 32 octets and keeping 223 leaves every channel error in place. The result reads as almost-right nonsense, which is worse than a clean failure.
- Wrong parameters fail silently. There is no exception that says "wrong field". Sanity-check by decoding a block you encoded yourself with the same settings.
- Descramble first. On a CCSDS link the block is pseudo-randomised before transmission; a still-scrambled block looks to the decoder like far more than 16 symbol errors.
- Erasures only help if you actually know the positions. Passing guessed erasure positions burns budget and can push a correctable block over the limit.
reedsoloraisesReedSolomonErrorwhen a block is uncorrectable, so wrap the decode; a whole-capture loop that dies on one bad block tells you nothing about the rest.