REED-SOLOMON(3)REED-SOLOMON(3)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 "rs.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
These functions implement Reed-Solomon error control encoding and
decoding. For optimal performance in a variety of applications, three
sets of functions are supplied. To access these functions, add "-lrs"
to your linker command line.
The functions with names ending in _int handle data in integer arrays,
permitting arbitrarily large codewords limited only by machine
resources.
The functions with names ending in _char take unsigned char arrays and
can handle codes with symbols of 8 bits or less (i.e., with codewords
of 255 symbols or less).
encode_rs_8 and decode_rs_8 implement a 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 polyno‐
mial form, not the dual-basis specified in the CCSDS standard, to rep‐
resent symbols. This code may be shortened by giving a non-zero pad
value to produce a (255-pad,223-pad) code. The padding will consist of
the specified number of zeroes at the front of the full codeword.
For full CCSDS compatibility, encode_rs_ccsds and decode_rs_ccsds are
provided. These functions use two lookup tables, Taltab to convert from
conventional to dual-basis, and Tal1tab to perform the inverse mapping
from dual-basis to conventional form, before and after calls to
encode_rs_8 and decode_rs_8.
The _8 and _ccsds functions do not require initialization.
To use the general purpose RS encoder or decoder (i.e., the _char or
_int versions), the user must first call init_rs_int or init_rs_char as
appropriate. The arguments are as follows:
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 such a huge code
would exhaust memory limits on a 32-bit machine). The resulting Reed-
Solomon code word will have 2^symsize - 1 symbols, each containing sym‐
size bits. The codeword may be shortened with the pad parameter
described below.
gfpoly gives the extended Galois field generator polynomial coeffi‐
cients, with the 0th coefficient in the low order bit. The polynomial
must be primitive; if not, the call will fail and NULL will be
returned.
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^sym‐
size - pad - 1 and K = N-nroots.
The encode_rs_char and encode_rs_int functions 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.
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.
To maximize performance, the encode and decode functions perform 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.)
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 unchanged. If eras_pos is non-null, it is used to
return a list of corrected symbol positions, in no particular order.
This means that the array passed through this parameter must have at
least nroots elements to prevent a possible buffer overflow.
The free_rs_int and free_rs_char functions free the internal space
allocated by the init_rs_int and init_rs_char functions, respecitively.
The functions encode_rs_8 and decode_rs_8 do not have corresponding
init and free, nor do they take the rs argument accepted by the other
functions as their parameters are statically compiled. These functions
implement a code equivalent to calling
init_rs_char(8,0x187,112,11,32,pad);
and using the resulting pointer with encode_rs_char and decode_rs_char.
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 Thiru‐
moorthy (harit@spectra.eng.hawaii.edu). Extra improvements suggested by
Detmar Welz (dwelz@web.de).
COPYRIGHT
Copyright 2002, Phil Karn, KA9Q. May be used under the terms of the GNU
General Public License (GPL).
SEE ALSO
CCSDS 101.0-B-5: Telemetry Channel Coding. http://www.ccsds.org/docu‐
ments/pdf/CCSDS-101.0-B-5.pdf
NOTE
CCSDS chose the "dual basis" symbol representation because it simpli‐
fied the implementation of a Reed-Solomon encoder in dedicated hard‐
ware. However, this approach holds no advantages for a software imple‐
mentation on a general purpose computer, so use of the dual basis is
recommended only if compatibility with the CCSDS standard is needed,
e.g., to decode data from an existing spacecraft using the CCSDS stan‐
dard. 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.
REED-SOLOMON(3)
