Full recovery data using reed solomon

Question

I'm testing a Reed Solomon algorithm from this repository in order to recover info in case something is externally changed.

Assuming:

m = bits per symbol
k = data
r = redundance 
n = bits per block = r + k = 2^m - 1
t = error correction = (n - k) / 2

I can codify and recover info using the following parameters:

m = 8
n = 255
r = 135
k = 120
t = 67

And works perfectly, I can recover 67 errors.

My assumtions are:

Only data will be corrupted, no redundancy.
To get full recovery n = 3 * k --> r = 2 * k.
Then n = 255 so r in this case shall be 170.
So I must have GF(2^m) and RS [n, k, n - k + 1] for use is GF(2^8) and RS [255, 85, 171]

With these parameters I get the error:

Error - Failed to create sequential root generator!

This means that library function make_sequential_root_generator_polynomial:

const std::size_t field_descriptor                =   8;    /* m = bit per symbol */
const std::size_t generator_polynomial_index      = 120;
const std::size_t generator_polynomial_root_count = 170;    /* root shall be equal to redundance */
const schifra::galois::field field(field_descriptor,
                                   schifra::galois::primitive_polynomial_size06,
                                   schifra::galois::primitive_polynomial06);
    if (
         !schifra::make_sequential_root_generator_polynomial(field,
                                                             generator_polynomial_index,
                                                             generator_polynomial_root_count,
                                                             generator_polynomial)
       )
    {
       std::cout << "Error - Failed to create sequential root generator!" << std::endl;
       return false;
    }

My problem is that I don't know why the algorithm fails. I think I have a concept problem, bug after read about the topic here and here, I don't get why is not possible.

Is it possible to use according assumtions or theory say that this is not possible?

Is the object field being created (field != NULL)? – mahesh May 25 '18 at 09:21 — mahesh, May 25 '18 at 09:21
field is created, with less redundant data works. – vgonisanz May 25 '18 at 09:27 — vgonisanz, May 25 '18 at 09:27

rcgldr · Accepted Answer · 2018-05-26T00:00:16.430

The current code in the question is failing because it sets

generator_polynomial_index = 120;

and 120 (index) + 170 (root count) is > 255 (field size), which is checked for in

make_sequential_root_generator_polynomial()

generator_polynomial_index is normally set to 0 (first consecutive root = 1) or 1 (first consecutive root = field primitive = 2), unless the goal is to use a self-reciprocal generator polynomial.

Even in the case of a self-reciprocal poly, for 170 roots, generator_polynomial_index = 128 - (170/2) = 43. Setting it to 120 is unusually high.

It could be possible for this to work as the roots are sequential powers modulo 255, so they could just wrap around, 2^120, 2^121, ... , 2^253, 2^254, 2^255=2^0, 2^256 = 2^1, ..., as this is done for self-reciprocal polynomials for an odd number of roots generator_polynomial_index = (255 - (number of roots / 2)), but perhaps the rest of the code has an issue with this.

Full recovery data using reed solomon

1 Answers1