Here is a program to compute fast Fourier transform (FFT) output using C++.
FFTs are of great importance to a wide variety of applications including digital signal processing (such as linear filtering, correlation analysis and spectrum analysis) and solving partial differential equations to algorithms for quick multiplication of large integers. Its efficient computation is a topic that has received considerable attention by many mathematicians, engineers and applied scientists.
In the field of signals and systems, there are two ways of looking at any complex waveform like square wave, saw-tooth or a practical voice signal: time domain and frequency domain. Depending upon the need to solve a problem or know the answer of some abrupt behaviour in a system response, we try to switch in between these two domains. Sometimes, a signal in time domain itself gives answers to many questions but sometimes we need frequency domain to get the answers. For example, we need frequency domain to know that a voice signal contains frequency content up to 20 kHz and not beyond that, and also to know that transmitting it over a telephone requires voice frequency up to 3.4 kHz and the rest of it is of no use.
Here we show an example to explain what it means to look at a signal in two domains. Fig. 1 shows a square signal in time domain and Fig. 2 shows its frequency domain.
We can see from these two figures that frequency domain gives more insight into a signal than time domain. The peaks in Fig. 2 show the frequency content present in a square wave. The highest peak corresponds to the fundamental frequency, while the other peaks are called harmonics. By seeing such a frequency-domain plot of voice signals researchers came out with a decision that up to 3.4 kHz of frequency content is useful, while the other harmonics have a very small amplitude that can be neglected. The discussion and arguments so far are equally valid for discrete signals as well.