DFT Computation
[Link]
next
previous
Next: Fast Fourier Transform Up: Image_Processing Previous: Four Forms of Fourier
DFT Computation
Vector Form of DFT Consider an N by N matrix with its (m,n)th element defined as:
where
Now the DFT can be written as (Eq. P5.54-2):
or
or in matrix form:
where and are N by 1 column (vertical) vectors representing the signal in time and frequency domain, respectively. Similarly, the inverse transform DFT can be written as
or in matrix form:
where
is the complex conjugate of
. Left multiplying
on both sides, we get
i.e.,
, or satisfying
. Also note that
is symmetric.
In general, any matrix
is called a unitary matrix. In particular, if a real unitary matrix
1 of 6
16-04-2012 21:02
DFT Computation
[Link]
satisfying is called an orthogonal matrix. Any such unitary or orthogonal matrix define a unitary or orthogonal transform:
can be used to
C Code for DFT:
for (n=0; n<N; n++) { Xr[n]=Xi[n]=0; for (m=0; m<N; m++) { w=2*pi*m*n/N; if (forward) w=-w; wr=cos(w); wi=sin(w); Xr[n]=Xr[n]+wr*xr[m]-wi*xi[m]; Xi[n]=Xi[n]+wr*xi[m]+wi*xr[m]; } Xr[n]=Xr[n]/sqrt(N); Xi[n]=Xi[n]/sqrt(N); }
Example 1 Consider a discrete signal of real values (imaginary components are 0):
The forward discrete Fourier transform is:
or
The inverse transform is:
2 of 6
16-04-2012 21:02
DFT Computation
[Link]
or
To represent this transform in matrix forms
, we find
and get
Note that the above matrix multiplication is a complex operation, and the product of two complex numbers is defined as
3 of 6
16-04-2012 21:02
DFT Computation
[Link]
Example 2 Consider a discrete signal of N=60 samples:
The two sinusoids have frequencies points.
and
representing, respectively, 22 and 6 cycles per period of
By DFT, the spectrum of the signal can be found as shown below.
In particular,
is the DC component, and the two real peaks
and
represent the cosine function
4 of 6
16-04-2012 21:02
DFT Computation
[Link]
and the two imaginary peaks
and
represent the sine function
In general, the spectrum
of a real signal
has the following properties:
is the average or DC component of the signal:
is the difference between the even components and odd components:
and
are always zero:
For
, the real part of
is even symmetric and the imaginary part of
is odd symmetric:
Spectrum Centralization In the spectrum of the example above, the N values DC component is on the left, the highest frequency component represent all frequency components. The is in the middle (not on the right!), while the
low frequency components are close to the two ends. Alternatively, it we want the DC component in the middle and the
5 of 6
16-04-2012 21:02
DFT Computation
[Link]
higher components close to the two ends, we can centralize the spectrum by shifting it to either left or right by
According to the shift property of the Fourier transform:
When
, we have
i.e., by changing the sign of all time samples with an odd index ( with DC component in the middle.
), the corresponding spectrum will be centralized
next
previous
Next: Fast Fourier Transform Up: Image_Processing Previous: Four Forms of Fourier Ruye Wang 2007-11-15
6 of 6
16-04-2012 21:02
