13
$\begingroup$

First of all let me state that I searched for this topic before asking. My question is as follows we have the Analytical Fourier Transform represented with an integral and Discrete Fourier Transform represented with a summation usually computed by a numerical software. My question is that although the relationship is exact at the sampled data points assuming they are equally spaced(say they are equally spaced in time) how can we say about the accuracy of the transform that is if we transform into frequency-domain both with DFT and AFT how will the coefficients for a particular frequency be related? Are they going to be the similar or the same under some conditions?

$\endgroup$

2 Answers 2

23
$\begingroup$

I assume you refer the continuous-time Fourier transform (CTFT)

$$X(\omega)=\int_{-\infty}^{\infty}x(t)e^{-i\omega t}dt\tag{1}$$

and to the discrete Fourier transform (DFT)

$$X[k]=\sum_{n=0}^{N-1}x[n]e^{-i2\pi nk/N}\tag{2}$$

where $x[n]$ and $X[k]$ are sequences, whereas $x(t)$ and $X(\omega)$ are functions. The DFT can be computed efficiently by the Fast Fourier Transform (FFT).

The DFT can be used to approximate the CTFT, but there are always two possible error sources, and you can never avoid both of them at the same time:

  1. truncation error: since the DFT uses a sequence of finite length, any signal $x(t)$ which does not have finite length (or is too long for computer memory) must be truncated.

  2. aliasing error: the DFT uses sample values $x[n]$ which can be equidistant samples of the function $x(t)$. Sampling can introduce aliasing if the sampling rate is smaller than twice the maximum frequency contained in $x(t)$.

