[go: up one dir, main page]
Scribd
Upload
118 views45 pages

DFT and FFT Chapter 6

The document discusses discrete Fourier transforms (DFT) and fast Fourier transforms (FFT). It covers topics like DFT properties, convolution, windowing functions, and algorithms for DFT and FFT. Specifically, it explains that DFT is used for discrete signals and describes the DFT equation and algorithm. It also discusses FFT as a faster version of DFT using decimation in time or decimation in frequency algorithms.

Uploaded by

Egyptian Bookstore
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
118 views45 pages

DFT and FFT Chapter 6

The document discusses discrete Fourier transforms (DFT) and fast Fourier transforms (FFT). It covers topics like DFT properties, convolution, windowing functions, and algorithms for DFT and FFT. Specifically, it explains that DFT is used for discrete signals and describes the DFT equation and algorithm. It also discusses FFT as a faster version of DFT using decimation in time or decimation in frequency algorithms.

Uploaded by

Egyptian Bookstore
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 45

Discrete and Fast Fourier

Transform
Supervised by : Dr. Neamat Elboghdadly

Presented by : Abdelkareem Fouda


Discrete Fourier Transform

 For continuous signals continuous fourier transform is used (CFT):

 Discrete time transform is the equivalent of CFT used for discrete signals
which obtained by sampling CFT.
The discrete time Fourier transfrom

 DFT equation
DFT algorithm

 DFT can also take another form

 Where the twiddle factor

Where k= 0,1,2,………., N-1


Twiddle factor properties

 Inverse symmetry property :


the necessary information is only in first half (0 : π)
 Periodicity property:
periodic every N
Example : for 4 point DFT , we can see that
W40 = +1
W41 = -j
W42 = -1
W43 = +j
W44 = +1 repeated values at the 4th. instant
Inverse Discrete time Fourier transform
DFT properties :

 Linearity
 Periodicity
 DFT of even and odd sequences
 Circular shift in time
 Circular shift in frequency
1- Linearity

 It means that DFT of signal is equals the Sum of DFT of its linear
combinations
i.e. DFT [y(n)] , where y(n) = x1 + x2 + x3
then DFT [y(n)]= DFT[x1] + DFT[x2] + DFT[x3]

General form :
2- Periodicity
3- DFT of even and odd sequences :

 For Even sequence :


the DFT of an even sequence is purely real , So DFT can be evaluated
using cosine only with symmetric about the midpoint .

Euler’s Formula : ejᶱ = cos (ᶱ) + j sin(ᶱ)


3- DFT of even and odd sequences :

 For Odd sequence :


the DFT of an odd sequence is purely imaginary , So DFT can be evaluated
using sine only with anti-symmetric about the midpoint .

x(n)=-x(-n)
4- Circular shift in time
5-Circular shift in frequency
Convolution:
 Convolution is defined as the overlap between 2 signals or the shared area
between 2 graphs .
 1- Linear convolution :

where the number of outputs = N+M-1


N: length of the sequence
M: length of the impulse sequence
Linear convolution
 How to perform linear convolution
2- circular convolution
Circular convolution
 The matrix approach one sequence rotating via circular shifting :

 Length of h(n) and x(n) must be equal


 In order to convert linear convolution to the equivalent circular one the two
 signals should padded with zeros in order to make the length of the input
 signals equal to the length of overall linear convolution (N+M-1)
Fast convolution

 For the filtering of long sequence data and due to limitations on the memory
size of the digital computer/processor
 The input sequence is divided in to number of blocks and output blocks are
computed for the respective input block
 The output blocks are fitted together to produce the complete output
sequence
 There are 2 methods (fast convolution methods)
1-overlap save
2-overlap add
Overlap save method
 Consider sequence x(n)
 Steps :
1- divide the sequence into subsequences each of length L
2- consider impulse response with length M
3- in circular convolution the 2 signals must be of the same length so we
will padd the sequence with (M-1) zeros at the beginning of the sequence and
padd the impulse with (L-1) zeros .
4-apply circular convolution
5- discard first (M-1) data from the output
Example :
Overlap add method
 Steps :
1- divide the sequence into subsequences each of length L
2- consider impulse response with length M
3- in circular convolution the 2 signals must be of the same length so we
will padd the sequence with (M-1) zeros at the end of the sequence and padd the
impulse with (L-1) zeros .
4-apply circular convolution
5- add (M-1) data from the output
Example :
DFT frequency response characteristics :
 To find the spectrum of a discrete signal we need samples from −∞ to + ∞ to
get X(w).
 In practice we only observe finite window of L samples With finite window
size L:
DFT frequency response characteristics :

 Errors that occur due to finite length sampling:


1-frequency selectivity
2- spectral leakage
3-scalloping loss
DFT frequency response characteristics :

1- frequency selectivity

Frequency selectivity is the ability to resolve different frequency


components of the input signal.
It is also called ‘frequency resolution’
DFT frequency response characteristics :
 1- Spectral leakage

 When a signal consists only of frequencies of integer multiples of fs /N


 Those frequencies have non zero coeff. while others are zero

 While when a signal consists of frequencies of non-integer multiples of Ts

 DFT coeff. Are no longer zero for frequencies Not in the original infinite
length signal.
 Because of the high side lobes , single tone signal will be spread among
several frequencies which will make it very hard to find the actual freq.
DFT frequency response characteristics :
 3-scalloping loss
 Definition :
Scalloping is the name used to describe fluctuations in the overall
magnitude response of an N-point DFT.
Windowing functions

 Modify DFT output response characteristics.

 Reduce spectral leakage.

 Provide variable resolution .


Windowing functions
 Window characteristics :
 Resolution: capability to distinguish different tones Inversely proportional to
main-lobe width.
 Peak-side lobe level: maximum response outside the main lobe.
Windowing functions
 Rectangular window :
Windowing functions
 The Hann window :
Fast Fourier Transform (FFT)

 The FFT is a faster version of the Discrete Fourier Transform


(DFT).
 FFT requires much less operations than DFT whose complexity is
N2
 There are two types of FFT algorithms :
1- Decimation in time (DIT)
2- Decimation in frequency (DIF)
Fast Fourier Transform (FFT)

 Decimation in time (DIT)


radix 2-fft algorithm
Decompose x[n] into two sequence of length N/2 even-numbered and
odd-numbered
Fast Fourier Transform (FFT)

 Decimation in time (DIT)


Fast Fourier Transform (FFT)

 Decimation in time (DIT)


Fast Fourier Transform (FFT)
 Decimation in time (DIT)
Fast Fourier Transform (FFT)
 Decimation in time (DIT)
Fast Fourier Transform (FFT)
 Decimation in time (DIT)
Fast Fourier Transform (FFT)
 Decimation in frequency (DIF)
Fast Fourier Transform (FFT)
 Decimation in frequency (DIF)
Fast Fourier Transform (FFT)
 Decimation in frequency (DIF)
Fast Fourier Transform (FFT)

You might also like