Archivio Istituzionale della RicercaThe 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))}.
On the Decoding Complexity of Cyclic Codes Up to the BCH Bound / Schipani, D.; Elia, Michele; Rosenthal, J:. - ELETTRONICO. - (2011), pp. 835-839. (Intervento presentato al convegno International Symposium on Information Theory tenutosi a San Petersbourg (Russia) nel July 31 - August 5, 2011) [10.1109/ISIT.2011.6034253].
On the Decoding Complexity of Cyclic Codes Up to the BCH Bound
ELIA, Michele;
2011
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))}.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11583/2440616
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo