DSPRelated.com
Free Books

Selected Continuous Fourier Theorems

This section presents continuous-time Fourier theorems that go beyond obvious analogs of the DTFT theorems proved in §2.3 above. The differentiation theorem comes up quite often, and its dual pertains as well to the DTFT. The scaling theorem provides an important basic insight into time-frequency duality. The Poisson Summation Formula (PSF) in continuous time extends the discrete-time version presented in §8.3.1. Finally, the extremely fundamental uncertainty principle is derived from the scaling theorem.

Radians versus Cycles

Our usual frequency variable is $ \omega$ in radians per second. However, certain Fourier theorems are undeniably simpler and more elegant when the frequency variable is chosen to be $ f$ in cycles per second. The two are of course related by

$\displaystyle \omega = 2\pi f.$ (B.1)

As an example, $ e^{j\omega t}$ is more compact than $ e^{j2\pi f t}$ . On the other hand, it is nice to get rid of all normalization constants in the Fourier transform and its inverse:
$\displaystyle X(f)$ $\displaystyle =$ $\displaystyle \ensuremath{\int_{-\infty}^{\infty}}x(t)e^{-j2\pi f t} dt$ (B.2)
$\displaystyle x(t)$ $\displaystyle =$ $\displaystyle \ensuremath{\int_{-\infty}^{\infty}}X(f)e^{j2\pi f t} df$ (B.3)

The ``editorial policy'' for this book is this: Generally, $ \omega$ is preferred, but $ f$ is used when considerable simplification results.


Differentiation Theorem

Let $ x(t)$ denote a function differentiable for all $ t$ such that $ x(\pm\infty)=0$ and the Fourier transforms (FT) of both $ x(t)$ and $ {\dot x}(t)$ exist, where $ {\dot x}(t)$ denotes the time derivative of $ x(t)$ . Then we have

$\displaystyle \zbox {{\dot x}(t) \;\longleftrightarrow\;j\omega X(\omega)}$ (B.4)

where $ X(\omega)$ denotes the Fourier transform of $ x(t)$ . In operator notation:

$\displaystyle \zbox {\hbox{\sc FT}_{\omega}({\dot x}) = j\omega X(\omega)}$ (B.5)


Proof: This follows immediately from integration by parts:

\begin{eqnarray*}
\hbox{\sc FT}_{\omega}({\dot x})
&\isdef & \int_{-\infty}^\infty {\dot x}(t) e^{-j\omega t} dt\\
&=& \left. x(t)e^{-j\omega t}\right\vert _{-\infty}^{\infty} -
\int_{-\infty}^\infty x(t) (-j\omega)e^{-j\omega t} dt\\
&=& j\omega X(\omega),
\end{eqnarray*}

since $ x(\pm\infty)=0$ .


Differentiation Theorem Dual


Theorem: Let $ x(n)$ denote a signal with Fourier transform $ X(\omega)$ , and let

$\displaystyle X^\prime(\omega) \isdefs \frac{d}{d\omega} X(\omega)$ (B.6)

denote the derivative of $ X$ with respect to $ \omega$ . Then we have

$\displaystyle \zbox {-jt x(t) \;\longleftrightarrow\;\frac{d}{d\omega}X(\omega)}$ (B.7)

where $ X(\omega)$ denotes the Fourier transform of $ x(t)$ .


Proof: We can show this by direct differentiation of the definition of the Fourier transform:

\begin{eqnarray*}
X^\prime(\omega) &\isdef & \frac{d}{d\omega} \int_{-\infty}^{\infty} x(t) e^{-j\omega t} dt\\
&=& \int_{-\infty}^{\infty} x(t) (-jt) e^{-j\omega t} dt\\
&=& \int_{-\infty}^{\infty} [-jtx(t)] e^{-j\omega t} dt\\
&=& \hbox{\sc FT}_\omega\{[-jtx(t)]\}
\end{eqnarray*}

An alternate method of proof is given in §2.3.13.

The transform-pair may be alternately stated as follows:

$\displaystyle \zbox {-t x(t) \;\longleftrightarrow\;\frac{d}{d(j\omega)}X(\omega)}$ (B.8)


Scaling Theorem

The scaling theorem (or similarity theorem) provides that if you horizontally ``stretch'' a signal by the factor $ \alpha $ in the time domain, you ``squeeze'' and amplify its Fourier transform by the same factor in the frequency domain. This is an important general Fourier duality relationship.


Theorem: For all continuous-time functions $ x(t)$ possessing a Fourier transform,

$\displaystyle \zbox {\hbox{\sc Stretch}_\alpha(x) \;\longleftrightarrow\;\left\vert\alpha\right\vert\hbox{\sc Stretch}_{(1/\alpha)}(X)}
$ (B.9)

where

$\displaystyle \hbox{\sc Stretch}_{\alpha,t}(x) \isdefs x\left(\frac{t}{\alpha}\right)
$ (B.10)

and $ \alpha $ is any nonzero real number (the abscissa stretch factor). A more commonly used notation is the following:

$\displaystyle \zbox {x\left(\frac{t}{\alpha}\right) \;\longleftrightarrow\; \left\vert\alpha\right\vert\cdot X(\alpha\omega)}$ (B.11)


Proof: Taking the Fourier transform of the stretched signal gives

\begin{eqnarray*}
\hbox{\sc FT}_{\omega}(\hbox{\sc Stretch}_\alpha(x))
&\isdef & \int_{-\infty}^\infty x\left(\frac{t}{\alpha}\right) e^{-j\omega t} dt\qquad\hbox{(let $\tau=t/\alpha$)}\\
&=& \int_{-\infty}^\infty x(\tau) e^{-j\omega (\alpha\tau)} d (\alpha\tau) \\
&=& \left\vert\alpha\right\vert\int_{-\infty}^\infty x(\tau) e^{-j(\alpha\omega)\tau} d \tau \\
&\isdef & \left\vert\alpha\right\vert X(\alpha\omega).
\end{eqnarray*}

The absolute value appears above because, when $ \alpha<0$ , $ d
(\alpha\tau) < 0$ , which brings out a minus sign in front of the integral from $ -\infty$ to $ \infty$ .


Shift Theorem

The shift theorem for Fourier transforms states that delaying a signal $ x(t)$ by $ \tau$ seconds multiplies its Fourier transform by $ e^{-j\omega\tau}$ .


