Computer Science – Information Theory
Scientific paper
2007-04-22
Computer Science
Information Theory
5 pages, 5 figures, to be presented at 2007 IEEE International Symposium on Information Theory, Nice, France (ISIT 2007)
Scientific paper
We consider a list decoding algorithm recently proposed by Pellikaan-Wu \cite{PW2005} for $q$-ary Reed-Muller codes $\mathcal{RM}_q(\ell, m, n)$ of length $n \leq q^m$ when $\ell \leq q$. A simple and easily accessible correctness proof is given which shows that this algorithm achieves a relative error-correction radius of $\tau \leq (1 - \sqrt{{\ell q^{m-1}}/{n}})$. This is an improvement over the proof using one-point Algebraic-Geometric codes given in \cite{PW2005}. The described algorithm can be adapted to decode Product-Reed-Solomon codes. We then propose a new low complexity recursive algebraic decoding algorithm for Reed-Muller and Product-Reed-Solomon codes. Our algorithm achieves a relative error correction radius of $\tau \leq \prod_{i=1}^m (1 - \sqrt{k_i/q})$. This technique is then proved to outperform the Pellikaan-Wu method in both complexity and error correction radius over a wide range of code rates.
No associations
LandOfFree
On Algebraic Decoding of $q$-ary Reed-Muller and Product-Reed-Solomon Codes 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 Algebraic Decoding of $q$-ary Reed-Muller and Product-Reed-Solomon Codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Algebraic Decoding of $q$-ary Reed-Muller and Product-Reed-Solomon Codes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-466506