Discrete Fourier Transform

Abu Saleh Musa Miah

Assistant Professor,
Dept. of CSE, BAUST, Bangladesh
email: musa@baust.edu.bd, tel: +8801734264899
web: www.baust.edu.bd/cse
 Frequency-Domain Sampling and Reconstruction of
Discrete-Time Signals

 The discrete Fourier transform (DFT) is one of the two most common, and powerful, procedures
encountered in the field of digital signal processing. (Digital filtering is the other.)

 The DFT enables us to analyze, manipulate, and synthesize signals in ways not possible with
continuous (analog) signal processing.

  The DFT's origin, of course, is the continuous Fourier transform X(f) defined as

 where x(t) is some continuous time-domain signal.[]

With the advent of the digital computer, the efforts of early digital processing pioneers led to the
development of the DFT defined as the discrete frequency-domain sequence X(m), where
 Under Standing the DFT Equation

From Euler's relationship e–jø = cos(ø) –jsin(ø), Eq. (3-2) is equivalent to

We have separated the complex exponential of Eq. (3-2) into its real and imaginary
components where

X(m) = the mth DFT output component, i.e., X(0), X(1), X(2), X(3), etc.,

m = the index of the DFT output in the frequency domain,

m = 0, 1, 2, 3, . . ., N–1,
x(n) = the sequence of input samples, x(0), x(1), x(2), x(3), etc.,

n = the time-domain index of the input samples, n = 0, 1, 2, 3, . . ., N–1,

j = ,
N = the number of samples of the input sequence and the number of frequency points in
the DFT output.
 Under Standing the DFT Equation

It's useful to see the structure of Eq. (3-3) by eliminating the summation and writing out all
the terms. For example, when N = 4, n and m both go from 0 to 3, and Eq. (3-3) becomes

Writing out all the terms for the first DFT output term corresponding to m = 0,

For the second DFT output term corresponding to m = 1, Eq. (3-4a) becomes
 Under Standing the DFT Equation
For the third output term corresponding to m = 2, Eq. (3-4a) becomes

Finally, for the fourth and last output term corresponding to m = 3, Eq. (3-
4a) becomes
The Discrete Fourier Transform (DFT)
 Each X(m) DFT output term is the sum of the point for point product between an
input sequence of signal values and a complex sinusoid of the form cos(ø) –
jsin(ø).
 The exact frequencies of the different sinusoids depend on both the sampling rate
fs, at which the original signal was sampled, and the number of samples N.
 For example, if we are sampling a continuous signal at a rate of 500 samples/s
and, then, perform a 16-point DFT on the sampled data,
 the fundamental frequency of the sinusoids is fs/N = 500/16
 or 31.25 Hz. The other X(m) analysis frequencies are integral multiples of the
fundamental frequency,
X(0) = 1st frequency term, with analysis frequency = 0 · 31.25 = 0 Hz,

X(1) = 2nd frequency term, with analysis frequency = 1 · 31.25 = 31.25 Hz,

X(2) = 3rd frequency term, with analysis frequency = 2 · 31.25 = 62.5 Hz,

X(3) = 4th frequency term, with analysis frequency = 3 · 31.25 = 93.75 Hz,

    ...
X(15) = 16th frequency term, with analysis frequency = 15 · 31.25 = 468.75 Hz.
Frequency Axis of DFT X(m)
 The N separate DFT analysis frequencies are

 So, in this example, the X(0)

 DFT term tells us the magnitude of any 0-Hz ("DC") component
contained in the input signal,
 the X(1) term specifies the magnitude of any 31.25-Hz component in
the input signal, and
 the X(2) term indicates the magnitude of any 62.5-Hz component in
the input signal, etc.

 Moreover, as we'll soon show by example, the DFT output terms also
determine the phase relationship between the various analysis
frequencies contained in an input signal.
The Discrete Fourier Transform (DFT)
 the magnitude and the power (magnitude squared) contained in
each X(m) term, and the standard definitions for right triangles
apply here as depicted in Figure.

 If we represent an arbitrary DFT output value, X(m), by its real and

imaginary parts
The Discrete Fourier Transform (DFT)

the magnitude of X(m) is

By definition, the phase angle of X(m), Xø(m), is

The power of X(m), referred to as the power spectrum, is the magnitude

squared where
DFT Example
Let's say we want to sample and perform an 8-point DFT on a continuous
input signal containing components at 1 kHz and 2 kHz, expressed as

 To make our example input signal xin(t) a little more interesting, we have
the 2-kHz term shifted in phase by 135° (3p/4 radians) relative to the 1-kHz
sine wave.
 With a sample rate of fs, we sample the input every 1/fs = ts seconds.

 Because N = 8, we need 8 input sample values on which to perform the DFT.

 So the 8-element sequence x(n) is equal to xin(t) sampled at the nts instants
in time so that

If we choose to sample xin(t) at a rate of fs = 8000 samples/s from Eq. (3-5),

our DFT results will indicate what signal amplitude exists in x(n) at the analysis
frequencies of mfs/N, or 0 kHz, 1 kHz, 2 kHz, . . ., 7 kHz. With fs = 8000
samples/s, our eight x(n) samples are
DFT Example

Now we're ready to apply Eq. (3-3) to determine the DFT of our x(n) input. We'll start with m =
1 because the m = 0 case leads to a special result that we'll discuss shortly. So, for m = 1, or the
1-kHz (mfs/N = 1·8000/8) DFT frequency term, Eq. (3-3) for this example becomes

x[n]=[0.35,0.707,0.64,0.207,-0.353,-0.707,-0.646,-0.207]
 to determine the DFT Example
DFT of our x(n)
input. We start   m=1 X(1)=
with m=1

 because the
m=0 case leads
to a special
result that we'll
discuss shortly.

 So, for m = 1, or
1-kHz

 (mfs/N=1·8000
/8)
 we correlate x(n)
with a 1 kHz
cosine wave and
a 1 kHz
sinewave
 DFT Example
  m=2 X(2)=
  So, for m = 2, or
2-kHz

 (=2·8000/8=2)

 we correlate x(n)
with a 2 kHz
cosine wave and
a 2 kHz
sinewave

Here our input x(n) contains a signal at a frequency of 2 kHz whose relative
amplitude is 2, and whose phase angle relative to a 2 kHz cosine is 45°.
 DFT Example
  m=3 X(3)=
  So, for m = 3, or
3-kHz

 (=3·8000/8=3)

 we correlate x(n)
with a 3 kHz
cosine wave and
a 3 kHz
sinewave
 DFT Example
  m=4 X(4)=
  So, for m = 4, or
3-kHz

 (=4·8000/8=3)

 we correlate x(n)
with a 4 kHz
cosine wave and
a 3 kHz
sinewave
 DFT Example
  m=5 X(5)=
  So, for m = 4, or
3-kHz

 (=4·8000/8=3)

 we correlate x(n)
with a 4 kHz
cosine wave and
a 3 kHz
sinewave
 DFT Example
  m=6 X(6)=
  So, for m = 4, or
3-kHz

 (=4·8000/8=3)

 we correlate x(n)
with a 4 kHz
cosine wave and
a 3 kHz
sinewave
 DFT Example
  m=6 X(7)=
  So, for m = 4, or
3-kHz

 (=4·8000/8=3)

 we correlate x(n)
with a 4 kHz
cosine wave and
a 3 kHz
sinewave
 DFT Example

Figure 3-4 DFT results from Example 1: (a) magnitude of X(m); (b) phase of
X(m); (c) real part of X(m); (d) imaginary part of X(m).
 DFT Example

Because cos(0) = 1, and sin(0) = 0,

 DFT Symmetry

 When the input sequence x(n) is real, as it will be for all of our example
 the complex DFT outputs for m = 1 to m = (N/2) − 1
 are redundant with frequency output values for m > (N/2).
 mth DFT output will have the same magnitude as the (N−m)th DFT out
 The phase angle of the DFT’s mth output is the negative of the
 phase angle of the (N−m)th DFT output.
 So the mth and (N−m)th outputs are related

for 1 ≤ m ≤ (N/2)−1. We can state that when the DFT input sequence is real,
X(m) is the complex conjugate of X(N−m), or
DFT Symmetry
 DFT Linearity
  The DFT has a very important property known as linearity.
 DFT of the sum of two signals is equal to the sum of the transforms of each signal;
 if an input sequence x1(n) has a DFT X1(m) and another input sequence x2(n) has a DFT
X2(m),
 then the DFT of the sum of these sequences
 Inverse DFT
 DFT as transforming time-domain data into a frequency-domain
representation.
 we can reverse this process and obtain the original time-domain
signal by performing the IDFT on the X(m) frequency-domain values.
 The standard expressions for the IDFT are

Example 1 into Eq. (3-23), we’ll go

from the frequency domain back to
the time domain and get our
original real Eq. (3-11′) x(n) sample
values of
 DFT Leakage

 Engineers often refer to DFT samples as “bins.”

 DFTs are constrained to operate on a finite set of N input values,

 if the input has a signal component at some intermediate frequency

between our analytical frequencies of mfs/N,

 say 1.5fs/N, this input signal will show up to some degree in all of the N
output analysis frequencies of our DFT! energy shows up in all of the
DFT’s output bins,
DFT Leakage

Figure 3-7 Sixty-four-point DFT: (a) input sequence of three cycles and the m =
4 analysis frequency sinusoid; (b) DFT output magnitude.
DFT Leakage

Sixty-four-point DFT: (a) 3.4 cycles input sequence and the m = 4 analysis
frequency sinusoid; (b) DFT output magnitude.
DFT Leakage and Sinc Function

where Ao is the peak value of the DFT’s input sinusoid. For our examples here, Ao is unity
DFT Leakage and Sinc Function

illustrate again what happens when the input frequency k is not located at a bin center.

Assume that a real 8 kHz sinusoid, having unity amplitude,

has been sampled at a rate of fs = 32000 samples/second.
If we take a 32-point DFT of the samples,

the DFT’s frequency resolution, or bin spacing, is fs/N = 32000/32 Hz = 1.0 kHz.
DFT Leakage and Sinc Function
illustrate again what happens when the input frequency k is not located at a bin center.
 Assume that a real 8 kHz sinusoid, having unity amplitude,
has been sampled at a rate of fs = 32000 samples/second.
If we take a 32-point DFT of the samples,
the DFT’s frequency resolution, or bin spacing, is fs/N = 32000/32 Hz = 1.0 kHz.

Figure DFT bin positive-frequency responses: (a) DFT input frequency = 8.0 kH

(b) DFT input frequency = 8.5 kHz;

DFT Leakage and Sinc Function

(c) DFT input frequency = 8.75 kHz.

DFT Leakage

Sixty-four-point DFT: (a) 3.4 cycles input sequence and the m = 4 analysis
frequency sinusoid; (b) DFT output magnitude.
Windows
Windows
Windows
Windows