Proof:

\begin{eqnarray*}
\hbox{\sc FT}_\omega(\hbox{\sc Shift}_\tau(x)) &\isdef &
\int_{-\infty}^\infty x(t-\tau) e^{-j\omega t}dt\qquad\mbox{(define $\sigma=t-\tau$)}\\
&=& \int_{-\infty}^\infty x(\sigma) e^{-j\omega (\sigma+\tau)}d\sigma\\
&=& e^{-j\omega \tau}\int_{-\infty}^\infty x(\sigma) e^{-j\omega \sigma}d\sigma\\
&\isdef & e^{-j\omega \tau}X(\omega)
\end{eqnarray*}

Thus,

$\displaystyle \zbox {x(t-\tau)\;\longleftrightarrow\;e^{-j\omega \tau}X(\omega).}$ (B.12)


Modulation Theorem (Shift Theorem Dual)

The Fourier dual of the shift theorem is often called the modulation theorem:

$\displaystyle \zbox {x(t)e^{j\nu t}\;\longleftrightarrow\;X(\omega-\nu)}$ (B.13)

This is proved in the same way as the shift theorem above by starting with the inverse Fourier transform of the right-hand side:

\begin{eqnarray*}
\hbox{\sc IFT}_\omega(\hbox{\sc Shift}_\nu(X)) &\isdef &
\frac{1}{2\pi}\int_{-\infty}^\infty X(\omega-\nu) e^{j\omega t}dt\qquad\mbox{(define $\sigma=\omega-\nu$)}\\
&=& \frac{1}{2\pi}\int_{-\infty}^\infty X(\sigma) e^{j(\sigma+\nu)t}d\sigma\\
&=& e^{j\nu t}\frac{1}{2\pi}\int_{-\infty}^\infty X(\sigma) e^{j\sigma t}d\sigma\\
&\isdef & e^{j\nu t} x(t)
\end{eqnarray*}

or,

$\displaystyle \zbox {e^{j\nu t} x(t) \;\longleftrightarrow\; X(\omega-\nu).}$ (B.14)


Convolution Theorem

The convolution theorem for Fourier transforms states that convolution in the time domain equals multiplication in the frequency domain. The continuous-time convolution of two signals $ x(t)$ and $ y(t)$ is defined by

$\displaystyle (x\ast y)(t) \isdef \ensuremath{\int_{-\infty}^{\infty}}x(\tau)y(t-\tau)d\tau.$ (B.15)

The Fourier transform is then

\begin{eqnarray*}
\hbox{\sc FT}_\omega(x\ast y) &\isdef &
\int_{-\infty}^\infty
\left[\ensuremath{\int_{-\infty}^{\infty}}x(\tau)y(t-\tau)d\tau\right]
e^{-j\omega t}dt\\
&=&
\int_{-\infty}^\infty d\tau\, x(\tau)
\ensuremath{\int_{-\infty}^{\infty}}dt\, y(t-\tau)e^{-j\omega t}\\
&=&
\int_{-\infty}^\infty d\tau\, x(\tau) e^{-j\omega\tau}Y(\omega)
\quad\mbox{(by the \emph{shift theorem})}\\
&=& X(\omega)Y(\omega),
\end{eqnarray*}

or,

$\displaystyle \zbox {x\ast y \;\longleftrightarrow\;X\cdot Y.}$ (B.16)

Exercise: Show that

$\displaystyle \zbox {x\cdot y \;\longleftrightarrow\;\frac{1}{2\pi}X\ast Y}$ (B.17)

when frequency-domain convolution is defined by

$\displaystyle (X\ast Y)(\omega) \isdef \ensuremath{\int_{-\infty}^{\infty}}X(\nu) Y(\omega-\nu) d\nu,$ (B.18)

where $ \nu$ is in radians per second, and that

$\displaystyle \zbox {x\cdot y \;\longleftrightarrow\;X\ast Y}$ (B.19)

when frequency-domain convolution is defined by

$\displaystyle (X\ast Y)(f) \isdef \ensuremath{\int_{-\infty}^{\infty}}X(\nu) Y(f-\nu) d\nu,$ (B.20)

with $ \nu$ in Hertz.


Flip Theorems

Let the flip operator be denoted by

\begin{eqnarray*}
\hbox{\sc Flip}_t(x) &\isdef & x(-t)\\
\hbox{\sc Flip}_\omega(X) &\isdef & X(-\omega),
\end{eqnarray*}

where $ t\in(-\infty,\infty)$ denotes time in seconds, and $ \omega\in(-\infty,\infty)$ denotes frequency in radians per second. The following Fourier pairs are easily verified:

\begin{eqnarray*}
\hbox{\sc Flip}(x) &\longleftrightarrow& \hbox{\sc Flip}(X)\\
\hbox{\sc Flip}(\overline{x}) &\longleftrightarrow& \overline{X}\\
\overline{x} &\longleftrightarrow& \hbox{\sc Flip}(\overline{X})
\end{eqnarray*}

The proof of the first relation is as follows:

\begin{eqnarray*}
\hbox{\sc FT}_{\omega}\left[\hbox{\sc Flip}(x)\right] &\isdef & \ensuremath{\int_{-\infty}^{\infty}}x(-t) e^{-j\omega t} dt\quad
\mbox{(set $\tau=-t$)}\\
&=& \int_{\infty}^{-\infty} x(\tau) e^{-j\omega (-\tau)} (-d\tau)\\
&=& \ensuremath{\int_{-\infty}^{\infty}}x(\tau) e^{-j(-\omega) \tau} d\tau\\
&=& X(-\omega) \isdef \hbox{\sc Flip}_\omega(X)
\end{eqnarray*}


Power Theorem

The power theorem for Fourier transforms states that the inner product of two signals in the time domain equals their inner product in the frequency domain.

The inner product of two spectra $ X(\omega)$ and $ Y(\omega)$ may be defined as

$\displaystyle \left<X,Y\right> \isdef \frac{1}{2\pi} \ensuremath{\int_{-\infty}^{\infty}}X(\omega)\overline{Y(\omega)}d\omega = \ensuremath{\int_{-\infty}^{\infty}}X(2\pi f)\overline{Y(2\pi f)}df.$ (B.21)

