search

tomerfiliba-org / reedsolomon

⏳🛡 Pythonic universal errors-and-erasures Reed-Solomon codec to protect your data from errors and bitrot. Includes a future-proof zero-dependencies pure-python implementation 🔮 and an optional speed-optimized Cython/C extension 🚀
http://pypi.python.org/pypi/reedsolo
Other
358 stars 86 forks source link

Possible error in error locator (chien search)? #19

Closed lrq3000 closed 1 year ago

lrq3000 commented 4 years ago

Also, I wonder if there is an error in line 681 (of reedsolo.py) errs = len(err_loc) - 1 why the -1?

Thanks to Jonas Braun for reporting this possible issue!

Mirror of https://github.com/lrq3000/reedsolomon/issues/1

lrq3000 commented 1 year ago

Likely an error, but it does not affect decoding that much, at worst it will overestimate its capabilities (ie, try to correct when it can't, but syndrome will still fail if checked). Also the equation just after seems fishy:

    errs = len(err_loc) - 1
    if (errs-erase_count) * 2 + erase_count > nsym:
        raise ReedSolomonError("Too many errors to correct")

I need to check whether the equation is correct. I'm not sure why I subtract erase_count from errs. The Singleton Bound is errs*2 + erase_count <= nsym.

lrq3000 commented 1 year ago

Ok so I checked and everything is very fine, in fact it's because the errors locator polynomial is offset, it goes from 1 to 256 (in GF(2^8)), so that's why we must subtract -1 to get its real length. I clarified by adding some comments.