Al-Amara University College

Department Of Medical Instrumentation Techniques Engineering

Digital Signal Processing

Report

Discrete Fourier Transform and Signal Spectrum

‫أسماء الطالب‬:

1.‫مصطفى عالء الدين عبد الزهرة‬

2.‫مقتدى عباس جلوب‬
3.‫حسين عبد الزهرة‬
4.‫سجاد محمد فرحان‬
5.‫علي كريم‬

Dr.Nabial dahdouh

2024/3/20

Introduction
The Fourier representation of signals that we studied in Chapter 3 is important for understanding how
filters work and what a spectrum is, but it is not a practical tool because the DTFT is a continuous
function of frequency and therefore its computation would in general require an infinite number of
operations. The purpose of this chapter is to introduce another representation of discrete-time signals,
the discrete Fourier transform (DFT), which is closely related to the discrete-time Fourier transform, and
can be implemented either in digital hardware or in software. The DFT is of great importance as an
efficient method for computing the discrete-time convolution of two signals, as a tool for filter design,
and for measuring spectra of discrete-time signals. While computing the DFT of a signal is generally easy
(requiring no more than the execution of a simple program) the interpretation of these computations
can be difficult because the DFT only provides a complete representation of finite-duration signals.

Definition of the discrete Fourier transform

Sampling the Fourier transform
It is not in general possible to compute the discrete-time Fourier transform of a signal because this
would require an infinite number of operations. However, it is always possible to compute a finite
number of frequency samples of the DTFT in the hope that, if the spacing between samples is sufficiently
small, this will provide a good representation of the spectrum. Simple results are obtained by sampling
in frequency at regular intervals. We therefore define the N-point discrete Fourier transform X[k] of a
signal x[n] as samples of its transform X(f) taken at intervals of 1/N:
∞
X[k] ≜ X(k/N) = ∑ ❑x[n]e−j2πkn/N for 0 ≤ k ≤ N – 1
n=−∞

Because X(f) is periodic with period 1, X[k] is periodic with period N, which justifies only considering the
values of X[k] over the interval [0, N − 1].

Condition for signal reconstruction from the DFT

