Recursive calculation of Fourier transform of discrete signal
V. Cizek · 2005
Two algorithms for the calculation of Fourier transform of a discrete signal are derived from the known recursive method for polynomial evaluation. The first algorithm processes the elements of the discrete signal in a natural order of elements and the second one in the reverse order. Both algorithms are modified for operation with real numbers only. The relation of these algorithms to the well known Goertzel algorithm and the Collatz's rule is demonstrated. Moreover, the application of the recursive algorithm to repeated DFT calculation is described.