Free Books
   Free Books    Mathematics of the DFT  

Fourier Transforms for Continuous/Discrete Time/Frequency

The Fourier transform can be defined for signals which are

  • discrete or continuous in time, and
  • finite or infinite in duration.
This results in four cases. Quite naturally, the frequency domain has the same four cases,
  • discrete or continuous in frequency, and
  • finite or infinite in bandwidth.
When time is discrete, the frequency axis is finite, and vice versa.

This book has been concerned almost exclusively with the discrete-time, discrete-frequency case (the DFT), and in that case, both the time and frequency axes are finite in length. In the following sections, we briefly summarize the other three cases. Table B.1 summarizes all four Fourier-transform cases corresponding to discrete or continuous time and/or frequency.


Table B.1: Four cases of sampled/continuous time and frequency.
\begin{table}\begin{center} \begin{displaymath} \begin{array}{\vert c\vert c\v... ...q. } \omega & \\ \hline \end{array}\end{displaymath} \end{center} \end{table}


Discrete Time Fourier Transform (DTFT)

The Discrete Time Fourier Transform (DTFT) can be viewed as the limiting form of the DFT when its length $ N$ is allowed to approach infinity:

$\displaystyle X(\tilde{\omega}) \isdef \sum_{n=-\infty}^\infty x(n) e^{-j\tilde{\omega}n} $

where $ \tilde{\omega}\isdef \omega T\in[-\pi,\pi)$ denotes the continuous normalized radian frequency variable,B.1 and $ x(n)$ is the signal amplitude at sample number $ n$.

The inverse DTFT is

$\displaystyle x(n) = \frac{1}{2\pi}\int_{-\pi}^\pi X(\tilde{\omega}) e^{j\tilde{\omega}n} d\tilde{\omega} $

which can be derived in a manner analogous to the derivation of the inverse DFT (see Chapter 6).

Instead of operating on sampled signals of length $ N$ (like the DFT), the DTFT operates on sampled signals $ x(n)$ defined over all integers $ n\in{\bf Z}$. As a result, the DTFT frequencies form a continuum. That is, the DTFT is a function of continuous frequency $ \tilde{\omega}\in[-\pi,\pi)$, while the DFT is a function of discrete frequency $ \omega_k$, $ k\in[0,N-1]$. The DFT frequencies $ \omega_k=2\pi k/N$, $ k=0,1,2,\ldots,N-1$, are given by the angles of $ N$ points uniformly distributed along the unit circle in the complex plane (see Fig.6.1). Thus, as $ N\to\infty$, a continuous frequency axis must result in the limit along the unit circle in the $ z$ plane. The axis is still finite in length, however, because the time domain remains sampled.

Fourier Transform (FT) and Inverse

The Fourier transform of a signal $ x(t)\in{\bf C}$, $ t\in(-\infty,\infty)$, is defined as

$\displaystyle X(\omega) \isdef \int_{-\infty}^\infty x(t) e^{-j\omega t} dt, \protect$ (B.1)

and its inverse is given by

$\displaystyle x(t) = \frac{1}{2\pi}\int_{-\infty}^\infty X(\omega) e^{j\omega t} d\omega. \protect$ (B.2)

Existence of the Fourier Transform

Conditions for the existence of the Fourier transform are complicated to state in general [12], but it is sufficient for $ x(t)$ to be absolutely integrable, i.e.,

$\displaystyle \left\Vert\,x\,\right\Vert _1 \isdef \int_{-\infty}^\infty \left\vert x(t)\right\vert dt < \infty . $

This requirement can be stated as $ x\in L1$, meaning that $ x$ belongs to the set of all signals having a finite $ L1$ norm ( $ \left\Vert\,x\,\right\Vert _1<\infty$). It is similarly sufficient for $ x(t)$ to be square integrable, i.e.,

$\displaystyle \left\Vert\,x\,\right\Vert _2^2\isdef \int_{-\infty}^\infty \left\vert x(t)\right\vert^2 dt < \infty, $

or, $ x\in L2$. More generally, it suffices to show $ x\in Lp$ for $ 1\leq p\leq 2$ [12, p. 47].

There is never a question of existence, of course, for Fourier transforms of real-world signals encountered in practice. However, idealized signals, such as sinusoids that go on forever in time, do pose normalization difficulties. In practical engineering analysis, these difficulties are resolved using Dirac's ``generalized functions'' such as the impulse (also called the delta function) [38].

The Continuous-Time Impulse

An impulse in continuous time must have ``zero width'' and unit area under it. One definition is

