Fast encoding of RS codes

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.