  Long Reed-Solomon (RS) codes are desirable for digital communication and
storage systems due to their improved error performance, but the high
computational complexity of their decoders is a key obstacle to their adoption
in practice. As discrete Fourier transforms (DFTs) can evaluate a polynomial at
multiple points, efficient DFT algorithms are promising in reducing the
computational complexities of syndrome based decoders for long RS codes. In
this paper, we first propose partial composite cyclotomic Fourier transforms
(CCFTs) and then devise syndrome based decoders for long RS codes over large
finite fields based on partial CCFTs. The new decoders based on partial CCFTs
achieve a significant saving of computational complexities for long RS codes.
Since partial CCFTs have modular and regular structures, the new decoders are
suitable for hardware implementations. To further verify and demonstrate the
advantages of partial CCFTs, we implement in hardware the syndrome computation
block for a $(2720, 2550)$ shortened RS code over GF$(2^{12})$. In comparison
to previous results based on Horner's rule, our hardware implementation not
only has a smaller gate count, but also achieves much higher throughputs.
