ABSTRACT

The discrete Fourier transform (DFT) is an important tool in the study of signals. It is an alternate representation of a periodic sequence of discrete set of points by finite sums of weighted trigonometric functions. Techniques for the fast computation of the DFT are called fast Fourier transforms (FFTs). Computationally efficient algorithms to compute DFT algorithms are called FFTs. It is assumed in these algorithms, that it is more expensive to perform multiplication, than either an addition or subtraction operation. In addition to the Cooley–Tukey and coprime-factorization FFT algorithms, there are other computationally efficient DFT algorithms. Nevertheless, the salient features of the Cooley–Tukey and coprime-factorization FFT algorithms are the basis of these other algorithms. In the computation of the DFT, a multiplication operation has been replaced by a shift and an addition operation by the use of the numbers.