KEC503

DIGITAL SIGNAL PROCESSING

Contents as per syllabus:

UNIT-4 Syllabus

4.1 Discrete Fourier Transform:

4.1.1 Concept and relations for DFT/IDFT,

4.1.2 Properties of the DFT
4.1.3 Circular convolution, computation of circular convolution by
graphical:
4.1.4 Linear filtering using DFT, aliasing error:
4.1.5 Twiddle factors and their properties,
4.1.6 DFT/IDFT as linear transformations,
4.1.7 Filtering of long data sequences –Overlap-Save and Overlap-Add
methods with examples.
4.2 Fast Fourier Transform (FFT):

4.2.1 Decimation in Time (DIT) Algorithm

4.2.2 Decimation in Frequency (DIF) Algorithm
4.1.1 Concept and relations for DFT/IDFT:

Discrete Fourier Transform (DFT)

The Discrete Fourier Transform (DFT) computes the values of the z-transform
for evenly spaced points around the unit circle for a given sequence.
If the sequence to be represented is of finite duration, i.e. has only a finite
number of non-zero values, the transform used is Discrete Fourier Transform
(DFT). DFT finds its applications in digital signal processing including linear
filtering, correlation analysis and spectrum analysis.

Definition
Let x(n) be a finite duration sequence. The N-point DFT of the sequence x(n) is
expressed by

and the corresponding IDFT is

Let X(z) be the z-transform for a sequence x(n) which is given by X(z)

with an ROC that includes the unit circle. If X(z) is sampled at the N equally
spaced points on the unit circle,

This is identical to the Fourier transform X(ejv) evaluated at the N equally

spaced frequencies
If the sequence x(n) has a finite duration of length N, then the z-transform is
given by

Substituting the IDFT relation for x(n), we have

The above equation is identical to that of frequency sampling form. When this is
evaluated over a unit circle, then

4.1.2 Properties of the DFT:

The properties of the DFT are useful in the practical techniques for processing
signals. The various properties are given below.

1. Periodicity

If X(k) is an N-point DFT of x(n), then

x(n + N) = x(n) for all n
X(k + N) = X(k) for all k

2. Linearity

If X1(k) and X2(k) are the N-point DFTs of x1(n) and x2(n) respectively, and a
and b are arbitrary constants either real or complex-valued, then
If y(n) = x(n), then the above equation reduces to

This expression relates the energy in the finite duration sequence x(n) to the
power in the frequency components X(k).
4.1.3 Circular convolution, computation of circular convolution by
graphical:

Circular Convolution (Periodic Convolution)

Consider the two sequences x1(n) and x2(n) which are of finite duration. Let
X1(k) and X2(k) be the N-point DFTs of the two sequences respectively and
they are given by

Let x3(n) be another sequence of length N and its N-point DFT be X3(k) which
is a product of X1(k) and X2(k), i.e.

The sequence x3(n) can be obtained by taking the inverse DFT of X3(k), i.e.

Consider the term within the brackets. It has the form

where x2((m – n), mod N) is the reflected and circularly shifted version of
x2(m) and n represents the number of indices that the sequence x(n) is shifted to
the right.
The above equation has a form similar to the convolution sum and it is called
circular convolution. The circularly shifted versions of x(m) are given below:

It is noted that a shift of n = N results in the original signal x(m).

Matrix Multiplication Method

The circular convolution of two sequences x(n) and h(n) can be obtained by
representing these sequences in the matrix form as given below:
The sequence x(n) is repeated via circular path shift of samples and represented
in N X N matrix form. The sequence h(n) is represented as column matrix. The
multiplication of these two matrices gives the sequence y(n).

Compute (a) linear and (b) circular periodic convolutions of the two sequences
x1(n) = {1, 1, 2,2} and x2(n) = {1, 2, 3, 4}.
(c) Also find circular convolution using the DFT and IDFT.

(a) Using matrix representation given as follows, the linear convolution of the
two sequences can be determined.
Hence, x3(n) = x1(n)* x2(n) = {1, 3, 7, 13, 14, 14, 8}

