 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
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
\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```
Ótimo!
0 aprovações
Carregar mais