If we split the N point data sequence into two N/2 point data sequences f1(n) and f2(n) corresponding to the even numbered and odd numbered samples of x(n) and F1(k) and F2(k) are the N/2 point DFTs of f1(k) and f2(k) respectively, then what is the N/2 point DFT X(k) of x(n)?

DFT Efficient Computation - Fast Fourier Transform Algorithms topics include:  Computation of discrete fourier transforms and fast fourier transforms, various approaches to their computation which include filtering and quantization and applications of FFT algorithms. The Fast Fourier Transform (FFT) is a computationally efficient method for calculating the Discrete Fourier Transform (DFT). It is a key tool in digital signal processing applications and is used as a benchmark for evaluating digital signal processor (DSP) performance.  The FFT algorithm is more efficient than a direct DFT... Show more

DFT Efficient Computation - Fast Fourier Transform Algorithms topics include:  Computation of discrete fourier transforms and fast fourier transforms, various approaches to their computation which include filtering and quantization and applications of FFT algorithms.

The Fast Fourier Transform (FFT) is a computationally efficient method for calculating the Discrete Fourier Transform (DFT). It is a key tool in digital signal processing applications and is used as a benchmark for evaluating digital signal processor (DSP) performance. 

The FFT algorithm is more efficient than a direct DFT computation. A direct DFT computation requires O(N^2) operations, while the FFT algorithm requires O(N log N) operations. This is a significant speedup for large data sets. 
For example, when N = 512, the direct DFT computational complexity is proportional to N2 = 262144, whereas the FFT computational complexity is proportional to Nlog2N = 2048. This means FFT is 32 times faster than DFT. 
The FFT algorithm was developed by Cooley-Tukey in 1965. The idea came about during a meeting of President Kennedy's Science Advisory Committee. The committee was discussing how to detect nuclear tests by the Soviet Union by setting up sensors around the country. An FFT algorithm was needed to analyze the output of these sensors. 

Related Test: Digital Signal Processing Practice Test: Discrete Fourier Transform - Properties and Applications

Show less