REED-SOLOMON(3)

📦
version 1.0+20161003 · 2 versions
, in ubuntu jammy

💖 REED-SOLOMON 💖

okay bestie, welcome to REED-SOLOMON(3) — it's a Library Functions Manual situation and it's literally about error control, which is giving protective bestie energy ngl 🫶

✨ NAME ✨

init_rs_int, encode_rs_int, decode_rs_int, free_rs_int, init_rs_char, encode_rs_char, decode_rs_char, free_rs_char, encode_rs_8, decode_rs_8, encode_rs_ccsds, decode_rs_ccsds — Reed-Solomon encoding/decoding ✨

🌸 SYNOPSIS 🌸

#include "fec.h"

void *init_rs_int(int symsize,int gfpoly,int fcr,int prim,
     int nroots,int pad);

void encode_rs_int(void *rs,int *data,int *parity);

int decode_rs_int(void *rs,int *data,int *eras_pos,int no_eras);

void free_rs_int(void *rs);

void *init_rs_char(int symsize,int gfpoly,int fcr,int prim,
     int nroots,int pad);

void encode_rs_char(void *rs,unsigned char *data,
     unsigned char *parity);

int decode_rs_char(void *rs,unsigned char *data,int *eras_pos,
     int no_eras);

void free_rs_char(void *rs);

void encode_rs_8(unsigned char *data,unsigned char *parity,
     int pad);

int decode_rs_8(unsigned char *data,int *eras_pos,int no_eras,
     int pad);

void encode_rs_ccsds(unsigned char *data,unsigned char *parity,
     int pad);

int decode_rs_ccsds(unsigned char *data,int *eras_pos,int no_eras,
     int pad);

unsigned char Taltab[256];
unsigned char Tal1tab[256];

🦋 DESCRIPTION 🦋

so these functions implement Reed-Solomon error control encoding and decoding. and because performance matters in, like, a variety of applications, you get three whole sets of functions. to get at them, you just add -lfec to your linker command line. that's it. that's the vibe check 💅

the functions whose names end in _int handle data in integer arrays, which means arbitrarily large codewords, limited only by machine resources. no cap, as big as your machine can handle 👑

the functions whose names end in _char take unsigned char arrays and can handle codes with symbols of 8 bits or less — i.e., codewords of 255 symbols or less.

encode_rs_8 and decode_rs_8 implement one very specific (255,223) code with 8-bit symbols, specified by the CCSDS: a field generator of 1 + X + X^2 + X^7 + X^8, and a code generator with first consecutive root = 112 and a primitive element of 11. these functions use the conventional polynomial form, not the dual-basis specified in the CCSDS standard, to represent symbols. this code can be shortened by giving a non-zero pad value, which produces a (255-pad,223-pad) code. the padding consists of the specified number of zeroes at the front of the full codeword. slay.

for full CCSDS compatibility, encode_rs_ccsds and decode_rs_ccsds are provided. these use two lookup tables: Taltab to convert from conventional to dual-basis, and Tal1tab to do the inverse mapping from dual-basis back to conventional form — before and after calls to encode_rs_8 and decode_rs_8. iconic.

the _8 and _ccsds functions do not require initialization 🎀

to use the general purpose RS encoder or decoder — that's the _char or _int versions — you have to call init_rs_int or init_rs_char first, whichever fits. the arguments go like this:

  • symsize — gives the symbol size in bits, up to 8 for init_rs_char or 32 for init_rs_int on a machine with 32-bit ints (though a code that huge would exhaust memory limits on a 32-bit machine, fr). the resulting Reed-Solomon code word will have 2^symsize - 1 symbols, each containing symsize bits. and yes you can shorten that codeword with the pad parameter described below 💖
  • gfpoly — gives the extended Galois field generator polynomial coefficients, with the 0th coefficient in the low order bit. the polynomial must be primitive. if it's not, the call will fail and NULL will be returned. so like, be careful 🫣
  • fcr — gives, in index form, the first consecutive root of the Reed Solomon code generator polynomial.
  • prim — gives, in index form, the primitive element in the Galois field used to generate the Reed Solomon code generator polynomial.
  • nroots — gives the number of roots in the Reed Solomon code generator polynomial. this equals the number of parity symbols per code block.
  • pad — gives the number of leading symbols in the codeword that are implicitly padded to zero in a shortened code block.

