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 ?

# Computational Complexity of Reed-Solomon Codes

Started by ●April 1, 2007

Reply by ●April 1, 20072007-04-01

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

Reply by ●April 1, 20072007-04-01

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)).

Reply by ●April 2, 20072007-04-02

>On Apr 1, 5:26 am, "kittuis4u" <kittui...@gmail.com> wrote: >> Hi all, >> I am doing some research on implementing Reed-Solomon Codes and wouldlike>> to read some information about the computational complexity inimplementing>> 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 ?

Reply by ●April 2, 20072007-04-02

"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