I'm trying to show how the discrete Fourier transform (DFT) arises from the equation for the continuous-time Fourier Transform. I've run into an interesting caveat which I can't seem to find an explanation to anywhere. My 'derivation' goes something like this:

Lets consider the continuous time Fourier transform equation $$ F(\omega) = \int_{-\infty}^{+\infty} \, f(t) \, e^{-2\pi i \omega t} \,dt $$ If $f(t)$ was to be discretised at $N$ evenly spaced sampling points with the sampling interval of $dt$, then it could be thought of as a continuous function of time with Dirac deltas at each sampling point. The integral of each of the deltas would be equal to the value of $f(t)$ at that point. Lets denote $f(t)$ at $k$-th sampling point (0-indexed) as $f_k$. Now, the integral is non-zero only at those delta functions so the entire above equation can be written as a sum $$ F(\omega) = dt \times \sum_{k=0}^{N-1} \, f_k\, e^{-2\pi i \omega (k dt)} $$ Even though the sum is finite, this is a continuous function of $\omega$. $F(\omega)$ turns out to be periodic in $\omega$ and therefore just a single period of it is needed to be kept to retain all of the information about the sampled version of $f(t)$ it came from.

All of this is (I believe) fine. Here comes the tricky bit. I want to then say that this single period of $F(\omega)$ can be sampled down to $N$ evenly spaced points which would in fact give the equation for the DFT. I say that: "It is one of the implications of the Shannon information theory (...) that for a general case of $N$ arbitrary bits of information, there does not exist a smaller set of bits which can be used to represent all of the information of the original $N$ bits. This places a lower bound on how many samples of $F(\omega)$ one can take."

Question 1: Is this a correct statement about implications of the information theory?

Question 2: I know that N bits of $F(\omega)$ are sufficient, but how do I prove it? To put it differently: How can I one show that for any arbitrary signal I will not loose any information about $f(t)$ by sampling $F(\omega)$ at only $N$ points.

  • 1
    $\begingroup$ the most fundamental thing is that the DFT maps a periodic sequence $x_n$ having period $N$ (so that $x_{n+N}=x_n \quad \forall n \in \mathbb{Z}$) to another periodic sequence $X_k$ having the same period $N$. Relating the DFT to the DTFT or, as you are trying to do, the continuous-time Fourier transform, requires a little bit of hand-waving to put it into a form of the Riemann integral. $\endgroup$ – robert bristow-johnson Jul 8 '19 at 21:39
  • $\begingroup$ How do you take N evenly spaced samples of the function f(t), which stretches from t = -inf to +inf? All the N samples will be infinitely apart, you can never get there. $\endgroup$ – DSP Rookie Apr 4 at 6:46
  • $\begingroup$ Also N samples dt apart : dt in an integral is infinitesimal small quantity. All of those N samples will actually be confined in an small region of t $\endgroup$ – DSP Rookie Apr 4 at 6:48

Note that f() can only be sampled down to N points per period if f() is bandlimited to include only spectrum below t_period/(2*N) in frequency. And a signal exactly periodic in N, with no frequency content at or above t_period/(2*N) in frequency can be exactly represented with N complex exponential basis vectors (Fourier). And the inverse.

The number of degrees of freedom in N complex basis vectors or N complex DFT results matches the number of degrees of freedom in N complex time samples.

|improve this answer|||||

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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