4.4. DERIVATION OF THE RADIX2 FFT
ALGORITHM
This section and those that follow provide a
detailed description of the internal data structures and operations
of the radix2 FFT for those readers interested in developing
software FFT routines or designing FFT hardware. To see just
exactly how the FFT evolved from the DFT, we return to the equation
for an Npoint DFT,
A straightforward derivation of the FFT proceeds
with the separation of the input data sequence x(n)
into two parts. When x(n) is segmented into its even and odd
indexed elements, we can, then, break Eq. (411) into two parts as
Equation 412
Pulling the constant phase angle outside the
second summation,
Equation 413
Well, here the equations get so long and drawn
out that we'll use the standard notation to simplify things. We'll
define W_{N} = e^{–}^{j}^{2}^{p}^{/}^{N} to represent the complex
phase angle factor that is constant with N. So Eq. (413) becomes
Equation 414
Because , we can
substitute in Eq. (414), as
Equation 415
So we now have two N/2 summations whose results can be
combined to give us the Npoint
DFT. We've reduced some of the necessary number crunching in Eq. (415) relative to Eq. (411) because the W terms in the two summations of Eq. (415) are identical.
There's a further benefit in breaking the Npoint DFT into two parts because the
upper half of the DFT outputs is easy to calculate. Consider the
X(m+N/2)
output. If we plug m+N/2 in for m in Eq. (415), then
Equation 416
It looks like we're complicating things, right?
Well, just hang in there for a moment. We can now simplify the
phase angle terms inside the summations because
Equation 417
for any integer n. Looking at the socalled twiddle factor in front of the second
summation in Eq. (416),
we can simplify it as
Equation 418
OK, using Eqs. (417) and (418), we represent Eq. (416)'s X(m+N/2)
as
Equation 419
Now, let's repeat Eqs. (415) and (419) to see the similarity;
Equation 420
and
Equation 420'
So here we are. We need not perform any sine or
cosine multiplications to get X(m+N/2).
We just change the sign of the twiddle factor and use
the results of the two summations from X(m) to
get X(m+N/2).
Of course, m goes from 0 to (N/2)–1 in Eq. (420) which means, for an Npoint DFT, we perform an N/2point DFT to get the first N/2 outputs and use those to get the
last N/2 outputs. For N = 8, Eqs. (420) and (420') are implemented as shown in Figure 42.
Figure 42. FFT implementation of an
8point DFT using two 4point DFTs.
If we simplify Eqs. (420) and (420') to the form
Equation 421
and
Equation 421'
we can go further and think about breaking the
two 4point DFTs into four 2point DFTs. Let's see how we can
subdivide the upper 4point DFT in Figure 42 whose four outputs are A(m) in
Eqs. (421) and (421'). We segment the inputs
to the upper 4point DFT into their odd and even components
Equation 422
Because , we
can express A(m) in the form of two N/4point DFTs, as
Equation 423
Notice the similarity between Eq. (423) and Eq. (420). This capability to subdivide an
N/2point DFT into two N/4point DFTs gives the FFT its
capacity to greatly reduce the number of necessary multiplications
to implement DFTs. (We're going to demonstrate this shortly.)
Following the same steps we used to obtained A(m),
we can show that Eq.(421)'s B(m)
is
Equation 424
For our N = 8
example, Eqs. (423) and
(424) are implemented as
shown in Figure 43. The
FFT's wellknown butterfly pattern
of signal flows is certainly evident, and we see the further
shuffling of the input data in Figure 43. The twiddle factor in Eqs. (423) and (424), for our N = 8 example, ranges from to because
the m index, for A(m)
and B(m), goes from 0 to 3. For any Npoint DFT, we can break each of the
N/2point DFTs into two N/4point DFTs to further reduce the
number of sine and cosine multiplications. Eventually, we would
arrive at an array of 2point DFTs where no further computational
savings could be realized. This is why the number of points in our
FFTs are constrained to be some power of 2 and why this FFT
algorithm is referred to as the radix2 FFT.
Figure 43. FFT implementation of an
8point DFT as two 4point DFTs and four 2point DFTs.
Moving right along, let's go one step further,
and then we'll be finished with our N = 8 point FFT derivation. The 2point
DFT functions in Figure
43 cannot be partitioned into smaller parts—we've reached
the end of our DFT reduction process arriving at the butterfly of a
single 2point DFT as shown in Figure 44. From the definition of
W_{N'} and
. So the
2point DFT blocks in Figure
43 can be replaced by the butterfly in Figure 44 to give us a full 8point FFT
implementation of the DFT as shown in Figure 45.
Figure 44. Single 2point DFT
butterfly.
Figure 45. Full decimationintime FFT
implementation of an 8point DFT.
OK, we've gone through a fair amount of
algebraic foot shuffling here. To verify that the derivation of the
FFT is valid, we can apply the 8point data sequence of Chapter 3's
DFT Example 1 to the 8point FFT represented by Figure 45. The data sequence representing
x(n) = sin(2p1000nt_{s}) + 0.5sin(2p2000nt_{s}+3p/4) is
Equation 425
We begin grinding through this example by
applying the input values from Eq. (425) to Figure 45, giving the data values shown on
left side of Figure 46.
The outputs of the second stage of the FFT are
Figure 46. 8point FFT of Example 1
from Section
3.1.
Calculating the outputs of the third stage of
the FFT to arrive at our final answer
So, happily, the FFT gives us the correct
results, and again we remind the reader that the FFT is not an
approximation to a DFT; it is the DFT with a reduced number of
necessary arithmetic operations. You've seen from the above example
that the 8point FFT example required less effort than the 8point
DFT Example 1 in Section 3.1.
Some authors like to explain this arithmetic reduction by the
redundancies inherent in the twiddle factors . They
illustrate this with the starburst
pattern in Figure 47
showing the equivalencies of some of the twiddle factors in an
8point DFT.
Figure 47. Cyclic redundancies in the
twiddle factors of an 8point FFT.
