Sub-Quadratic Decoding of One-Point Hermitian Codes

DOI10.1109/TIT.2015.2424415zbMATH Open1359.94864arXiv1405.6008MaRDI QIDQ2977424FDOQ2977424

Authors: Peter Beelen, Johan Rosenkilde né Nielsen 

Publication date: 28 April 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: We present the first two sub-quadratic complexity decoding algorithms for one-point Hermitian codes. The first is based on a fast realisation of the Guruswami-Sudan algorithm by using state-of-the-art algorithms from computer algebra for polynomial-ring matrix minimisation. 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 same methods from computer algebra, yielding similar asymptotic complexities.

Full work available at URL: https://arxiv.org/abs/1405.6008

Mathematics Subject Classification ID

Decoding (94B35) Other types of codes (94B60)

Cited In (5)

• Fractional decoding of \(r\)-Hermitian codes
• Power error locating pairs
• Row reduction applied to decoding of rank-metric and subspace codes
• Improved power decoding of interleaved one-point Hermitian codes
• Power decoding Reed-Solomon codes up to the Johnson radius

This page was built for publication: Sub-Quadratic Decoding of One-Point Hermitian Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2977424)