2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

1

Development of Complex Curricula for Molecular Bionics and Infobionics Programs within a consortial* framework**
Consortium leader
PETER PAZMANY CATHOLIC  UNIVERSITY
Consortium members
SEMMELWEIS UNIVERSITY, DIALOG CAMPUS PUBLISHER
The Project has been realised with the support of the European Union and has been co-financed by the European Social Fund ***

**Molekuláris bionika és Infobionika Szakok tananyagának komplex fejlesztése konzorciumi keretben
***A projekt az Európai Unió támogatásával, az Európai Szociális Alap társfinanszírozásával valósul meg.

PETER PAZMANY
CATHOLIC UNIVERSITY

SEMMELWEIS
UNIVERSITY

sote_logo.jpg
dk_fejlec.gif
INFOBLOKK

2011.10.06.

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

2

Peter Pazmany Catholic University  
Faculty of Information Technology

Digital-and Neural Based Signal Processing & Kiloprocessor Arrays

Spectral analysis and filter design

www.itk.ppke.hu

Digitális-neurális-, és kiloprocesszoros architektúrákon alapuló jelfeldolgozás

Spektrálanalízis és szûrõtervezés

dr. Oláh András


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

3

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

3

Outline
•
Spectralanalysisofsignals

•
Frequency-domainsamplingandDFT

•
EfficientcomputationofDFT:FastFourierTransformation(FFT)

•
Theradix-2FFT

•
Spectralshapingofsignals:filtering

•
Digitalfilterdesign

•
Linear-PhaseFIRfiltersusingwindows


Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

4

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

4

Spectral analysis of signals
•
TheFouriertransfom(andFourierseries)isanimportantmathematicaltoolsthatisusefulintheanalysisanddesignofLTIsystems.

•
Frequencyanalysisismostconvenientlyperformedonadigitalsignalprocessor.


Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design

A/D

LinearDSP

x(n) 


x(t) 


XC(.) 

x(t) 

x(n) 


xp(n) 


XC(.) 


X(k) 



X(.) 


FT

DTFT

DFT

sampling

sampling

per. rep.

per. rep.

FS

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

5

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

5

Frequency-domain sampling
•
SinceX(.)isperiodicwithperiod2.,onlysamplesinthefundamentalfrequencyrangearenecessary.WetakeNequidistantsamplesintheinterval0..<2.withspacing..=2./N,asshowninnextfigure.



Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


.

X(.)


-.

.

2.


X(k·..)

k·..


..


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

6

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

6

Frequency-domain sampling (cont’)
•
IfweevaulatetheDTFTX(.)at.=2.k/N,weobtain


wherethesummationissubdividedintoaninfinitenumberofsummations,whichfromwechangetheindexintheinnersummationfromnton-lNandinterchangetheorderofthesummation:
fork=0,1,2,...,N-1.

Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

7

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

7

Frequency-domain sampling (cont’)
•
Thexp(n)istheperiodicrepetitionofx(n)everyNsamples,itcanbeexpandedinaFourierseriesas

withFouriercoefficients

Therefore
Itprovidesthereconstructionoftheperiodicsignalxp(n)fromthesamplesofthespectrumX(.).

Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

8

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

8

Frequency-domain sampling (cont’)
•
Ifweconsiderafinite-durationsequencex(n),whichisnonzerointheinterval0.n.L-1,andN.Lsothatx(n)canberecoveredfromxp(n)withoutambiguity.IfN<Litisnotpossibleduetotime-domainaliasing.



Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


x(n)

n

L


xp(n)

n

L


xp(n)

n

N

N . L

N <L 


N



aliasing

no aliasing


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

9

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

9

Frequency-domain sampling (cont’)
•
AssumethatN.L,sincex(n)=xp(n)for0.n.N-1weobtain


•
Wecancompute


•
whereP(.)isthebasicinterpolationfunction:



Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design



2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

10

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

10

Frequency-domain sampling (cont’)
•
Weobservethatthefunctionhastheproperty

•
ConsequentlytheinterpolationformulagivesexactlythesamplevaluesX(2.k/N)for.=2.k/Nandallotherfrequenciesitprovidesaproperlyweigthedlinearcombinationoftheoriginalspectralsamples.


Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


A/D

DFT


X(2.k/N) 

P(.)

x(n) 


x(t) 


X(.) 

Interpolation

Real timeoperation

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

11

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

11

The Discrete Fourier Transform (DFT)
•
TheformulasfortheDFTandIDFTmaybeexpressedas


whereWNisanNthrootofunity.
•
LetusdefineanN-pointvectorxNofthesignalsequencex(n)andanN-pointvectorXNoffrequencysamples,andanNxNmatrixWNas


Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