You always have at least one of the two above errors because for avoiding the truncation error you need a finite length signal $x(t)$, which cannot be band-limited (i.e. you'll get an aliasing error). The aliasing error can be avoided if you have an ideally band-limited signal and if you choose the sampling frequency sufficiently high, but such a signal cannot have finite duration, so you get a truncation error.

Taking these two errors into account, you can approximate the CTFT by the DFT. Assuming equidistant frequency points with a spacing of $\Delta f$, and a time-domain sampling interval of $T$ you have

$$X(2\pi k\Delta f)\approx T\sum_{n=0}^{N-1}x(nT)e^{-i2\pi kn/N} $$

with $N=1/(\Delta f\cdot T)$, assuming that the relevant part of $x(t)$ has been shifted to the range $[0,NT]$.

$\endgroup$
2
  • 2
    $\begingroup$ That was exactly what I was asking for in particular the relation ship between $X[k]$ and $X(w)$ with the assumption that n also represents time. So while sampling in time domain we got the exact representation(with infinitely precise instrument and a complete theory say) of the analytical time-domain function $x(t)$ sampled at particular times. I will study your answer in more detail. $\endgroup$
    – Vesnog
    Commented Jan 22, 2015 at 18:00
  • $\begingroup$ Clean answer with pragmatic approach $\endgroup$
    – jlandercy
    Commented Oct 6, 2021 at 23:39
2
$\begingroup$

I myself couldn't find a source that directly relates the discrete and continuous Fourier transforms, only approximations, limits, and graphical examples. I worked something out, and this post seems like as good as place as anything to share it.

First some definitions of the key functions.

continuous Fourier transform (if $t$ in seconds, then $f$ in Hz):

$FT\{x(t)\}(f) = \int_{-\infty}^{\infty} x(t) e^{i(-2\pi)ft} dt$

discrete Fourier transform:

$DFT\{y[n]\}[k] = \sum_{n=0}^{N-1} y[n] e^{i \frac{-2\pi}{N}kn}$

Rectangular window (atypical notation):

$U\{a, b\}(t) = \begin{cases} & 1 \text{ if } t\in [a,b) \\ & 0 \text{ if } t\notin [a,b) \end{cases}$

Sinc function:

$sinc(f) = \begin{cases} & 1 \text{ if } f = 0 \\ & \frac{sin(\pi f)}{\pi f} \text{ if } f \neq 0 \end{cases}$

Discrete signal sampling a continuous signal:

$y[n] = \begin{cases} & x(n \Delta t) \text{ if } n\in \{0, 1, ..., M-2, M-1\} \\ & 0 \text{ if } n\in \{M, M+1, ..., N-2, N-1\} \end{cases}$

Note that $y[n]$ has $N$ points but only samples only $M$ points of $x(t)$ with constant time-step $\Delta t$. The other $N-M$ zeros take into account zero-padding.

Now for the relation. To put it in a sentence, the DFT of a finite sample of a continuous $x(t)$ is equal to a discrete sample of the FT of the Dirac-sampled and rectangular-windowed $x(t)$ (3rd line).

$ FT\{x(t)\}(f)*(sinc(M\Delta t\ f) e^{i(-\pi M\Delta t)f})*(\sum_{b=-\infty}^{\infty}\delta(f-\frac{b}{\Delta t})) \Biggr|_{f = \frac{k}{N\Delta t}} \\ = \frac{1}{M} FT\{x(t)\}(f)*(M\Delta t\ sinc(M\Delta t\ f) e^{i(-\pi M\Delta t)f})*(\frac{1}{\Delta t}\sum_{b=-\infty}^{\infty}\delta(f-\frac{b}{\Delta t})) \Biggr|_{f = \frac{k}{N\Delta t}} \\ = \frac{1}{M} FT\{x(t) U\{0, M\Delta t\}(t) \sum_{n=-\infty}^{\infty}\delta (t-n\Delta t)\}(\frac{k}{N\Delta t}) \\ = \frac{1}{M} \int_{-\infty}^{\infty} x(t) U\{0, M\Delta t\}(t) \sum_{n=-\infty}^{\infty}\delta (t-n\Delta t)\ e^{i(-2\pi) \frac{k}{N\Delta t} t} dt \\ = \frac{1}{M} \int_{0}^{M\Delta t} \sum_{n=0}^{M-1} x(n \Delta t) \delta (t-n\Delta t)\ e^{i(-2\pi) \frac{k}{N\Delta t} n \Delta t} dt \\ = \frac{1}{M} \sum_{n=0}^{M-1} \int_{0}^{M\Delta t} y[n] \delta (t-n\Delta t)\ e^{i \frac{-2\pi}{N} kn} dt \\ = \frac{1}{M} \sum_{n=0}^{M-1} y[n] e^{i \frac{-2\pi}{N} kn} \int_{0}^{M\Delta t} \delta (t-n\Delta t)\ dt \\ = \frac{1}{M} \sum_{n=0}^{M-1} y[n] e^{i \frac{-2\pi}{N} kn} 1 \\ = \frac{1}{M} \sum_{n=0}^{N-1} y[n] e^{i \frac{-2\pi}{N} kn} \\ = \frac{1}{M} DFT\{y[n]\}[k] $

This relation explains many principles of using the DFT that are often repeated but rarely explained:

  1. Zero-padding increases $N$ and decreases $\frac{k}{N\Delta t}$, which increases frequency resolution (you can define $\Delta f = \frac{1}{N\Delta t}$).

  2. You'll notice that with finer resolution, you'll see $sinc$ shapes in the DFT because finite $M$ is equivalent to truncating $x(t)$ to $x(t) U\{0, M\Delta t\}(t)$. If you don't like the $sinc$ because of its many lobes causing overlap, you could choose a different window with length $M$, hence the principle of windowing before zero-padding.

  3. You want to sample $x(t)$ as much as possible to maximize the sample length $M$; no amount of zero-padding will change that. A larger $M$ means a narrower and taller $sinc$, which asymptotically approaches a Dirac delta function. People often scale DFTs by $1/M$ to normalize the magnitude across different sample lengths (1st line).

  4. The DFT is N-periodic, and the corresponding FT (the entire first line, not only of $x(t)$) is $\frac{1}{\Delta t}$-periodic due to the convolution by a Dirac comb. The frequencies in $x(t)$ larger than the Nyquist frequency $\frac{1}{2\Delta t}$ are not captured in the DFT and are instead added to the smaller frequencies; this frequency-pollution is called aliasing. This is caused by sampling, no way to completely avoid it. There are a couple ways to deal with this: a) attenuate frequencies above the Nyquist frequency with a low-pass a.k.a anti-aliasing filter before sampling, and b) sample with finer time resolution to capture higher frequencies.

