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)
2.3.6 Fast Fourier transform FFT For example: using the first property, we can group terms in Eq. (2. 234)as Re[x(n)]reloan ]+ Relx(N-n)rely k(N-n +re -m()mv]m(N-n)m-)]=(m()-mzxN-nlmpy by this method the number of multiplications can be reduced by approximately a factor of 2 The second property, 1. e, the periodicity of the complex sequence W, can be employed in achieving significantly greater reductions of the computation
For example: using the first property, we can group terms in Eq. (2.234) as By this method, the number of multiplications can be reduced by approximately a factor of 2. The second property, i.e., the periodicity of the complex sequence , can be employed in achieving significantly greater reductions of the computation. 2.3.6 Fast Fourier transform (FFT) ( ) ( ) ( ) ( ( ) ( )) kn N k N n N kn Re x n Re WN + Re x N − n Re W = Re x n + Re x N − n Re W − ( ) ( ) ( ) ( ( ) ( )) kn N k N n N kn − Im x n Im WN − Im x N − n Im W = − Im x n − Im x N − n Im W − kn WN
2.3.6 Fast Fourier transform FFT In 1965. cooley and tukey published an algorithm for the computation of the discrete Fourier transform that is applicable when N is a composite number; i. e, N is the product of two or more integers. The algorithms are known as fast Fourier transform, or simply FFt algorithms
In 1965, Cooley and Tukey published an algorithm for the computation of the discrete Fourier transform that is applicable when N is a composite number; i.e., N is the product of two or more integers. The algorithms are known as fast Fourier transform, or simply FFT, algorithms. 2.3.6 Fast Fourier transform (FFT)
2.3.6 Fast Fourier transform FFT UThe fundamental principle: decompose the computation of the discrete fourier transform of a sequence of length into successively smaller discrete Fourier transform aTwo basic classes of FFt algorithms decimation-in-time decimation-in-frequency
❑The fundamental principle: decompose the computation of the discrete Fourier transform of a sequence of length into successively smaller discrete Fourier transform. ❑Two basic classes of FFT algorithms: – decimation-in-time – decimation-in-frequency 2.3.6 Fast Fourier transform (FFT)
2.3.6 Fast Fourier transform FFT 1. Decimation-in-Time FFt algorithms Assuming: N=2M separating x(n)into two N/2-point sequence consisting of the even-numbered points in x(n) and the odd-numbered points in x(n). With X(k) given by X(k)=∑x(n)x,k=01…N then X(k)=∑x(nx+∑xn)W n old
1. Decimation-in-Time FFT Algorithms Assuming: separating x(n) into two N/2-point sequence consisting of the even-numbered points in x(n) and the odd-numbered points in x(n). With X(k) given by then 2.3.6 Fast Fourier transform (FFT) M N = 2 ( ) ( ) , 0,1, 1 1 0 = = − − = X k x n W k N N n n k N ( ) = ( ) + ( ) n old nk N n even nk X k x n WN x n W
2.3.6 Fast Fourier transform FFT With the substitution of variables n=2r for n even and n=2r+I for n odd H(k)=∑x(2那3+∑x2r+)WNk =∑x(2)w3y+W∑x(2r+1)Wy (2.237) r=0 r=0 But W=W∠ since W2=e-j(2m/N) e2(M/2)
With the substitution of variables n=2r for n even and n=2r+1 for n odd, But since 2.3.6 Fast Fourier transform (FFT) ( ) ( ) ( ) ( ) ( )( ) ( )( ) − = − = − = − = + = + + = + + 1 2 2 1 2 2 1 2 1 2 2 2 1 2 2 1 2 2 1 N r o r k N N r o k N r k N N r o N r o r N r k N x r W W x r W X k x r W x r W k (2.237) 2 2 WN =WN ( ) ( ) 2 2 2 2 2 N j N j N WN = e = e =W − −