Fundamentals of Measurement Technology (5) Prof Wang Boxiong
Fundamentals of Measurement Technology (5) Prof. Wang Boxiong
2.3.6 Fast Fourier transform(FFT) The discrete Fourier transform DFT) DF7:X(k)=∑x()=∑x()Wk=01 2232) n=0 k IDFT: x(n) x(k )e 之Y(k)W0 (2233) where W=eN Since x(n) may be complex we can write x()=∑(Rem)evl]-x)]mp+e()kepv+mmD k=0.1,,N-1 (2.234)
The discrete Fourier transform (DFT): where Since x(n) may be complex we can write 2.3.6 Fast Fourier transform (FFT) : ( ) ( ) ( ) 0,1, , 1 1 2 1 = = = − − = − = − DFT X k x n e x n W k N N n o n k N N n o n k N j ( ) ( ) ( ) 0,1, , 1 1 1 : 1 2 1 = = = − − = − − = X k W n N N X k e N IDFT x n N k o nk N N k o nk N j (2.232) (2.233) N j N W e 2 − = ( ) ( ( ) ( ) ) ( ( ) ( ) ) − = = − + + 1 0 N n kn N kn N kn N kn X k Re x n Re WN Im x n Im W j Re x n Re W Im x n Im W k = 0,1,,N −1 (2.234)
2.3.6 Fast Fourier transform FFT From Eq(2.234)it is clear that 1) For each value of k, the direct computation of X(k requires 4N real multiplication and (4N-2) real additions X(h must be computed for n different values of k the direct computation of the discrete Fourier transform of a sequence x(n) requires 4N2 real multiplications and N(4N-2 )real additions or alternatively, N2 complex multiplications and N(N-1) complex additions
From Eq. (2.234) it is clear that 1) For each value of k, the direct computation of X(k) requires 4N real multiplication and (4N-2) real additions. 2) X(k) must be computed for N different values of k, the direct computation of the discrete Fourier transform of a sequence x(n) requires 4N2 real multiplications and N(4N-2) real additions or, alternatively, N2 complex multiplications and N(N-1) complex additions. 2.3.6 Fast Fourier transform (FFT)
2.3.6 Fast Fourier transform FFT For the direct computation of the discrete Fourier transform, 4N2 real multiplications and N(4N-2)real additions are required The amount of computation and thus the computation time, is approximately proportional to n2. so the number of arithmetic operations required to compute the dft by the direct method becomes very large for large values of w x Conclusion: computational procedures that reduce the number of multiplications and additions are of considerable interest
For the direct computation of the discrete Fourier transform, 4N2 real multiplications and N(4N-2) real additions are required. The amount of computation, and thus the computation time, is approximately proportional to N2 , so the number of arithmetic operations required to compute the DFT by the direct method becomes very large for large values of N. ❖Conclusion: computational procedures that reduce the number of multiplications and additions are of considerable interest. 2.3.6 Fast Fourier transform (FFT)
2.3.6 Fast Fourier transform FFT Improving the efficiency of the computation of the dFt exploits one or both of the following special properties of the quantities 1)Symmetry A (2235) 2)Periodicity W=WN Wk+N)n (2236)
Improving the efficiency of the computation of the DFT exploits one or both of the following special properties of the quantities : 1) Symmetry 2) Periodicity 2.3.6 Fast Fourier transform (FFT) kn WN ( ) ( ) * kn N k N n WN = W − (2.235) ( ) (k N )n N k n N N kn WN W W + + = = (2.236)