(b) Similarly, circular convolution of the two sequences is shown

For m=0:

x2(– n, (mod 4)) is the sequence x2(n) folded. The folded sequence is obtained
by plotting x2(n) in a clockwise direction.

x3(0) is obtained by computing the product sequence, i.e. multiplying the

sequences x1(n) and x2(–n,(mod 4)), point by point and taking the sum, we get
x3(0) = 15.
For m=1:

x2(1 – n, (mod 4)) is the sequence x2(– n, (mod 4)) rotated counterclockwise by
one unit in time. From the product sequence, the sum is x3(1) = 17.
For m = 2:

x2(2 – n, (mod 4)) is the sequence x2(– n, (mod 4)) rotated counterclockwise by
two units in time. From the product sequence, the sum is x3(2) = 15.
For m=3:

x2(3 – n, (mod 4)) is the sequence x2(– n, (mod 4)) rotated counterclockwise by
three units in time.
From the product sequence, the sum is x3(3) = 13.

Hence, the circular convolution of the two sequences x1(n) and x2(n) is
x3(n) = {15, 17, 15, 13}.

Graphical representation for circular convolution evaluation:

Therefore, x3(n) = {15, 17, 15, 13}.

4.1.4 Linear filtering using DFT, aliasing error:

DFT as linear filtering:

DFT provides an alternative approach to time domain convolution. It can be

used to perform linear filtering in frequency domain.

Thus,Y(ω)=X(ω).H(ω)↔y(n)

The problem in this frequency domain approach is that Y(ω), X(ω) and H(ω)are
continuous function of ω, which is not fruitful for digital computation on
computers. However, DFT provides sampled version of these waveforms to
solve the purpose.
The advantage is that, having knowledge of faster DFT techniques likes of FFT,
a computationally higher efficient algorithm can be developed for digital
computer computation in comparison with time domain approach.

Consider a finite duration sequence, [x(n)=0,for, n<0 and n≥L] generalized

equation, excites a linear filter with impulse response [h(n)=0,for n<0 and
n≥M].

x(n)y(n)
1
output = y(n) =∑ 0 h(𝑘 )x(n − 𝑘)

From the convolution analysis, it is clear that, the duration of y(n) is L+M−1.

In frequency domain,

Y(ω)=X(ω).H(ω)

Now, Y(ω) is a continuous function of ω and it is sampled at a set of discrete

frequencies with number of distinct samples which must be equal to or exceeds
L+M−1.

With ω=2πNk,

Y(ω)=X(k).H(k), where k=0,1,….,N-1

Where, X(k)and H(k) are N-point DFTs of xn and hn respectively. x(n) & h(n)
are padded with zeros up to the length N. It will not distort the continuous
spectra X(ω) and H(ω). Since N ≥ L+M−1, N-point DFT of output sequence yn
is sufficient to represent yn in frequency domain and these facts infer that the
multiplication of N-point DFTs of X(k) and H(k), followed by the computation
of N-point IDFT must yield y(n).

This implies, N-point circular convolution of x(n)and h(n) with zero padding,
equals to linear convolution of x(n) and h(n).

Thus, DFT can be used for linear filtering.

N should always be greater than or equal to L+M−1. Otherwise, aliasing effect

would corrupt the output sequence.

4.1.5 Twiddle factor and their properties:

Twiddle factors (represented with the letter W) are a set of values that is used to
speed up DFT and IDFT calculations.

For a discrete sequence x(n), we can calculate its Discrete Fourier Transform
and Inverse Discrete Fourier Transform using the following equations.

DFT: x(k) =

IDFT: x(n) =

The computation procedure for the above is quite complex.

Twiddle factors are mathematically represented as:

Rewriting the equations for calculating DFT and IDFT using twiddle factors we
get:

DFT:

IDFT:

We use the twiddle factor to reduce the computational complexity of calculating

DFT and IDFT.

The twiddle factor is a rotating vector quantity. All that means is that for a given
N-point DFT or IDFT calculation, it is observed that the values of the twiddle
factor repeat at every N cycles. The expectation of a familiar set of values at
every (N-1)th step makes the calculations slightly easier. (N-1 because the first
sequence is a 0)

Alternatively, we can also say that the twiddle factor has periodicity/a cyclic
property.

Matrix method of calculating DFT and IDFT with twiddle factors

The above DFT equation using the twiddle factor can also be written in matrix
form. The matrix form of calculating a DFT and an IDFT eases up many
calculations.

X(k) = x(n)
Similarly an IDFT can be calculated using a matrix form using the following
equation.

x(n) =

Here, is the complex conjugate of the twiddle factor. To get the values of the
complex conjugate, just invert the signs of the complex components of the
twiddle factor. For example: The complex conjugate of 0.707+0.707j will
become 0.707-0.707j.

Property of twiddle factors:

For a 4-point DFT

Let’s derive the twiddle factor values for a 4-point DFT using the formula
above.

For n=0 and k=0,

(From Euler’s formula: )

As you can see, the value starts repeating at the 4th instant. This periodic
property can is shown in the diagram below.

Similarly calculating for the remaining values we get the series below:

=1
= -j
= -1
=j
=1
4.1.6 DFT as linear transform:

The matrix of is known as the matrix of linear transformation. Check out the
scene of the linear transformation in DFT below.

We have the formula for calculating DFT using a matrix as:

X(k) = x(n)

x(n) = X(k)

We also have the formula for calculating the IDFT using a matrix as:

x(n) =

Equating the last two equations:

Here, ‘I’ is an identity matrix of order N. This equation represents the fact that
the DFT displays linear transformation characteristics.

4.1.7 Filtering of long data sequences –Overlap-Save and Overlap-Add

methods with examples:

While implementing linear convolution in FIR filters, the input signal sequence
x(n) is much longer than the impulse response sequence h(n) of a DSP system.
Circular convolution can also be used to implement linear convolution by
padding zeros. The output cannot be obtained until the entire input signal is
received and hence there will be characteristic delays. Also, as the signal N1 +
N2 - 1 gets longer; FFT implementation and the size of the memory needed
become impractical. In order to eliminate these problems while performing
filtering operation (i.e. convolution) in the frequency-domain, two signal
segmentation methods, namely the overlap-add and the overlap-save techniques,
can be used to perform fast convolution by sectioning or grouping the long
input sequence into blocks or batches of samples and the final convolution
output sequence can be obtained by combining the partial convolution results
generated from each block.
Overlap-Add Method:
Figure shows the overlap–add fast convolution method.

Overlap – Add Fast Convolution Method

Steps Needed to Perform Overlap2Add Fast Convolution Method

(a) (N -1) zeros are padded (added) at the end of the impulse response
sequence h(n) which is of length M and a sequence of length M + N -
1 = L is obtained. Then, this L-point FFT is performed and the output
values are stored.
(b) An L-point FFT on the selected data block is performed. Here
each data block has N input data values and (M -1) zeros.
(c) The stored frequency response of the filter, i.e. the FFT output
sequence obtained in step (a) is multiplied by the FFT output
sequence of the selected data block obtained in step (b).
(d) An L-point inverse FFT is performed on the product sequence
obtained in step (c).
(e) The first (M – 1) IFFT values obtained in step (d) is overlapped
with the last (M – 1) IFFT values for the previous block. Then
addition is done to produce the final convolution output sequence
y(n).
(f) For the next data block, go to step (b).

Overlap – Save Method

It has already been shown that multiplication of two DFTs yields a

circular convolution of time domain
sequences, i.e. y(n) = x(n) ∗ h(n) = IFFT [X( f ) H( f )]. But a linear
convolution is required for the implementation of an FIR filter. The
overlap – save method is useful for converting a circular convolution
into a linear convolution.
Figure shows the overlap – save convolution method.
 The Overlap – Save Convolution Method

Steps to Perform Overlap – Save Fast Convolution Method

