c++redundancyerror-correctionreed-solomon# Full recovery data using reed solomon

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?

Solution

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.

- How to create 24 bit unsigned integer in C
- Are multiple variable-length arrays in a structure in C possible?
- Making recvfrom() function non-blocking
- cs50 runoff infinite loop
- Can the unsigned keyword be used in non-obvious ways?
- In C/C++ what's the simplest way to reverse the order of bits in a byte?
- Dot Product function in C language
- How to read two lines with a random numbers count from input into two arrays
- RobotC - Programming an Elevator
- Strange behavior when adding longs in RobotC
- Do unsigned functions have to return something?
- Duplicate symbols in Microsoft C library
- Using ssize_t vs int
- undefined reference to `sctp_get_no_strms'
- Passing pointer of an array to a function in C
- C Program to find day of week given date
- Embedding Python in C, linking fails with undefined reference to `Py_Initialize'
- Converting python string object to c char* using ctypes
- State-of-the-art for embedding scriptable, interactive SVG in Gtk+ applications?
- Does the stack get freed after scope block?
- VS Code's C/C++ extension says the C23 true and false keywords are undefined
- How to use Docker compose in c program?
- How to declare a pointer to a character array in C?
- How to get one character at a time
- How to get a timeout to work when connecting to a socket
- Periodically trigger pthread workers and wait for completion
- The return value goes wrong if I release something else
- Have two C compilers
- My function is not reading data from the input file properly (C)
- Consolidating GNU C's and C23's deprecated function attribute