|
The Fast Fourier Transform (FFT) is a widely used algorithm that computes the Discrete Fourier Transform (DFT) using much fewer operations than a direct implementation of the DFT. FFTs are of great importance to a wide variety of applications. One of the most important application areas is telecommunications. FFTs are used in communications standards such as 3GPP-LTE, WiMAX, and many others. In fact, the ubiquitous OFDM (Orthogonal Frequency Division Multiplexing) signals are generated using the FFT.
In this article we present an implementation of the FFT on the StarCore SC3000 DSP core. We use a radix-4 decimation in frequency (DIF) variant of the FFT and optimize our code to take advantage of the SC3000's parallel architecture, resulting in a highly efficient implementation. We discuss the implementation in detail, including code structure and optimizations. The FFT output is verified against a floating-point MATLAB model, and actual implementation performance results are given for the MSC8144, the first device to utilize Freescale's StarCore SC3000 core architecture.
Introduction
This article describes how to implement a Radix-4 Fast Fourier Transform Algorithm using the StarCore SC3000 DSP. In this article we will introduce how the SC3000 architecture allows the implementation of a very efficient Radix-4 FFT.
Discrete Fourier Transform (DFT) Definition
The Discrete Fourier Transform (DFT) is used to transform a vector of samples in time into frequency coefficients. Assuming a vector of samples x(n) containing N complex number samples (n = 0,…, N-1), the DFT X(k) of a sequence x(n) is defined as
where j is the square root of –1 and WNnk is known as the twiddle factor. The Fourier Transform X(k) can be thought of as the "frequency domain" representation of x(n), where n is defined as the time index and k as the frequency index.
Radix-4 Fast Fourier Transform (FFT)
Assuming an input vector whose length is a power of two, which is common, the Radix-4 FFT reduces the number of multiplications needed to compute an N-point DFT with complex inputs from 2N2 to (3*N/4) log4(N). It does this by breaking the DFT down into multiple 4-point DFTs. Click here for a derivation of the radix-4 FFT. The radix-4 DIF butterfly equations (i.e. 4-point DFT's) in our implementation are summarized in Figure 1 below.
(Click to enlarge)
(Click to enlarge)
Note: Twiddle factors in the figure are defined as
Figure 1. Implemented radix-4 DIF butterfly on SC3000.
Effects of finite word arithmetic – Saturation
On fixed-point processors, the dynamic range is [-1,1). In a radix-4 DIF FFT, the values computed in every butterfly stage can grow by 
[1]. Therefore the butterfly inputs must be scaled down to prevent results outside of the dynamic range, an event called overflow that can cause large errors in the output.
The inputs are scaled down by 4 in our implementation because in a floating-point implementation of the radix-4 DIF FFT, scaling down by 4 at each butterfly stage forces the output to be in the range [-1,1). Another motivation for choosing a scale factor of 4 is that, being a power of 2, the scaling can be accomplished by an arithmetic right shift as opposed to an expensive division routine. Because the scaling factors in our implementation are static, we are using what is referred to as the fixed-scaling method.
If we scale we scale down by 4 at each stage, the final FFT output is scaled down by 4M, where M is the number of butterfly stages (M is calculated as shown in Eq.[10]). This scales the DFT equation given in Eq.[1] by 1/4M as shown in Eq.[10].
(Click to enlarge)
As an example, if we want to implement a 1024-point DIF FFT, we have M = log4(1024) = 5 stages and the final FFT output is scaled by 1/4M = 1/45 = 1/1024 . Note that if a radix-4 algorithm uses a scaling of a factor of 4, the total scaling amount is equal to a factor of 1/N.
Footnotes
1. Although the inputs of each butterfly stage have real and imaginary parts with magnitudes less than one, the real and imaginary parts of the outputs can have a maximum magnitude of:
|
