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

Lyons, Richard G - Understanding Digital Signal Processing


DisciplinaProcessamento Digital de Sinais1.103 materiais4.140 seguidores
Pré-visualização50 páginas
We\u2019ve transposed the original binary bits representing the normal 
index order by reversing their positions. The most significant bit becomes the least significant bit and the least
significant bit becomes the most significant bit, the next to the most significant bit becomes the next to the least 
significant bit, and the next to the least significant bit becomes the next to the most significant bit, and so on.\u2020
\u2020 Many that are first shall be last; and the last first. [Mark 10:31]
Table 4-1 Input Index Bit Reversal for an 8-Point FFT
4.5 Radix-2 FFT Butterfly Structures
Let\u2019s explore the butterfly signal flows of the decimation-in-time FFT a bit further. To simplify the signal 
flows, let\u2019s replace the twiddle factors in 
Figure 4-5 with their equivalent values referenced to , where N = 8. We can show just the exponents m of 
, to get the FFT structure shown in Figure 4-8. That is, from Figure 4-5 is equal to and is shown as 
a 2 in Figure 4-8, from Figure 4-5 is equal to and is shown as a 4 in Figure 4-8, etc. The 1s and \u22121s in 
the first stage of Figure 4-5 are replaced in Figure 4-8 by 0s and 4s, respectively. Other than the twiddle factor 
notation, Figure 4-8 is identical to Figure 4-5. We can shift around the signal nodes in Figure 4-5 and arrive at 
an 8-point decimation-in-time FFT as shown in Figure 4-9. Notice that the input data in Figure 4-9 is in its 
normal order and the output data indices are bit-reversed. In this case, a bit-reversal operation needs to be 
performed at the output of the FFT to unscramble the frequency-domain results.
Figure 4-8 Eight-point decimation-in-time FFT with bit-reversed inputs.
Figure 4-9 Eight-point decimation-in-time FFT with bit-reversed outputs.
Figure 4-10 shows an FFT signal-flow structure that avoids the bit-reversal problem altogether, and the 
graceful weave of the traditional FFT butterflies is replaced with a tangled, but effective, configuration.
Figure 4-10 Eight-point decimation-in-time FFT with inputs and outputs in normal order.
Not too long ago, hardware implementations of the FFT spent most of their time (clock cycles) performing 
multiplications, and the bit-reversal process necessary to access data in memory wasn\u2019t a significant portion of 
the overall FFT computational problem. Now that high-speed multiplier/accumulator integrated circuits can 
multiply two numbers in a single clock cycle, FFT data multiplexing and memory addressing have become 
much more important. This has led to the development of efficient algorithms to perform bit reversal[
7\u201310].
There\u2019s another derivation for the FFT that leads to butterfly structures looking like those we\u2019ve already 
covered, but the twiddle factors in the butterflies are different. This alternate FFT technique is known as the 
decimation-in-frequency algorithm. Where the decimation-in-time FFT algorithm is based on subdividing the 
input data into its odd and even components, the decimation-in-frequency FFT algorithm is founded upon 
calculating the odd and even output frequency samples separately. The derivation of the decimation-in-
frequency algorithm is straightforward and included in many tutorial papers and textbooks, so we won\u2019t go 
through the derivation here[4,5,15,16]. We will, however, illustrate decimation-in-frequency butterfly 
structures (analogous to the structures in Figures 4-8 through 4-10) in Figures 4-11 though 4-13.
Figure 4-11 Eight-point decimation-in-frequency FFT with bit-reversed inputs.
Figure 4-12 Eight-point decimation-in-frequency FFT with bit-reversed outputs.
Figure 4-13 Eight-point decimation-in-frequency FFT with inputs and outputs in normal order.
So an equivalent decimation-in-frequency FFT structure exists for each decimation-in-time FFT structure. It\u2019s 
important to note that the number of necessary multiplications to implement the decimation-in-frequency FFT 
algorithms is the same as the number necessary for the decimation-in-time FFT algorithms. There are so many 
different FFT butterfly structures described in the literature that it\u2019s easy to become confused about which 
structures are 
decimation-in-time and which are decimation-in-frequency. Depending on how the material is presented, it\u2019s 
easy for a beginner to fall into the trap of believing that decimation-in-time FFTs always have their inputs bit-
reversed and decimation-in-frequency FFTs always have their outputs bit-reversed. This is not true, as the 
above figures show. Decimation-in-time or -frequency is determined by whether the DFT inputs or outputs are 
partitioned when deriving a particular FFT butterfly structure from the DFT equations.
4.6 Alternate Single-Butterfly Structures
Let\u2019s take one more look at a single butterfly. The FFT butterfly structures in 
Figures 4-8, 4-9, 4-11, and 4-12 are the direct result of the derivations of the decimation-in-time and 
decimation-in-frequency algorithms. Although it\u2019s not very obvious at first, the twiddle factor exponents shown 
in these structures do have a consistent pattern. Notice how they always take the general forms shown in Figure 
4-14(a).\u2020 To implement the decimation-in-time butterfly of Figure 4-14(a), we\u2019d have to perform two complex 
multiplications and two complex additions. Well, there\u2019s a better way. Consider the decimation-in-time 
butterfly in Figure 4-14(a). If the top input is x and the bottom input is y, the top butterfly output would be
\u2020 Remember, for simplicity the butterfly structures in Figures 4-8 through 4-13 show only the twiddle factor exponents, k and k+N/2, 
and not the entire complex twiddle factors.
Figure 4-14 Decimation-in-time and decimation-in-frequency butterfly structures: (a) original form; (b) 
simplified form; (c) optimized form.
(4-26)
and the bottom butterfly output would be
(4-27)
Fortunately, the operations in Eqs. (4-26) and (4-27) can be simplified because the two twiddle factors are 
related by
(4-28)
So we can replace the twiddle factors in 
Figure 4-14(a) with to give us the simplified butterflies shown in Figure 4-14(b). Because the twiddle 
factors in Figure 4-14(b) differ only by their signs, the optimized butterflies in Figure 4-14(c) can be used. 
Notice that these optimized butterflies require two complex additions but only one complex multiplication, thus 
reducing our computational workload.\u2020
\u2020 It\u2019s because there are (N/2)log2N butterflies in an N-point FFT that we said the number of complex multiplications performed by an 
FFT is (N/2)log2N in Eq. (4-2).
We\u2019ll often see the optimized butterfly structures of Figure 4-14(c) in the literature instead of those in Figure 4-
14(a). These optimized butterflies give us an easy way to recognize decimation-in-time and decimation-in-
frequency algorithms. When we do come across the optimized butterflies from Figure 4-14(c), we\u2019ll know that 
the algorithm is decimation-in-time if the twiddle factor precedes the \u22121, or else the algorithm is decimation-in-
frequency if the twiddle factor follows the \u22121.
Sometimes we\u2019ll encounter FFT structures in the literature that use the notation shown in Figure 4-15[5, 12]. 
These wingless butterflies are equivalent to those shown in Figure 4-14(c). The signal-flow convention in 
Figure 4-15 is such that the plus output of a circle is the sum of the two samples that enter the circle from the 
left, and the minus output of a circle is the difference of the samples that enter the circle. So the outputs of the 
decimation-in-time butterflies in Figures 4-14(c) and 4-15(a) are given by
(4-29)
Figure 4-15 Alternate FFT butterfly notation: (a) decimation in time; (b) decimation in frequency.
The outputs of the decimation-in-frequency butterflies in Figures 4-14(c) and 4-15(b) are
(4-30)
So which FFT structure is the best one to use? It depends on the application, the hardware implementation, and 
convenience. If we\u2019re using a software routine
Luiza Irina
Luiza Irina fez um comentário
Ótimo!
0 aprovações
Carregar mais