the resulting Reed-Solomon code has parameters (N,K), where N = 2^symsize - pad - 1 and K = N-nroots. math is mathing ✨

encode_rs_char and encode_rs_int accept the pointer returned by init_rs_char or init_rs_int respectively, to encode a block of data using the specified code. the input data array is expected to contain K symbols (of symsize bits each, right justified in each char or int) and nroots parity symbols will be placed into the parity array, right justified. cute and tidy.

the decode_ functions correct the errors in a Reed-Solomon codeword of N symbols, up to the capability of the code. an optional list of "erased" symbol indices may be given in the eras_pos array to assist the decoder — this parameter may be NULL if no erasures are given. the number of erased symbols must be given in the no_eras parameter.

🚨 okay so listen. to maximize performance, the encode and decode functions do no "sanity checking" of their inputs. decoder failure may result if eras_pos contains duplicate entries, and both encoder and decoder will fail if an input symbol exceeds its allowable range. (symbol range overflow cannot occur with the _8 or _ccsds functions, or with the _char functions when 8-bit symbols are specified.) no cap, this is the dangerous part 💀

the decoder corrects the symbols "in place", returning the number of symbols in error. if the codeword is uncorrectable, -1 is returned and the data block is left unchanged. if eras_pos is non-null, it's used to return a list of corrected symbol positions, in no particular order. which means the array you pass through this parameter must have at least nroots elements, or you risk a possible buffer overflow. do not skip that part bestie 😭

free_rs_int and free_rs_char free the internal space allocated by init_rs_int and init_rs_char, respectively. clean up after yourself, main character energy 🌈

the functions encode_rs_8 and decode_rs_8 do not have corresponding init and free, and they also don't take the rs argument that the other functions accept, because their parameters are statically compiled. these functions implement a code equivalent to calling

init_rs_char(8,0x187,112,11,32,pad);

and then using the resulting pointer with encode_rs_char and decode_rs_char. so convenient 🎀

💜 RETURN VALUES 💜

init_rs_int and init_rs_char return a pointer to an internal control structure that must be passed to the corresponding encode, decode and free functions. these functions return NULL on error.

the decode_ functions return a count of corrected symbols, or -1 if the block was uncorrectible.

👑 AUTHOR 👑

Phil Karn, KA9Q (karn@ka9q.net), based heavily on earlier work by Robert Morelos-Zaragoza (robert@spectra.eng.hawaii.edu) and Hari Thirumoorthy (harit@spectra.eng.hawaii.edu). extra improvements suggested by Detmar Welz (dwelz@web.de). shoutout to the legends 🫶

Copyright 2004, Phil Karn, KA9Q. May be used under the terms of the GNU Lesser General Public License (LGPL).

🔍 SEE ALSO 🔍

⭐ NOTE ⭐

CCSDS chose the "dual basis" symbol representation because it simplified the implementation of a Reed-Solomon encoder in dedicated hardware. however, this approach holds no advantages for a software implementation on a general purpose computer. so use of the dual basis is recommended only if you need compatibility with the CCSDS standard — e.g., to decode data from an existing spacecraft using the CCSDS standard 🛰️✨ if you just want a fast (255,223) RS codec without needing to interoperate with a CCSDS standard code, use encode_rs_8 and decode_rs_8. periodt 💅

and that's the whole page, bestie 🎀 this was REED-SOLOMON(3) from the Library Functions Manual — go forth and correct those errors, you've got this 🌸💖🦋

📦 where this page comes from