(a) (N 21) zeros are padded (added) at the end of the impulse response sequence
h(n) which is of length M and a sequence of length (M + N - 1) = L is obtained.
Then, this L-point FFT is performed and the output values are stored.
(b) An L-point FFT on the selected data block is performed. Here each data
block begins with the last (M - 1) values in the previous data block, except the
first data block which begins with (M - 1) zeros.
(c) The stored frequency response of the filter, i.e. the FFT output sequence
obtained in step (a) is multiplied by the FFT output sequence of the selected
data block obtained in step (b).
(d) An L-point inverse FFT is performed on the product sequence obtained in
step (c).
(e) The first (M 2 1) values from successive output of step (d) are discarded and
the last N values of the IFFT obtained in step (d) is saved to produce the output
y(n).
(f) For the next data block, go to step (b).
4.2 FAST FOURIER TRANSFORM (FFT)
The fast Fourier transform (FFT) is an algorithm that efficiently computes the
discrete Fourier transform(DFT). The DFT of a sequence {𝑥(𝑛)} of length 𝑁 is
given by a complex-valued sequence {𝑋(𝑘)}

Let 𝑊 be the complex-valued phase factor, which is a𝑁 root of unity

expressed by
/
𝑊 =𝑒

Hence 𝑋(𝑘) becomes

Similarly, IDFT becomes

From the above equations, it is evident that for each value of k, the direct
computation of 𝑋(𝑘)involves 𝑁 complex multiplications (4𝑁 real
multiplications) and 𝑁 – 1 complex additions (4𝑁 – 2 realadditions). Hence, to
compute all 𝑁 values of DFT, 𝑁 complex multiplications and 𝑁(𝑁– 1)
complexadditions are required. The DFT and IDFT involve the same type of
computations.

If 𝑥(𝑛) is a complex-valued sequence, then the 𝑁-point DFT given in Eq. (6.17)
can be expressed as
Equating the real and imaginary parts of the above equation, we have

The direct computation of the DFT requires 2𝑁 evaluations of trigonometric

functions, 4𝑁 realmultiplications and 4𝑁(𝑁 − 1) real additions. Also, this is
primarily inefficient as it does not exploit thesymmetry and periodicity
properties of the phase factor WN, which are given below:
/
Symmetry Property 𝑊 = −𝑊

Periodicity Property 𝑊 =𝑊

An efficient algorithm for DFT computation is the fast Fourier transform

algorithm because FFTalgorithms exploit the above two properties.

Radix-2 FFT
By adopting a divide and conquer approach, a computationally efficient
algorithm for the DFT can bedeveloped. This approach depends on the
decomposition of an N-point DFT into successively smallersize DFTs.

If 𝑁 is factored as 𝑁 = 𝑟 𝑟 𝑟 . . . 𝑟 where 𝑟 = 𝑟 =. . . = 𝑟 = 𝑟, then 𝑁 = 𝑟𝐿.

Hence, the DFT will be of size ‘𝑟’, where this number ‘𝑟’ is called the radix of
the FFT algorithm. In this section, the most widely used radix-2 FFT algorithms
are described. FFT algorithms take advantage of the periodicity and symmetry
of the complex number𝑊 =𝑒 .

4.2.1 Decimation in Time (DIT) Algorithm

In this case, let us assume that 𝑥(𝑛) represents a sequence of 𝑁 values, where
𝑁 is an integer power of2, that is, 𝑁 = 2 . The given sequence is decimated
(broken) into two𝑁/2point sequences consisting ofthe even numbered values of
𝑥(𝑛) and the odd numbered values of 𝑥(𝑛).
The 𝑁-point DFT of sequence 𝑥(𝑛) is given by

Breaking 𝑥(𝑛) into its even and odd numbered values, we obtain

Substituting 𝑛 = 2𝑟 for n even and 𝑛 = 2𝑟 + 1 for 𝑛 odd, we have

Here,

Therefore, Eq. (6.25) can be written as

Where𝐺(𝑘) and 𝐻(𝑘) are the 𝑁/2-point DFTs of the even and odd numbered
sequences respectively.

