Johan Rosenkilde with coauthors Sven Puchinger and Irene Bouw of Ulm University just submitted the paper
“Improved Power Decoding of Interleaved One-Point Hermitian Codes”
to the journal Designs, Codes and Cryptography
Hermitian codes are the prime example of Algebraic Geometry codes, and they have the potential to supersede the widely used Reed-Solomon codes in many applications due to their longer length at comparable decoding capability. “Interleaving” is a technique where a code over a small alphabet is used to build one over a large alphabet; this is especially useful in settings where bursts of errors are common, such as scratches on a CD.
The paper presents a new decoding algorithm for these “Interleaved Hermitian codes”: the new algorithm is able to correct more errors than any previous algorithm for these codes. Further, we demonstrate that this makes Interleaved Hermitian codes the best known codes in terms of decoding capability for a wide range of parameters, where one wishes relatively short codes over large alphabets. The paper also details how to implement the algorithm efficiently, achieving the rare sub-quadratic complexity in the code length.
The paper draws its techniques from three previous papers:
- “Improved Power Decoding of One-Point Hermitian Codes”, by the same authors, WCC 2017.
- “Decoding of Interleaved Reed–Solomon Codes Using Improved Power Decoding”, by Sven Puchinger and Johan Rosenkilde, ISIT 2017.
- “Power Decoding Reed–Solomon Codes Up to the Johnson Radius” by Johan Rosenkilde, submitted to Advances in Mathematics of Communications.
All four papers can be found on Johan’s web page