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 Cooley-Tukey radix-r decimation in time (DIF) as well as the Sande-Tukey 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 Cooley-Tukey 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 Radix-R 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..

 

Radix-2 FFT

The Radix-2 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 Radix-2 FFT formula below:

This results in processing that follows the signal flow graph:

Figure 1: Radix-2 SFG for a 16 point FFT

 

Radix-4 FFT

Using the same principle as the Radix-2 reduction the Radix-4 algorithm equates the sum of N/4 sequences to the DFT summation. Resulting in the formula:

Processing for the Radix-4 FFT follows the signal flow graph:

Figure 2: Radix-4 SFG for a 16 point FFT

 

Split-Radix 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 Radix-4 and Radix-2 decompositions it is possible to use each in the same algorithm to reduce computational complexity. For even indexed outputs the Radix-2 algorithms reduces all twiddles to 1, while for the odd indexed outputs the Radix-4 algorithm provides the least number of multiplications in the butterfly. Thus using both Radix-4 and Radix-2 in the same algorithm in the portion where each respective algorithm reduces complexity the Split-Radix FFT results.

In contrast to the Radix-2 and Radix-4 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 Radix-2 algorithm used in the form:

 

While for odd indexes the Radix-4 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.