Links

The Fourier Transform

Continuous Time Fourier Transform

Definition 24

The Continuous Time Fourier Transform converts an aperiodic signal into the frequency domain.
X(ω)=x(t)ejωtdtX(\omega) = \int_{-\infty}^{\infty}{x(t)e^{-j\omega t}dt}
The intuition for this transform comes from the Fourier Series. Only periodic signals can be represented by the Fourier Series. If we start with a finite signal
x(t)x(t)
, then we can just make it periodic by copying the domain over which it is nonzero so it repeats over a period
TT
. Call this signal
x~(t)\tilde{x}(t)
. Since
x~\tilde{x}
is periodic, we can find its fourier series coefficients.
ak=1TTx~(t)ejn2πTt=1TTx(t)ejn2πTt=1Tx(t)ejn2πTta_k = \frac{1}{T}\int_{T}{\tilde{x}(t)e^{-jn\frac{2\pi}{T}t}} = \frac{1}{T}\int_{T}{x(t)e^{-jn\frac{2\pi}{T}t}} = \frac{1}{T}\int_{-\infty}^{\infty}{x(t)e^{-jn\frac{2\pi}{T}t}}
These steps are possible because
x~(t)=x(t)\tilde{x}(t) = x(t)
over a single period, and
x(t)x(t)
is zero outside that period.
Tak=x(t)ejn2πTtTa_k = \int_{-\infty}^{\infty}{x(t)e^{-jn\frac{2\pi}{T}t}}
Notice that if we let
TT
approach infinity, then
ω0=2πT\omega_0 = \frac{2\pi}{T}
becomes very small, so the
TakTa_k
can almost be thought of as samples of some continuous time function. What this means is for a general aperiodic signal, regardless of if it is finite or not, we can think of it as having "infinite period" and thus made up of a continuous set of frequencies. This is what motivates the CTFT.

Definition 25

The Inverse Continuous Time Fourier Transform takes us from the frequency domain reprsentation of a function
X(ω)X(\omega)
to its time domain representation
x(t)x(t)
x(t)=12πX(ω)ejωtdωx(t) = \frac{1}{2\pi}\int_{-\infty}^{\infty}{X(\omega)e^{j\omega t}d\omega}
We can arrive at this equation by starting from the Fourier series again. Our faux signal
x~(t)\tilde{x}(t)
which was the periodic function we constructed out of our aperiodic one is represented by its Fourier Series
x~(t)=kakejkω0t=k=(1TX(ω))ejωtw=kω0.\tilde{x}(t) = \sum_{k-\infty}^{\infty}{a_ke^{jk\omega_0t}} = \sum_{k=-\infty}^{\infty}{\left(\frac{1}{T}X(\omega)\right)e^{j\omega t}}|_{w=k\omega_0}.
Notice this is just rewriting
aka_k
as the samples of the Fourier Transform
X(ω)X(\omega)
.
T=2πω0T = \frac{2\pi}{\omega_0}
so
x~(t)=12πk=ω0X(ω)ejωtw=kω0\tilde{x}(t) = \frac{1}{2\pi} \sum_{k=-\infty}^{\infty}{\omega_0X(\omega)e^{j\omega t}}|_{w=k\omega_0}
x(t)=limTx~(t)=limω00x~(t)=12πX(ω)ejωtdω.x(t) = \lim_{T\to\infty}{\tilde{x}(t)} = \lim_{\omega_0\to0}{\tilde{x}(t)} = \frac{1}{2\pi}\int_{-\infty}^{\infty}{X(\omega)e^{j\omega t}d\omega}.

Properties of the CTFT

For all these properties, assume that
x(t)X(ω)x(t) \leftrightarrow X(\omega)
and
y(t)Y(ω)y(t) \leftrightarrow Y(\omega)
Linearity:
ax(t)+by(t)aX(ω)+bY(ω)ax(t) + by(t) \leftrightarrow aX(\omega) + bY(\omega)
Time Shift:
x(tt0)ejωt0X(ω)x(t-t_0) \leftrightarrow e^{-j\omega t_0}X(\omega)
Time/Frequency Scaling:
x(at)1aX(ωa)x(at) \leftrightarrow \frac{1}{|a|}X(\frac{\omega}{a})
Conjugation:
x(t)X(ω)x^*(t) \leftrightarrow X^*(-\omega)
Derivative:
ddtx(t)jωX(ω),ddωX(ω)jtx(t)\frac{d}{dt}x(t) \leftrightarrow j\omega X(\omega), \frac{d}{d\omega}X(\omega) \leftrightarrow -jt x(t)
Convolution/Multiplication:
(xy)(t)X(ω)Y(ω),x(t)y(t)12π(XY)(ω)(x*y)(t) \leftrightarrow X(\omega)Y(\omega), x(t)y(t) \leftrightarrow \frac{1}{2\pi}(X*Y)(\omega)
Frequency Shift:
ejω0tx(t)X(ωω0)e^{j\omega_0 t}x(t) \leftrightarrow X(\omega - \omega_0)
Parsevals Theorem:
x(t)2dt=12πX(ω)2dω\int_{-\infty}^{\infty}{|x(t)|^2dt} = \frac{1}{2\pi}\int_{-\infty}^{\infty}{|X(\omega)|^2d\omega}

Convergence of the CTFT

A big question that arises when thinking about the Fourier Transform is whether or not the integral
x(t)ejωt\int{x(t)e^{-j\omega t}}
actually converges.

Theorem 5

If
x(t)dt\int_{-\infty}^{\infty}{|x(t)|dt}
converges, then
X(ω)X(\omega)
exists and is continuous. In addition,
X(ω)X(\omega)
approaches 0 as
ω|\omega|
approaches
\infty
.
Conceptually, this theorem makes sense because
x(t)ejωt=x(t)ejωt=x(t).|x(t)e{-j\omega t}| = |x(t)| |e^{-j\omega t}| = |x(t)|.
So if one converges, the other must converge. However, this means that
x(t)=1x(t)=1
,
x(t)=sin(ωt)x(t)=\sin(\omega t)
,
x(t)=cos(ωt)x(t)=\cos(\omega t)
don’t have a "strict" Fourier Series because the integral doesn’t converge for these periodic signals. In order to get around this, we can define a "generalized" Fourier Transform which operates on periodic signals.
Starting with
x(t)=1x(t)=1
, we know that in the frequency domain, the only consituent frequency is
ω=0\omega=0
. This means that
X(ω)=kδ(ω)X(\omega) = k\delta(\omega)
where
kk
is some scalar. Using the Inverse Fourier Transform,
x(t)=12πkδ(ω)ejωtdω=k2π.x(t) = \frac{1}{2\pi}\int{k\delta(\omega)e^{j\omega t}d\omega} = \frac{k}{2\pi}.
That means
k=2πk = 2\pi
, so
x(t)=1X(ω)=2πδ(ω).x(t) = 1 \leftrightarrow X(\omega) = 2\pi \delta(\omega).
Now if we apply the frequency shift property, we see that
x(t)=ejω0t=2πδ(ωω0).x(t) = e^{j\omega_0 t} = 2\pi \delta(\omega - \omega_0).
With this, we can define our generalized Fourier Transform for periodic signals.

Definition 26

The generalized Fourier Transform for a periodic signal
x(t)x(t)
is
X(ω)=ak2πδ(ωω0)X(\omega) = \sum_{-\infty}^{\infty}{a_k\cdot 2\pi \delta(\omega - \omega_0)}
where
aka_k
are the coefficients of the Fourier Series of
x(t)x(t)
.
This definition works because any periodic signal can be represented by its Fourier Series. The rational behind using the Dirac Delta in this generalized Fourier Transform is exlained by the Theory of Distributions which can be found in Appendix.

Discrete Time Fourier Transform

Definition 27

The Discrete Time Fourier Transform converts aperiodic discrete signals into the frequency domain.
X(ω)=x[n]ejωnX(\omega) = \sum_{-\infty}^{\infty}{x[n]e^{-j\omega n}}
The intution for the Discrete Time Fourier Transform is more or less the same as that of the Continuous Time Fourier Transform.

Definition 28

The Inverse Discrete Time Fourier Transform converts the frequency domain representation of a signal back into its time domain representation.
x[n]=12π<2π>X(ω)ejωndωx[n] = \frac{1}{2\pi}\int_{<2\pi>}{X(\omega)e^{j\omega n}d\omega}

Properties of the DTFT

For all these properties, assume that
x[n]X(ω)x[n] \leftrightarrow X(\omega)
and
y[n](ω)y[n]\leftrightarrow (\omega)
Time Shift:
x[nn0]ejωn0X(ω)x[n-n_0] \leftrightarrow e^{-j\omega n_0}X(\omega)
Frequency Shift:
X(ωω0)ejω0nx[n]X(\omega - \omega_0) \leftrightarrow e^{j\omega_0 n}x[n]
Time Reversal:
x[n]X(ω)x[-n] \leftrightarrow X(-\omega)
Conjugation:
x[n]=X(ω)x^*[n] = X^*(-\omega)
Time Expansion: In discrete time, compression of a signal doesn’t make sense because we can’t have partial steps (i.e n must be an integer). However, we can stretch a signal.
xM[n]X(Mω),xM[n]={x[nM]when nmodM=00else.x_M[n] \leftrightarrow X(M\omega), x_M[n] = \begin{cases} x\left[\frac{n}{M}\right] & \text{when } n \mod M = 0\\ 0 & \text{else.} \end{cases}
Derivative Property:
nx[n]jddωX(ω)nx[n] \leftrightarrow j \frac{d}{d\omega}X(\omega)
Multiplication Property:
x[n]y[n]12π2πX(θ)Y(ωθ)dθx[n]y[n] \leftrightarrow \frac{1}{2\pi}\int_{2\pi}{X(\theta)Y(\omega-\theta)d\theta}
Convolution Property:
(xy)[n]=X(ω)Y(ω)(x*y)[n] = X(\omega)Y(\omega)

Convergence of the DTFT

Just like in continuous time, it was unclear whether or not the integral would converge, in discrete time, it is unclear if the infinite sum will converge. The convergence theorem for both are essentially the same.

Theorem 6

If
x[n]\sum_{-\infty}^{\infty}{|x[n]|}
converges, then
X(ω)X(\omega)
exists and is continuous.
Just like in continuous time, periodic signals like
x[n]=1,x[n]=sin(ω0t),x[n]=cos(ω0t)...x[n] = 1, x[n] = sin(\omega_0t), x[n]=cos(\omega_0t)...
are problematic because they don’t converge under the "strict" transform, so they require a generalized transform. In the frequency domain, a constant signal like
x[n]=1x[n] = 1
will be the sum of all frequencies. This will look like a sum of Dirac Deltas
X(ω)=kl=δ(ω2πl).X(\omega) = k \sum_{l=-\infty}^{\infty}{\delta(\omega - 2\pi l)}.
Applying the synthesis equation to this, we get
x(t)=12π2πkl=δ(ω2πl)=k2πl=2πδ(ω2πl)=k2π2πδ(ω2π0)=k2π.x(t) = \frac{1}{2\pi}\int_{2\pi}{k \sum_{l=-\infty}^{\infty}{\delta(\omega - 2\pi l)}} = \frac{k}{2\pi}\sum_{l=-\infty}^{\infty}{\int_{2\pi}{\delta(\omega - 2\pi l)}} = \frac{k}{2\pi}\int_{2\pi}{\delta(\omega - 2\pi \cdot 0)} = \frac{k}{2\pi}.
Therefore
k=2πk = 2\pi
, so
x[n]=1X(ω)=2πl=δ(ω2πl)x[n] = 1 \leftrightarrow X(\omega) = 2\pi\sum_{l=-\infty}^{\infty}{\delta(\omega - 2\pi l)}
and we can apply the frequency shift property to get
x[n]=ejω0nX(ω)=2πl=δ(ωω02πl).x[n] = e^{j\omega_0n} \leftrightarrow X(\omega) = 2\pi\sum_{l=-\infty}^{\infty}{\delta(\omega - \omega_0 - 2\pi l)}.
Once again using the Fourier Series representation of
x[n]x[n]
, we can define the generalized Discrete Time Fourier Transform.

Definition 29

For a perioidic signal
x[n]x[n]
, the generalized Discrete Time Fourier Transform is
x[n]2πakδ(ω2πNk)x[n] \leftrightarrow 2\pi\sum_{-\infty}^{\infty}{a_k\delta\left(\omega-\frac{2\pi}{N}k\right)}
where
aka_k
are the Fourier Series coefficients of
x[n]x[n]

Discrete Fourier Transform

Whereas the CTFT takes a continuous signal and outputs a continuous frequency spectrum and the DTFT takes a discrete signal and outputs a continuous, periodic frequecy spectrum, the Discrete Fourier Transform takes a discrete periodic signal and outputs a discrete frequency spectrum.

Definition 30

For a length
NN
finite sequence
{x[n]}0n1\{x[n]\}^{n-1}_{0}
, the Discrete Fourier Transform of the signal is a length N finite sequence
{X[k]}0n1\{X[k]\}^{n-1}_{0}
where
X[k]=n=0N1x[n]ej2πNkn.X[k] = \sum_{n=0}^{N-1}{x[n]e^{-j\frac{2\pi}{N}kn}}.
One way to interpret the DFT is in terms of the Fourier series for a disrete periodic signal
x~[n]=x[n mod N]\tilde{x}[n]=x[n\text{ mod N}]
. Recall that the coefficient of the kth term of the Fourier Series is
ak=1Nn=0N1x[n]ej2πNkn.a_k = \frac{1}{N}\sum_{n=0}^{N-1}{x[n]e^{-j\frac{2\pi}{N}kn}}.
Notice that the
aka_k
of the Fourier Series are the DFT values except scaled by a factor of
NN
. This gives an intuitive inverse DFT.

Definition 31

For a length N finite sequence
{X[k]}0N1\{X[k]\}^{N-1}_{0}
representing the DFT of a finite perioidc signal
{x[n]}0N1\{x[n]\}^{N-1}_{0}
, the inverse DFT is given by
x[n]=1Nk=0N1X[k]ej2πNkn.x[n] = \frac{1}{N}\sum_{k=0}^{N-1}{X[k]e^{j\frac{2\pi}{N}kn}}.
One important property of the DFT is its complex conjugacy. When
x[n]x[n]
is a real valued signal, then
X[nk]=X[k]X[n-k]=X[k]^*
. This can easily be shown by substituting
NkN-k
into the DFT formula. Further intuition for the DFT comes from relating it to the DTFT. Suppose we have a finite signal
x[n]x[n]
which is
00
for
n<0n < 0
and
n>N1n > N-1
. The DTFT of this signal is
X(ω)=n=x[n]ejωn=n=0N1x[n]ejωn.X(\omega) = \sum_{n=-\infty}^{\infty}{x[n]e^{-j\omega n}} = \sum_{n=0}^{N-1}{x[n]e^{-j\omega n}}.
Suppose we sample the DTFT at intervals of
2πNk\frac{2\pi}{N}k
, then
X[k]=X(2πNk)=n=0N1x[n]ej2πNkn.X[k] = X\left(\frac{2\pi}{N}k\right) = \sum_{n=0}^{N-1}{x[n]e^{-j\frac{2\pi}{N}k n}}.
Thus we can think of the DFT as a
NN
point sample of the DTFT.

2D Fourier Transforms

So far, our Fourier Transforms have been limited to signals of a single dimension. However, in the real world, signals might be multidimensional (think images). Thankfully, each of the Fourier Transforms generalizes easily into higher dimensions.\
2D CTFT: X(ω1,ω2)=x(t1,t2)ejω0tejω1tdt1dt2\textbf{2D CTFT: }X(\omega_1, \omega_2) = \int_{-\infty}^{\infty}\int_{-\infty}^{\infty}{x(t_1, t_2)e^{-j\omega_0t}e^{-j\omega_1t}dt_1dt_2}
Inverse 2D CTFT: x(t1,t2)=1(2π)2X(ω1,ω2)ejω1t1ejω2t2dω1dω2\textbf{Inverse 2D CTFT: }x(t_1, t_2) = \frac{1}{(2\pi)^2}\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}{X(\omega_1, \omega_2)e^{j\omega_1t_1}e^{j\omega_2t_2}d\omega_1d\omega_2}
2D DTFT: X(ω1,ω2)=n2=n1=x[n1,n2]ejω1n1ejω2n2\textbf{2D DTFT: }X(\omega_1, \omega_2) = \sum_{n_2=-\infty}^{\infty}\sum_{n_1=-\infty}^{\infty}{x[n_1,n_2]e^{-j\omega_1n_1}e^{-j\omega_2n_2}}
Inverse 2D DTFT: x[n1,n2]=ω2=ω1=X(ω1,ω2)ejω1n1ejω2n2\textbf{Inverse 2D DTFT: }x[n_1, n_2] = \sum_{\omega_2=-\infty}^{\infty}\sum_{\omega_1=-\infty}^{\infty}{X(\omega_1,\omega_2)e^{j\omega_1n_1}e^{j\omega_2n_2}}
2D DFT: X[k1,k2]=n2=0N21n1=0N11x[n1,n2]ej2πN1k1n1ej2πN2k2n2\textbf{2D DFT: }X[k_1, k_2] = \sum_{n_2=0}^{N_2-1}\sum_{n_1=0}^{N_1-1}{x[n_1, n_2]e^{-j\frac{2\pi}{N_1}k_1 n_1}e^{-j\frac{2\pi}{N_2}k_2 n_2}}
2D DFT: x[n1,n2]=k2=0N21k1=0N11X[k1,k2]ej2πN1k1n1ej2πN2k2n2\textbf{2D DFT: }x[n_1, n_2] = \sum_{k_2=0}^{N_2-1}\sum_{k_1=0}^{N_1-1}{X[k_1, k_2]e^{j\frac{2\pi}{N_1}k_1 n_1}e^{j\frac{2\pi}{N_2}k_2 n_2}}
Just like in 1 dimension, absolute summability/integrability guarantee the convergence of these transforms. It turns out that when a 2D signal is simply a multiplication of two 1D signals, the Fourier Transforms are very easy to compute.

Theorem 7

If
x(t1,t2)=x(t1)x(t2)x(t_1, t_2) = x(t_1)x(t_2)
, then
X(ω1,ω2)=X(ω1)X(ω2)X(\omega_1, \omega_2) = X(\omega_1)X(\omega_2)