by Forrest Sheng Bao http://fsbao.net
You need a web browser that supports MathML to read this doc. To see whether your browser supports it, please check whether you can see formulas on this page. By default, Linux and Mac user should be able to make it from their Mozilla Firefox browser. For Windows users, well, that's not a question you should ask me.
The author cannot guarantee this article has no typo. Please confirm all equations before you use them.
There are so many guys asking me the difference between DTFT and DFT. And, they confused these two concepts with FFT and STFT.
I will follow this order to explain things:
Almost everyone on this green earth knows FT. It is defined as
where and f is the physical frequency. In Eq. 1, is the sginal in frequency domain while is the signal in time domain.
STFT is very easy, simply adding aon the right hand side of Eq. 1:
So the output of STFT is a 2-D function. Generally people represent its contour in a grid, each box of which is called a Heisenberg box. But, simply forget it. It has nothing to do with the main clue of this article.
Now simply look at Eq. 1. The right hand side is a continuous integral. This is impossible in engineering since the signals we can get are series (discrete) sampled periodically. Fourier Transform performed on a time domain sequence is the DTFT:
where L is the length of the time domain sequence, a.k.a. windowed segment.The transformation in Eq. 3 is called "DTFT of a lengh-L signal."
In Eq. 3, the FT is discretized in time domain. Computationally, you cannot represent all frequencies since they are uncountable and endless real numbers. So we also need to discretize the FT in frequency domain, the DFT: where and k are nature numbers between 0 and N-1.
Signal Processing written by Sophocles J. Orfanidis provides a definition to DFT: "The N-point DFT of a length-L signal is defined to be the DTFT evaluated at N equally spaced frequencies over the full Nyquist interval" (Sec.9.2.3).
Eq. 4 is called the "N-point DFT of a length-L signal."
It is just an algorithm.Signal Processing written by Sophocles J. Orfanidis says " The fast Fourier transform is a fast implementation of the DFT." FFT is in fact a Divide-and-Conquer algorithm.
In 1964, Cooley and Tukey published a paper which demonstrated the famous FFT algorithm. There are also some other concerning about FFT, such as radix-n FFT, decimation-in-time FFT or decimation-in-frequency FFT. In general,the FFT we mentioned is the decimation-in-time radix-2 FFT.
You don't need to consider these details. What you need is just a black box, which will output a series in digital frequency domain, when you input a time series.