Discrete Fourier Transform and

Signal Spectrum
 Discrete Fourier Transform
• signal spectrum:
representation of the digital
signal in terms of its
frequency component in a
frequency domain. Hence, the
spectral plot better displays
frequency information of a
digital signal.
• discrete Fourier transform
(DFT): The algorithm
transforming the time domain
signal samples to the
frequency domain
components.
• The DFT is widely used in
many other areas, including
spectral analysis, acoustics,
imaging/ video, audio,
instrumentation, and
communications systems. A 1,000-Hz sinusoid with 32 samples at a sampling
rate of 8,000 Hz.
Fourier Series Coefficients of Periodic Digital Signals
• Consider a periodic digital signal x(t) sampled at a rate of fs Hz with the
fundamental period T0 = NT, where there are N samples within the duration of the
fundamental period and T = 1/fs is the sampling period.
• According to Fourier series analysis, the coefficients of the Fourier series expansion
of a periodic signal x(t) in a complex form is:

where k is the number of

harmonics corresponding to the
x[n]
harmonic frequency of kf0 and ω0 x[N+1] = x[1]
= 2π/T0 and f0 = 1/T0 are the x[1]
fundamental frequency in radians
per second and the fundamental
frequency in Hz, respectively.
x[0]

x[N] =x[0]
 Fourier Series Coefficients
• If substitute T0 = NT, ω0 = 2π/T0 and x[n] x[N+1] = x[1]
approximate the integration over one
period using a summation by x[1]
substituting dt = T and t = nT. We
obtain:
x[0]
x[n]

k  2kn x[N] =x[0]

c e
j
and x[n]  N
k
k  

•The Fourier series coefficient ck is periodic of N:

x[n] x[n]

so, for convenience, we compute the spectrum over the range from 0 to fs Hz with
nonnegative indices, that is:
x[n]
 Fourier Series Coefficients

• For the kth harmonic, the frequency is

f = k f0 Hz.
• The frequency spacing between the consecutive spectral lines, called
the frequency resolution, is f0 Hz.
 Example1:
• The periodic signal
x(t) = sin (2πt)
is sampled using the rate fs = 4 Hz.
a. Compute the spectrum ck using the samples in one period.
b. Plot the two-sided amplitude spectrum |ck| over the range from -2 to 2 Hz.

x[n]
x[1]
nT nT
x[n]  sin(2f 0 nT )  sin(2 )  sin(2 ) x[2]
T0 NT x[0]

n n
 sin(2 )  sin(2 )  sin(0.5n)
N 4 x[3]

plot the first eight samples

Example1, cont.
• Choosing the duration of one period, N = 4, we have the sample
values as follows
x[0] x[1] x[2] x[3]

x[n] x[0] x[1] x[2] x[3]

x[n] x[0] x[1] x[2] x[3]

x[0] x[1] x[2] x[3]

x[n] x[n]
Example1, cont.
cn = cn+N = cn-N

below

The spectrum in the range of 2 to 2 Hz presents the information of the sinusoid

with a frequency of 1 Hz and a peak value of 2|c1|= 1, which is converted from
two sides to one side by doubling the spectral value. Note that we do not double
the direct-current (DC) component, that is, c0.
Discrete Fourier
Transform Formulas

x[n] x[N+1]=x[1]

x[1]

x[0]

x[N]=x[0]

x[n] x[n] X[k]

x[1]

x[N-1]
x[0]
 Discrete Fourier Transform Formulas
x[n]

• We determine the Fourier series coefficients using one-period N data samples.

Then we multiply the Fourier series coefficients by a factor of N to obtain:
N 1 2kn
j
X [k ]  Nck   x[n]e
n 0
N , k  0, 1,...........N  1
• Now let us conclude the DFT definition. Given a sequence x[n], 0 ≤ n ≥ N -1,
its DFT is defined as:
N 1 2kn N 1
j
X [k ]  
n 0
x[n]e N  
n 0
x[n]WNkn , k  0, 1,...........N  1

X [k ]  x[0]WNk 0  x[1]WNk1  x[2]WNk 2  ... x[ N 1]WNk ( N 1)

