Computing Multidimensional Discrete Fourier Transforms by Polynomial Transforms
Original Publication Date: 1980-Oct-01
Included in the Prior Art Database: 2005-Feb-13
In this article we introduce an improved technique for computing multi-dimensional discrete Fourier transforms (DFTs) by polynomial transforms. We show that a DFT of size NxN, with N=2/t/, can be computed by a single polynomial transform, N DFTs of N terms plus N/2/ multiplications. (See Original for pages 1972-1974 top).