12

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

12

The DFT as a linear transformation
•
TheN-pointDFTmaybeexpressedinmatrixformas

•
whereWNisthematrixofthelineartransformation.WeobservethatWNisaVandermondetypematrixwiththefollowingproperties:–
det(W).0(›theinverseexists:W-1=1/N·W*,whereW*denotesthecomplexconjugateofthematrixW)

–
WNk+N=WNk

–
WNk+N/2=-WNk

–
WNkM=WN/Mk

•
TheN-pointIDFTmaybeexpressedinmatrixformas

Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

13

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

13

Example
•
ComputetheDFTofthefour-pointsequencex(n)=[0123].

•
ThefirststepistodeterminethematrixW4


•
Thenthesolutionis


Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

14

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

14

DFT applications
•
TheDFTandIDFTarecomputationaltoolsthatplayaveryimportantroleinmanydigitalsignalporcessingapplications:–
Frequencyanalysisofsignals

–
Powerspectrumestimation

–
LinearfilteringmethodsbasedontheDFT

–
DiscreteCosineTransform

–
inOFDMcommunicationtechnology

–
andsoon


Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

15

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

15

Efficient computation of DFT
•
Thegoal:weneedtospeeduptheDFTcalculationaccordingtothereal-timerequirement.

•
Measuresofcomputationalefficiencyingeneral:–
Numberofadditions

–
Numberofmultiplications

–
Amountofmemoryrequired

–
Scalabilityandregularity


•
Forthepresentdiscussionwe’llfocusmostonnumberofmultiplicationsasameasureofcomputationalcomplexity–
Morecostlythanadditionsforfixed-pointprocessors

–
Samecostasadditionsforfloating-pointprocessors,butnumberofoperationsiscomparable


Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

16

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

16

Fast Fourier Transformation
•
WhatistheFFT?–
Acollectionof“tricks”thatexploitthesymmetryoftheDFTcalculationtomakeitsexecutionmuchfaster.

–
SpeedupincreaseswithDFTsize.

•
History–
~1880-algorithmfirstdescribedbyGauss

–
1965-algorithmrediscovered(notforthefirsttime)byCooleyandTukey

–
1984-Split-radixFFTisduetoDuhamelandHollmann

•
ThedevelopmentofcomputationallyefficientalgorithmsforDFTismadepossibleifweadopta„divide-and-conquer”approach.

Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

17

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

17

Divide-and-conquer approach
•
Nisfactoredasaproductoftwointegers:N=LM

•
Thesequencex(n)canbestoredasatwo-dimensionalarrayindexedbylandm:


•
Weusecolunm-wisemappingforx(n):


n=m·L + l


Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design

x(0)
 x(L)
 x(2L)
 ...
 x((M-1)·L)
 
x(1)
 x(L+1)
 x(2L+1)
 ...
 x((M-1)·L+1)
 
x(2)
 x(L+2)
 x(2L+2)
 ...
 x((M-1)·L+2)
 
...
 ...
 ...
 ...
 ...
 
x(L-1)
 x(2L-1)
 x(3L-1)
 ...
 x(LM-1)
 

m

0

L-1

.
.
.

0

M-1

.    .    .

l


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

18

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

18

Divide-and-conquer approach (cont’)
•
TheDFTX(k)canbestoredaswellasatwo-dimensionalarrayindexedbypandq:


•
Weuserow-wisemappingforX(k):


K=M·p + q


Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design

X(0)
 X(1)
 X(2)
 ...
 X(M-1)
 
X(M)
 X(M+1)
 X(M+2)
 ...
 X(2M-1)
 
X(2M)
 X(2M+1)
 X(2M+2)
 ...
 X(3M-1)
 
...
 ...
 ...
 ...
 ...
 
X((L-1)·M)
 X((L-1)·M+1)
 X((L-1)·M+2)
 ...
 X(LM-1)
 


q

p

0

L-1

.
.
.

0

M-1

.    .    .


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

19

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

19

Divide-and-conquer approach (cont’)


•
Withthesesimplificationitcanbeexpressedas


ItinvolvesthecomputationofDFTsoflengthMandlengthL.
•
Wecansubdividethecomputationintothreesteps.


Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


1

2

3


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

20

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

20

Divide-and-conquer approach (cont’)


1.
First,wecomputeLtimestheM-pointDFTs:

2.
Wecomputethemultiplications:

3.
Finally,wecomputeMtimestheL-pointDFTs:


Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


1

2

3


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

21

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

21

Divide-and-conquer approach (cont’)
•
Thecomputationalcomplexityis

–
Complexmultiplication:


