4
$\begingroup$

I was using MATLAB for approximating FTs. Why DFT is used if we can approximate the transform-integration using summation.

$\endgroup$
25
  • 2
    $\begingroup$ also, don't forget we rarely actually care about an approximation of the CTFT, as what we deal with is usually limited and hence can be dealt with discrete methods in a way that's more useful. $\endgroup$ – Marcus Müller Oct 26 '20 at 16:44
  • 3
    $\begingroup$ @LelouchYagami Compare the FT and DFT equations. Both multiply by a complex exponential and then sum. And the reason for using the FFT is that it is extremely fast. $\endgroup$ – MBaz Oct 26 '20 at 17:42
  • 2
    $\begingroup$ boy, i dunno where to begin here. not only is the OP missing something basic, but also most, nearly all, of these comments are way off, too. $\endgroup$ – robert bristow-johnson Oct 26 '20 at 18:49
  • 4
    $\begingroup$ the fact is that discrete-time functions $x[n]$ that are uniformly-sampled continuous-time functions $x(nT)$ are approximations to the continuous-time function $x(t)$. the fact is that the DFT is (among other things) an approximation to the CTFT. limiting the limits of the CTFT integral to finite (but large) limits and then representing that integral as a specific Riemann summation leads directly to the DFT. $\endgroup$ – robert bristow-johnson Oct 26 '20 at 18:54
  • 2
    $\begingroup$ i'm just saying that "approximat[ing] the CTFT-integral itself" is the DFT. $\endgroup$ – robert bristow-johnson Oct 26 '20 at 23:30
4
$\begingroup$

Assuming that future vistors won't take the time to read all the comments, I'd like to give a very simple and straightforward interpretation of the discrete Fourier transform (DFT) as an approximation of the continuous-time Fourier transform (CTFT).

First, we need to assume that the signal to be transformed decays sufficiently for large value of $|t|$. (If it doesn't, we can still use the DFT to approximate the CTFT, but the truncation error will be large.) Furthermore, we choose the origin $t=0$ such that the relevant part of the signal appears for $t\ge 0$. Then we can approximate the Fourier integral in the following way:

$$X(j\Omega)=\int_{-\infty}^{\infty}x(t)e^{-j\Omega t}dt\approx \int_{0}^{T}x(t)e^{-j\Omega t}dt\tag{1}$$

with some sufficiently large $T$. The approximation $(1)$ generally results in a truncation error, which can be made small by an appropriate choice of $T$.

Now we can approximate the right-hand side of $(1)$ by a Riemann sum:

$$\int_{0}^{T}x(t)e^{-j\Omega t}dt\approx\sum_{n=0}^{N-1}x(n\Delta t)e^{-j\Omega n\Delta t}\Delta t\tag{2}$$

where $\Delta t$ is the sampling interval and $T=N\Delta t$. The approximation $(2)$ introduces an aliasing error, which can be made small by choosing $\Delta t$ sufficiently small.

Computing the right-hand side of $(2)$ at discrete frequencies $\Omega_k=2\pi k f_s/N$, $k=0,1,\ldots,N-1$, where $f_s=1/\Delta t$ is the sampling frequency, finally results in

$$\begin{align}X(j\Omega_k)&\approx\sum_{n=0}^{N-1}x(n\Delta t)e^{-j\Omega_k n\Delta t}\Delta t\\&=\frac{1}{f_s}\sum_{n=0}^{N-1}x(n\Delta t)e^{-j\frac{2\pi}{N}nk}\\&=\frac{1}{f_s}\textrm{DFT}\big\{x_d[n]\big\},\qquad x_d[n]=x(n\Delta t)\tag{3}\end{align}$$

Eq. $(3)$ says that the CTFT of $x(t)$ can be approximated on a set of discrete frequencies by the DFT of a sampled version of $x(t)$. Two types of error have to be taken into account: 1. the truncation error, from truncating the signal, and 2. the aliasing error, from sampling the signal.

Note that we can never avoid both errors, because for finite length signals (with zero truncation error) we always get an aliasing error due to the infinite bandwidth of finite length signals, and for perfectly band-limited signals (with zero aliasing error), we always have a truncation error because they can't have finite length. In practice we always have to deal with both types of error.

In sum, answering the question in your question title: under the aforementioned conditions, the DFT is an approximation of the CTFT integral, and it has the advantage that there exist very efficient algorithms (FFT) for its computation.

$\endgroup$
5
  • $\begingroup$ I already know this approximation. Can you share any comparison chart of both methods regarding the speed of computation? Using FFT to compute CTFT vs Using direct equation (approximated as summation) of the same finite duration continuous-time signal. That would be the answer to this question.Mr.MBaz also said FFT is extremely fast. I only got comparison chart of FFT vs DFT direct computation. $\endgroup$ – Lelouch Yagami Oct 27 '20 at 15:24
  • $\begingroup$ Doing an integral approximation of the CTFT the textbook way is going to be about as computationally intensive or maybe a bit more, as doing a DFT the hard way. So you can just take the DFT direct computation times as your CTFT times. $\endgroup$ – TimWescott Oct 27 '20 at 15:29
  • $\begingroup$ Or you could actually do the work yourself and benchmark both. That'll give you a way deeper understanding. $\endgroup$ – TimWescott Oct 27 '20 at 15:29
  • 1
    $\begingroup$ well, they don't listen to me, Matt. maybe they will listen to you. $\endgroup$ – robert bristow-johnson Oct 27 '20 at 17:46
  • 1
    $\begingroup$ @robertbristow-johnson: I wrote this down because we don't have this stuff on our site yet, and I think we should have it. The OP seems to want something else, but that's a different matter. $\endgroup$ – Matt L. Oct 27 '20 at 20:18

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.