Sub-quadratic decoding of one-point hermitian codes

Research output: Contribution to journalJournal articleResearchpeer-review

233 Downloads (Pure)

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.
Original languageEnglish
JournalIEEE Transactions on Information Theory
Volume61
Issue number6
Pages (from-to)3225-3240
ISSN0018-9448
DOIs
Publication statusPublished - 2015

Bibliographical note

Copyright 2015 IEEE. IEEE. Personal use of this material is permitted. Permission
from IEEE must be obtained for all other uses, in any current or future media, including reprinting /republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

Keywords

  • Hermitian codes
  • AG codes
  • list decoding
  • Guruswami–Sudan
  • power decoding

Cite this