–
Complexadditions:

•
Forexample,N=M·L=500·2,theninsteadoftoperform106complexmultiplicationsviadirectcomputationofDFT,thismethodleadsto503.000complexmultiplicationthatrepresentsareductionbyaboutafactorof2.

•
IfNcanbefactoredintoaproductofprimenumbersoftheform


N=i1·i2·...· i.
•
thenitleadstoamoreefficientcomputationalalgorithms.


Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


1

2

3


1

2

3


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

22

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

22

Radix-2 FFT algorithms
•
OfparticularimportanceisthecaseinwhichN=r.,wherenumberriscalledtheradixoftheFFTalgorithm.ThemostwidelyusedFFTalgorithmsaretheRadix-2algorithms.

•
ThetotalnumberofcomplexmultiplicationisN/2·log2(N)andthecomplexadditionsisN·log2(N).Thecomplexityreductioniscomparedinthetable:


Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design

N
 .=N2/[N/2·log2(N)]
 
16
 8
 
32
 12.8
 
64
 21.3
 
128
 36.6
 
256
 64
 
512
 113.8
 
1024
 204.8
 

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

23

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

23

Decimation-in-time radix-2 FFT algorithms
•
Thedecimation-in-timebasedonthedecimationofthedatasequencewhichcanberepeatedagainandagainuntiltheresultingsequencesarereducedtoone-point.Thebasiccomputation(2-pointDFT)isthebasicbutterfly:


•
WherethesignalflowgraphnotationdescribesthethreebasicDSPoperations:–
Addition

–
Multiplicationbyaconstant

–
(anddelay)


Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design

a

b

-1


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

24

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

24

Three stages in the computation of an N=8-point DFT

Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design

2-point
DFT

2-point
DFT

2-point
DFT

2-point
DFT

Combine 2-point 
DFT’s

Combine 2-point 
DFT’s

Combine 4-point 
DFT’s

x(0)

x(4)

x(2)

x(6)

x(1)

x(5)

x(3)

x(7)

X(0)

X(1)

X(2)

X(3)

X(4)

X(5)

X(6)

X(7)


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

25

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

25

8-point decimation-in-time FFT
•
Eg.:x(n)=[11110000]


Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

26

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

26

Spectral shaping of signals: filtering

•
Inthefilterdesignprocess,wedeterminethecoefficientsofacausalFIR(orIIR)filterthatcloselyapproximatestheHd(.)desiredfrequencyresponsespecifications.

Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design

Hd(.) 

H(.) 

h(n) 

desired

approximation

Implementation on FIR 
(or IIR) architecture


Filter

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

27

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

27

Filter types

Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design

Lowpass filter

Highpass filter

Bandpass filter

Notch filter

.

X(.)


Hd(.)


.

X(.)



Hd(.)

.

X(.)


Hd(.)


.

X(.)


Hd(.)


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

28

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

28

Lowpass filter
•
Theimpulseresponsehd(n)ofanideallowpassfilterwithfrequencyresponsecharacteristic

•
Theimpulseresponseofthisfilteris

•
Problems:–
Causality

–
Infiniteinduration(FIRimplementation?)

Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design

lowpass_imp_resp.png

Noncausal  

It is phisically unrealizable!

Note: IIR has stability problems.

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

29

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

29

Paley-Wiener Theorem
•
WhatarethenecessaryandsufficientconditionsthatafrequencyresponsecharacteristicH(.)mustsatisfyinorderfortheresultiongfiltertobecausal?

•
Ifh(n)hasfiniteenergyandh(n)=0forn<0,then

Conversely,if|H(.)|issquareintergarbleandiftheintegralisfinite,thenwecanassociate|H(.)|withaphaseresponse.(.),sothattheresultingfilterwithfrfequencyresponse
iscausal.

Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

30

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

30

Characteristics of phisically realizable filters

•
Problem:Given.1,.2,.pand.s,findthelowestcomplexityfilterthatmeetsspecification,accordingto


Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

31

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

31

Digital filter design
•
Approaches:–
Linear-PhaseFIRfiltersusingwindows›oursubject

–
Linear-PhaseFIRfiltersbythefrequency-samplingmethod

–
Optimumequiripplelinear-phaseFIRfilters

–
DesignofIIRfiltersfromanalogfilters•
designbyapproximationofderivatives

•
designbyimpulseinvariance

•
designbythebilineartransformation



Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

32

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

32

Linear-Phase FIR filters using windows
•
InthismethodwebeginwiththedesiredfrequencyresponsespecificationHd(.)anddeterminethecorrespondingimpulseresponsehd(n).Indeed,hd(n)isrelatedtoHd(.)bytheDiscreteTimeFourierTransformation(DTFT):

•
Forexampleinthecaseof


ideallowpassfilter:

Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


lowpass_imp_resp.png


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

33

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

33

Linear-Phase FIR filters using windows
•
Theimpulseresponsehd(n)isinfiniteindurationandmustbetruncatedatsomepoint,sayat|n|=(M-1)/2,toyieldanFIRfilteroflengthM.

•
Truncationisequivalenttomultyplyinghd(n)bya„rectangularwindow”,definedas


•
ThustheimpulseresponseottheFIRfilterbecomes


Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

34

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

34

Illustration

Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


lowpass_imp_resp.png

lowpass_rec_window.png
lowpass_trunc_imp_resp.png

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

35

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

35

Linear-Phase FIR filters using windows
•
TorealizeancausalFIRfilterweneedadelay(M-1)/2:

•
Clearly,g(n)isnoncausalandinfiniteinduration.


Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

36

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

36

The effect of the window function
•
RecallthatmultiplicationofthewindowfunctionwR(n)withhd(n)isequivalenttoconvulationofHd(.)withWR(.):


whereWR(.)istheDTFToftherectangularwindow:

Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design



2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

37

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

37

The effect of the window function

Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

38

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

38

The effect of the window function (cont’)

Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design



Illustrationoftypeofapproximationobtainedatadiscontinuityoftheidealfrequencyresponse.


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

39

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

39

The rectangular window

Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


Main Lobe Width:4./(M+1)
SidelobeMagnitude= -13 db
StopbandAttenuation=-21db


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

40

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

40

The rectangular window

Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


M=51


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

41

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

41

Gibbs phenomena

Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

42

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

42

Window functions for FIR filter design
•
TheGibbseffectisalleviatedbytheuseofwindowsthatdonotcontainabruptdiscontinuitiesintheirtime-domaincharacteristicsw(n),andhavecorrespondinglylowsidelobesintheirfrequency-domaincharacteristicsW(.).

•
SomewindowfunctionsthatpossesdesirableGibbsphenomena:–
Bartlettwindow

–
Hammingwindow

–
Hanningwindow

–
Blackmanwindow

–
...


Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

43

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

43

Bartlett window

Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design

M=11


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

44

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

44

Hanning window

Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design

M=11


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

45

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

45

Hamming window

Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design

M=11


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

46

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

46

Blackman window

Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design

M=11


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

47

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

47

Important characteristics of some window functions

Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design

Window Type
 Peak SidelobeAmplitude
(relative)
[dB]
 Approximate Width of Mainlobe
 Peak Approximation error20 log.
[dB]
 
Rectangular
 -13
 4./(M+1)
 -21
 
Bartlett
 -25
 8./(M+1)
 -25
 
Hanning
 -31
 8./(M+1)
 -44
 
Hamming
 -41
 8./(M+1)
 -53
 
Blackman
 -57
 12./(M+1)
 -74
 


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

48

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

48

Windows based FIR filter design
•
Given.1,.2,.pand.s

1.
Compute


2.
Compute20lg(.)andselectwindowtype

3.
ChoosethefilterorderM,tomeettransitionwidth

4.
Filtercoefficientsaregivenby



Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design



where


Implemetation on 
FIR architecture


2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

49

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

49

Pros and Cons of Window based Design
•
Advantages–
Easytodesign

–
Canbeappliedtogenerallinearsystemdesign

•
Disadvantages–
Exceedsthespecseverywhereexceptattheedgesofthepassbandandstopband

–
.1,.2,cannotbeindependentlycontrolled.Havetodesignmoreconservativelyforthesmallerofthetwo.


:

Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design


Digital-and Neural Based Signal Processing & Kiloprocessor Arrays: Spectral analysis and filter design

2011.10.06..

TÁMOP –4.1.2-08/2/A/KMR-2009-0006 

50

Summary
•
WedevelopedtheDFTbysamplingthespectrumX(.)ofthesequencex(n).

•
Wedevelopedthestructureofthebasicdecimation-in-timeFFT.

•
UseoftheFFTalgorithmreducesthenumberofmultiplicationsrequiredtoperformtheDFTbyafactorofmorethan100for1024-pointDFTs,withtheadvantageincreasingwithincreasingDFTsize.

•
WehavedescribedtheFIRfiltersdesignusingwindows.Historically,itwasthefirstproposedmethodforFIRdesign.Itsmajordisadvantageisthelackofprecisecontrolofdesignparameters.

•
Asageneralrule,FIRfiltersareusedinapplicationswherethereisaneedforalinear-phasefilter.


Nextlecture:Adaptivesignalprocessing.