This expression can be interpreted as the inverse Fourier transform of $ X\cdot\overline{Y}$ evaluated at $ t=0$ :

$\displaystyle \left<X,Y\right> \isdef \frac{1}{2\pi} \left.\ensuremath{\int_{-\infty}^{\infty}}X(\omega)\overline{Y(\omega)}e^{j\omega t}d\omega\right\vert _{t=0}.$ (B.22)

By the convolution theoremB.7) and flip theoremB.8),

$\displaystyle X\cdot \overline{Y}\;\longleftrightarrow\;x\ast \hbox{\sc Flip}(\overline{y}),$ (B.23)

which at $ t=0$ gives

$\displaystyle (x\ast \hbox{\sc Flip}(\overline{y}))(0) = \left.\ensuremath{\int_{-\infty}^{\infty}}x(\tau)\overline{y(\tau-t)}d\tau\right\vert _{t=0} = \ensuremath{\int_{-\infty}^{\infty}}x(\tau)\overline{y(\tau)}d\tau \isdef \left<x,y\right>$ (B.24)

Thus,

$\displaystyle \zbox {\left<x,y\right> \;\longleftrightarrow\;\left<X,Y\right>.}$ (B.25)


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} \frac{1}{\Delta}, & 0\leq t\leq \Delta \\ [5pt] 0, & \hbox{otherwise}. \\ \end{array} \right. \protect$ (B.26)

An impulse can be similarly defined as the limit of any pulse shape which maintains unit area and approaches zero width at time 0 [150]. 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.27)

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}.$ (B.28)

