The functions presented below provide a coherent calling interface. For example, they do not require the user to manage the memory of the object manipulated by the library. The functions below shall be used by any user of the library and shall be preferred over their low levels counterparts.
To use the following functions with a given ring you must
prefix their names with the name you gave the ring you
are using. Also, the name of all types, vectors (vec)
and Reed-Solomon codes (rs) must be prefixed by the
name of the ring. Consider the following example which does the
addition of two vectors over GF(101).
#include <decoding/decoding.h>
#define RING_NAME my_field
#define PRIME 101
#include <decoding/rings/gfp_word.c>
int main(void) {
my_field_vec a,b,c;
my_field_ring_init();
my_field_inits(a,b,c,NULL);
my_field_add(c,a,b);
return 0;
}We first declare three vectors a, b and c of type
my_field_vec.
my_field_vec a,b,c;The type my_field_vec is in fact the
type vec corresponding to vectors, but prefixed with
my_field_ which is the name we gave to GF(101). Therefore
the type my_field_vec corresponds to vectors with coefficients
in GF(101). The same reasoning holds for all the following
functions.
my_field_ring_init();
my_field_inits(a,b,c,NULL);
my_field_add(c,a,b); This mecanism allows one to use several rings at the same time.
#include <decoding/decoding.h>
#define RING_NAME gf101
#define PRIME 101
#include <decoding/rings/gfp_word.c>
#include <decoding/algos.c>
#define RING_NAME gf2_8
#define EXT_DEGREE 8
#include <decoding/rings/gf2n_word.c>
#include <decoding/algos.c>
int main(void) {
gf101_vec a,b,c;
gf2_8_vec u,v,w;
gf101_ring_init();
gf2_8_ring_init();
gf101_inits(a,b,c,NULL);
gf2_8_inits(u,v,w,NULL);
gf101_add(c,a,b);
gf2_8_add(w,u,v);
return 0;
}The uma type (Unaligned Memory Access) shall be used everywhere
you need indices. In particular, all function in decoding returning
polynomial degrees, valuations, number of elements within a certain
set or list are all of type uma. It usually corresponds to long,
but do not assume that. You can safely assume that every int can be
casted to uma without problem. When using decoding remember to
use uma and not int for array indices.
The crit_* family of funtions indicates a critical zone in the
code where all the arithmetic operations involving uma's must
be performed correctly. For example, suppose that you have to
multiply two polynomials of degree d1 and d2. Then you shall
use
uma d3;
d3 = crit_add(d1,d2);to compute the degree of the product of the two polynomials.
If the sum of d1 and d2 does not hold within a machine
word the SIGABRT signal is raised, otherwise d3 will
be equal to d1 + d2. All arithmetic operations have their
crit_ counterpart.
uma crit_add(a,b);Return a + b if it holds within a machine.
If a or b is negative or if it overflows the SIGABRT
signal is raised.
uma crit_sub(a,b);Return a - b if it holds within a machine.
If a or b is negative or if it overflows the SIGABRT
signal is raised.
uma crit_mul(a,b);Return a * b if it holds within a machine.
If a or b is negative or if it overflows the SIGABRT
signal is raised.
uma crit_div(a,b);Return a / b.
If a or b is negative or if it overflows the SIGABRT
signal is raised.
void vec_init(vec r);Initialize the vector r.
This function must called before anything else.
void vec_inits(vec r,...);Initialize a NULL-terminated list of vectors. This function must called before anything else.
void vec_clear(vec r);Free the memory occupied by the vector r.
You must not use r after a call to this function.
If you want to use r you must make a call to vec_init.
void vec_clears(vec r,...);Free a NULL-terminated list of vectors.
You must not use the vectors after a call to this function.
If you want to use some or all of the vectors you must make
calls vec_init or vec_inits.
void vec_zero(vec r);Set all the components of r to zero.
void vec_append(vec r,R a);Append a to r.
void vec_random(vec r);Set all the compoenets of r to random elements of the ring.
void vec_random_hamming_weight(vec r,uma nr,uma w);Set r to be a random vector of length nr and
Hamming weight w.
void vec_add(vec r,vec a,vec b);Set r to a + b.
If a and b have not the same length
the shortest vector is padded with zeros.
void vec_sub(vec r,vec a,vec b);Set r to a - b.
If a and b have not the same length
the shortest vector is padded with zeros.
void vec_mul_by_cte(vec r,vec a,R b);Set r to a * b.
void vec_set_coeff(vec r,R a,uma i);Set the ith coefficient of r to a.
void vec_get_coeff(R r,vec a,uma i);Set r to the ith ceofficient of a.
uma vec_get_len(vec a);Return the length of a.
uma vec_hamming_weight(vec a);Return the Hamming weight of a.
uma vec_hamming_distance(vec a,vec b);Return the Hamming distance between a and b.
If a and b have the not the same size then
-1 is returned.
uma vec_copy(vec r,vec a);Make a deep copy of a into r.
uma vec_cmp(vec a,vec b);Return 0 if and only if a equals b.
If a and b do not have the same length they
are not equal.
void vec_ptr_clear(vec *a,uma n);Clear the array a of vectors of size n.
void vec_print(FILE *out,vec_ptr a);Pruma a into out.
void rs_code_init(rs_code rs,uma n,uma k);Initialize rs of length n and dimension k.
This function must be called before doing anything else with rs.
The support of rs will be a zero vector.
void rs_code_init_with_support(rs_code rs,uma n,uma k);Initialize rs of length n and dimension k.
This function must be called before doing anything else with rs.
Decoding will attempt to create the support of rs:
it will first set the first coordinate to zero, then
it will use R_next to set the other coordinates.
Make sure that the ring you are using has enough elements.
For exemple, if the ring is a prime field gfp then the
support will be set to [0,1,2,3,...,n].
void rs_code_clear(rs_code rs);Free the memory occupied by rs.
void rs_code_random(vec r,rs_code rs);Set r to be a random codeword of rs.
uma rs_code_sudan_koetter(vec **r,rs_code rs,vec y,uma tau);Given a Reed-Solomon code rs and a received word y with at most
tau errors, return the number of codewords within distance tau
of y and set r to an array containing the codewords.
The Sudan algorithm is used, the interpolation step is done with the
Koetter algorithm.
uma rs_code_guruswami_sudan_koetter(vec **r,rs_code rs,vec y,uma tau);Given a Reed-Solomon code rs and a received word y with at most
tau errors, return the number of codewords within distance tau
of y and set r to an array containing the codewords.
The Guruswami-Sudan algorithm is used, the interpolation step is done
with the Koetter algorithm.
uma rs_code_gao(vec r,rs_code rs,vec y);Given a Reed-Solomon code rs and a received word y, set r
to be the codeword at distance at most half the minimum distance
of y if it exists, in which case 1 is returned.
If no codeword is found 0 is returned.
In fact rs_code_gao return the number of codewords around y.
The Gao unique decoding algorithm is used.
void *ll_malloc(uma n);Allocate n bytes of memory and return a pointer to the allocated
region.
If any error occur during malloc the SIGABRT signal is raised
by the abort function.
void *ll_realloc(void *ptr,uma n);Change the size of the memory block pointed to by ptr to n bytes.
If any error occur during malloc the SIGABRT signal is raised
by the abort function.
void *ll_calloc(uma n);Allocate n bytes of memory and return a pointer to the allocated
region. The memory is set to zero.
If any error occur during malloc the SIGABRT signal is raised
by the abort function.
void ll_free(void *p);Free the memory space pointed to by p.
The following functions allow one to compute the parameters to give the Sudan and Guruswami-Sudan algorithms. They apply to all Reed-Solomon codes over any kind of ring. That's the reason they take as arguments only the length and the dimension of the Reed-Solomon code and, for some, the number of errors to be corrected.
int sudan_max_errors(int n,int k);Return the maximum number of errors that can be corrected by the
Sudan algorithm for a Reed-Solomon code of length n and
dimension k. (Lemma 8, page 6 of Decoding Reed-Solomon codes
beyond the Error-Correction Diameter, Madhu Sudan.)
int sudan_list_size(int n,int k,int tau);Return the list-size for the Sudan algorithm given the length
n and the dimension k of the Reed-Solomon code, and the
number of errors tau that one wants to correct.
int guruswami_sudan_max_errors(int n,int k);Return the maximum number of errors that can be corrected by the
Guruswami-Sudan algorithm for a Reed-Solomon code of length n and
dimension k. (Theorem 8, page 8 of Improved Decoding of
Reed-Solomon and Algebraic-Geometry Codes, Venkatesan Guruswami
and Madhu Sudan.)
int guru_sudan_mult(int n,int k,int tau);Return the multitplicity of the interpolating curve
of the Guruswami-Sudan algorithm for a Reed-Solomon code
of length n and dimensions k where tau errors have
to be corrected. (Lemma 7, page 8 of Improved Decoding of
Reed-Solomon and Algebraic-Geometry Codes, Venkatesan Guruswami
and Madhu Sudan.)
int guruswami_sudan_list_size(int n,int k,int tau,int m);Return the list-size for the Guruswami-Sudan algorithm given the
length n and the dimension k of the Reed-Solomon code, and the
number of errors tau that one wants to correct with multiplicity
m.
int guruswami_sudan_errors(int n,int k,int m);Return the maximum number of errors that can be corrected
by the Guruswami-Sudan algorithm given a Reed-Solomon code
of length n, dimension k and the multiplicity m.
int bitsize(unsigned long a);Return the minimum number of bits neede to represent a.
int half_log2(unsigned long a);Return the greatest exponent n such that 2^n < a.
Written by Guillaume Quintin (quintin@lix.polytechnique.fr).
decoding-defines(3),
decoding-alphabets(3).