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

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

2011-02-15

arxiv.org/abs/1102.2939v2

Computer Science

Information Theory

accepted for publication in Proceedings ISIT 2011. IEEE copyright

Scientific paper

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))\}$.

Affiliated with

Also associated with

No associations

Rating

On the Decoding Complexity of Cyclic Codes Up to the BCH Bound does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Decoding Complexity of Cyclic Codes Up to the BCH Bound, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Decoding Complexity of Cyclic Codes Up to the BCH Bound will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-377744