Home

difference between DTFT, DFT and FFT

by Forrest Sheng Bao http://fsbao.net

There are so many guys ask me the difference between DTFT and DFT. And most of them can't distinguish computational resolution and physical resolution. More, many of them are confused about why we say "N-point DFT of a length-L". What is N-point? and what is "length-L"? why there are two discrete values, N and L? Sometimes even myself are puzzled by them.

DTFT stands for Discrete-Time Fourier Transform
DFT stands for Discrete Fourier Transform

DTFT is defined as
X(\omega)=\sum_{L-1}^{n=0}x(n)e^{-j \omega n}
this web page from RICE university provide an explanation http://cnx.rice.edu/content/m10247/latest/

Then what is DFT? Signal Processing written by Sophocles J. Orfanidis provides a definition:
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,0 \leq \omega \leq 2 \pi (sec.9.2.3)

DFT is defined as
X(\omega_{k})=\sum_{L-1}^{n=0}x(n)e^{-j \omega_{k} n}
which is call a N-point DFT of a length-L signal

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.

So N only concerns DFT and computational resolution.But L concerns both the DTFT and DFT.It also limits the physical 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 .

in DTFT the input signal is discretized while in DFT both the input signal and the computational method are discretized. Thus, DFT is a numerical calculation while DTFT defines an analytical solution.

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

But please remember,there are many types of FFT. In general,the FFT we mentioned is the decimation-in-time radix-2 FFT.

Here are another two webpages from RICE university
http://cnx.rice.edu/content/m0504/latest/
http://cnx.rice.edu/content/m10783/latest/