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 − −