c++error-correctionreed-solomon

What is the value of the ideal value of the generator polynomial index in the Schifra library for Reed-Solomon error correcting code?


I am trying to use the the Schifra Reed-Solomon error correcting code library in a project. I have no background about how Reed-Solomon code and Galois field work. I am having trouble figuring out the ideal value of the generator_polynomial_index for a 16 bit symbol(field descriptor).

My code works for the the index 0 and many others. I have tried all values of index. The code works for a lot of them (0-32724 & 32779-65485 to be precise) but

Questions

  1. What is the most ideal value?
  2. What is changing if I switch to another value of index(which also works but is not ideal)?

Rest of my discoveries:

  • field_descriptor = symbol size(bits/symbol)

  • code_length(Total number of symbols(data symbols + error-correction code symbols)) = 2^symbol_size - 1 (Library only supports this value of code length)

  • generator_polynomial_root_count = fec_length(redundancy or number of error-correction symbols)

  • Errors are measured in symbols and not bits i.e. 1 incorrect bit in a particular symbol is counted as 1 error. But even if all 16 bits are incorrect; it would count as 1 error(not 16).

  • The maximum number of errors and erasures which can be rectified should obey the following inequality: 2*num_errors + num_erasures < fec_length

Please correct me if I am mistaken anywhere

const std::size_t field_descriptor                =   16;
const std::size_t generator_polynomial_index      =  index;
const std::size_t generator_polynomial_root_count = 50;

/* Reed Solomon Code Parameters */
const std::size_t code_length = 65535;
const std::size_t fec_length  =  50;
const std::size_t data_length = code_length - fec_length;

/* Instantiate Finite Field and Generator Polynomials */
const schifra::galois::field field(field_descriptor,
schifra::galois::primitive_polynomial_size14, schifra::galois::primitive_polynomial14);

Solution

  • what is the ideal value of the generator_polynomial_index

    There probably isn't an "ideal" value.

    I had to look at the github code to determine that the generator field index is the log of the first consecutive root of the generator polynomial.

    https://github.com/ArashPartow/schifra/blob/master/schifra_sequential_root_generator_polynomial_creator.hpp

    Typically the index is 0 (first consecutive root == 1) or 1 (first consecutive root == Alpha (the field primitive)). Choosing index = 1 is used for a "narrow sense" code. It slightly simplifies the Forney Algorithm. Link to wiki article, where "c" represents the log of the first consecutive root (it lists the roots as a^c, a^(c+1), ...):

    https://en.wikipedia.org/wiki/Forney_algorithm

    Why use a narrow sense code:

    https://math.stackexchange.com/questions/2174159/why-should-a-reed-solomon-code-be-a-narrow-sense-bch-code

    For hardware, the number of unique coefficients can be reduced by using a self-reciprocal generator polynomial, where the first consecutive root is chosen so that the generator polynomial is of the form: 1 x^n + a x^(n-1) + b x^(n-2) + ... + b x^2 + a x + 1. For 32 roots in GF(2^16), the first consecutive root is alpha^((65536-32)/2) = alpha^32752, and the last consecutive root would be alpha^32783. Note this is only possible with a binary field GF(2^n), and not possible for non-binary fields such as GF(929) (929 is a prime number). The question shows a range for index that doesn't include 32752; if 32752 doesn't work with this library, it's due to some limitation in the library, and not with Reed Solomon error correction algorithms.

    Other than these 3 cases, index = 0, 1, or self-reciprocal generator polynomial, I'm not aware of any reason to choose a different index. It's unlikely that the choice of index has any effect on trying to decode beyond the normal limits.


    The maximum number of errors and erasures which can be rectified should obey the following inequality: 2*num_errors + num_erasures < fec_length

    That should be

    2*num_errors + num_erasures <= fec_length