What is the meaning of the DFT?

Possible Duplicate:
Real Discrete Fourier Transform
What is the most lucid, intuitive explanation for the various FTs - CFT, DFT, DTFT and the Fourier Series?
Discrete-time Fourier transform

I read about the Discrete Fourier Transform. I understand how to compute it given a sequence of numbers(digital signal), but I still didn't get what's the meaning of the new sequence I get as the output.

I mean, I know that the Fourier Transform takes an analog signal representation in the time domain and returns its representation in the frequency domain, its spectrum. If I look at the analog signal in a time-window $T$, sampling it $N$ times , then the sampling interval will be $t_0 = T/N$ and the sampling frequency will be $f_s =1/t_0$. The sampled values of the analog signal give me a new digital signal, lets say $s_n$

So what is the meaning of the DFT of this digital signal $s_n$? How the DFT sequence related to $s_n$? How it is related to the original analog signal? What is the meaning of these frequency components I get? Should they be taught of an approximation the previous analog signal frequency components or as sampled values of its spectrum?

Thanks a lot!

Answer

As you noted, the discrete Fourier transform (DFT) maps a length-$N$ sequence to its (also length-$N$) frequency-domain equivalent. The time-domain signal $s[n]$ is transformed into a frequency-domain signal $S[k]$, such that the following two relations hold true:

$$ S[k] = \sum_{n=0}^{N-1} s[n] e^{\frac{-j2\pi k n}{N}} \text{ (the DFT)} $$ $$ s[n] = \sum_{k=0}^{N-1} S[k] e^{\frac{j2\pi k n}{N}} \text{ (the inverse DFT)} $$ (ignoring scale factors that can be placed in many different places depending upon the preference of the author; one way to make them "symmetric" is to place a factor of $\frac{1}{\sqrt{N}}$ in front of each equation: the unitary DFT).

There are a number of intuitive interpretations for the action implied by these equations. Here's the way I usually think about them:

• 
  
  

  Forward DFT: Each DFT output value $S[k]$ is a complex value that represents the amplitude and phase of $s[n]$'s content at frequency $\frac{2\pi k}{N}$. The multiplication by the exponential function effectively shifts $s[n]$ down in frequency by $\frac{2\pi k}{N}$. The sum over $N$ time samples can then be thought of as applying a decimating lowpass filter. So, effectively, the $N$ outputs of the DFT represent the results of applying a bank of equally-spaced filters across $s[n]$'s frequency band, thus measuring "how much" energy is present in various frequency bands in the input signal.

  
  


• 
  

  Inverse DFT: The DFT output values $S[k]$ are used to weight a number of complex exponential functions in order to resynthesize the original time-domain signal $s[n]$. The frequency associated with $S[k]$ is the additive inverse of the frequency used during the forward DFT. This view clearly shows that the DFT can be thought of as a means to decompose an arbitary finite-length time-domain signal $s[n]$ into a set of weighted orthogonal complex exponential functions (or "complex sinusoids").

  
  

Now, extending this concept a bit: when you sample a continuous-time signal $s(t)$ at discrete time instants, you get a (potentially infinite-length) discrete-time signal $s[n]$. Applying the Fourier transform to such a discrete-time signal results in the discrete time Fourier transform (DTFT), which is continuous in frequency and, like the DFT, periodic in frequency with period $2\pi$. Assuming that a large-enough sample rate was used during the conversion to discrete-time, the result of the DTFT will look a lot like the Fourier transform of the original signal $s(t)$.The DFT is only applicable to finite-length signals, so in order to apply it, one must truncate the discrete-time signal $s[n]$ to some finite length $N$, resulting in a potentially-shorter signal $s_N[n]$.

• 
  

  For this special case of a finite-length discrete-time signal, the $N$ DFT outputs are just equally-spaced samples of $s_N[n]$'s DTFT.

  
  
  


• 
  

  $s_N[n]$'s DTFT is related to $s[n]$'s DTFT; they may differ if $s[n]$ was longer than $N$ samples long originally and some truncation/windowing was involved in generating a finite sample length.

  
  


• 
  

  $s[n]$'s DTFT is related to the original signal's Fourier transform, with the caveat that the DTFT is periodic, so all of the frequency content from the continuous-time signal that is unambiguously representable in discrete-time (the bandwidth of which is determined by the sample rate used) is contained within a single length-$2\pi$ period of $s[n]$'s DTFT.