A REVIEW OF THE DISCRETE FOURIER-TRANSFORM .1. MANIPULATING THE POWERS OF 2

Since fast algorithms for the discrete fourier transform (DFT) were first introduced thirty years ago, they have had a major impact on signal processing and are now a basic part of every electrical engineer's education. However, some of the options, and particularly the recent advances, are not as widely known as they deserve. Over two papers, the fast algorithms for the DFT are reviewed. The first paper considers why the DFT works and looks at the various fast algorithms for transforms whose orders are a power of two. The second paper will look at techniques for other orders, at adapting algorithms for purely real data, and at the problems for fixed-point noise.