Forums

Computational Complexity of Reed-Solomon Codes

Started by kittuis4u April 1, 2007
Hi all,
I am doing some research on implementing Reed-Solomon Codes and would like
to read some information about the computational complexity in implementing
Reed-Solomon Codes.

Could anyone site some nice references to reed about this.

I would like to know the details of the number of multipliers needed and
also about the number of memory locations needed to implement and (n,k)
R-S code. 

Thanks in advance,
Krishna Emani. 

_____________________________________
Do you know a company who employs DSP engineers?  
Is it already listed at http://dsprelated.com/employers.php ?
On Apr 1, 5:26 am, "kittuis4u" <kittui...@gmail.com> wrote:
> Hi all, > I am doing some research on implementing Reed-Solomon Codes and would like > to read some information about the computational complexity in implementing > Reed-Solomon Codes. > > Could anyone site some nice references to reed about this. > > I would like to know the details of the number of multipliers needed and > also about the number of memory locations needed to implement and (n,k) > R-S code. > > Thanks in advance, > Krishna Emani. >
I like Richard Blahut's book "Algebraic Codes for Data Transmission". Can't remember exactly how detailed it is in terms of memory requirements, but he covers the complexity part quite well. Julius
On Apr 1, 5:26 am, "kittuis4u" <kittui...@gmail.com> wrote:
> Hi all, > I am doing some research on implementing Reed-Solomon Codes and would like > to read some information about the computational complexity in implementing > Reed-Solomon Codes.
If you mean computational complexity in the Computer Science sense, there is a paper in the IEEE Transactions on Information Theory around 1975 or so by Jorn Justesen which says the answer is O(n log^2 n). If you are asking about typical implementations, then n-k multipliers are needed for syndrome computation and for error location and evaluation. The number of multipliers needed for solving the key equation depends on how much time is available. The area-time complexity is O((n-k)^2), and typically, implementations use 4(n-k) or 6(n-k) or 8(n-k) multipliers to solve in (n-k) cycles, (e.g. http://www.ifp.uiuc.edu/~sarwate/pubs/decoder.ps) or 3 or 4 multipliers to solve in 0.5(n-k)^2 clock cycles (which works for high rate codes for which 0.5(n-k)^2 < n, e.g. (255,239) RS code over GF(256) but not (255,223) RS code over GF(256)).
>On Apr 1, 5:26 am, "kittuis4u" <kittui...@gmail.com> wrote: >> Hi all, >> I am doing some research on implementing Reed-Solomon Codes and would
like
>> to read some information about the computational complexity in
implementing
>> Reed-Solomon Codes. > >If you mean computational complexity in the Computer Science >sense, there is a paper in the IEEE Transactions on Information >Theory around 1975 or so by Jorn Justesen which says the >answer is O(n log^2 n). If you are asking about typical >implementations, >then n-k multipliers are needed for syndrome computation and >for error location and evaluation. The number of multipliers needed >for solving the key equation depends on how much time is available. >The area-time complexity is O((n-k)^2), and typically, implementations >use 4(n-k) or 6(n-k) or 8(n-k) multipliers to solve in (n-k) cycles, >(e.g. http://www.ifp.uiuc.edu/~sarwate/pubs/decoder.ps) >or 3 or 4 multipliers to solve in 0.5(n-k)^2 clock cycles (which works >for high rate codes for which 0.5(n-k)^2 < n, e.g. (255,239) RS code >over GF(256) but not (255,223) RS code over GF(256)). > >
Thank you very much, Thanks a lot for the information. The link that was given is not working. Could you please check about it and give me the link again. Could you please cite some more references online. Thanks in Advance, Krishna Emani. _____________________________________ Do you know a company who employs DSP engineers? Is it already listed at http://dsprelated.com/employers.php ?
"kittuis4u" <kittuis4u@gmail.com> wrote in message 
news:1-SdncjI7PHtkozbnZ2dnUVZ_tSunZ2d@giganews.com...
> > Thank you very much, > Thanks a lot for the information. The link that was given is not working. > Could you please check about it and give me the link again.
Try http://www.ifp.uiuc.edu/~sarwate/pubs/Sarwate01High.pdf