MAKE A RING

OVERVIEW

The goal of decoding is to provide decoding algorithms for error correcting codes. We tried to write algorithms in a generic way so that a lot of alphabets can be used (e.g. finite fields, finite local rings). It is up to the user of the library to give some C code that provides the arithmetic of the ring he wants to use. The word "alphabet" is badly chosen because decoding requires an alphabet to be a (not nessarily commutative) ring with identity. We will use the words "alphabet" and "ring" interchangeably.

The current page describes how to provide your own alphabet to decoding. A few alphabets, such as prime fields, are provided by decoding but are far from being optimized. For exemple, if you want optimized finite fields in caracteristic 2, you can use MPFQ. For a list of alphabets proposed by decoding see decoding-alphabets(3).

DESCRIPTION

It is strongly recommanded to have a separated file for each alphabet you want to use or implement. We first include the ring_init.h file, this is mandatory.

#include <decoding/ring_init.h>

You must give a name to the ring you are implementing with the R macro. In fact the user can provide a name via the RING_NAME function.

#ifdef RING_NAME
#define R RING_NAME
#else
#define R GF5
#endif

This name will correspond to the C type to declare elements of GF(5). All functions that manipulate elements of GF(5), such as polynomial multiplication, will see their names prefixed with GF5.

For test purpose you can define how to create the ring in MAGMA with the R_magma_decl string. It is not mandatory.

const char *R_magma_decl = __S(R) " := GF(5)";

Then you tell decoding that the ring is of type Z/nZ with n that can hold within a machine word with RING_MODN_WORD. We also say that the characteristic holds within a machine integer with RING_CHAR_UMA. Then you have to store the characteristic in the R_char variable which is a GMP integer even if the characteristic can hold within a machine integer. You also have to fill the R_uma_char variable with the characteristic if the latter holds within the former. Otherwise R_uma_char should be set to -1. If the ring is commutative you should define RING_COMM. If the ring has characteristic 2 you should define RING_CHAR2. If the ring is a finite field you should define RING_FF. Note that these macros are only accessible within decoding and activate some optimized algorithms. They are not accessible to the end-user. The R_ext_degree variable must be filled in with the degree corresponding to the extension degree of the ring over its base ring. For example, R_ext_degree is 1 for finite prime fields. Finally you have to specify the cardinality of the ring with the R_card GMP integer. If the ring is not finite then R_card should be 0.

#define RING_CHAR_UMA
#define RING_MODN_WORD
#define RING_COMM
#define RING_FF
const uma R_uma_char = 5;
const uma R_ext_degree = 1;
mpz_t R_char;
mpz_t R_card;

Now you declare the C type to represent elements of your ring. For example, with GF(5), one only needs an int to represents its elements. We typedef three different types: a pointer to the int type, an array of one int and the int type itself. The typedefs must be respectively R_ptr, R and R_content. Then you have to provide the neutral element for multiplication called R_one.

typedef int *R_ptr;
typedef int R[1];
typedef int R_content;
int R_one[1] = { 1 };

Note that R and R_ptr designate almost the same type and the second typedef is syntactic sugar.

LIST OF MANDATORY FUNCTIONS

The following functions must be provided. They follow the semantic of the GMP mpz_ functions. This document is generated from the comments of the include/decoding/rings/GF5.c, you can look at it to have a working example of a ring whose elements hold in a C int.

void R_ring_init(void);: This function is mandatory before doing anything with the ring. It performs some variables initialization.
void R_ring_clear(void);: When the ring is no more needed, you call this function to free the memory occupied by the ring, usually what was allocated by R_ring_init.
void R_clear(R a);: Frees the memory occupied by a. If you use a after a call to R_clear the behavior is undefined.
void R_clears(R a);: Free the memory occupied by a NULL-terminated list of R variables. If you use one of the variable after a call to R_clears the behavior is undefined.
void R_init(R a);: Initialize a and set its value to 0. This is the place to allocate some memory needed for a.
void R_inits(R a,...);: Initialize a NULL-terminated list of R variables, and set their values to 0. This is the place to allocate some memory needed for the variables.
void R_copy(R r,R a);: Copy the value of a into r. This must be a deep copy.
void R_swap(R r,R a);: Swap the values of r and a.
void R_init_copy(R r,R a);: Initialize r and do a deep copy of a into r.
void R_print(FILE *out,R a);: Print (prettyprint) a into the output stream out.
int R_cmp(R a,R b);: Compare a and b and returns 0 if and only if the value of a is mathematically equal to the value of b.
int R_iszero(R a);: Compare a and 0. Returns 0 if and only if a is nonzero.
void R_zero(R r);: Set r to 0.
void R_random(R r);: Set r to a random element of the ring.
void R_add(R r,R a,R b);: Set r to a + b. Note that r, a and b can point to the same memory.
void R_sub(R r,R a,R b);: Set r to a - b. Note that r, a and b can point to the same memory.
void R_sub_sub(R r,R a,R b);: Set r to r - a - b. Note that r, a and b can point to the same memory.
void R_add_mul(R r,R a,R b);: Set r to r + (a * b). Note that r, a and b can point to the same memory.
void R_sub_mul(R r,R a,R b);: Set r to r - (a * b). Note that r, a and b can point to the same memory.
void R_neg(R r,R a);: Set r to -a. Note that r and a can point to the same memory.
void R_mul(R r,R a,R b);: Set r to a * b. Note that r, a and b can point to the same memory.
void R_square(R r,R a);: Set r to a * a. Note that r and a can point to the same memory.
void R_pthroot(R r,R a);: Set r to be the p-th root of a where p is the characteristic of the ring. If the ring has characteristic zero then r = a.
int R_inv(R r,R a);: Set r to a^-1. Return 0 if and only if a has an inverse. If a has no inverse then the value of r is undefined. Note that r and a can point to the same memory.
int R_div(R r,R a,R b);: Set r to a / b). Return 0 if and only if b has an inverse. If b has no inverse then the value of r is undefined. Note that r, a and b can point to the same memory.
void R_castint(R r,int a);: Set r to the value of 1 + 1 + ... + 1 (a times) where 1 is the unity element of the ring.
void R_castuma(R r,uma a);: Set r to the value of 1 + 1 + ... + 1 (a times) where 1 is the unity element of the ring.
void R_cast_integer(R r,mpz_t a);: Set r to the value of 1 + 1 + ... + 1 (a times) where 1 is the unity element of the ring.
void R_next(R r,R a);: Set r to the element of the ring following a. Suppose that your ring has cardinality n. You must order the elements of your ring so that they can all be reached with exactly n calls to R_next. This function is useful to construct the support of Reed-Solomon codes.

AUXILIARY VARIABLES AND FUNCTIONS

You can add auxiliary variables and functions. Let say you want to add myfunc. It is recommended to prefix the function name with R_. This is how to proceed:

#define R_myfunc __C(R,_myfunc)

void R_myfunc(int a,R b);

[ ... ]

void R_myfunc(int a,R b) {
  ...
}

[ ... ]

#undef R_myfunc

The [ ... ] usually contains the implementation of the ring, at least all the functions described above. You can use the new function with the name R_myfunc before the #undef R_myfunc. The __C macros concatenates R (GF5 for example) and _myfunc. Thus name of the new function in other source files or after the #undef R_myfunc is GF5_myfunc. The same holds for variables:

#define R_myvar __C(R,_myvar)

some_type R_myvar;

[ ... ]

#undef R_myvar

Finally you must include decoding/lowlevels_decl.h at the end of the source file.

#include <decoding/lowlevels_decl.h>

AUTHOR