Home

FT, STFT, DTFT, DFT and FFT, revisited

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:

  • FT: Fourier Transform
  • STFT: Short-Time Fourier Transform, a.k.a. Windowed Fourier Transform (WFT)
  • DTFT: Discrete-Time Fourier Transform, the discreteness on time domain
  • DFT: Discrete Fourier Transform, the discreteness on frequency domain
  • FFT: Fast Fourier Transform, an algorithm to implement DFT

Fourier Transform (FT)

Almost everyone on this green earth knows FT. It is defined as

F ⁡ ω = ∫ - inf + inf f ⁡ t e j ω t d t     (1)

where ω = 2 π f and f is the physical frequency. In Eq. 1, F⁡ω is the sginal in frequency domain while F⁡t is the signal in time domain.

Short-time Fourier Transform (STFT)

STFT is very easy, simply adding a s u - t on the right hand side of Eq. 1:

F ⁡ ω t = ∫ - inf + inf f ⁡ u e - j ω u s ⁡ u - t d u     (2)

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.

DTFT: Discrete-Time Fourier Transform

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:

X ⁡ ω = ∑ L - 1 n = 0 x ⁡ n e - j ω n     (3)

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."

Discrete Fourier Transform (DFT)

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: X ⁡ ω k = ∑ n = 0 L - 1 x ⁡ n e - j ω k n     (4) where ω k = 2 π k N 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."

Discussion: DTFT vs. DFT

  • DTFT is a "time sampling" Fourier Transform and DFT is a "frequency sampling" DTFT. So, DFT is a "time sampling and frequency sampling" Fourier Transform.
  • We define DTFT because we have to sample the continual infinite signal whereas we define DFT coz we can't calculate at every frequency point. DTFT discretize the time domain while DFT discretize the frequency domain additionally.
  • N only concerns DFT and limits computational frequency resolution. But L concerns both the DTFT and DFT, and limits the physical frequency resolution.
  • The D in DTFT emphases the discretization in time domain while the D in DFT emphases the discretization in frequency domain. Indeed, the frequency domain here we mention is digital frequency domain varies from 0 to 2 Pi .

So, finally, what is FFT?

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.

Refernces: