6Fourier transforms
IB Methods
6.8 The discrete Fourier transform
Recall that the Fourier transform is defined as
˜
f(k) =
Z
R
e
−ikx
f(x) dx.
To find the Fourier transform, we have to know how to perform the integral. If
we cannot do the integral, then we cannot do the Fourier transform. However,
it is usually difficult to perform integrals for even slightly more complicated
functions.
A more serious problem is that we usually don’t even have a closed form of
the function
f
for us to perform the integral. In real life,
f
might be some radio
signal, and we are just given some data of what value
f
takes at different points..
There is no hope that we can do the integral exactly.
Hence, we first give ourselves a simplifying assumption. We suppose that
f
is mostly concentrated in some finite region [
−R, S
]. More precisely,
|f
(
x
)
|
1
for x 6∈ [−R, S] for some R, S > 0. Then we can approximate our integral as
˜
f(k) =
Z
S
−R
e
−ikx
f(x) dx.
Afterwards, we perform the integral numerically. Suppose we “sample”
f
(
x
) at
x = x
j
= −R + j
R + S
N
for N a large integer and j = 0, 1, ··· , N − 1. Then
˜
f(k) ≈
R + S
N
N−1
X
j=0
f(x
j
)e
−ikx
j
.
This is just the Riemann sum.
Similarly, our computer can only store the result
˜
f
(
k
) for some finite list of
k. Let’s choose these to be at
k = k
m
=
2πm
R + S
.
Then after some cancellation,
˜
f(k
m
) ≈
R + S
N
e
2πimR
R+S
N−1
X
j=0
f(x
j
)e
2πi
N
jm
= (R + S)e
2πimR
R+S
1
N
N−1
X
j=0
f(x
j
)ω
−jm
,
where
ω = e
2πi
N
is an Nth root of unity. We call the thing in the brackets
F (m) =
1
N
N−1
X
j=0
f(x
j
)ω
−jm
.
Of course, we’ve thrown away lots of information about our original function
f
(
x
), since we made approximations all over the place. For example, we have
already lost all knowledge of structures varying more rapidly than our sampling
interval
R+S
N
. Also,
F
(
m
+
N
) =
F
(
m
), since
ω
N
= 1. So we have “forced” some
periodicity into our function F , while
˜
f(k) itself was not necessarily periodic.
For the usual Fourier transform, we were able to re-construct our original
function from the
˜
f
(
k
), but here we clearly cannot. However, if we know the
F
(
m
) for all
m
= 0
,
1
, ··· , N −
1, then we can reconstruct the exact values of
f
(
x
j
) for all
j
by just solving linear equations. To make this more precise, we
want to put what we’re doing into the linear algebra framework we’ve been using.
Let
G
=
{
1
, ω, ω
2
, ··· , ω
N−1
}
. For our purposes below, we can just treat this as
a discrete set, and
ω
i
are just meaningless symbols that happen to visually look
like the powers of our Nth roots of unity.
Consider a function g : G → C defined by
g(ω
j
) = f(x
j
).
This is actually nothing but just a new notation for
f
(
x
j
). Then using this new
notation, we have
F (m) =
1
N
N−1
X
j=0
ω
−jm
g(ω
j
).
The space of all functions
g
:
G → C
is a finite-dimensional vector space,
isomorphic to C
N
. This has an inner product
(f, g) =
1
N
N−1
X
j=0
f
∗
(ω
j
)g(ω
j
).
This inner product obeys
(g, f) = (f, g)
∗
(f, c
1
g
1
+ c
2
g
2
) = c
1
(f, g
1
) + c
2
(f, g
2
)
(f, f) ≥ 0 with equality iff f(ω
j
) = 0
Now let e
n
: G → C be the function
e
m
(ω
j
) = ω
jm
.
Then the set of functions
{e
m
}
for
m
= 0
, ··· , N −
1 is an orthonormal basis
with respect to our inner product. To show this, we can compute
(e
m
, e
m
) =
1
N
N−1
X
j=0
e
∗
m
(ω
j
)e
m
(ω
j
)
=
1
N
N−1
X
j=0
ω
−jm
ω
jm
=
1
N
N−1
X
j=0
1
= 1.
For n 6= m, we have
(e
n
, e
m
) =
1
N
N−1
X
j=0
e
∗
n
(ω
j
)e
m
(ω
j
)
=
1
N
N−1
X
j=0
ω
j(m−n)
=
1
N
1 − ω
(m−n)N
1 − ω
m−n
.
Since
m−n
is an integer and
ω
is an
N
th root of unity, we know that
ω
(m−n)N
= 1.
So the numerator is 0. However, since
n 6
=
m
,
m −n 6
= 0. So the denominator is
non-zero. So we get 0. Hence
(e
n
, e
m
) = 0.
We can now rewrite our F (m) as
F (m) =
1
N
N−1
X
j=0
ω
−jm
f(x
j
) =
1
N
N−1
X
j=0
e
∗
m
(ω
j
)g(ω
j
) = (e
m
, g).
Hence we can expand our g as
g =
N−1
X
m=0
(e
m
, g)e
m
=
N−1
X
m=0
F (m)e
m
.
Writing f instead of g, we recover the formula
f(x
j
) = g(ω
j
) =
N−1
X
m=0
F (m)e
m
(ω
j
).
If we forget about our
f
s and just look at the
g
, what we have effectively done is
take the Fourier transform of functions taking values on
G
=
{
1
, ω, ··· , ω
N−1
}
∼
=
Z
N
.
This is exactly analogous to what we did for the Fourier transform, except
that everything is now discrete, and we don’t have to worry about convergence
since these are finite sums.