• The inverse DFT is given by:
N 1 2kn N 1

 
1 j 1
x[n]  X [k ]e N  X [k ]W N kn , n  0, 1,...........N  1
N k 0
N k 0
1
x[n]  ( X [0]W N 0 n  X [1]W N1n  X [2]W N 2 n  ...  X [ N  1]W N ( N 1) n
N
 Discrete Fourier Transform Formulas in matlab

• We can use MATLAB functions fft() and ifft() to compute the

DFT coefficients and the inverse DFT with the following
syntax:
Example2:
• Given a sequence x[n] for 0≥ n ≤3, where x[0] = 1, x[1] = 2, x[2] =3, and x[3] = 4,
– a. Evaluate its DFT X[k].

X[k] x[n] x[n]

X[0] x[n] x[0] x[1] x[2] x[3]

x[0] x[1] x[2] x[3]

X[1] x[n] x[0] x[1] x[2] x[3]

x[0] x[1] x[2] x[3]

Example2, cont.

X[2] x[n] x[0] x[1] x[2] x[3]

x[0] x[1] x[2] x[3]

X[3] x[n] x[0] x[1] x[2] x[3]

x[0] x[1] x[2] x[3]

Example3:
• Using the DFT coefficients X[k] for 0≥ k ≤3 computed in Example2,
– a. Evaluate its inverse DFT to determine the time domain sequence x[n].

x[n] X[k] X[k]

x[0] X[k] X[0] X[1] X[2] X[3]

Example3, cont.

x[1] X[k] X[0] X[1] X[2] X[3]

X[0] X[1] X[2] X[3]

x[2] X[k] X[0] X[1] X[2] X[3]

X[0] X[1] X[2] X[3]

Example3, cont.

x[3] X[k] X[0] X[1] X[2] X[3]

X[0] X[1] X[2] X[3]

 Relationship between the frequency bin k and its
associated frequency

• The calculated N DFT coefficients X[k] represent the frequency components

ranging from 0 Hz (or radians/second) to fs Hz (or ωs radians/second), hence
we can map the frequency bin k to its corresponding frequency as follows:

• We can define the frequency resolution as the frequency step between two
consecutive DFT coefficients to measure how fine the frequency domain
presentation is and achieve

or in terms of Hz, it follows that

Example4:

• In Example2, given a sequence x[n] for 0≥ n ≤3, If the

sampling rate is 10 Hz,
– a. Determine the sampling period, time index, and sampling
time instant for a digital sample x[3] in time domain.
– b. Determine the frequency resolution, frequency bin
number, and mapped frequency for each of the DFT
coefficients X[1] and X[3] in frequency domain.
Example4 solution,

x[3]

X[1]

X[3]
 Amplitude Spectrum Power Spectrum
• For the discrete sequence x[n] with a range of n = 0, 1, 2, . . . , N - 1, its N DFT
coefficients are: N 1 2kn N 1
j
X [k ]  
n 0
x[n]e N  
n 0
x[n]WNkn , k  0, 1,...........N  1

• Since each calculated DFT coefficient is a complex number, it is not convenient to

plot it versus its frequency index. Hence, after evaluating X[k], the magnitude and
phase of each DFT coefficient (we refer to them as the amplitude spectrum and
phase spectrum, respectively) can be determined and plotted versus its frequency
index. The amplitude spectrum is defined as:

X[k] X[k] X[k]

x[n]

X[k]

x[n]
 Amplitude Spectrum Power Spectrum
• Correspondingly, the phase spectrum is given by:

X[k]
X[k]

• Besides the amplitude spectrum, the power spectrum is also used. The DFT
power spectrum is defined as:

X[k] X[k] X[k]

• Again, notice that the frequency resolution, which denotes the frequency
spacing between DFT coefficients in frequency domain, is defined as:

It follows that better frequency resolution can be achieved by using a longer

data sequence.

spectral density, power spectral density (PSD), or energy spectral density (ESD)
Example5: x[n]

• Consider the sequence

Assuming that fs = 100 Hz,
– a. Compute the amplitude
spectrum, phase spectrum, and
power spectrum.

• Solution:
– a. Since N = 4, and using the DFT shown in Example1, we find the
DFT coefficients to be:
X[0] = 10, X[1] = -2 + j2, X[2] = -2, and X[3] = -2 - j2
The amplitude spectrum, phase spectrum, and power density spectrum are
computed as follows:
For k = 0, f = k fs/N = 0 x 100/4 = 0 Hz,
X[0]
X[0]
X[0]
X[0]
Example5, cont.

X[1]
X[1]
X[1]

X[1]

X[2]
X[2]
X[2]

X[2]

X[3]
X[3]
X[3]

X[3]
Example6:
• Consider a digital sequence sampled at the rate of 10 kHz. If we use a size of
1,024 data points and apply the 1,024-point DFT to compute the spectrum,
– a. Determine the frequency resolution.
– b. Determine the highest frequency in the spectrum.
 DFT coefficients computation using fast Fourier
transform (FFT) algorithm
• The FFT algorithm requires the time domain sequence x[n] to have a
length of data points equal to a power of 2; that is, 2m samples,
where m is a positive integer.
• If the length of the available data is not equal to a power of 2
(required by the FFT), we can pad the data sequence with zeros to
create a new sequence with a larger number of samples, N = 2m > N.
The modified data sequence for applying FFT, therefore, is

x[n] x[n]

• The signal spectra obtained via zero-padding the data sequence does
not add any new information and does not contain more accurate
signal spectral presentation. In this situation, the frequency spacing
is reduced due to more DFT points, and the achieved spectrum is an
interpolated version with ‘‘better display.’’
Zero padding effect by using FFT
Example7:
Spectral Estimation Using Window Functions

• When we apply DFT to the sampled data, we theoretically imply the

following assumptions:
– first, that the sampled data are periodic to themselves (repeat
themselves)
– second, that the sampled data are continuous to themselves and band
limited to the folding frequency which is often violated.

• Spectral leakage: refers to the misrepresentation of components other than

integer multiples of the fundamental frequency.
Spectral leakage: Example
• Consider the pure 1-Hz sine wave with 32 samples shown in the figure. If we
use a window size of N = 16 samples, which is a multiple of the two
waveform cycles, the second window repeats with continuity. However, when
the window size is chosen to be 18 samples, which is not a multiple of the
waveform cycles (2.25 cycles), the second window repeats the first window
with discontinuity.
Spectral leakage: Example
• To reduce the effect of spectral leakage, a window function can be used whose
amplitude tapers smoothly and gradually toward zero at both ends.
• Applying the window function w[n] to a data sequence x[n] to obtain a
windowed sequence xw[n]: xw[n]= x[n] w[n] , for n = 0, 1, . . . , N - 1:
Window Functions
Using Window Functions to reduce Spectral leakage: Example
Spectral leakage: Biosignal Example
 Fast Fourier Transform (FFT)

• The fast Fourier transform (FFT) is a discrete Fourier transform algorithm

which reduces the number of computations needed for N samples from 2N2 to
2Nlog2N , where log is the base-2 logarithm.
• If x[n] under FFT does not contain 2m samples, then we simply append it
with zeros until the number of the appended sequence is equal to an integer
of a power of 2 data points.
• FFT implemented by decimating the signal in the time domain. It is also
possible to implement the FFT by decimating the signal in the f frequency
domain.
• Complex multiplications of DFT = N2, and
Complex multiplications of FFT = N/2 log2(N)

Applying DFT will require 1,024 x 1,024 = 1,048,576 complex

multiplications;
however, applying FFT will need only (1,024/2) log2 (1,024) = 5,120
complex multiplications.
FFT Method of Decimation-in-Frequency

if we split X[k] into:

or

we can rewrite X[k] into:

FFT Method of Decimation-in-Frequency, cont.
FFT Method of Decimation-in-Frequency, cont.
Method of Decimation-in-Frequency, Example
• Given a sequence x[n] for 0 ≤ n ≤ 3, where x[0] = 1, x[1] = 2, x[2] = 3,
and x[3] = 4,
– a. Evaluate its DFT X[k] using the decimation-in-frequency FFT
method.
– b. Determine the number of complex multiplications.
Solution:
a. Using the FFT block diagram

b. The number of complex multiplications is four, which can also be

determined by: