SM 5 BSZ - FFT version differencies.
(Aug 7 2000)

Different FFT implementations

The relative performance (speed of execution) depends on fft size and stereo/mono. The speed depends on cash usage and computer architecture and I do not yet know which routines to select for different situations on different hardware platforms.

On a Pentium 66MHz which is the slowest computer I have acces to the 3 different versions run at equal speed. They all use about 23% of the total cpu time available when sampling is at 20kHz for a single channel 1024FFT with a sin squared window. On a Pentium MMX sampling at 44.1kHz 4096FFT's run 30% faster with the approximate FFT.

Fig.1 and fig.2 show graphs with a real to complex FFT. These graphs represent correctly produced FFT's.

Fig.3 and fig.4 show graphs with a more elaborate algorithm which is sometimes considerably faster. Here the signal is first mixed digitally with 10kHz to produce an IQ pair. The IQ pair is filtered in a IIR filter to remove components above 5kHz and then the number of points is reduced by a factor of two. Finally the IQ pair is transformed by use of a complex FFT. The IIR filter is fast but introduces two errors. Firstly the frequency response is no longer flat which is absolutely no problem - later digital processes will correct the frequency respons of the analog filters preceding the D/A converter and the deviation from flattnes is also absorbed completely. Secondly, the limited steepness of the IIR filter causes an aliasing spur that will degrade performance towards the ends of the spectrum. This is usually no problem either since the analog circuitry outside the computer has to attenuate signals near the spectrum ends to avoid aliasing from the A/D sampling and to avoid the mirror image signal when mixing from RF to audio. The approximate FFT should not be used if more than 90% of the bandwidth from zero to the Nyquist frequency is to be used.


Fig. 1. Real to complex FFT. A near saturating audio signal at about 1kHz uses 22.8% of the available CPU time on a Pentium 66MHz. The noise floor is flat at about 0dB as can be seen in fig.2. S/N = 110dB at a bandwidth of about 20Hz.


Fig. 2. Real to complex FFT. No signal present at the A/D input. This graph shows the noise floor for fig.1.


Fig. 3. Digital mixing from real signal to complex signal at half the frequency followed by complex FFT. A near saturating audio signal at about 1kHz uses 22.7% of the available CPU time on a Pentium 66MHz. The digital filters have a peak at about 1kHz, see fig 4. S/N is about the same as with a correct FFT. The alias signal at 9kHz is a spur caused by insufficient steepness of the digital IIR filter between the mixing and the fft steps.


Fig. 4. Digital mixing from real signal to complex signal at half the frequency followed by complex FFT. No signal fed to the A/D input. This noise floor shows peaks at about 1 and 9 kHz due to imperfections of the fast IIR filter used.