COMPUTATION OF DISCRETE FOURIER TRANSFORM

AIM AND OBJECTIVE:

To compute Discrete Fourier transform of a given signal and perform filtering using
DFT

INTRODUCTION
In mathematics, the discrete Fourier transform (DFT) is a specific kind of Fourier
transform, used in Fourier analysis. It transforms one function into another, which is
called the frequency domain representation, or simply the DFT, of the original
function (which is often a function in the time domain). But the DFT requires an input
function that is discrete and whose non-zero values have a limited (finite) duration.
Such inputs are often created by sampling a continuous function, like a person's voice.
Unlike the discrete-time Fourier transform (DTFT), it only evaluates enough
frequency components to reconstruct the finite segment that was analyzed. Using the
DFT implies that the finite segment that is analyzed is one period of an infinitely
extended periodic signal; if this is not actually true, a window function has to be used
to reduce the artifacts in the spectrum. For the same reason, the inverse DFT cannot
reproduce the entire time domain, unless the input happens to be periodic (forever).
Therefore it is often said that the DFT is a transform for Fourier analysis of finite-
domain discrete-time functions. The sinusoidal basis functions of the decomposition
have the same properties (Mitra S., 2006).
The input to the DFT is a finite sequence of real or complex numbers (with more
abstract generalizations discussed below), making the DFT ideal for processing
information stored in computers. In particular, the DFT is widely employed in signal
processing and related fields to analyze the frequencies contained in a sampled signal,
to solve partial differential equations, and to perform other operations such as
convolutions or multiplying large integers. A key enabling factor for these
applications is the fact that the DFT can be computed efficiently in practice using a
fast Fourier transform (FFT) algorithm.
Pre-lab:
In practice the Fourier components of data are obtained by digital computation rather
than by analog processing. Because the analog waveform consists of an infinite
number of contiguous points, the representation of all the values is a practical
impossibility.
(i) Consider a data sequence x (n) = {u, u+1, u+2, u+3, u+3, u+2, u+1, u}.
Compute 8-point DFT of this sequence and verify the answer by calculating
Inverse DFT.
(ii) Determine the computational complexity of the DFT.
(iii) Enumerate how DFT can be used in filtering.

ANSWERS
Using the UEL ID: U1159336,
The sequence x(n)={6,7,8,9,9,8,7,6}

(i) Considering the data sequence x (n) = {6,7,8,9,8,7,6}. Compute 8-point DFT
of this sequence and verify the answer by calculating Inverse DFT.
INPUT S1 S2 OUTPUT
X(0)=6 6+9=15 15+15=30 30+30=60
X(1)=7 7+8=15 15+15=30 (W 0 )
(30-30) 8 =0

X(2)=8 8+7=15 (W 0 ) 0+0=0

15-15 8 =0
X(3)=9 9+6=15 (W 2 ) (W 0 )
15-15 8 =0 (0-0) 8 =0

X(4)=9 (6-9)*1=-3 -3+(-j)=-3-j -3-j+(-2.828-j1.414)=-

5.828-j2.414
X(5)=8 (7-8)*0.707-j0.707=- -0.707+j0.707+(-2.121-j2.121)=- (W 0 )
-3-j-(-2.828-j1.414) 8
0.707+j0.707 2.828-j1.414
=-0.172+j0.414
X(6)=7 (8-7)*-j=-j (W 0 ) -3+j+(2.828-j1.414)=-
-3-(-j) 8 =-3+j
0.172-j0.414
X(7)=6 (9-6)*(-0.707-j0.707)=- -0.707+j0.707-(2.121-j2.121) (W 0 )
-3+j-(2.828-j1.414) 8
2.121-j2.121 (W 2 )
8 =2.828-j1.414 =-5.828+j2.414

INPUT S1 S2 OUTPUT
X(0)=60 (W 0 ) (W 0 ) (W 0 )
60+0 8 =60 60+0 8 =60 60+(-12) 8 =48/8=6
X(4)=0 (W 0 ) (W 2 ) (W 1 )
60-0 8 =60 60+0 8 =60 60+(-2.828-j2.828) 8

=56/8=7
X(6)=0 (W 0 ) (W 0 ) (W 2 )
0+0 8 =0 60-0 8 =60 60+4j 8 =64/8=8
X(2)=0 (W 0 ) (W 2 ) 60+(-
0-0 8 =0 60+0 8 =60
8.484+j8.484)=72/8=9
X(7)=-5.828+j2.414 -5.828+j2.414+(- (W 0 ) (W 0 )
-6+j2+(-6-j2) 8 =-12 60-(-12) 8 =72/8=9
(W 0 )
0.172-j0.414) 8

=-6+j2
X(3)=-0.172-j0.414 -5.828+j2.414-(- - (W 1 )
60-(-2.828-j2.828) 8
5.656+j2.828+(5.656+j2.828)
(W 0 ) =64/8=8
0.172-j0.414) 8 =
(W 2 )
8 =-2.828-j2.828
-5.656+j2.828
X(5)=-0.172+j0.414 -0.172+j0.414+(- (W 0 ) (W 2 )
-6+j2-(-6-j2) 8 =4j 60-4j 8 =56/8=7
(W 0 )
5.828-j2.414) 8

=-6-j2
X(1)=-5.828-j2.414 -0.172+j0.414-(- 5.656+j2.828-(5.656+j2.828) 60-(-
(W 2 ) 8.484+j8.484)=48/8=6
(W 0 ) 8 =-8.484+j8.484
5.828-j2.414) 8

= 5.656+j2.828

(ii) Determine the computational complexity of the DFT.

For the direct FFT approach
x(n)=[ 6 , 7, 8 ,9 , 9,8, 7 ,6 ]
The N-point x(n) is given by
N−1 − j2 π nk
DFT =[ x (n )]=x (k )= ∑ x (n )e N

n=0

7 − j 2 π nk
=x (k )= ∑ x( n)e 8

n=0
For [ K =0,1,2,3−−−−N −1]
......[ K=0,1,2,3−−−−7]
substituting n into the equation
− j 2 πk − j 4 πk − j6 πk − j8 πk − j10 πk − j12 πk − j14 πk
8 8 8 8 8 8 8
=6 +7 e +8 e +9 e +9 e +8 e +7 e +6 e
− jπk − jπk − j 3 πk − j5 πk − j 3 πk − j 7 πk
4 2 4 − jπk 4 2 4
=6 +7 e +8 e +9e +9e +8 e +7 e +6e
When K=1
6+7 +8+9+ 9+8+7+ 6=60

When K=1
6+(4.949− j 4.949)+(−8 j )+(−6.363− j 6.363)+(−9)+(−5.656+ j 5.656)+(7 j)+( 4.242+ j 4.242)
=−5.828− j 2.414
When K=2
6+(−7 j)+(−8 )+( 9 j)+(9)+(−8 j)+(−7 )+(6 j)=0

When K=3
6+(−4.949− j 4.949)+(8 j )+(6.363− j6.363)+(−9)+(5.656+ j5.656)+(−7 j)+(−4.242+ j 4.242)
=−0.172− j 0.414

When K=4
6+(−7)+(8)+(−9)+(9)+(−8)+(7 )+(−6 )=0

When K=5
6+(−4.949+ j 4.949)+(−8 j)+(6.363+ j6.363)+(−9)+(5.656− j 5.656)+(7 j)+(−4 .242− j 4.242)
=−0.172+ j0.414

When K=6
6+(7 j )+(−8)+(−9 j)+(9)+(8 j)+(−7 )+(−6 j)=0

When K=7
6+(4.949+ j 4.949 )+(8 j )+(−6.363+ j6.363 )+(−9)+(−5.656− j 5.656 )+(−7 j )+(4 .242− j 4.242)
=−5.828+ j2.414
x(n )=[ 60 ,−5 . 828− j2 . 414 ,0 ,−0 .172− j 0 . 414 , 0 ,−0. 172+ j 0 . 414 , 0 ,−5. 828+ j2 . 414 ]
To calculate the percentage saving of the 8-point DFT we say
Direct computation
Number of complex additions
=N (N −1). . where. . N =8
=8(8−1 )=56
Number of complex multiplications
=N 2=8 2=64
Radix -2 FFT
Number of complex additions
=N log 2 N
=8 log 2 8=24

Number of complex multiplications

N
= log 2 N
2
8
= log 2 8=12
2

Therefore the percentage saving in addition is

No ..of .addition.in.radix ..2 FFT

=100− ×100
No ..of .addition.in.direct . FFT
24
=100− ×100=57 .14 %
56

Therefore the percentage saving in multiplication is

No ..of .multiplication .in.radix ..2 FFT

=100− ×100
No ..of .multiplication.in.direct .FFT
12
=100− ×100=81 .25 %
64

(iii) Enumerate how DFT can be used in filtering.

using the DFT to convert a system's impulse response into its frequency response.
Figure (a) is the impulse response of the system. Looking at this curve isn't going to
give you the slightest idea what the system does. Taking a 64 point DFT of this
impulse response produces the frequency response of the system, shown in (b). Now
the function of this system becomes obvious, it passes frequencies between 0.2 and
0.3, and rejects all others. It is a band-pass filter. The phase of the frequency response
could also be examined; however, it is more difficult to interpret and less interesting

Lab work:
Using MATLAB
(i) Write a program to implement 8-point DFT and IDFT for a sequence and plot
Q (i) in Pre-Lab. Verify for the Q (i) in Pre-Lab.
(ii) Consider an input sequence x(n) as{ u, u+1, u+2, u+3, u+3, u+2, u+1, u},
given to a filter with an impulse response h(n), {passport number in
digits}.Plot the frequency response, H(ω) of the system.

Post-lab work:
(i) Analyse the type of the filter from the response obtained in Lab work (ii).
(ii) Evaluate the passband and stopband frequencies from the response obtained in
Lab work (ii).
Note:-u is the last digit of your UEL ID.

REFERENCES
1. Mitra.A, S., (2006), “Digital Signal Processing”, 3rd Edition, McGraw-Hill.
2. Mayer-Baese, Uwe. (2007), “Digital Signal Processing with Field
Programmable Gate Arrays”, 3rd Edition, Springer.
3. Proakis and Manolakis, (2005), “Digital Signal Processing”. (3rd Edition),
Prentice Hall.
4. Orfandis, (1996), “Digital Signal Processing”. Prentice Hall.
5. Ifeachor and Jervis, (2003), “Digital Signal Processing”. Wiley.
6. Vinay K. Ingle, and Proakis, (2007), “Digital signal processing using
MATLAB”, Thomson book ware companion series.
7. Singh, and Srinivasan, S. (2006), “Digital Signal Processing:
Implementations Uisng DSP Microprocesors with Examples from
TMS320C54xx”, Thomson brooks/cole.