reed-solomon#

Reed-Solomon error correction over GF(2^8) for OCaml.

Systematic Reed-Solomon encoder and decoder with configurable code parameters. The decoder recovers up to t = (n - k) / 2 symbol errors using syndrome computation, Berlekamp-Massey, Chien search, and the Forney algorithm. Ships with the CCSDS 131.0-B-4 RS(255,223) preset (t = 16) used on TM downlinks and spacecraft telemetry; other codes are defined by populating Reed_solomon.config directly (field polynomial, primitive element, first root).

Installation#

Install with opam:

$ opam install reed-solomon

If opam cannot find the package, it may not yet be released in the public opam-repository. Add the overlay repository, then install it:

$ opam repo add samoht https://tangled.org/gazagnaire.org/opam-overlay.git
$ opam update
$ opam install reed-solomon

Usage#

encode_systematic takes exactly k data bytes and returns an n-byte codeword whose first k bytes are the data unchanged and whose last 2t bytes are parity. For the CCSDS preset, that's 223 data bytes in and 255 codeword bytes out:

# let data = Bytes.make 223 '\x42' in
  let codeword = Reed_solomon.encode_systematic Reed_solomon.ccsds data in
  Bytes.length codeword
- : int = 255

Round-trip a message, corrupting up to t = 16 symbols on the channel:

# let data = Bytes.make 223 '\x00' in
  Bytes.blit_string "hello, reed-solomon" 0 data 0 19;
  let codeword = Reed_solomon.encode_systematic Reed_solomon.ccsds data in
  (* Flip 16 arbitrary symbols — at the limit of what we can recover. *)
  for i = 0 to 15 do
    Bytes.set_uint8 codeword (i * 11) (Bytes.get_uint8 codeword (i * 11) lxor 0xa5)
  done;
  match Reed_solomon.decode Reed_solomon.ccsds codeword with
  | Ok recovered -> String.sub (Bytes.to_string recovered) 0 19
  | Error e -> Fmt.str "decode failed: %a" Reed_solomon.pp_error e
- : string = "hello, reed-solomon"

When the channel flips more than t = 16 symbols, the decoder reports failure rather than returning silently corrupted data:

# let data = Bytes.make 223 '\x00' in
  let codeword = Reed_solomon.encode_systematic Reed_solomon.ccsds data in
  for i = 0 to 16 do Bytes.set_uint8 codeword i 0xff done;
  match Reed_solomon.decode Reed_solomon.ccsds codeword with
  | Ok _ -> "unexpectedly recovered"
  | Error e -> Fmt.str "decode failed: %a" Reed_solomon.pp_error e
- : string = "decode failed: Chien search failed to find roots"

Licence#

ISC