4 ms·
Ah, okay thanks. My coding theory is a bit weak, but it looks like this algorithm depends on the specific form of RS codes that you mentioned. I think the prese
by akalin 9y ago
Ah, okay thanks. My coding theory is a bit weak, but it looks like this algorithm depends on the specific form of RS codes that you mentioned. I think the presentation outlines a form of RS erasure codes which is more general (e.g., allows Cauchy parity matrices instead of Vandermonde-derived ones).
Using a general matrix inversion is indeed inefficient, and becomes impractical for large k. However, the special-purpose row reduction algorithm I mentioned gets to O(nm^2) which is much better, although worse than the O(nm) algorithm you mentioned, which makes sense given that that one handles more specific RS codes.
Thanks for elaborating! It's reminding me that I really should brush up on coding theory, though -- do you have any resources/textbooks you'd recommend for someone familiar with the mathematical background? (Finite fields, etc.)
- omazurov 9y agoI'm a bit rusty myself (all those small mistakes I made). I'm now more concerned with the engineering side of error correction (elegant implementations and more importantly a totally new class of dynamic error correction I have in another GitHub project). I can't recommend any good up-to-date textbook - haven't read any in long time.
- akalin 9y agoNo problem. Do you happen to have a source for the algorithm you explained, though? I recognize the parity-check matrix, but the rest I can't seem to find in any of the usual coding theory texts; usually, they treat erasures as part of the full RS decoding process.
- omazurov 9y agoThe source of the algorithm I described is my mind. It's so elementary that I believe it is omnipresent but disguised by more complicated math, usually due to other ways to define RS codes.
- akalin 9y agoI agree re. being disguised by complicated math. Although even if you think it's elementary, I encourage you to write it up somewhere, like a blog post. I'm sure there are people out there like me who would find it novel. :) If I ever do use it or write about it, I'll make sure to cite you. Thanks again!