(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 [36,150]. (It is still commonly called a ``delta function'', however, despite the misnomer.)


Gaussian Pulse

The Gaussian pulse of width (second central moment) $ \sigma $ centered on time 0 may be defined by

$\displaystyle g_\sigma(t) \frac{1}{\sigma\sqrt{2\pi}}\isdef e^{-\frac{t^2}{\sigma^2}}$ (B.29)

where the normalization scale factor is chosen to give unit area under the pulse. Its Fourier transform is derived in Appendix D to be

$\displaystyle G_\sigma(\omega) = e^{-\frac{\omega^2}{2(1/\sigma)^2}}.$ (B.30)


Rectangular Pulse

The rectangular pulse of width $ \tau$ centered on time 0 may be defined by

$\displaystyle p_\tau(t) \isdef \left\{\begin{array}{ll} 1, & \left\vert t\right\vert\leq\frac{\tau}{2} \\ [5pt] 0, & \left\vert t\right\vert>\frac{\tau}{2}. \\ \end{array} \right.$ (B.31)

Its Fourier transform is easily evaluated:

\begin{eqnarray*}
P_\tau(\omega) &\isdef & \hbox{\sc FT}_\omega(p_\tau) \isdef \int_{-\infty}^\infty p_\tau(t) e^{-j\omega t}dt\\
&=& \int_{-\frac{\tau}{2}}^{\frac{\tau}{2}} e^{-j\omega t}dt
= \left.-\frac{1}{j\omega} e^{-j\omega t}\right\vert _{t=-\frac{\tau}{2}}^{\frac{\tau}{2}}\\
&=& \frac{e^{j\omega \frac{\tau}{2}} - e^{-j\omega \frac{\tau}{2}}}{j\omega}
= \frac{2j\sin\left(\omega \frac{\tau}{2}\right)}{j\omega}\\
&=& \tau\frac{\sin\left(\omega \frac{\tau}{2}\right)}{\omega\frac{\tau}{2}}
= \tau\frac{\sin(\pi f\tau)}{\pi f\tau}\\
&\isdef & \tau\,\mbox{sinc}(f\tau)
\end{eqnarray*}

Thus, we have derived the Fourier pair

$\displaystyle \zbox {p_\tau(t) \;\longleftrightarrow\;\tau\,\mbox{sinc}(f\tau)} \protect$ (B.32)

Note that sinc$ (f)$ is the Fourier transform of the one-second rectangular pulse:

$\displaystyle p_1(t) \;\longleftrightarrow\;$sinc$\displaystyle (f)$ (B.33)

From this, the scaling theorem implies the more general case:

$\displaystyle p_1\left(\frac{t}{\tau}\right) \;\longleftrightarrow\;\tau\,$sinc$\displaystyle (f\tau)$ (B.34)


Sinc Impulse

The preceding Fourier pair can be used to show that

$\displaystyle \zbox {\lim_{\tau\to\infty} \tau\,\mbox{sinc}(f\tau) = \delta(f).}$ (B.35)


Proof: The inverse Fourier transform of $ \tau\,$sinc$ (f\tau)$ is

\begin{eqnarray*}
p_\tau(t)
&=& \ensuremath{\int_{-\infty}^{\infty}}\tau\,\mbox{sinc}\left(\frac{\omega}{2\pi}\tau\right) e^{j\omega t}\frac{d\omega}{2\pi}\\
&=& \ensuremath{\int_{-\infty}^{\infty}}\tau\,\mbox{sinc}(f\tau) e^{j2\pi f t}df\\
&=& \left\{\begin{array}{ll}
1, & \left\vert\tau\right\vert\leq 1/2 \\ [5pt]
0, & \mbox{otherwise}. \\
\end{array} \right.
\end{eqnarray*}

In particular, in the middle of the rectangular pulse at $ t=0$ , we have

$\displaystyle p_\tau(0)=\ensuremath{\int_{-\infty}^{\infty}}\tau\,\mbox{sinc}(f\tau) df = 1, \quad \forall \tau>0.$ (B.36)

This establishes that the algebraic area under $ \tau\,$sinc$ (\tau f)$ is 1 for every $ \tau>0$ . Every delta function (impulse) must have this property.

We now show that $ \tau\,$sinc$ (f\tau)$ also satisfies the sifting property in the limit as $ \tau\to\infty$ . This property fully establishes the limit as a valid impulse. That is, an impulse $ \delta(t)$ is any function having the property that

$\displaystyle \ensuremath{\int_{-\infty}^{\infty}}g(t)\delta(t)dt = \left<g,\delta\right> = g(0)$ (B.37)

for every continuous function $ g(t)$ . In the present case, we need to show, specifically, that

$\displaystyle \lim_{\tau\to\infty}\ensuremath{\int_{-\infty}^{\infty}}G(f)\tau\,\mbox{sinc}(\tau f)\,df = G(0).$ (B.38)

Define $ P_\tau(f)\isdef \tau\,$sinc$ (f\tau)$ . Then by the power theoremB.9),

$\displaystyle \left<G,P_\tau\right> = \left<g,p_\tau\right> = \ensuremath{\int_{-\infty}^{\infty}}g(t) p_\tau(t)\,dt = \int_{-\tau/2}^{\tau/2} g(t)\,dt.$ (B.39)

Then as $ \tau\to\infty$ , the limit converges to the algebraic area under $ g$ , which is $ G(0)$ as desired:

$\displaystyle \lim_{\tau\to\infty}\int_{-\tau/2}^{\tau/2} g(t)\,dt = \ensuremath{\int_{-\infty}^{\infty}}g(t)\,dt = \left.\ensuremath{\int_{-\infty}^{\infty}}e^{-j\omega t} g(t)\,dt \right\vert _{\omega=0} = G(0).$ (B.40)

We have thus established that

$\displaystyle {\lim_{\tau\to\infty}\tau\,\mbox{sinc}(f\tau) = \delta(f),}$ (B.41)

where

sinc$\displaystyle (f)\isdef \frac{\sin(\pi f)}{\pi f}.$ (B.42)

For related discussion, see [36, p. 127].


Impulse Trains

The impulse signal $ \delta(t)$ (defined in §B.10) has a constant Fourier transform:

$\displaystyle \hbox{\sc FT}_f(\delta) \isdef \int_{-\infty}^\infty \delta(t) e^{-j2\pi f t}\,dt = 1, \quad \forall f\in{\bf R}$ (B.43)

An impulse train can be defined as a sum of shifted impulses:

$\displaystyle \psi_P(t) \isdef \sum_{m=-\infty}^\infty \delta(t-mP)$ (B.44)

Here, $ P$ is the period of the impulse train, in seconds--i.e., the spacing between successive impulses. The $ P$ -periodic impulse train can also be defined as

$\displaystyle \psi_P(t)\eqsp \frac{1}{P}\,\raisebox{0.8em}{\rotatebox{-90}{\resizebox{1em}{1em}{\ensuremath{\exists}}}}\left(\frac{t}{P}\right), \protect$ (B.45)

where $ \,\raisebox{0.8em}{\rotatebox{-90}{\resizebox{1em}{1em}{\ensuremath{\exists}}}}(t)$ is the so-called shah symbol [23]:

$\displaystyle {\,\raisebox{0.8em}{\rotatebox{-90}{\resizebox{1em}{1em}{\ensuremath{\exists}}}}(t) \, \isdef \sum_{m=-\infty}^\infty \delta(t-m)}$ (B.46)

Note that the scaling by $ 1/P$ in (B.46) is necessary to maintain unit area under each impulse.

We will now show that

$\displaystyle \zbox {\,\raisebox{0.8em}{\rotatebox{-90}{\resizebox{1em}{1em}{\ensuremath{\exists}}}}(t)\;\longleftrightarrow\;\,\raisebox{0.8em}{\rotatebox{-90}{\resizebox{1em}{1em}{\ensuremath{\exists}}}}(f).}$ (B.47)

That is, the Fourier transform of the normalized impulse train $ \,\raisebox{0.8em}{\rotatebox{-90}{\resizebox{1em}{1em}{\ensuremath{\exists}}}}(t)$ is exactly the same impulse train $ \,\raisebox{0.8em}{\rotatebox{-90}{\resizebox{1em}{1em}{\ensuremath{\exists}}}}(f)$ in the frequency domain, where $ t$ denotes time in seconds and $ f$ denotes frequency in Hz. By the scaling theorem (§B.4),

$\displaystyle {\,\raisebox{0.8em}{\rotatebox{-90}{\resizebox{1em}{1em}{\ensuremath{\exists}}}}\left(\frac{t}{P}\right) \;\longleftrightarrow\;P\,\raisebox{0.8em}{\rotatebox{-90}{\resizebox{1em}{1em}{\ensuremath{\exists}}}}(Pf),}$ (B.48)

so that the $ P$ -periodic impulse-train defined in (B.46) transforms to

\begin{eqnarray*}
\psi_P(t) &=& \frac{1}{P}\,\raisebox{0.8em}{\rotatebox{-90}{\resizebox{1em}{1em}{\ensuremath{\exists}}}}\left(\frac{t}{P}\right)
\;\longleftrightarrow\;\,\raisebox{0.8em}{\rotatebox{-90}{\resizebox{1em}{1em}{\ensuremath{\exists}}}}(Pf) \eqsp \sum_{m=-\infty}^\infty \delta(Pf-m)\\
&=& \frac{1}{P}\sum_{m=-\infty}^\infty \delta\left(f-\frac{m}{P}\right)
\eqsp \frac{1}{P}\psi_{\frac{1}{P}}(f) \eqsp \Psi_P(f).
\end{eqnarray*}

Thus, the $ P$ -periodic impulse train transforms to a $ (1/P)$ -periodic impulse train, in which each impulse contains area $ 1/P$ :

$\displaystyle {\Psi_P(f) \isdefs \hbox{\sc FT}_f(\psi_P) \eqsp \frac{1}{P}\psi_{\frac{1}{P}}(f)}$ (B.49)


Proof: Let's set up a limiting construction by defining

$\displaystyle \,\raisebox{0.8em}{\rotatebox{-90}{\resizebox{1em}{1em}{\ensuremath{\exists}}}}_M(t) \isdefs \sum_{m=-M}^M \delta(t-m),$ (B.50)

so that $ \lim_{M\to\infty}\,\raisebox{0.8em}{\rotatebox{-90}{\resizebox{1em}{1em}{\ensuremath{\exists}}}}_M(t)=\,\raisebox{0.8em}{\rotatebox{-90}{\resizebox{1em}{1em}{\ensuremath{\exists}}}}(t)$ . We may interpret $ \,\raisebox{0.8em}{\rotatebox{-90}{\resizebox{1em}{1em}{\ensuremath{\exists}}}}_M(t)$ as a sampled rectangular pulse of width $ 2M$ seconds (yielding $ 2M+1$ samples).By linearity of the Fourier transform and the shift theoremB.5), we readily obtain the transform of $ \,\raisebox{0.8em}{\rotatebox{-90}{\resizebox{1em}{1em}{\ensuremath{\exists}}}}_M(t)$ to be

\begin{eqnarray*}
\hbox{\sc FT}_f(\,\raisebox{0.8em}{\rotatebox{-90}{\resizebox{1em}{1em}{\ensuremath{\exists}}}}_M) &\isdef & \hbox{\sc FT}_f\left[\sum_{m=-M}^M \hbox{\sc Shift}_{m}(\delta)\right]\\
&=& \sum_{m=-M}^M \hbox{\sc FT}_f[\hbox{\sc Shift}_{m}(\delta)] \eqsp \sum_{m=-M}^M e^{-j2\pi f m}.
\end{eqnarray*}

Using the closed form of a geometric series,

$\displaystyle \sum_{m=L}^U r^m \eqsp \frac{ r^L - r^{U+1}}{1-r},$ (B.51)

with $ r=e^{-j\pi f}$ , we can write this as

\begin{eqnarray*}
\hbox{\sc FT}_f(\,\raisebox{0.8em}{\rotatebox{-90}{\resizebox{1em}{1em}{\ensuremath{\exists}}}}_M)
&=& \frac{e^{j2\pi f M } - e^{-j2\pi f M } e^{-j2\pi f }}{1-e^{-j2\pi f }}\\ [10pt]
&=& \frac{e^{-j\pi f}}{e^{-j\pi f}}
\cdot
\frac{e^{j\pi f (2M+1) } - e^{-j\pi f (2M+1) }}{e^{j\pi f}-e^{-j\pi f}}\\ [10pt]
&=& \frac{\sin[\pi f (2M+1) ]}{\sin(\pi f)}\\ [5pt]
&\isdef & (2M+1)\,\hbox{asinc}_{2M+1}(2\pi f )
\end{eqnarray*}

where we have used the definition of $ \hbox{asinc}$ given in Eq.$ \,$ (3.5) of §3.1. As we would expect from basic sampling theory, the Fourier transform of the sampled rectangular pulse is an aliased sinc function. Figure 3.2 illustrates one period $ M\cdot\hbox{asinc}_M(\omega)$ for $ M=11$ .

The proof can be completed by expressing the aliased sinc function as a sum of regular sinc functions, and using linearity of the Fourier transform to distribute $ \hbox{\sc FT}_f$ over the sum, converting each sinc function into an impulse, in the limit, by §B.13:

\begin{eqnarray*}
(2M+1)\,\hbox{asinc}_{2M+1}(2\pi f) &\isdef &
\frac{\sin[\pi f (2M+1) ]}{\sin(\pi f)}\\ [5pt]
&=& \sum_{k=-\infty}^{\infty} \mbox{sinc}(2Mf-k)\\ [5pt]
&\to& \sum_{k=-\infty}^{\infty} \delta(f-k)
\end{eqnarray*}

by §B.13. Note that near $ f=0,2,4,\ldots$ , we have

\begin{eqnarray*}
\hbox{\sc FT}_f(\,\raisebox{0.8em}{\rotatebox{-90}{\resizebox{1em}{1em}{\ensuremath{\exists}}}}_M) &=& \frac{\sin[\pi f (2M+1) ]}{\sin(\pi f)}
\;\;\approx\;\; \frac{\sin[\pi f (2M+1) ]}{\pi f}\\ [5pt]
&=&(2M+1)\mbox{sinc}[(2M+1)f]
\;\;\to\;\;\delta(f)
\end{eqnarray*}

as $ M\to\infty$ , as shown in §B.13. Similarly, near $ f=1,3,5,\ldots$ , we have

$\displaystyle \hbox{\sc FT}_f(\,\raisebox{0.8em}{\rotatebox{-90}{\resizebox{1em}{1em}{\ensuremath{\exists}}}}_M) \;\;\approx\;\; \frac{\sin[\pi f (2M+1) ]}{-\pi f} \;\;\to\;\;\delta(f)$ (B.52)

as $ M\to\infty$ . Finally, we expect that the limit for non-integer $ f$ can be neglected since

$\displaystyle \lim_{M\to\infty}\int_a^b \frac{\sin(M\pi f)}{\pi f} df \eqsp 0,$ (B.53)

whenever $ n<a\leq b<n+1$ and $ n$ is some integer, as implied by §B.13.

See, e.g., [23,79] for more about impulses and their application in Fourier analysis and linear systems theory.

Exercise: Using a similar limiting construction as before,

$\displaystyle \Psi_P(f) = \lim_{L\to\infty} \Psi_{P,L}(f) \isdefs \lim_{L\to\infty} \frac{2\pi}{P}\sum_{l=-L}^L \delta\left(2\pi f-l\frac{2\pi}{P}\right),$ (B.54)

show that a direct inverse-Fourier transform calculation gives

$\displaystyle \psi_{P,L}(t) = \frac{\sin\left[\pi(2L+1)\frac{t}{P}\right]}{\sin\left( \pi \frac{t}{P}\right)},$ (B.55)

and verify that the peaks occur every $ P$ seconds and reach height $ (2L+1)/P$ . Also show that the peak widths, measured between zero crossings, are $ P/(2L+1)$ , so that the area under each peak is of order 1 in the limit as $ L\to\infty$ . [Hint: The shift theorem for inverse Fourier transforms is $ e^{j\nu t}x(t) \;\leftrightarrow\;
X(f-\nu)$ , and $ \hbox{\sc IFT}_t(\delta)=1/(2\pi)$ .]


Poisson Summation Formula

As shown in §B.14 above, the Fourier transform of an impulse train is an impulse train with inversely proportional spacing:

$\displaystyle \psi_R(t)\;\longleftrightarrow\;{\frac{1}{R}}\cdot\psi_{\frac{1}{R}}(f) = \,\raisebox{0.8em}{\rotatebox{-90}{\resizebox{1em}{1em}{\ensuremath{\exists}}}}(Rf)$ (B.56)

where

$\displaystyle \psi_R(t) \isdefs \sum_{m=-\infty}^\infty \delta(t-mR) = \frac{1}{R}\,\raisebox{0.8em}{\rotatebox{-90}{\resizebox{1em}{1em}{\ensuremath{\exists}}}}\left(\frac{t}{R}\right).$ (B.57)

Using this Fourier theorem, we can derive the continuous-time PSF using the convolution theorem for Fourier transforms:B.1

$\displaystyle \sum_m w(t-mR) = \psi_R \ast w \;\longleftrightarrow\; \Psi_R \cdot W = \frac{1}{R}\cdot\psi_{\frac{1}{R}}\cdot W$ (B.58)

Using linearity and the shift theorem for inverse Fourier transforms, the above relation yields

\begin{eqnarray*}
\sum_m w(t-mR)
&=& \frac{1}{R} \hbox{\sc IFT}_t
\left[W(f)\sum_k\delta\left(f-k\frac{1}{R}\right) \right]
\quad\left(\mbox{define $f_k\isdef \frac{k}{R}$}\right)
\\ [5pt]
&=& \frac{1}{R} \hbox{\sc IFT}_t
\left[\sum_k W(f_k)\cdot\delta\left(f-f_k\right) \right]\\ [5pt]
&=& \frac{1}{R}
\sum_k W(f_k)\cdot\hbox{\sc IFT}_t \left[\delta\left(f-f_k\right) \right]\\ [5pt]
&=& \frac{1}{R} \sum_k W(f_k)e^{j 2\pi f_k t}.
\end{eqnarray*}

We have therefore shown

$\displaystyle \zbox {\sum_{m=-\infty}^{\infty} w(t-mR) = \frac{1}{R} \sum_{k=-\infty}^{\infty} W(f_k)e^{j 2\pi f_k t}, \quad f_k\isdef \frac{k}{R}.} \protect$ (B.59)

Compare this result to Eq.$ \,$ (8.30). The left-hand side of (B.60) can be interpreted $ s_R(t)=\hbox{\sc Alias}_R(w)$ , i.e., the time-alias of $ w$ on a block of length $ R$ . The function $ s_R(t)$ is periodic with period $ R$ seconds. The right-hand side of (B.60) can be interpreted as the inverse Fourier series of $ W(f)$ sampled at intervals of $ 1/R$ Hz. This sampling of $ W(\omega)$ in the frequency domain corresponds to the aliasing of $ w(t)$ in the time domain.


Sampling Theory

The dual of the Poisson Summation Formula is the continuous-time aliasing theorem, which lies at the foundation of elementary sampling theory [264, Appendix G]. If $ x(t)$ denotes a continuous-time signal, its sampled version $ x(nT)$ , $ n\in{\bf Z}$ , is associated with the continuous-time signal

$\displaystyle x_d(t) \isdefs x(t)\psi_T(t) \isdefs x(t)\sum_m\delta(t-mT).$ (B.60)

where $ T$ denotes the (fixed) sampling interval in seconds. The sampled signal values $ x(nT)$ are thus treated mathematically as coefficients of impulses at the sampling instants. Taking the Fourier transform gives

\begin{eqnarray*}
X_d(f) &=& \hbox{\sc FT}_f(x\cdot\psi_T) \eqsp X\ast \Psi_T\\
&=& \frac{1}{T}X\ast \psi_{1/T}
\eqsp f_s\sum_{k=-\infty}^{\infty}X(f-kf_s)
\end{eqnarray*}

where $ f_s\isdef 1 f_s\isdef 1/T$ denotes the sampling rate in radians per second. Note that $ X_d(f)$ is periodic with period $ f_s$ . We see that if $ X(f)$ is bandlimited to less than $ f_s$ radians per second, i.e., if $ X(f)=0$ for all $ \vert f\vert\geq f_s/2$ , then only the $ k=0$ term will be nonzero in the summation over $ k$ , and this means there is no aliasing. The terms $ X(f-kf_s)$ for $ k\neq 0$ are all aliasing terms.


The Uncertainty Principle

The uncertainty principle (for Fourier transform pairs) follows immediately from the scaling theorem (§B.4). It may be loosely stated as

Time Duration $ \times$ Frequency Bandwidth $ \geq$ c
where $ c$ is some constant determined by the precise definitions of ``duration'' in the time domain and ``bandwidth'' in the frequency domain.

If duration and bandwidth are defined as the ``nonzero interval,'' then we obtain $ c=\infty$ , which is not useful. This conclusion follows immediately from the definition of the Fourier transform and its inverse (§2.2).

Duration and Bandwidth as Second Moments

More interesting definitions of duration and bandwidth are obtained using the normalized second moments of the squared magnitude:

$\displaystyle \Delta t$ $\displaystyle \isdef$ $\displaystyle \frac{1}{\left\Vert\,x\,\right\Vert _2} \sqrt{\int_{-\infty}^\infty t^2 \left\vert x(t)\right\vert^2 \,dt}
\quad\isdef \quad \frac{\left\Vert\,tx\,\right\Vert _2}{\left\Vert\,x\,\right\Vert _2}$  
$\displaystyle \Delta \omega$ $\displaystyle \isdef$ $\displaystyle \frac{1}{\left\Vert\,X\,\right\Vert _2} \sqrt{\int_{-\infty}^\infty \omega^2 X(\omega) \frac{d\omega}{2\pi}}
\quad\isdef \quad \frac{\left\Vert\,\omega X\,\right\Vert _2}{\left\Vert\,X\,\right\Vert _2},
\protect$ (B.61)

where

\begin{eqnarray*}
\left\Vert\,x\,\right\Vert _2^2 &\isdef & \int_{-\infty}^\infty \left\vert x(t)\right\vert^2 dt\nonumber \\
\left\Vert\,X\,\right\Vert _2^2 &\isdef & \int_{-\infty}^\infty \left\vert X(\omega)\right\vert^2 \frac{d\omega}{2\pi}
\end{eqnarray*}

By the DTFT power theorem2.3.8), we have $ \left\Vert\,x\,\right\Vert _2=\left\Vert\,X\,\right\Vert _2$ . Note that writing `` $ \left\Vert\,tx\,\right\Vert _2$ '' and `` $ \left\Vert\,\omega X\,\right\Vert _2$ '' is an abuse of notation, but a convenient one. These duration/bandwidth definitions are routinely used in physics, e.g., in connection with the Heisenberg uncertainty principle [59].Under these definitions, we have the following theorem [202, p. 273-274]:


Theorem: If $ \sqrt{\vert t\vert}x(t) \to 0$ as $ \left\vert t\right\vert\to\infty$ , then

$\displaystyle \zbox {\Delta t\cdot \Delta \omega \geq \frac{1}{2}} \protect$ (B.62)

with equality if and only if

$\displaystyle x(t) = Ae^{\alpha t^2}, \quad \alpha>0.$ (B.63)

That is, only the Gaussian function (also known as the ``bell curve'' or ``normal curve'') achieves the lower bound on the time-bandwidth product.


Proof: Without loss of generality, we may take consider $ x(t)$ to be real and normalized to have unit $ L2$ norm ( $ \left\Vert\,x\,\right\Vert _2=1$ ). From the Schwarz inequality [264],B.2

$\displaystyle \left\vert\int_{-\infty}^\infty t x(t) \left[\frac{d}{dt}x(t)\right] dt\right\vert^2 \leq \int_{-\infty}^\infty t^2 x^2(t) dt \int_{-\infty}^\infty \left\vert\frac{d}{dt}x(t)\right\vert^2 dt. \protect$ (B.64)

The left-hand side can be evaluated using integration by parts:

$\displaystyle \int_{-\infty}^\infty tx \frac{dx}{dt} dt = \left . t \frac{x^2(t)}{2} \right\vert _{-\infty}^{\infty} - \frac{1}{2} \int_{-\infty}^\infty x^2(t) dt \isdef -\frac{1}{2}\left\Vert\,x\,\right\Vert _2^2 = -\frac{1}{2}$ (B.65)

where we used the assumption that $ \sqrt{\vert t\vert}x(t) \to 0$ as $ \left\vert t\right\vert\to\infty$ .

The second term on the right-hand side of (B.65) can be evaluated using the power theorem and differentiation theoremB.2):

$\displaystyle \int_{-\infty}^\infty \left\vert\frac{dx(t)}{dt}\right\vert^2 dt = \int_{-\infty}^\infty \left\vert j\omega X(\omega)\right\vert^2 \frac{d\omega}{2\pi} = \int_{-\infty}^\infty \omega^2 \left\vert X(\omega)\right\vert^2 \frac{d\omega}{2\pi}$ (B.66)

Substituting these evaluations into (B.65) gives

$\displaystyle \left\vert-\frac{1}{2}\right\vert^2 \leq \left\Vert\,tx\,\right\Vert _2^2 \left\Vert\,\omega X\,\right\Vert _2^2.$ (B.67)

Taking the square root of both sides gives the uncertainty relation sought.

If equality holds in the uncertainty relation (B.63), then (B.65) implies

$\displaystyle \frac{d}{dt}x(t) = c t x(t)$ (B.68)

for some constant $ c$ , implying $ x(t)=A e^{\frac{c}{2} t^2}$ for some constants $ A$ and $ c$ .


Time-Limited Signals

If $ x(t)=0$ for $ \left\vert t\right\vert\geq \Delta t/2$ , then

$\displaystyle \Delta t\cdot\Delta \omega \geq \pi$ (B.69)

where $ \Delta\omega$ is as defined above in (B.62).


Proof: See [202, pp. 274-5].


Time-Bandwidth Products Unbounded Above

We have considered two lower bounds for the time-bandwidth product based on two different definitions of duration in time. In the opposite direction, there is no upper bound on time-bandwidth product. To see this, imagine filtering an arbitrary signal with an allpass filter.B.3 The allpass filter cannot affect bandwidth $ \Delta\omega$ , but the duration $ \Delta t$ can be arbitrarily extended by successive applications of the allpass filter.


Relation of Smoothness to Roll-Off Rate

In §3.1.1, we found that the side lobes of the rectangular-window transform ``roll off'' as $ 1/\omega$ . In this section we show that this roll-off rate is due to the amplitude discontinuity at the edges of the window. We also show that, more generally, a discontinuity in the $ n$ th derivative corresponds to a roll-off rate of $ 1/\omega^{n+1}$ .

The Fourier transform of an impulse $ x(t)=\delta(t)$ is simply

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

by the sifting property of the impulse under integration. This shows that an impulse consists of Fourier components at all frequencies in equal amounts. The roll-off rate is therefore zero in the Fourier transform of an impulse.

By the differentiation theorem for Fourier transforms (§B.2), if $ x\;\leftrightarrow\;X$ , then

$\displaystyle {\cal F}_\omega\{{\dot x}\} = j\omega X(\omega),$ (B.71)

where $ {\dot x}(t)\isdef \frac{dx}{dt}(t)$ . Consequently, the integral of $ x(t)$ transforms to $ X(\omega)/(j\omega)$ :

$\displaystyle \int_{-\infty}^t x(\tau)\,d\tau \;\longleftrightarrow\;\frac{X(\omega)}{j\omega}$ (B.72)

The integral of the impulse is the unit step function:

$\displaystyle \int_{-\infty}^t \delta(\tau)\,d\tau = u(t) \isdef \left\{\begin{array}{ll} 1, & t\geq0 \\ [5pt] 0, & t<0 \\ \end{array} \right.$ (B.73)

Therefore,B.4

$\displaystyle U(\omega) = \frac{1}{j\omega}.$ (B.74)

Thus, the unit step function has a roll-off rate of $ -6$ dB per octave, just like the rectangular window. In fact, the rectangular window can be synthesized as the superposition of two step functions:

$\displaystyle w_R(n) = u\left(n+\frac{M-1}{2}\right) - u\left(n-\frac{M-1}{2}\right)$ (B.75)

Integrating the unit step function gives a linear ramp function:

$\displaystyle \int_{-\infty}^t u(\tau)d\tau = t \cdot u(t) = \left\{\begin{array}{ll} t, & t\geq0 \\ [5pt] 0, & t<0 \\ \end{array} \right..$ (B.76)

Applying the integration theorem again yields

$\displaystyle t\cdot u(t) \;\longleftrightarrow\;\frac{1}{(j\omega)^2}.$ (B.77)

Thus, the linear ramp has a roll-off rate of $ -12$ dB per octave. Continuing in this way, we obtain the following Fourier pairs:

\begin{eqnarray*}
\delta(t) &\longleftrightarrow& 1\\
u(t) &\longleftrightarrow& \frac{1}{j\omega}\\
t\cdot u(t) &\longleftrightarrow& \frac{1}{(j\omega)^2}\\
\frac{1}{2}t^2 u(t) &\longleftrightarrow& \frac{1}{(j\omega)^3}\\
\vdots & \vdots & \vdots \\
\frac{1}{n!}t^n u(t) &\longleftrightarrow& \frac{1}{(j\omega)^{n+1}}
\end{eqnarray*}

Now consider the Taylor series expansion of the function $ x(t) = t^n u(t)$ at $ t=0$ :

$\displaystyle x(t) = x(0) + {\dot x}(0) x + \frac{1}{2!}{\ddot x}(0) x^2 + \cdots$ (B.78)

The derivatives up to order $ n-1$ are all zero at $ t=0$ . The $ n$ th derivative, however, has a discontinuous jump at $ t=0$ . Since this is the only ``wideband event'' in the signal, we may conclude that a discontinuity in the $ n$ th derivative corresponds to a roll-off rate of $ 1/\omega^{n+1}$ . The following theorem generalizes this result to a wider class of functions which, for our purposes, will be spectrum analysis window functions (before sampling):


Theorem: (Riemann Lemma): If the derivatives up to order $ n$ of the function $ w(t)$ exist and are of bounded variation (defined below), then its Fourier Transform $ W(\omega)$ is asymptotically of orderB.5 $ 1/\omega^{n+1}$ , i.e.,

$\displaystyle W(\omega) = {\cal O}\left(\frac{1}{\omega^{n+1}}\right), \quad(\hbox{as }\omega\to\infty)$ (B.79)

Proof: Following [202, p. 95], let $ w(t)$ be any real function of bounded variation on the interval $ (a,b)$ of the real line, and let

$\displaystyle w(t) = w_{\scriptscriptstyle\uparrow}(t) - w_{\scriptscriptstyle\downarrow}(t)$ (B.80)

denote its decomposition into a nondecreasing part $ w_{\scriptscriptstyle\uparrow}(t)$ and nonincreasing part $ -w_{\scriptscriptstyle\downarrow}(t)$ .B.6 Then there exists $ \tau\in(a,b)$ such that

\begin{eqnarray*}
\mbox{re}\left\{W_{\scriptscriptstyle\uparrow}(\omega)\right\}
&=& \int_a^b w_{\scriptscriptstyle\uparrow}(t)\cos(\omega t) dt \\
&=& w_{\scriptscriptstyle\uparrow}(a)\int_a^\tau \cos(\omega t) dt
+ w_{\scriptscriptstyle\uparrow}(b)\int_\tau^b \cos(\omega t) dt
\end{eqnarray*}

Since

$\displaystyle \left\vert\int_a^\tau\cos(\omega t) dt\right\vert = \left\vert\frac{\sin(\omega \tau) - \sin(\omega a)}{\omega}\right\vert \leq \frac{2}{\vert\omega\vert}$ (B.82)

we conclude

$\displaystyle \left\vert\mbox{re}\left\{W_{\scriptscriptstyle\uparrow}(\omega)\right\}\right\vert = \left\vert\int_a^b w_{\scriptscriptstyle\uparrow}(t)\cos(\omega t) dt \right\vert \leq \left\vert w_{\scriptscriptstyle\uparrow}(a)\right\vert\frac{2}{\vert\omega\vert} + \left\vert w_{\scriptscriptstyle\uparrow}(b)\right\vert\frac{2}{\vert\omega\vert} \leq \frac{4M}{\left\vert\omega\right\vert}$ (B.83)

where $ M\isdef \max\{\left\vert w_{\scriptscriptstyle\uparrow}(a)\},\left\vert w_{\scriptscriptstyle\uparrow}(b)\right\vert\right\vert$ , which is finite since $ w$ is of bounded variation. Note that the conclusion holds also when $ (a,b)=(-\infty,\infty)$ . Analogous conclusions follow for im$ \left\{W_{\scriptscriptstyle\uparrow}(\omega)\right\}$ , re$ \left\{w_{\scriptscriptstyle\downarrow}(\omega)\right\}$ , and im$ \left\{w_{\scriptscriptstyle\downarrow}(\omega)\right\}$ , leading to the result

$\displaystyle \left\vert W(\omega)\right\vert = {\cal O}\left(\frac{1}{\omega}\right).$ (B.84)

If in addition the derivative $ w^\prime (t)$ is bounded on $ (a,b)$ , then the above gives that its transform $ j\omega W(\omega)$ is asymptotically of order $ 1/\omega$ , so that $ W(\omega) =
{\cal O}(1/\omega^2)$ . Repeating this argument, if the first $ n$ derivatives exist and are of bounded variation on $ (a,b)$ , we have $ W(\omega) =
{\cal O}(1/\omega^{n+1})$ . $ \Box$

Since spectrum-analysis windows $ w(n)$ are often obtained by sampling continuous time-limited functions $ w(t)$ , we normally see these asymptotic roll-off rates in aliased form, e.g.,

$\displaystyle \hbox{\sc Alias}_{\Omega_s}\left(\frac{1}{w^{n+1}}\right) = \sum_{k=-\infty}^\infty\frac{1}{(w+k\Omega_s)^{n+1}}$ (B.85)

where $ \Omega_s=2\pi f_s$ denotes the sampling rate in radians per second. This aliasing normally causes the roll-off rate to ``slow down'' near half the sampling rate, as shown in Fig.3.6 for the rectangular window transform. Every window transform must be continuous at $ \omega=\pm\pi$ (for finite windows), so the roll-off envelope must reach a slope of zero there.

In summary, we have the following Fourier rule-of-thumb:

$\displaystyle \zbox {\hbox{$n$\ derivatives} \;\longleftrightarrow\;-6(n+1) \hbox{ dB per octave roll-off rate}}$ (B.86)

This is also $ -20(n+1)$ dB per decade.

To apply this result to estimating FFT window roll-off rate (as in Chapter 3), we normally only need to look at the window's endpoints. The interior of the window is usually differentiable of all orders. For discrete-time windows, the roll-off rate ``slows down'' at high frequencies due to aliasing.


Next Section:
Beginning Statistical Signal Processing
Previous Section:
Notation