$\displaystyle \delta(t) \isdef \lim_{\Delta \to 0} \left\{\begin{array}{ll} \fr... ...eq t\leq \Delta \\ [5pt] 0, & \hbox{otherwise}. \\ \end{array} \right. \protect$ (B.3)

An impulse can be similarly defined as the limit of any integrable pulse shape which maintains unit area and approaches zero width at time 0. As a result, the impulse under every definition has the so-called sifting property under integration,

$\displaystyle \int_{-\infty}^\infty f(t) \, \delta(t)\, dt = f(0), \protect$ (B.4)

provided $ f(t)$ is continuous at $ t=0$. This is often taken as the defining property of an impulse, allowing it to be defined in terms of non-vanishing function limits such as

$\displaystyle \delta(t) \isdef \lim_{\Omega\to\infty}\frac{\sin(\Omega t)}{\pi t}. $

(Note, incidentally, that $ \sin(\Omega t)/\pi t$ is in $ L2$ but not $ L1$.)

An impulse is not a function in the usual sense, so it is called instead a distribution or generalized function [12,38]. (It is still commonly called a ``delta function'', however, despite the misnomer.)

Fourier Series (FS) and Relation to DFT

In continuous time, a periodic signal $ x(t)$, with period $ P$ seconds,B.2 may be expanded into a Fourier series with coefficients given by

$\displaystyle X(\omega_k) \isdef \frac{1}{P}\int_0^P x(t) e^{-j\omega_k t} dt, \quad k=0,\pm1,\pm2,\dots \protect$ (B.5)

where $ \omega_k \isdef 2\pi k/P$ is the $ k$th harmonic frequency (rad/sec). The generally complex value $ X(\omega_k)$ is called the $ k$th Fourier series coefficient. The normalization by $ 1/P$ is optional, but often included to make the Fourier series coefficients independent of the fundamental frequency $ 1/P$, and thereby depend only on the shape of one period of the time waveform.

Relation of the DFT to Fourier Series

We now show that the DFT of a sampled signal $ x(n)$ (of length $ N$), is proportional to the Fourier series coefficients of the continuous periodic signal obtained by repeating and interpolating $ x$. More precisely, the DFT of the $ N$ samples comprising one period equals $ N$ times the Fourier series coefficients. To avoid aliasing upon sampling, the continuous-time signal must be bandlimited to less than half the sampling rate (see Appendix D); this implies that at most $ N$ complex harmonic components can be nonzero in the original continuous-time signal.

If $ x(t)$ is bandlimited to $ \omega T\in(-\pi,\pi)$, it can be sampled at intervals of $ T$ seconds without aliasing (see §D.2). One way to sample a signal inside an integral expression such as Eq.$ \,$(B.5) is to multiply it by a continuous-time impulse train

$\displaystyle \Psi_T(t) \isdef T\sum_{n=-\infty}^\infty \delta(t-nT) \protect$ (B.6)

where $ \delta(t)$ is the continuous-time impulse signal defined in Eq.$ \,$(B.3).

We wish to find the continuous-time Fourier series of the sampled periodic signal $ x(nT)$. Thus, we replace $ x(t)$ in Eq.$ \,$(B.5) by

$\displaystyle x_s(t) \isdef x(t)\cdot \Psi_T(t). $

By the sifting property of delta functions (Eq.$ \,$(B.4)), the Fourier series of $ x_s$ isB.3

\begin{eqnarray*} X_s(\omega_k) = \frac{1}{P} \int_0^P x_s(t) e^{-j\omega_k t} d... ...1}{P} \sum_{n=0}^{\lceil P/T\rceil-1} x(nT) e^{-j\omega_k nT} T. \end{eqnarray*}

If the sampling interval $ T$ is chosen so that it divides the signal period $ P$, then the number of samples under the integral is an integer $ N\isdef P/T$, and we obtain

\begin{eqnarray*} X_s(\omega_k) &=& \frac{T}{P} \sum_{n=0}^{N-1} x(nT) e^{-j\o... ...{1}{N}\hbox{\sc DFT}_{N,k}(x_p), \quad k=0,\pm 1, \pm 2, \dots \end{eqnarray*}

where $ x_p\isdef [x(0),x(T),\dots,x((N-1)T)]$. Thus, $ X_s(\omega_k)=X(\omega_k)$ for all $ k$ at which the bandlimited periodic signal $ x(t)$ has a nonzero harmonic. When $ N$ is odd, $ X(\omega_k)$ can be nonzero for $ k\in[-(N-1)/2,(N-1)/2]$, while for $ N$ even, the maximum nonzero harmonic-number range is $ k\in[-N/2+1,N/2-1]$.

In summary,

$\textstyle \parbox{0.8\textwidth}{% WHY IS THIS NEEDED??? \emph{the Fourier ser... ...he DFT length, and $N$\ is also the number of samples in each period of $x$.}}$

Next Section:
Selected Continuous-Time Fourier Theorems
Previous Section:
Fast Fourier Transform (FFT) Algorithms