On the Decoding Complexity of Cyclic Codes Up to the BCH Bound

Abstract

The standard algebraic decoding algorithm of cyclic codes $[n,k,d]$ up to the BCH bound $t$ 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\sqrt{n})$, and that of the error location from $O(nt)$ to at most $\max \{O(t\sqrt{n}),O(t^2\log (t)\log (n))\}$.

accepted for publication in Proceedings ISIT 2011. IEEE copyright

References in corpus (2)

• Improvements on Cantor-Zassenhaus Factorization Algorithm
• Efficient evaluation of polynomials over finite fields

Cited by in corpus (2)

• FEC-Assisted Parallel Decoding of Polar Coded Frames: Design Considerations
• On fuzzy syndrome hashing with LDPC coding