Luiza Irina fez um comentário

Ótimo!

• 0 aprovações

709 pág.

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 fez um comentário

Ótimo!

• 0 aprovações