Here, each sum is computed for 0 ≤ 𝑘 ≤ 𝑁/2 − 1 since 𝐺(𝑘) and 𝐻(𝑘) are
considered periodic with period𝑁/2.
Therefore,

/
Using the symmetry property of, 𝑊 = −𝑊 Eq. (6.27) becomes

Fig. 1 Flow Graph of the First Stage Decimation-In-Time FFT Algorithm for N
=8

For a direct computation of an 𝑁-point DFT, without exploiting symmetry, 𝑁

complexmultiplications and 𝑁(𝑁– 1) ≈ 𝑁 complex additions were required.
Based on the decomposition ofEq. (6.26), the computation of an 𝑁-point DFT
using the decomposition requires the computationsof two (𝑁/2)-point DFTs
which requires 2(𝑁/2) or 𝑁 /2 complex multiplications and
approximately2(𝑁/2) or 𝑁 /2 complex additions, which must be combined
with N complex multiplications, correspondingto multiplying the second sum
by 𝑊 and 𝑁 complex additions, corresponding to adding thatproduct to the
first sum. Hence, the computation of Eq. (6.26) for all values of 𝑘 requires
𝑁 + 2(𝑁/2) or 𝑁 + 𝑁 /2 complex multiplications and 𝑁 + 𝑁 /2 complex
additions.

The above process may be continued by expressing each of the two (N/2)-point
DFTs, 𝐺(𝑘) and 𝐻(𝑘)as a combination of two (𝑁/4)-point DFTs, assuming
that (𝑁/2) is even since 𝑁 is equal to a power of2. Each of the (𝑁/2)-point
DFTs in Eq. (6.26) is computed by breaking each of the sums in Eq. (6.26)into
two (𝑁/4)-point DFTs, which is then combined to give the (𝑁/2)-point DFTs.
Thus 𝐺(𝑘) and 𝐻(𝑘)in Eq. (6.26) shall be computed as explained below.

Where𝐴(𝑘) is the (𝑁/4)-point DFT of even numbers of the above sequence

and𝐵(𝑘) is the (𝑁/4)-point DFT of odd numbers of the above sequence.

Similarly,
 Fig. 2Flow Graph of the Second Stage Decimation-in-time FFT Algorithm for
𝑁 = 8.

From Eq. (6.29), we get

In the above equations, since

/ .
𝑊 / = 𝑊 and 𝑊 =𝑒 =𝑒 = −1,

𝐴(0) = 𝐴(2)and𝐴(1) = 𝐴(3)

𝐴(0) = 𝐴(2)and𝐴(1) = 𝐴(3)

Similarly, from Eq. (6.30), we get

 Fig. 2 The Flow-Graph of the Decimation-in-time FFT Algorithm for N = 8.

Table 1

Index Binary representation Bit reversed binary Bit reversal index

0 000 000 0
1 001 100 4
2 010 010 2
3 011 110 6
4 100 001 1
5 101 101 5
6 110 011 3
7 111 111 7
 Fig. 2 Basic Butterfly Flow Graph for the Computationin the DIT FFT
Algorithm.

Fig. 2 Flow Graph for theReduced Flow-Graph for an 8-Point DIT FFT.

4.2.2 Decimation-In-Frequency (DIF) Algorithms

The decimation-in-time FFT algorithm decomposes the DFT by sequentially
splitting input samples𝑥(𝑛) in the time domain into sets of smaller and smaller
subsequences and then forms a weighted combinationof the DFTs of these
subsequences. Another algorithm called decimation-in-frequency
FFTdecomposes the DFT by recursively splitting the sequence elements 𝑋(𝑘)
in the frequency domain intosets of smaller and smaller subsequences. To
derive the decimation-in-frequency FFT algorithm for𝑁, a power of 2, the input
sequence 𝑥(𝑛) is divided into the first half and the last half of the points
asdiscussed below.
Two different forms of Eq. (6.32) are obtained, depending on whether k is even
or odd. Decomposingthe sequence in the frequency domain, 𝑋(𝑘), into an even
numbered subsequence 𝑋(2𝑟) and an oddnumbered subsequence 𝑋(2𝑟 + 1)
where 𝑟 = 0, 1, 2, … , (𝑁/2 − 1), yields
Equations (6.33) and (6.34) represent the N/2-point DFTs. Equation (6.33) gives
the sum of the firsthalf and the last half of the input sequence. Equation (6.34)
gives the product of 𝑊 with the differenceof the first half and the last half of
the input sequence.

For an 8-point DFT, i.e.,𝑁 = 8

𝑔(0) = 𝑥(0) + 𝑥(4) ℎ(0) = 𝑥(0) − 𝑥(4)

𝑔(1) = 𝑥(1) + 𝑥(5) ℎ(0) = 𝑥(0) − 𝑥(4)
𝑔(2) = 𝑥(2) + 𝑥(6) ℎ(0) = 𝑥(0) − 𝑥(4)
𝑔(3) = 𝑥(3) + 𝑥(7) ℎ(0) = 𝑥(0) − 𝑥(4)

Here, the computation of the DFT is done by first forming the sequences
𝑔(𝑛)and ℎ(𝑛), then calculatingℎ(𝑛)𝑊 , and finally evaluating the 𝑁/2-point
DFTs of these two sequences to obtain the even numberedoutput points and the
odd numbered output points, respectively. The flow-graph of the first stage of
an8-point DFT computation scheme defined by Eqs. (6.33) and (6.34) is shown
in Fig. 6.
Where
Fig. 5Flow Graph of the First Stage of Decimation-In-Frequency FFT for N = 8.

Substituting the identity WNN/2 = –1 in the above equation, we get

When r=2l (even),

Therefore,

When r=2l+1 (odd),

Where

Where
Similarly, Eq. (6.34) becomes

Figure 6 shows the flow-graph of the second stage of decimation-in-frequency

decomposition ofan 8-point DFT into four 2-point DFT computations.
Fig. 6Flow Graph of the Second Stage of Decimation-In-Frequency FFT for
N=8.

Fig. 6 Reduced Flow Graph of Final Stage DIF FFT for N = 8.

University Questions Related to Unit-4

[Link] Questions Marks Exam

Year
Q.1 If x (n) = {6, 5 ,4,3} what will be x ((2-n)4). 2 2017-18

Q.2 What is the DFT of δ(n)? 2 2017-18

what is Discrete Time Fourier Transform and How 2 2015-16
it
is related to Discrete Fourier Transform?
Q.3 Define Time Reversal of a sequence in DFT. 2 2017-18

Q.4 What is twiddle factor in DFT? 2 2017-18

Q.5 What is the difference between circular convolution 2 2017-18
and linear convolution?

Q.6 use the 4 point DFT and IDFT to determine circular 10 2017-
convolution of the following sequence: 18,2015-
x (n) : {1,2,3,l} 16
h (n) : {4,3.2,2}
Q.7 Determine the 8-point DFT of the following 10 2017-18
sequence using DIF FFT algorithm:
x (n): {1,2.3,4}
Q.8 Write a short notes on the following: 10 2017-18
(i) Butterfly Computation (ii) Inplace Computation
(iii) Bit reversal
Q.9 State and prove the circular convolution theorem. 5 2017-18
Q.10 Determine the circular convolution of the following 10 2017-18
sequences and compare the
results with linear convolution:
x (n)= (1,2,3,4)
h(n) = (1,2,1)
Q.11 The first five points of 8-point DFTof a real valued 10 2017-18
sequence are:{0.25, 0.125 - j0.3018, 0, 0.125 -
j0.0518,0}.
Determine the remaining three points.
Q.12 Find the inverse DFT of the sequence : 10 2017-18
X(k) = {6, -2+i2, -2, -2-i2),using DIT-FFT
algorithm.
Q.13 Derive and draw the flow graph for DIF FFT 10 2017-18
algorithm for N= 8.