1. Sub-Quadratic Decoding of One-Point Hermitian Codes.
- Author
-
Nielsen, Johan S. R. and Beelen, Peter
- Subjects
- *
HERMITIAN structures , *DECODING algorithms , *POLYNOMIAL rings , *PROBABILITY theory , *ASYMPTOTIC distribution - Abstract
We present the first two sub-quadratic complexity decoding algorithms for one-point Hermitian codes. The first is based on a fast realization of the Guruswami–Sudan algorithm using state-of-the-art algorithms from computer algebra for polynomial-ring matrix minimization. The second is a power decoding algorithm: an extension of classical key equation decoding which gives a probabilistic decoding algorithm up to the Sudan radius. We show how the resulting key equations can be solved by the matrix minimization algorithms from computer algebra, yielding similar asymptotic complexities. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF