A review of the discrete Fourier transform. 2. Non-radix algorithms, real transforms and noise

For pt.1 see ibid., vol.7, no.4, p.169-77 (1995). 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. This article, the second of two which review the fast algorithms for the DFT, looks at algorithms for transforms whose orders are not a power of two. Also discussed are ways of adapting algorithms for purely real data, the problems of fixed-point noise, and implementation options with existing hardware