Lyons, Richard G - Understanding Digital Signal Processing
709 pág.

Lyons, Richard G - Understanding Digital Signal Processing


DisciplinaProcessamento Digital de Sinais1.103 materiais4.124 seguidores
Pré-visualização50 páginas
only 
meaningful when the corresponding |X(m)| is well above the average FFT output noise level.
4.3 Derivation of the Radix-2 FFT Algorithm
This section and those that follow provide a detailed description of the internal data structures and operations of 
the radix-2 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 N-point DFT,
(4-11)
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. (4-11) into two 
parts as
(4-12)
Pulling the constant phase angle outside the second summation,
(4-13)
Well, here the equations become so long and drawn out that we\u2019ll use a popular notation to simplify things. 
We\u2019ll define
(4-13\u2032)
to represent the complex phase-angle factor that is constant with N. So, 
Eq. (4-13) becomes
(4-14)
Because , we can substitute WN/2 for in 
Eq. (4-14), as
(4-15)
where m is in the range 0 to N/2\u22121. Index m has that reduced range because each of the two N/2-point DFTs on 
the right side of 
Eq. (4-15) are periodic in m with period N/2.
So we now have two N/2 summations whose results can be combined to give us the first N/2 samples of an N-
point DFT. We\u2019ve reduced some of the necessary number crunching in Eq. (4-15) relative to Eq. (4-11) 
because the W terms in the two summations of Eq. (4-15) are identical. There\u2019s a further benefit in breaking the 
N-point 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. (4-15), then
(4-16)
It looks like we\u2019re complicating things, right? Well, just hang in there for a moment. We can now simplify the 
phase-angle terms inside the summations because
(4-17)
for any integer n. Looking at the so-called twiddle factor in front of the second summation in 
Eq. (4-16), we can simplify it as
(4-18)
OK, using 
Eqs. (4-17) and (4-18), we represent Eq. (4-16)\u2019s X(m+N/2) as
(4-19)
Now, let\u2019s repeat 
Eqs. (4-15) and (4-19) to see the similarity:
(4-20)
and
(4-20\u2032)
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)\u22121 in 
Eq. (4-20), which means to compute an N-point DFT, we actually perform two N/2-point DFTs\u2014one N/2-point 
DFT on the even-indexed x(n) samples and one N/2-point DFT on the odd-indexed x(n) samples. For N = 8, 
Eqs. (4-20) and (4-20\u2032) are implemented as shown in Figure 4-2.
Figure 4-2 FFT implementation of an 8-point DFT using two 4-point DFTs.
Because \u2212e\u2212j2\u3c0m/N = e\u2212j2\u3c0(m+N/2)/N, the negative W twiddle factors before the second summation in Eq. (4-20\u2032) are 
implemented with positive W twiddle factors that follow the lower DFT in Figure 4-2.
If we simplify Eqs. (4-20) and (4-20\u2032) to the form
(4-21)
and
(4-21\u2032)
we can go further and think about breaking the two 4-point DFTs into four 2-point DFTs. Let\u2019s see how we can
subdivide the upper 4-point DFT in 
Figure 4-2 whose four outputs are A(m) in Eqs. (4-21) and (4-21\u2032). We segment the inputs to the upper 4-point 
DFT into their odd and even components:
(4-22)
Because , we can express A(m) in the form of two N/4-point DFTs, as
(4-23)
Notice the similarity between 
Eqs. (4-23) and (4-20). This capability to subdivide an N/2-point DFT into two N/4-point DFTs gives the FFT 
its capacity to greatly reduce the number of necessary multiplications to implement DFTs. (We\u2019re going to 
demonstrate this shortly.) Following the same steps we used to obtained A(m), we can show that Eq.(4-21)\u2019s B
(m) is
(4-24)
For our N = 8 example, 
Eqs. (4-23) and (4-24) are implemented as shown in Figure 4-3. The FFT\u2019s well-known butterfly pattern of 
signal flows is certainly evident, and we see the further shuffling of the input data in Figure 4-3. The twiddle 
factor in Eqs. (4-23) and (4-24), 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 N-point DFT, we can break each of the N/2-point DFTs into two 
N/4-point DFTs to further reduce the number of sine and cosine multiplications. Eventually, we would arrive at 
an array of 2-point DFTs where no further computational savings could be realized. This is why the number of 
points in our FFTs is constrained to be some power of two and why this FFT algorithm is referred to as the 
radix-2 FFT.
Figure 4-3 FFT implementation of an 8-point DFT as two 4-point DFTs and four 2-point DFTs.
Moving right along, let\u2019s go one step further, and then we\u2019ll be finished with our N = 8-point FFT derivation. 
The 2-point DFT functions in 
Figure 4-3 cannot be partitioned into smaller parts\u2014we\u2019ve reached the end of our DFT reduction process, 
arriving at the butterfly of a single 2-point DFT as shown in Figure 4-4. From the definition of WN, 
 and . So the 2-point DFT blocks in Figure 4-3 can be 
replaced by the butterfly in Figure 4-4 to give us a full 8-point FFT implementation of the DFT as shown in 
Figure 4-5.
Figure 4-4 Single 2-point DFT butterfly.
Figure 4-5 Full decimation-in-time FFT implementation of an 8-point DFT.
OK, we\u2019ve gone through a fair amount of algebraic foot shuffling here. To verify that the derivation of the FFT 
is valid, we can apply the 8-point data sequence of Chapter 3\u2019s DFT Example 1 to the 8-point FFT represented 
by Figure 4-5. The data sequence representing x(n) = sin(2\u3c01000nts) + 0.5sin(2\u3c02000nts+3\u3c0/4) is
(4-25)
We begin grinding through this example by applying the input values from Eq. (4-25) to Figure 4-5, giving the 
data values shown on left side of Figure 4-6. The outputs of the second stage of the FFT are
Figure 4-6 Eight-point 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\u2019ve seen 
from the above example that the 8-point FFT example required less effort than the 8-point 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 4-7 showing the equivalencies of some of 
the twiddle factors in an 8-point DFT.
Figure 4-7 Cyclic redundancies in the twiddle factors of an 8-point FFT.
4.4 FFT Input/Output Data Index Bit Reversal
OK, let\u2019s look into some of the special properties of the FFT that are important to FFT software developers and
FFT hardware designers. Notice that 
Figure 4-5 was titled \u201cFull decimation-in-time FFT implementation of an 8-point DFT.\u201d The decimation-in-
time phrase refers to how we broke the DFT input samples into odd and even parts in the derivation of Eqs. (4-
20), (4-23), and (4-24). This time decimation leads to the scrambled order of the input data\u2019s index n in Figure 
4-5. The pattern of this shuffled order can be understood with the help of Table 4-1. The shuffling of the input 
data is known as bit reversal because the scrambled order of the input data index can be obtained by reversing 
the bits of the binary representation of the normal input data index order. Sounds confusing, but it\u2019s really 
not\u2014Table 4-1 illustrates the input index bit reversal for our 8-point FFT example. Notice the normal index 
order in the left column of Table 4-1 and the scrambled order in the right column that corresponds to the final 
decimated input index order in Figure 4-5.
Luiza Irina
Luiza Irina fez um comentário
Ótimo!
0 aprovações
Carregar mais