The Discrete Fourier Transform
The Fourier transform is a time domain to frequency domain mathematical transform. For any given continuous signal the Fourier transform provides a decomposition of the signal into the amplitudes and frequencies of a set of sine waves which would reproduce the original signal when summed. This property makes it easy to identify the frequencies at which most of the signal strength is being transmitted, making the Fourier transform an ideal tool for spectrum analysis. To perform the transform by machine the signal has to sampled and the discrete Fourier transform (DFT) used.
For an N sample transform the DFT is defined by the formula:
Where x(n) is the sample at time index of n and X(k) is a vector of N values at frequency index k corresponding to the magnitude of the sine waves at resulting from the decomposition of the time indexed signal.
Examining the equation we can see that the calculation of the DFT would be of complexity O(N 2 ) and require. The direct implementation of this equation would require considerably hardware complexity and would be slow.
The complexity of the DFT calculation is greatly reduced with the use of fast algorithms based on the nested decomposition of the summations within the DFT. The seminal work produced on fast Fourier algorithms are the CooleyTukey radixr decimation in time (DIF) as well as the SandeTukey decimation in frequency (DIF) Fast Fourier Transform (FFT). Other fast DFT algorithms exist but to date the majority of enhanced performance DFTs are based on the CooleyTukey algorithm or some evolution upon the FFT.
FFT Algorithms The FFT exist in two functionally equivalent forms known as decimation in time (DIT) and decimation in frequency (DIF). Both are a decomposition of the DFT by processing through r sample computational units and reduce the computational complexity of DFT from O(N 2 ) to O(Nlog(N)). The various algorithms that result from the FFT are collectively known as RadixR Fast Fourier Transforms.
The most popular Radix r choices are those of r = 2 and r = 4, and a commonly used advancement upon the FFT is the use of mixed radix..
Radix2 FFT The Radix2 algorithm takes the DFT and applies a common factor reduction equating the sum of two N/2 sequences to the N point sequence of the original DFT. Resulting in the Radix2 FFT formula below:
This results in processing that follows the signal flow graph:
Figure 1: Radix2 SFG for a 16 point FFT
Radix4 FFT Using the same principle as the Radix2 reduction the Radix4 algorithm equates the sum of N/4 sequences to the DFT summation. Resulting in the formula:
Processing for the Radix4 FFT follows the signal flow graph:
Figure 2: Radix4 SFG for a 16 point FFT
SplitRadix FFT
The Split Radix FFT (SRFFT) is an algorithm that takes advantage of the observation that different decompositions can be used for different portions of the algorithm. Applying this to the Radix4 and Radix2 decompositions it is possible to use each in the same algorithm to reduce computational complexity. For even indexed outputs the Radix2 algorithms reduces all twiddles to 1, while for the odd indexed outputs the Radix4 algorithm provides the least number of multiplications in the butterfly. Thus using both Radix4 and Radix2 in the same algorithm in the portion where each respective algorithm reduces complexity the SplitRadix FFT results.
In contrast to the Radix2 and Radix4 algorithms the SRFFT cannot be derived from index mapping and even and odd indexes are treated separately with the respective algorithms used:
For even indexes the Radix2 algorithm used in the form:
While for odd indexes the Radix4 algorithm is used in the form:
The resulting signal flow from this separate index treatment provides a SFG as shown here:
Figure 3: SRFFT SFG for a 16 point FFT

Copyright (C)2004 CDS Technology Inc., All rights reserved. 
