What is the relation between analytical Fourier transform and DFT?

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]$.


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).

$ \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.

  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 inputs except $f=0$, so the summation term is only nonzero when $k - Mb - La = 0$, or rather $a = \frac{k - Mb}{L}$:

$ = \sum_{b=-\infty}^{\infty} A[\frac{k - Mb}{L}] 1 e^{i(-\pi)(0)} \\ = \sum_{b=-\infty}^{\infty} A[\frac{k - Mb}{L}] $

In this special case, the $\frac{1}{M}$-scaled DFT reflects the FT (or rather the Fourier Series coefficients) much more directly; you don't need to zero-pad or deal with windowing effects. However, 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.