Hi all, This Blog is an English archive of my PhD experience in Imperial College London, mainly logging my research and working process, as well as some visual records.

Thursday 2 August 2007

Fourier transform

In mathematics, the Fourier transform, named in honor of French mathematician Joseph Fourier, is a certain linear operator that maps functions to other functions. Loosely speaking, the Fourier transform decomposes a function into a continuous spectrum of its frequency components, and the inverse transform synthesizes a function from its spectrum of frequency components. A useful analogy is the relationship between a series of pure notes (the frequency components) and a musical chord (the function itself). In mathematical physics, the Fourier transform of a signal x(t) can be thought of as that signal in the "frequency domain." This is similar to the basic idea of the various other Fourier transforms including the Fourier series of a periodic function. (See also fractional Fourier transform and linear canonical transform for generalizations.)

Definitions

There are several common conventions for defining the Fourier transform of a complex-valued Lebesgue integrable function, x.\, In communications and signal processing, for instance, it is often the function:

X(f) = \int_{-\infty}^{\infty} x(t)\ e^{-i 2\pi f t}\,dt, for every real number f.\,

When the independent variable t\, represents time (with SI unit of seconds), the transform variable f\, represents ordinary frequency (in hertz). The complex-valued function, X,\, is said to represent x\, in the frequency domain. I.e., if x\, is a continuous function, then it can be reconstructed from X\, by the inverse transform:

x(t) = \int_{-\infty}^{\infty} X(f)\ e^{ i 2 \pi f t}\,df, for every real number t.\,


Other notations for X(f)\, are: \hat{x}(f)\, and \mathcal{F}\{x\}(f).\,

The interpretation of X\, is aided by expressing it in polar coordinate form: X(f) = A(f)\ e^{i \phi (f)},\, where:

A(f) = |X(f)|, \, the amplitude
\phi (f) = \angle X(f), \, the phase.

Then the inverse transform can be written:

x(t) = \int_{-\infty}^{\infty} A(f)\ e^{ i(2\pi f t +\phi (f))}\,df,

which is a recombination of all the frequency components of x(t).\, Each component is a complex sinusoid of the form eift whose amplitude is A(f) and whose initial phase angle (at t = 0) is φ(f).


In mathematics, the Fourier transform is commonly written in terms of angular frequency: \omega = 2\pi f,\, whose units are radians per second.

The substitution f = \frac{\omega}{2\pi}\, into the formulas above produces this convention:

X(\omega) = \int_{-\infty}^\infty x(t)\ e^{- i\omega t}\,dt [1]
x(t) = \frac{1}{2\pi} \int_{-\infty}^{\infty} X(\omega)\ e^{ i\omega t}\,d\omega,

which is also a bilateral Laplace transform evaluated at s = iω.However, this destroys the symmetry, resulting in the transform pair


To restore the symmetry of the transforms, the factor can be split evenly between the Fourier transform and the inverse, which leads to another popular convention:

 X(\omega) = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^\infty x(t)\ e^{- i\omega t}\,dt
x(t) = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{\infty} X(\omega)\ e^{ i\omega t}\,d\omega.

This convention and the X(f) convention are unitary transforms.

Variations of all three conventions can be created by conjugating the complex-exponential kernel of both the forward and the reverse transform. The signs must be opposites. Other than that, the choice is (again) a matter of convention.

Summary of popular forms of the Fourier transform
angular
frequency
 \omega \,
(rad/s)
unitary  X_1(\omega) \ \stackrel{\mathrm{def}}{=}\  \frac{1}{\sqrt{2 \pi}} \int_{-\infty}^{\infty} x(t) \ e^{-i \omega t}\, dt \ = \frac{1}{\sqrt{2 \pi}} X_2(\omega) = \frac{1}{\sqrt{2 \pi}} X_3 \left ( \frac{\omega}{2 \pi} \right )\,

 x(t) = \frac{1}{\sqrt{2 \pi}} \int_{-\infty}^{\infty} X_1(\omega) \ e^{i \omega t}\, d \omega \

non-unitary  X_2(\omega) \ \stackrel{\mathrm{def}}{=}\  \int_{-\infty}^{\infty} x(t) \ e^{-i \omega t} \ dt \ = \sqrt{2 \pi}\ X_1(\omega) = X_3 \left ( \frac{\omega}{2 \pi} \right ) \,

 x(t) = \frac{1}{2 \pi} \int_{-\infty}^{\infty} X_2(\omega) \ e^{i \omega t} \ d \omega \

ordinary
frequency
 f \,
(hertz)
unitary  X_3(f) \ \stackrel{\mathrm{def}}{=}\  \int_{-\infty}^{\infty} x(t) \ e^{-i 2 \pi f t} \ dt \ = \sqrt{2 \pi}\ X_1(2 \pi f) = X_2(2 \pi f)\,

 x(t) = \int_{-\infty}^{\infty} X_3(f) \  e^{i 2 \pi f t}\, df \


Generalization

There are several ways to define the Fourier transform pair. The "forward" and "inverse" transforms are always defined so that the operation of both transforms in either order on a function will return the original function. In other words, the composition of the transform pair is defined to be the identity transformation. Using two arbitrary real constants a and b, the most general definition of the forward 1-dimensional Fourier transform is given by

X(\omega) = \sqrt{\frac{|b|}{(2 \pi)^{1-a}}} \int_{-\infty}^{+\infty}  x(t) e^{-i b \omega t} \, dt

and the inverse is given by

x(t) = \sqrt{\frac{|b|}{(2 \pi)^{1+a}}} \int_{-\infty}^{+\infty}  X(\omega) e^{i b \omega t} \, d\omega

Note that the transform definitions are symmetric; they can be reversed by simply changing the signs of a and b.

The convention adopted in this article is (a,b) = (0,1). The choice of a and b is usually chosen so that it is geared towards the context in which the transform pairs are being used. The non-unitary convention above is (a,b) = (1,1). Another very common definition is (a,b) = (0,2π) which is often used in signal processing applications. In this case, the angular frequency ω becomes ordinary frequency f. If f (or ω) and t carry units, then their product must be dimensionless. For example, t may be in units of time, specifically seconds, and f (or ω) would be in hertz (or radian/s).

The Fourier transform F(k) of a function f(x) is implemented as FourierTransform[f, x, k], and different choices of a and b can be used by passing the optional FourierParameters->{a, b} option. By default, Mathematica takes FourierParameters as (0,1). Unfortunately, a number of other conventions are in widespread use. For example, (0,1) is used in modern physics, (1,-1) is used in pure mathematics and systems engineering, (1,1) is used in probability theory for the computation of the characteristic function, (-1,1) is used in classical physics, and (0,-2pi) is used in signal processing. In this work, following Bracewell (1999, pp. 6-7), it is always assumed that a==0 and b==-2pi unless otherwise stated. This choice often results in greatly simplified transforms of common functions such as 1, cos(2pik_0x), etc.

Since any function can be split up into even and odd portions E(x) and O(x),

f(x)==1/2[f(x)+f(-x)]+1/2[f(x)-f(-x)]==E(x)+O(x),
(11)

a Fourier transform can always be expressed in terms of the Fourier cosine transform and Fourier sine transform as

F_x[f(x)](k)==int_(-infty)^inftyE(x)cos(2pikx)dx-iint_(-infty)^inftyO(x)sin(2pikx)dx.

Table of important Fourier transforms

The following table records some important Fourier transforms. G and H denote Fourier transforms of g(t) and h(t), respectively. g and h may be integrable functions or tempered distributions. Note that the two most common unitary conventions are included.

Functional relationships


Signal Fourier transform
unitary, angular frequency
Fourier transform
unitary, ordinary frequency
Remarks

 g(t)\,  G(\omega)\!\ \stackrel{\mathrm{def}}{=}\ \!

\frac{1}{\sqrt{2 \pi}} \int_{-\infty}^{\infty}\!\!g(t) e^{-i \omega t}\, dt
 G(f)\!\ \stackrel{\mathrm{def}}{=}\

\int_{-\infty}^{\infty}\!\!g(t) e^{-i 2\pi f t}\, dt

101 a\cdot g(t) + b\cdot h(t)\, a\cdot G(\omega) + b\cdot H(\omega)\, a\cdot G(f) + b\cdot H(f)\, Linearity
102 g(t - a)\, e^{- i a \omega} G(\omega)\, e^{- i 2\pi a f} G(f)\, Shift in time domain
103 e^{ iat} g(t)\, G(\omega - a)\, G \left(f - \frac{a}{2\pi}\right)\, Shift in frequency domain, dual of 2
104 g(a t)\, \frac{1}{|a|} G \left( \frac{\omega}{a} \right)\, \frac{1}{|a|} G \left( \frac{f}{a} \right)\, If |a|\, is large, then g(a t)\, is concentrated around 0 and \frac{1}{|a|}G \left( \frac{\omega}{a} \right)\, spreads out and flattens. It is interesting to consider the limit of this as | a | tends to infinity - the delta function
105 G(t)\,  g(-\omega)\,  g(-f)\, Duality property of the Fourier transform. Results from swapping "dummy" variables of  t \, and  \omega \,.
106 \frac{d^n g(t)}{dt^n}\,  (i\omega)^n  G(\omega)\,  (i 2\pi f)^n  G(f)\, Generalized derivative property of the Fourier transform
107 t^n g(t)\, i^n \frac{d^n G(\omega)}{d\omega^n}\, \left (\frac{i}{2\pi}\right)^n \frac{d^n G(f)}{df^n}\, This is the dual of 106
108 (g * h)(t)\, \sqrt{2\pi} G(\omega) H(\omega)\, G(f) H(f)\, g * h\, denotes the convolution of g\, and h\, — this rule is the convolution theorem
109 g(t) h(t)\, (G * H)(\omega) \over \sqrt{2\pi}\, (G * H)(f)\, This is the dual of 108
110 g(t)\, is purely real, and an even function G(\omega)\, and G(f)\, are purely real, and even functions
111 g(t)\, is purely real, and an odd function G(\omega)\, and G(f)\, are purely imaginary, and odd functions

Square-integrable functions


Signal Fourier transform
unitary, angular frequency
Fourier transform
unitary, ordinary frequency
Remarks

 g(t) \,  G(\omega)\!\ \stackrel{\operatorname{def}}{=}\ \!

\frac{1}{\sqrt{2 \pi}} \int_{-\infty}^{\infty}\!\!g(t) e^{-i \omega t} \operatorname{d}t \,
 G(f)\!\ \stackrel{\operatorname{def}}{=}\

\int_{-\infty}^{\infty}\!\!g(t) e^{-i 2\pi f t} \operatorname{d}t \,

201 \operatorname{rect}(a t) \, \frac{1}{\sqrt{2 \pi a^2}}\cdot \operatorname{sinc}\left(\frac{\omega}{2\pi a}\right) \frac{1}{|a|}\cdot \operatorname{sinc}\left(\frac{f}{a}\right) The rectangular pulse and the normalized sinc function
202  \operatorname{sinc}(a t)\, \frac{1}{\sqrt{2\pi a^2}}\cdot \operatorname{rect}\left(\frac{\omega}{2 \pi a}\right) \frac{1}{|a|}\cdot \operatorname{rect}\left(\frac{f}{a} \right)\, Dual of rule 201. The rectangular function is an idealized low-pass filter, and the sinc function is the non-causal impulse response of such a filter.
203  \operatorname{sinc}^2 (a t) \,  \frac{1}{\sqrt{2\pi a^2}}\cdot \operatorname{tri} \left( \frac{\omega}{2\pi a} \right)  \frac{1}{|a|}\cdot \operatorname{tri} \left( \frac{f}{a} \right) tri is the triangular function
204  \operatorname{tri} (a t) \, \frac{1}{\sqrt{2\pi a^2}} \cdot \operatorname{sinc}^2 \left( \frac{\omega}{2\pi a} \right) \frac{1}{|a|}\cdot \operatorname{sinc}^2 \left( \frac{f}{a} \right) \, Dual of rule 203.
205 e^{-\alpha t^2}\, \frac{1}{\sqrt{2 \alpha}}\cdot e^{-\frac{\omega^2}{4 \alpha}} \sqrt{\frac{\pi}{\alpha}}\cdot e^{-\frac{(\pi f)^2}{\alpha}} Shows that the Gaussian function exp( − αt2) is its own Fourier transform. For this to be integrable we must have 0" src="http://upload.wikimedia.org/math/c/a/9/ca9f9f0b0f73d40a69aadedbfe0f7c53.png">.
206  e^{iat^2} = \left. e^{-\alpha t^2}\right|_{\alpha = -i a} \,  \frac{1}{\sqrt{2 a}} \cdot e^{-i \left(\frac{\omega^2}{4 a} -\frac{\pi}{4}\right)}  \sqrt{\frac{\pi}{a}} \cdot e^{-i \left(\frac{\pi^2 f^2}{a}  -\frac{\pi}{4}\right)} common in optics
207 \cos ( a t^2 ) \,  \frac{1}{\sqrt{2 a}} \cos \left( \frac{\omega^2}{4 a} - \frac{\pi}{4} \right)  \sqrt{\frac{\pi}{a}}  \cos \left( \frac{\pi^2 f^2}{a} - \frac{\pi}{4} \right)
208 \sin ( a t^2 ) \,  \frac{-1}{\sqrt{2 a}} \sin \left( \frac{\omega^2}{4 a} - \frac{\pi}{4} \right)  - \sqrt{\frac{\pi}{a}}  \sin \left( \frac{\pi^2 f^2}{a} - \frac{\pi}{4} \right)
209 \operatorname{e}^{-a|t|} \,  \sqrt{\frac{2}{\pi}} \cdot \frac{a}{a^2 + \omega^2}  \frac{2 a}{a^2 + 4 \pi^2 f^2} a>0
210  \frac{1}{\sqrt{|t|}} \,  \frac{1}{\sqrt{|\omega|}}  \frac{1}{\sqrt{|f|}} the transform is the function itself
211  J_0 (t)\,  \sqrt{\frac{2}{\pi}} \cdot \frac{\operatorname{rect} \left( \frac{\omega}{2} \right)}{\sqrt{1 - \omega^2}}  \frac{2\cdot \operatorname{rect} (\pi f)}{\sqrt{1 - 4 \pi^2 f^2}} J0(t) is the Bessel function of first kind of order 0
212  J_n (t) \,  \sqrt{\frac{2}{\pi}} \frac{ (-i)^n T_n (\omega) \operatorname{rect} \left( \frac{\omega}{2} \right)}{\sqrt{1 - \omega^2}}  \frac{2 (-i)^n T_n (2 \pi f) \operatorname{rect} (\pi f)}{\sqrt{1 - 4 \pi^2 f^2}} it's the generalization of the previous transform; Tn (t) is the Chebyshev polynomial of the first kind.
213  \frac{J_n (t)}{t} \,  \sqrt{\frac{2}{\pi}} \frac{i}{n} (-i)^n \cdot U_{n-1} (\omega)\,

\cdot \ \sqrt{1 - \omega^2} \operatorname{rect} \left( \frac{\omega}{2} \right)

 \frac{2 \operatorname{i}}{n} (-i)^n \cdot U_{n-1} (2 \pi f)\,

\cdot \ \sqrt{1 - 4 \pi^2 f^2}  \operatorname{rect} ( \pi f )

Un (t) is the Chebyshev polynomial of the second kind
214 \operatorname{sech}(a t) \, \frac{1}{a}\sqrt{\frac{\pi}{2}}\operatorname{sech} \left( \frac{\pi}{2 a} \omega \right) \frac{\pi}{a} \operatorname{sech} \left( \frac{\pi^2}{ a} f \right) Hyperbolic secant is its own Fourier transform

Distributions


Signal Fourier transform
unitary, angular frequency
Fourier transform
unitary, ordinary frequency
Remarks

 g(t) \,  G(\omega)\!\ \stackrel{\mathrm{def}}{=}\ \!

\frac{1}{\sqrt{2 \pi}} \int_{-\infty}^{\infty}\!\!g(t) e^{-i \omega t}\, dt
 G(f)\!\ \stackrel{\mathrm{def}}{=}\

\int_{-\infty}^{\infty}\!\!g(t) e^{-i 2\pi f t}\, dt

301 1\, \sqrt{2\pi}\cdot \delta(\omega)\, \delta(f)\, \displaystyle\delta(\omega) denotes the Dirac delta distribution.
302 \delta(t)\, \frac{1}{\sqrt{2\pi}}\, 1\, Dual of rule 301.
303 e^{i a t}\, \sqrt{2 \pi}\cdot \delta(\omega - a)\, \delta(f - \frac{a}{2\pi})\, This follows from and 103 and 302.
304 \cos (a t)\, \sqrt{2 \pi} \frac{\delta(\omega\!-\!a)\!+\!\delta(\omega\!+\!a)}{2}\, \frac{\delta(f\!-\!\begin{matrix}\frac{a}{2\pi}\end{matrix})\!+\!\delta(f\!+\!\begin{matrix}\frac{a}{2\pi}\end{matrix})}{2}\, Follows from rules 101 and 303 using Euler's formula: \displaystyle\cos(a t) = (e^{i a t} + e^{-i a t})/2.
305 \sin( at)\, i \sqrt{2 \pi}\frac{\delta(\omega\!+\!a)\!-\!\delta(\omega\!-\!a)}{2}\, i \frac{\delta(f\!+\!\begin{matrix}\frac{a}{2\pi}\end{matrix})\!-\!\delta(f\!-\!\begin{matrix}\frac{a}{2\pi}\end{matrix})}{2}\, Also from 101 and 303 using \displaystyle\sin(a t) = (e^{i a t} - e^{-i a t})/(2i).
306 t^n\, i^n \sqrt{2\pi} \delta^{(n)} (\omega)\, \left(\frac{i}{2\pi}\right)^n \delta^{(n)} (f)\, Here, \displaystyle n is a natural number. \displaystyle\delta^n(\omega) is the \displaystyle n-th distribution derivative of the Dirac delta. This rule follows from rules 107 and 302. Combining this rule with 1, we can transform all polynomials.
307 \frac{1}{t}\, -i\sqrt{\frac{\pi}{2}}\sgn(\omega)\, -i\pi\cdot \sgn(f)\, Here \displaystyle\sgn(\omega) is the sign function; note that this is consistent with rules 107 and 302.
308 \frac{1}{t^n}\, -i \begin{matrix} \sqrt{\frac{\pi}{2}}\cdot \frac{(-i\omega)^{n-1}}{(n-1)!}\end{matrix} \sgn(\omega)\, -i\pi \begin{matrix} \frac{(-i 2\pi f)^{n-1}}{(n-1)!}\end{matrix} \sgn(f)\, Generalization of rule 307.
309 \sgn(t)\, \sqrt{\frac{2}{\pi}}\cdot \frac{1}{i\ \omega }\, \frac{1}{i\pi f}\, The dual of rule 307.
310  u(t) \, \sqrt{\frac{\pi}{2}} \left( \frac{1}{i \pi \omega} + \delta(\omega)\right)\, \frac{1}{2}\left(\frac{1}{i \pi f} + \delta(f)\right)\, Here u(t) is the Heaviside unit step function; this follows from rules 101 and 309.
311  e^{- a t} u(t) \, \frac{1}{\sqrt{2 \pi} (a + i \omega)} \frac{1}{a + i 2 \pi f} u(t) is the Heaviside unit step function and a > 0.
312 \sum_{n=-\infty}^{\infty} \delta (t - n T) \, \begin{matrix} \frac{\sqrt{2\pi }}{T}\end{matrix}  \sum_{k=-\infty}^{\infty} \delta \left( \omega -k \begin{matrix} \frac{2\pi }{T}\end{matrix} \right)\, \frac{1}{T} \sum_{k=-\infty}^{\infty} \delta \left( f -\frac{k }{T}\right) \, The Dirac comb — helpful for explaining or understanding the transition from continuous to discrete time.

Fourier transform properties

Notation: f(t) \quad \stackrel{\mathcal{F}}{\Longleftrightarrow}\quad F(\omega) denotes that f(t) and F(ω) are a Fourier transform pair.

Linearity
af_1(t) + bf_2(t) \quad \stackrel{\mathcal{F}}{\Longleftrightarrow}\quad aF_1(\omega) + bF_2(\omega)


Convolution
f_1(t) * f_2(t) \quad \stackrel{\mathcal{F}}{\Longleftrightarrow}\quad F_1(\omega)F_2(\omega)


Conjugation
\overline{f(t)} \quad \stackrel{\mathcal{F}}{\Longleftrightarrow}\quad \overline{F(-\omega)}


Scaling
 f(at) \quad \stackrel{\mathcal{F}}{\Longleftrightarrow}\quad \frac{1}{|a|}F\biggl(\frac{\omega}{a}\biggr), \qquad a \in \mathbb{R}, a \ne 0


Time reversal
f(-t) \quad \stackrel{\mathcal{F}}{\Longleftrightarrow}\quad F(-\omega)


Time shift
f(t-t_0) \quad \stackrel{\mathcal{F}}{\Longleftrightarrow}\quad e^{-i\omega t_0}F(\omega)


Modulation (multiplication by complex exponential)
f(t)\cdot e^{i\omega_{0}t} \quad \stackrel{\mathcal{F}}{\Longleftrightarrow}\quad F(\omega-\omega_{0})\qquad \omega_{0} \in \mathbb{R},


Multiplication by sin ω0t
f(t)\sin \omega_{0}t \quad \stackrel{\mathcal{F}}{\Longleftrightarrow}\quad \frac{i}{2}[F(\omega+\omega_{0})-F(\omega-\omega_{0})]\,


Multiplication by cos ω0t
f(t)\cos \omega_{0}t \quad \stackrel{\mathcal{F}}{\Longleftrightarrow}\quad \frac{1}{2}[F(\omega+\omega_{0})+F(\omega-\omega_{0})]\,


Integration
\int_{-\infty}^{t} f(u)\, du \quad \stackrel{\mathcal{F}}{\Longleftrightarrow}\quad \frac{1}{i\omega}F(\omega)+\pi F(0)\delta(\omega)\,


Parseval's theorem
\int_{\mathbb{R}} f(t)\cdot \overline{g(t)}\, dt = \int_{\mathbb{R}} F(\omega)\cdot \overline{G(\omega)}\, d\omega \,

No comments: