YOUR QUICK AND DIRTY WAY TO LIST DECODING WITH GURUSWAMI-SUDAN

OVERVIEW

This page describes how to use the library for list decoding with the Guruswami-Sudan algorithm.

DESCRIPTION

You do not have time, do not know how or do not want to read the documentation of decoding but still, you want to use it for list decoding with the guruswami-Sudan algorithm.

HOW TO USE GURUSWAMI-SUDAN QUICKLY?

Go to your favorite directory where you write code. Create any .c file, say foo.c containing

#include <decoding/decoding.h>

#define RING_NAME ring
#define PRIME 101
#include <decoding/rings/gfp_word.c>
#include <decoding/algos.c>

#define N   50 /* length of the code */
#define K   10 /* dimension of the code */
#define TAU 22 /* number of errors to put */

int main(void) {
  int nc,i;
  ring_vec m,y,e,*c;
  ring_rs_code rs;
  ring_ring_init();
  ring_vec_inits(m,y,e,0);
  ring_rs_code_init_with_support(rs,N,K);
  ring_rs_code_random_codeword(m,rs);
  ring_vec_random_hamming_weight(e,N,TAU);
  ring_vec_add(y,m,e);
  nc = ring_rs_code_guruswami_sudan_koetter(&c,rs,y,GURUSWAMI_SUDAN_MAX_ERRORS);
  for( i = 0 ; i < nc ; i++ ) {
    /* do something with c[i], 
       the i-th codeword in the list
       returned by the decoding algorithm. */
  }
  return 0;
}

We first make a prime field, here we work with GF(101). Then we declare and initialize the vectors that we need. We first need to initialize the field.

ring_vec m,y,e,*c;
[...]
ring_ring_init();
ring_vec_inits(m,y,e,0);

Then we build a Reed-Solomon code over ring which is GF(101) in our exemple.

ring_rs_code rs;
[...]
ring_rs_code_init_with_support(rs,N,K);

We choose a random codeword and error of weight TAU to build a received word wuth TAU errors.

ring_rs_code_random_codeword(m,rs);
ring_vec_random_hamming_weight(e,N,TAU);
ring_vec_add(y,m,e);

Finally, we call the Guruswami-Sudan algorithm to correct as many errors it can. It will return the number nc of elements in the array c of codewords.

nc = ring_rs_code_guruswami_sudan_koetter(&c,rs,y,GURUSWAMI_SUDAN_MAX_ERRORS);

You can also use the library without installing it, for more details please see decoding-cwi(3).

AUTHOR

Written by Guillaume Quintin (quintin@lix.polytechnique.fr).

SEE ALSO

decoding-cwi(3).