Fast Discrete Fourier Transform
Original Publication Date: 1978-Jan-01
Included in the Prior Art Database: 2005-Feb-20
A discrete Fourier transform (DPT) of dimension N = N(1).N(2), where N(1), N(2)...N(d) are relative primes, can be viewed as a multidimensional transform of dimension N(1) x N(2)... x N(d). Moreover, if N(1), N(2)... N(2) are primes or powers of primes, the individual DFTs of dimension N(1), N(2)... N(2) can be computed by correlations. In this article, it is shown that the bulk of the calculations required to evaluate a DFT of dimension N(1).N(2)... N(d) corresponds to computing multidimensional correlations, which can in turn, be computed efficiently by polynomial transforms.