4 ms·
My “foolproof” comment was based on Vandermonde matrices not always being invertible during decoding without an extra step, which tripped up multiple implementa
by akalin 8y ago
My “foolproof” comment was based on Vandermonde matrices not always being invertible during decoding without an extra step, which tripped up multiple implementations. (PAR1 suffered from this problem, then they tried to fix it with PAR2 but still failed!)
I think we discussed a while ago doing Vandermonde decoding without matrix inversion, so that’s one advantage that Vandermonde matrices have. (Although I haven’t seen an implementation do that optimization.)
I don’t actually know if Cauchy matrices apply for error correction and not just erasure codes —- I’d be interested if other people know!
- omazurov 8y agoAccording to Wikipedia, PAR1 suffered from: > The recovery algorithm had a bug, due to a flaw[1] in the academic paper[2] on which it was based. I remember that the same bug was cited by ZFS[3]. Amazing. Of all algorithm descriptions, one with a bug seems to have been picked up the most. Of course, there is nothing wrong with Vandermonde encoding itself, just don't use that paper any more. Cauchy is equivalent to Vandermonde, so it should allow for error correction to the same extent but I couldn't find any algorithm description/implementation. [1] Plank, James S.; Ding, Ying (April 2003). "Note: Correction to the 1997 Tutorial on Reed-Solomon Coding" [2] Plank, James S. (September 1997). "A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems" [3] https://github.com/illumos/illumos-gate/blob/master/usr/src/uts/common/fs/zfs/vdev_raidz.c https://github.com/illumos/illumos-gate/blob/master/usr/src/...