Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages


home | help
REED-SOLOMON(3)		   Library Functions Manual	       REED-SOLOMON(3)

       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

       #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];

       These  functions	 implement Reed-Solomon	error control encoding and de-
       coding. 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 re-

       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  en-
       code_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 de-
       scribed 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  re-

       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  im-
       plicitly	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  re-
       turned  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 re-
       turn  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 al-
       located 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


       and using the resulting pointer with encode_rs_char and decode_rs_char.

       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.

       Phil Karn, KA9Q (,	 based	heavily	 on  earlier  work  by
       Robert Morelos-Zaragoza ( and Hari	Thiru-
       moorthy ( Extra improvements suggested by
       Detmar Welz (

       Copyright 2002, Phil Karn, KA9Q.	May be used under the terms of the GNU
       General Public License (GPL).

       CCSDS 101.0-B-5:	Telemetry Channel Coding.

       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 in-
       teroperate with a CCSDS standard	code, use encode_rs_8 and decode_rs_8.



Want to link to this manual page? Use this URL:

home | help