29-01-2011, 07:23 PM
RADER ALGORITHM
PROJECT INTERIM REPORT
Submitted by
Bibina V.C.
First Semester
M.Tech, Signal Processing
DEPARTMENT OF ELECTRONICS AND COMMUNICATION ENGINEERING
COLLEGE OF ENGINEERING
TRIVANDRUM
PROJECT INTERIM REPORT
Submitted by
Bibina V.C.
First Semester
M.Tech, Signal Processing
DEPARTMENT OF ELECTRONICS AND COMMUNICATION ENGINEERING
COLLEGE OF ENGINEERING
TRIVANDRUM
[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