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