RS-Code on schifra library - how set up polynommial?

Question

I am currently trying to get the schifra library running for making some tests to implement it later in my code.

I am currently looking at the schifra_reed_solomon_example02.cpp and try to understand how I have to set the values to suite my needs.

/* Finite Field Parameters */
   const std::size_t field_descriptor                 =   8; // GF(2^8) ok
   const std::size_t generator_polynommial_index      = 120; // what is this?
   const std::size_t generator_polynommial_root_count =  32; // polynomial up to x^32

   /* Reed Solomon Code Parameters */
   const std::size_t code_length = 255;  // amount of symbols in codeword
   const std::size_t fec_length  = 32;  // minimal distance d ?
   const std::size_t data_length = code_length - fec_length; // amount of symbols my message has

So what I try to have is an RS-Code for n, k , d = (128, 16, 113)

And I would proceed the following:

/* Finite Field Parameters */
   const std::size_t field_descriptor                 =   8; // I want GF(2^8)
   const std::size_t generator_polynommial_index      = 120; // still not knowing
   const std::size_t generator_polynommial_root_count =  16; // because polynomial up to 16

   /* Reed Solomon Code Parameters */
   const std::size_t code_length = 128;  // 128 byte codewords
   const std::size_t fec_length  = 113;  // minimal distance, 113 because d = n - k +1
   const std::size_t data_length = 16; 

I then receive at encoding a mesage an error.

schifra::galois::field_polynomial generator_polynomial(field);

   schifra::sequential_root_generator_polynomial_creator(field,
                                                         generator_polynommial_index,
                                                         generator_polynommial_root_count,
                                                         generator_polynomial);

   /* Instantiate Encoder and Decoder (Codec) */
   schifra::reed_solomon::encoder<code_length,fec_length> encoder(field,generator_polynomial);
   schifra::reed_solomon::decoder<code_length,fec_length> decoder(field,generator_polynommial_index);

   std::string message = "A professional i"; // its 16 bytes
   std::cout << "Original Message:   [" << message << "]" << std::endl;
  message = message + std::string(data_length - message.length(),static_cast<unsigned char>(0x00)); // this one is also done in example

   std::cout << "Original Message:   [" << message << "]" << std::endl;
   std::cout << "Message length: " << message.length() << std::endl; // still 16 bytes

   /* Instantiate RS Block For Codec */
   schifra::reed_solomon::block<code_length,fec_length> block;

   /* Transform message into Reed-Solomon encoded codeword */
   if (!encoder.encode(message,block))
   {
      std::cout << "Error - Critical encoding failure!" << std::endl;
      return 1;
   }

The Error - Critical encoding failure! is then given.

I think what I do wrong is setting up the polynommial correct - maybe someone can help me?

Answer 1

I am a beginner who tried to use the Schifra library. I didn't know anything about Reed Solomon codes and after weeks of digging into source code, I found a combination that always works. I still don't know any of the math that the RS codes use.

Some jargon that might be useful:

• Symbol: Smallest quantum of information that the RS code will recognize(generally set to 8 bits(1 byte))
• FEC: It is the redundancy or the error correction "symbols" which are appended at the end of your data
• Data: The data you want to generate RS codes for.
• Galois field: A polynomial or a mapping that the Reed Solomon code uses to do error correction (I don't know any math that goes behind RS codes)

The combination that works and making some sense out of the initializing variables without delving into the math:

• Field descriptor= Size of a symbol (generally set to 8 bits in length)
• Generator polynomial index= No clue what this is but setting it to 0 always works and gives a small performance boost compared to other values.
• Generator Polynomial Root Count= Needs to be equal to FEC length
• Code length= This value HAS to be (2^(symbol size or Field Descriptor)-1). It denotes the number of symbols your final encoded string (Data symbols+ Error Corr Symbols). Note that the total size of the encoded string in bits equals Code length* symbol size.
• FEC length: Number of error correction symbols.
• Data length: Number of data symbols. (As initiated in examples as Code_length - FEC_length) this should not be touched.

It should be noted that for a particular symbol size the code length is fixed and one can vary what percent of that code length will be data and what will be error correction symbols. And as common sense suggests, more error correction symbols leads to more error correction capability.

On running the encoder, you pass a block object along with the data as arguments.

On running the method encoder.encode the "block" is populated with the encoded data(Data + ECC).

After corruption, decoding is done. The number of errors, erasures which can be corrected by the decoder is explained in this link

The decoder takes the block and the erasure list(if applicable) as arguments and returns the original message/data if the number of erasure and errors were within the range of the ECC(look at the link).