Improving erasure-resilient encoding/decoding by combining Cauchy and Hankel/Toeplitz matrix structure
Victor Pan
We combine Cauchy and Toeplitz/Hankel matrix structure to improve the estimated running time and memory space of the known practical schemes for erasure-resilient encoding/decoding. Both encoding and decoding stages can be performed in nearly linear time by involving polynomial interpolation and multipoint evaluation. Due to the large overhead constants of the asymptotically fast known algorithms for the latter tasks (particularly, for interpolation), the resulting encoding/decoding scheme is, however, considered practically inferior to the more straightforward quadratic time algorithms. We propose a new algorithm (with its three variations at the encoding stage) that substantially decreases the latter overhead constants at both encoding and decoding stages. At the encoding stage, the algorithm also yields acceleration by logarithmic factor – to reach the complexity level of FFT or polynomial multiplication. Our computations do not involve polynomial interpolation. Multipoint polynomial evaluation is kept local to only one substage of the decoding computations. Even if this substage is replaced by the known algorithms running in quadratic time, our improvements at the other stages makes our algorithm practically very promising. Technically, we achieve our progress by combining the Cauchy structure of the generator matrix with Hankel/Toeplitz matrix structure.