[attachment=8547]

ABSTRACT
This project aims to develop Rader Algorithm using VHDL and implement on
a FPGA chip. Rader algorithm (1968) is a fast Fourier transform (FFT) algorithm that
computes the discrete Fourier transform (DFT) of prime sizes by re-expressing the DFT
as a cyclic convolution. Since Rader algorithm only depends upon the periodicity of the
DFT kernel, it is directly applicable to any other transform (of prime order) with a
similar property. The algorithm can be modified to gain a factor of two savings for the
case of DFTs of real data, using a slightly modified re-indexing/permutation to obtain
two half-size cyclic convolutions of real data. Winograd extended Rader algorithm to
include prime-power DFT sizes and today Rader’s algorithm is sometimes described
as a special case of Winograd’s FFT algorithm, also called the multiplicative Fourier
transform algorithm, which applies to an even larger class of sizes