文档介绍：September 7, 2000
Fourier Transforms
1 Finite Fourier Transform
Any discussion of finite Fourier transforms and MATLAB immediately encoun-
ters a notational issue – we have to be careful about whether the subscripts start
at zero or one. The usual notation for finite Fourier transforms uses subscripts
j and k that run from 0 to n 1. MATLAB uses notation derived from matrix
−
theory where the subscripts run from 1 to n, so we will use yj+1 for mathemat-
ical quantities that will also occur in MATLAB code. We will reserve i for the
complex unit, √ 1.
The finite, or− discrete, Fourier transform of plex vector y with n ele-
ments y , j = 0, . . . n 1 is plex vector Y with n elements
j+1 −
n 1
− 2ijkπ/n
Y = y e−, k = 0, . . . , n 1
k+1 j+1 −
j=0
X
The exponentials are plex n-th roots of unity, . they are all powers of
2πi/n
ω= e−= cos δ i sin δ
−
where δ= 2π/n. The transform can also be expressed with matrix-vector
notation
Y = F y
where the finite Fourier transform matrix F has elements
jk
fk+1,j+1 = ω
It turns out that F is nearly its own inverse. More precisely, plex
conjugate transpose of F satisfies
F H F = nI
so
1 1 H
F −= F
n
This allows us to invert the Fourier transform.
1
y = F H Y
n
Hence
n 1
1 −
y = Y e2ijkπ/n, j = 0, . . . , n 1
j+1 n k+1 −
kX=0
1
We should point out that this is not the only notation for finite Fourier
transform mon use. The minus sign in plex exponentials in the
first equation, and in the definiton of ω, sometimes occurs in the inverse trans-
pose instead. And the 1/n scaling factor in the inverse transform is sometimes
replaced by 1/√n scaling factors in both transforms.
In MATLAB, the Fourier matrix F could be generated for any given n by
omega = exp(-2*pi*i/n);
j = 0:n-1;
k = j’
F = omega.^(k*j)
The quantity k*j is an outer product, an n-by-n matrix whose elements are the
products of the elements of two vectors. However, the built-in function fft
t