An important question is whether the DFT provides a complete representation of the signal, that
is, if the signal can be reconstituted from its DFT. From what we know about sampling, we
expect that this will only be possible under certain conditions. Specifically, we have seen in
Chapter 1 that, if we take N samples per period of a continuous-time signal with period T, then
the signal can be exactly reconstructed provided that N > 2 W T, where W is the largest
frequency component in the signal. Similarly, if we take N samples per period of the continuous-
frequency, periodic signal X(f) with period 1, we expect that the spectrum can be reconstructed if
N is greater than the duration of the time signal x[n]. The sampling operation is equivalent to a
multiplication by a train of impulses (Fig. 4.1), which is covered in more detail in Chapter 5.
Therefore, sampling at intervals of 1/N effectively forms the new spectrum
∞ ∞ ∞
X˜(f) ≜= X(f) ∑ δ(f − k/N) = ∑ X(k/N)δ(f − k/N) = ∑ X[k]δ(f − k/N
n=−∞ n=−∞ n=−∞

Inverse discrete Fourier transform

So far, we have proven that the finite-duration signal x[n] can in principle be reconstructed from
its DFT X[k], but we have not given an explicit formula for achieving this reconstruction. We
will show by two different methods that the desired inverse DFT formula is:
n −1
1
x[n] =
n ∑ X[k] e j 2 πkn / N
k=0

A first method for deriving this formula is to combine (4.4) with the definition of X˜(f) in (4.2)
∞
X˜(f) = ∑ X[k] δ(f − k/N)
k=−∞

∞ ∞
1 1 1
Taking the inverse DTFT, one obtains: x[n] =
n
x˜[n] =
n ∑ X˜(f) e j 2 πfn df = ∑ − X[k]
n k=−∞
n=−∞
1
1
n0
∫ (f − k/N)e j 2 πfn df

Relation to discrete Fourier series

We have shown that taking N samples of the DTFT X(f) of a signal x[n] is equivalent to forming
a periodic signal ˜x[n] which is derived from x[n] by time aliasing. If the duration of x[n] is
smaller than N, one period of ˜x[n] is identical to x[n] within a factor of N. These results are the
dual of those obtained in Section 1.3 for the sampling of periodic, continuous time signals. We
showed that taking N samples per period of the periodic signal x(t) results in frequency aliasing
of the Fourier series coefficients Xk. If the bandwidth of x(t) is less than N/2T, the Fourier series
coefficients of the discrete-time signal coincide with those of the original signal x(t). Thus, there
is a duality between sampling in frequency the DTFT of a discrete-time signal to form the DFT,
and sampling in time a periodic signal to form the discrete Fourier series. In both cases, sampling
produces signals that are discrete and periodic in both the time and the frequency domain.
Therefore, the discrete Fourier transform and the discrete Fourier series are the same
mathematical operation (within a factor of N). This result is to be expected because there is a
one-to-one correspondence between discrete time signals of duration N and discrete, periodic
signals with period N. Specifically, given a finite-duration signal x[n], we can always generate a
periodic signal ˜xN [n] by repeating x[n] indefinitely at intervals of N samples:

x[n + rN] = x[n] ∗ ∑ δ[n − rN]

∞ ∞
x˜N [n] ≜ ∑
r=−∞ r=−∞

Application to filter design

The DFT can be used to design filters that approximate arbitrary specifications. Specifically,
suppose that the frequency response of the filter to be approximated is H(f). The frequency
sampling method of filter design consists in sampling H(f) at intervals of 1/N, then taking the
inverse DFT, yielding an FIR filter of length N. As shown by Equation (4.3), the unit-sample
response hN [n] of the FIR filter will be a time-aliased version of the desired unit-sample
response h[n]:

[ ] [∑ ]
∞ ∞
hN [n] = h [ n ]∗ ∑ δ [n−rN ] R N [N] = h[n+rN ] R N [N]
r =−∞ r=−∞

If the desired frequency response is smooth enough that h[n] decays to a negligible value for n ≥
N, the frequency response HN (f) of this FIR filter will provide a good approximation to H(f).
On the other hand, if H(f) has abrupt discontinuities, the unit-sample response h[n] will decay
very slowly, and HN (f) will always show ripples regardless of the value of N (Gibbs’
phenomenon). Such ripples are apparent in Figure 4.3, which shows the frequency response of
two lowpass filters designed by frequency sampling with N = 33.

Properties of the discrete Fourier transform

Most properties of the discrete Fourier transform are easily derived from those of the discrete-
time Fourier transform by making the substitution of variables f = k/N. However, some care is
needed because, as we have just seen, the DFT is inherently an operation on periodic signals.

Cyclic convolution modulo N

DTFT of the (linear) convolution of two signals x[n] ∗ h[n] is the product of their transforms
One property which requires some discussion is the convolution theorem. We know that the

X(f) H(f). If a similar theorem could be demonstrated for the DFT, it would be of great practical
importance because one could reduce filtering operations to simple multiplications of the DFTs.
We will show that this is indeed possible under certain conditions. For this purpose, we need to
introduce the cyclic convolution modulo N of two periodic signals ˜xN [n] and h˜N [n]

Convolution of two finite-duration signals using the DFT

This result is quite general: if x[n] and h[n] are both of finite duration, it is always possible to
compute the DFTs with a sufficient number of points to ensure that the cyclic convolution gives
the same result as the linear convolution. Specifically, if L is the length of x[n], and M is the
length of h[n], the length of the linear convolution is M + L − 1. Therefore, it suffices to compute
DFTs of length N ≥ M + L − 1 in order to make sure that the convolution will not 8 be time-
aliased. In this case, the following scheme for filtering the input x[n] by the filter h[n] becomes
possible: 1. Compute the N-point DFT of x[n] 2. Compute the N-point DFT of h[n] 3. Form the
product Y [k] = X[k] H[k] 4. Compute the inverse N-point DFT of Y [k]. The interest of this
method is that fast DFT algorithms allow this sequence of operations to be carried out in less
time than a direct (time-domain) implementation of the convolution sum.

Frequency-domain implementation of FIR filters

The preceding results show that linear convolutions can be realized by means of the DFT pro-
vided that the two signals to be convolved have finite durations. In many applications, however,
one needs to convolve a relatively short unit sample response (say a few tens to a few hundred
points) with a signal of indefinite duration. In such cases, the method outlined above may no
longer be applicable because the signal x[n] might be too long to fit in the computer memory.
Even if sufficient memory were available, computational times might be too long, and inaccu-
racies resulting from finite-precision arithmetic might be too great to make the DFT method
useful. In real time applications, having to wait until the signal has ended before the filtering
operation can be started would be clearly unacceptable. Fortunately, it is possible to modify the
DFT method of convolution to make it applicable to signals of indefinite duration. The general
idea is to first segment the signal x[n] into chunks of manageable size, then compute the
convolution of each segment with the unit-sample response h[n] by the DFT method, and finally
join the results of the convolutions for all segments. Some care is needed in joining the
convolved segments, however, because the cyclic convolution of a signal segment with the unit-
sample response will coincide with the linear convolution only for part of the segment. We
describe here one particular implementation called the overlap save method. A slightly different
method called overlap add is described in Oppenheim and Schafer

Summary of Fourier transforms

In these notes, we have studied four different kinds of Fourier transforms: 1. The continuous-
time Fourier transform (CTFT) 2. The discrete-time Fourier transform (DTFT) 3. The continuous
time Fourier series (CTFS) 4. The discrete Fourier transform (DFT) or discrete Fourier series
(DFS) The last three transforms can be considered as special cases of the CTFT obtained by
sampling (multiplying by a periodic impulse train) in either the time domain or the frequency
domain, or both. Sampling in one domain corresponds to an aliasing operation (convolution by a
periodic impulse train) in the opposite domain. To each of these transforms correspond both a
convo-lution theorem and a product theorem. Convolutions can be either discrete or continuous,
and either cyclic or “linear”. Which of these four types of convolutions should be used follows
from the properties of the signals to be convolved: discrete convolution for discrete signals,
cyclic convolutions for periodic signals, and convolution modulo N for signals that are both
discrete and periodic. Table 4.1 summarizes the type of signals to which each of the 4 transforms
applies, and gives the appropriate convolution and product theorems.

Summary
The N-point discrete Fourier transform of a signal is obtained by sampling its DTFT at frequency
intervals of 1/N. If the duration of the signal is no more than N, the N-point DFT provides a 12
complete representation of the signal, and is related to the signal by the finite formulas
N−1
X[k] = ∑ X[n] e− j2 πkn/ N
N =0

N−1
1
X[n]=
N
∑ X[K] e j 2 πkn / N
N =0
These formulas are mathematically the same as the Fourier series for discrete, periodic signals.
This is because sampling at intervals of 1/N in frequency inherently generates an N-periodic
signal ˜x[n], which coincides with the finite-duration signal x[n] over one of its periods. A major
application of the DFT is the efficient implementation of convolution (filtering) operations for
either two signals of finite duration or one FIR filter and one signal of indefinite duration (e.g.
using the overlap-save method). These methods have to be used with caution because the product
of two N-point DFTs is not the transform of linear convolution of the two signals, but the
transform of their cyclic convolution modulo