Forums

Fast encoding of RS codes

Started by ananthr January 27, 2008
Hi!

I am doing some research in Computer Security, and I want to implement
Reed-Solomon codes to get outputs of some provable minimum distance.
I've researched on speed benchmarks and they always seem to include the
decoding stage as well. 

Can you point me towards some references on fast encoding of RS codes.
And this is for a CS application so I would like to try the general code
(not just the [255, 223] code for CD applications).
I know that they can be implemented as matrix multiplication, but naively
this is slow, and wanted to know if there's any faster encoding algorithms
out there?

Thank you all.

--
Ananth


On Jan 27, 11:21 am, "ananthr" <ananthr1...@gmail.com> wrote:
> Hi! > > I am doing some research in Computer Security, and I want to implement > Reed-Solomon codes to get outputs of some provable minimum distance. > I've researched on speed benchmarks and they always seem to include the > decoding stage as well. > > Can you point me towards some references on fast encoding of RS codes. > And this is for a CS application so I would like to try the general code > (not just the [255, 223] code for CD applications). > I know that they can be implemented as matrix multiplication, but naively > this is slow, and wanted to know if there's any faster encoding algorithms > out there? > > Thank you all. > > -- > Ananth
The naive mutrix multiplication algorithm requires k(n-k) multiplications to encode a (n, k) Reed-Solomon code. For large values of n (and k), a finite-field Fast Fourier Transform method can be used to reduce the number of multiplications, but this is a multi-radix FFT whose efficiency depends on the factorization of n, and so there is no guarantee that use of the FFT will mean fewer multiplications than the standard matrix multiplication method. See the book "Algebraic Codes for Data Transmission" by Richard Blahut for some details on how the finite- field FFT works.