Something convenient happens when you sample several full periods from a periodic signal perfectly aligned to its period. Let's say $x(t)$ has period $P\Delta t$ and you sample $L$ full periods. Without zero-padding, $N=M=LP$.

Because x(t) is periodic, its Fourier transform has the form:

$FT\{x(t)\}(f) = \sum_{a=-\infty}^{\infty} A[a] \delta (f - \frac{a}{P\Delta t}) $

So what does the DFT look like?

$ \frac{1}{M} DFT\{y[n]\}[k] \\ = \frac{1}{M} \sum_{a=-\infty}^{\infty} A[a] \delta (f - \frac{a}{P\Delta t})*(M\Delta t\ sinc(M\Delta t\ f) e^{i(-\pi M\Delta t)f})*(\frac{1}{\Delta t}\sum_{b=-\infty}^{\infty}\delta(f-\frac{b}{\Delta t})) \Biggr|_{f = \frac{k}{N\Delta t}} \\ = \sum_{b=-\infty}^{\infty} \sum_{a=-\infty}^{\infty} A[a] sinc(M\Delta t\ (f - \frac{b}{\Delta t} - \frac{a}{P\Delta t})) e^{i(-\pi M\Delta t)(f - \frac{b}{\Delta t} - \frac{a}{P\Delta t})} \Biggr|_{f = \frac{k}{N\Delta t}} \\ = \sum_{b=-\infty}^{\infty} \sum_{a=-\infty}^{\infty} A[a] sinc(M\Delta t\ (\frac{k}{N\Delta t} - \frac{b}{\Delta t} - \frac{a}{P\Delta t})) e^{i(-\pi M\Delta t)(\frac{k}{N\Delta t} - \frac{b}{\Delta t} - \frac{a}{P\Delta t})} \\ = \sum_{b=-\infty}^{\infty} \sum_{a=-\infty}^{\infty} A[a] sinc(k - Mb - La) e^{i(-\pi)(k - Mb - La)} $

$k - Mb - La$ is a function of only integers, so it itself is an integer. $sinc(f)=0$ for all integer $f$ except $sinc(0)=1$, so the summation term is only possibly nonzero when $k - Mb - La = 0$, or $a = \frac{k - Mb}{L} = \frac{k}{L} - Pb$. $A[a]$ is nonzero only for integers $a$; $Pb$ is an integer, so that leaves $\frac{k}{L}$ needing to be an integer, or $k$ being a multiple of $L$.

$ = \sum_{b=-\infty}^{\infty} A[\frac{k}{L} - Pb] sinc(0) e^{i(-\pi)(0)} \\ = \sum_{b=-\infty}^{\infty} A[\frac{k}{L} - Pb] (: \frac{k}{L} \in \mathbb{Z}) $

In this special case, the $\frac{1}{M}$-scaled DFT reflects the FT (or rather the Fourier Series coefficients $A[a]$ ) much more directly; you don't need to zero-pad or deal with windowing effects. One sampled period ($L=1$) is fine; more periods ($L>1$) increases the frequency resolution $\frac{1}{N\Delta t}$, but that only adds points where $k$ is not a multiple of $L$ and the DFT is $0$. Aliasing still occurs because you're still sampling a continuous signal.

This special case isn't very practical when sampling a signal because you often don't know the period of a continuous signal to align your sampling. (Some people make the mistake of trying to repeat their discrete sample to represent the continuous signal; this introduces errors if sampling was not perfectly aligned.) However, if you're constructing a frequency spectrum to represent a periodic signal, the inverse DFT can be used to get full periods of the sampled signal in the time domain.

$\endgroup$
1
  • 1
    $\begingroup$ Hi, I just wanted to let you know that I found this answer helpful for my purposes, and your answer helped me to find a really nice resource by Trefethen which I'll drop here for anyone's future reference. (Goes into a lot of the same stuff as you did.) people.maths.ox.ac.uk/trefethen/pdetext.html $\endgroup$
    – Nick S
    Commented May 24, 2023 at 16:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .