Next: Two-Dimensional Fourier Transform Up: Fourier_Analysis Previous: Four Forms of Fourier

# Numerical Implementation of DFT

• 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 in tabular form:

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 . Also note that is symmetric.

In general, any matrix satisfying is called a unitary matrix. In particular, if a real unitary matrix satisfying is called an orthogonal matrix. Any such unitary or orthogonal matrix can be used to define a unitary or orthogonal transform:

• Fast Fourier Transform

The number of operations (multiplications and additions) needed for computing each of the frequency components is proportional to , i.e., the computational complexity of an N-point DFT is . However, there exists a fast algorithm due to the properties of the DFT matrix . Specifically, based on the following three properties of :

a Fast Fourier Transform (FFT) of complexity can be derived (refer to problem 5.54 of OWN or this page for details). It is this major improvement of computational complexity that makes Fourier transform practically possible in many applications.

• Example 1

Consider a discrete signal of real values (imaginary components are 0):

The forward discrete Fourier transform is:

or

The inverse transform is:

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

• Example 2

Consider a discrete signal of N=60 samples:

The two sinusoids have frequencies and representing, respectively, 22 and 6 cycles per period of points.

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

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 represent all frequency components. The DC component is on the left, the highest frequency component 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 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, this shift in frequency domain can be equivalently implemented in time domain. Consider the inverse transform of this shifted spectrum :

i.e., if we change the sign of every other time sample, the corresponding Fourier spectrum will be centralized with DC component in the middle.

Next: Two-Dimensional Fourier Transform Up: Fourier_Analysis Previous: Four Forms of Fourier
Ruye Wang 2003-11-17