Header

UZH-Logo

Maintenance Infos

On the decoding complexity of cyclic codes up to the BCH bound


Schipani, D; Elia, M; Rosenthal, J (2011). On the decoding complexity of cyclic codes up to the BCH bound. In: IEEE. IEEE International Symposium on Information Theory proceedings (ISIT), 2011 : July 31, 2011 - Aug. 5, 2011, St. Petersburg, Russia. Piscataway, NJ, US: IEEE, 835-839.

Abstract

The standard algebraic decoding algorithm of cyclic codes [n, k, d] up to the BCH bound δ = 2t + 1 is very efficient and practical for relatively small n while it becomes unpractical for large n as its computational complexity is O(nt). Aim of this paper is to show how to make this algebraic decoding computationally more efficient: in the case of binary codes, for example, the complexity of the syndrome computation drops from O(nt) to O(t√n), while the average complexity of the error location drops from O(nt) to max{O(t√n), O(t log2(t)log log(t)log(n))}.

Abstract

The standard algebraic decoding algorithm of cyclic codes [n, k, d] up to the BCH bound δ = 2t + 1 is very efficient and practical for relatively small n while it becomes unpractical for large n as its computational complexity is O(nt). Aim of this paper is to show how to make this algebraic decoding computationally more efficient: in the case of binary codes, for example, the complexity of the syndrome computation drops from O(nt) to O(t√n), while the average complexity of the error location drops from O(nt) to max{O(t√n), O(t log2(t)log log(t)log(n))}.

Statistics

Citations

3 citations in Web of Science®
8 citations in Scopus®
Google Scholar™

Altmetrics

Additional indexing

Item Type:Book Section, refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Mathematics
Dewey Decimal Classification:510 Mathematics
Language:English
Date:2011
Deposited On:14 Jan 2012 18:48
Last Modified:05 Apr 2016 15:23
Publisher:IEEE
ISBN:978-1-4577-0596-0 (P) 978-1-4577-0594-6 (E)
Additional Information:Kongresstagungsband: IEEE International Symposium on Information Theory ; (St. Petersburg) : 2011.07.31-08.05 / ISIT ; (St. Petersburg) : 2011.07.31-08.05
Publisher DOI:https://doi.org/10.1109/ISIT.2011.6034253

Download

Full text not available from this repository.
View at publisher