10
$\begingroup$

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!

$\endgroup$
1
  • 2
    $\begingroup$ Hey! Welcome to dsp.SE :) I'm not an expert of DFT, but a very quick search of the site gives me a lot of questions and explanations of it: 1, 2, 3. Maybe there's something on the site already that can help you, did you look through all the offered answers? We try to avoid duplicating same information in multiple answers. I'm sure that we will be glad to help you with any questions you might have left after that :) $\endgroup$
    – penelope
    Commented Nov 6, 2012 at 9:53

1 Answer 1

9
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.