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
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);
what is the ideal value of the generator_polynomial_index
If using Forney algorithm to generate error values, then ideal value for index is 1, which translates into a "narrow sense code". 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.
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:
For hardware or if using multiply by constant tables in software, 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.
The maximum number of errors and erasures which can be rectified should obey the following inequality: 2*num_errors + num_erasures < fec_length
The limit is:
2*num_errors + num_erasures <= fec_length
Doing fewer corrections provides some margin against mis-correction due to too many errors + erasures.