Algorithm, application mapping, design and realization of the time-frequency representation with flexible kernels based on their lifting scheme [Elektronische Ressource] / von Andre T. Guntoro
220 pages
English
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Algorithm, application mapping, design and realization of the time-frequency representation with flexible kernels based on their lifting scheme [Elektronische Ressource] / von Andre T. Guntoro

-

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
220 pages
English

Description

Technische Universita¨t Darmstadt, Institute of Microelectronic SystemsAlgorithm,ApplicationMapping,DesignandRealizationoftheTime-FrequencyRepresentationwithFlexibleKernelsbasedontheirLiftingSchemeAndre GuntoroPh.D. Thesis, June 2009Copyright © 2009Institute of Microelectronic SystemsTechnische Universita¨t DarmstadtKarlstr. 15, D-64283 Darmstadt, GermanyAlgorithm,ApplicationMapping,DesignandRealizationoftheTime-FrequencyRepresentationwithFlexibleKernelsbasedontheirLiftingSchemeVomFachbereichElektrotechnikundInformationstechnikderTechnischenUniversita¨tDarmstadtzurErlangungdesakademischenGradeseinesDoktor-Ingenieurs(Dr.-Ing.)genehmigteDissertationvonM.Sc.AndreT.Guntorogeborenam13.Juli1979inIndramayu,IndonesienReferent: Prof.Dr.Dr.h.c.mult.ManfredGlesnerTechnischeUniversita¨tDarmstadtKorreferent: Prof.Dr.-Ing.Dr.h.c.NorbertFliegeUniversita¨tMannheimTagderEinreichung: 30.06.2009Tagdermu¨ndlichenPru¨fung: 05.11.2009D17Darmstadt2009buatpapa...“Theremustbeabeginningofanygreatmatter,butthecontinuinguntotheenduntil itbethoroughlyfinishedyieldsthetrueglory.”SirFrancisDrakeAcknowledgmentsMy very first thank you goes to Jesus Christ for his unconditional loving. Without yourpassionandendlessblessing,Iwon’tbeabletostandstrong andaccomplishmanygreatachievements.I’d like to thank Prof. Manfred Glesner for his guidance and for giving me the op-portunity to be involved in various projects. Also I’d like to thank Prof.

Sujets

Informations

Publié par
Publié le 01 janvier 2009
Nombre de lectures 21
Langue English
Poids de l'ouvrage 1 Mo

Exrait

TechnischeUniversita¨tDarmstadt,InstituteofMicroelectronicSystems

Algorithm,ApplicationMapping,
DesignandRealizationof
theTime-FrequencyRepresentation
withFlexibleKernelsbasedon
theirLiftingScheme

AndreGuntoro

Ph.D.Thesis,June2009

Copyright

©

9002

InstituteofMicroelectronic

Systems

TechnischeUniversita¨tDarmstadt

Karlstr.15,D-64283Darmstadt,Germany

Algorithm,ApplicationMapping,
DesignandRealizationof
theTime-FrequencyRepresentation
withFlexibleKernelsbasedon
theirLiftingScheme

VomFachbereichElektrotechnikundInformationstechnik
derTechnischenUniversita¨tDarmstadt
zurErlangungdesakademischenGradeseines
Doktor-Ingenieurs(Dr.-Ing.)
genehmigteDissertation
nov

.cS.MAndreT.Guntoro
geborenam13.Juli1979
inIndramayu,Indonesien

Referent:Prof.Dr.Dr.h.c.mult.ManfredGlesner
TechnischeUniversita¨tDarmstadt
Korreferent:Prof.Dr.-Ing.Dr.h.c.NorbertFliege
Universita¨tMannheim
TagderEinreichung:30.06.2009
Tagdermu¨ndlichenPru¨fung:05.11.2009

71DDarmstadt2009

“There

tsum

eb

a

beginning

ubta

papa...

ofanygreatmatter,

butthecontinuinguntotheenduntilitbe

thoroughlynishedyieldsthetrueglory.”

SirFrancisDrake

Acknowledgments

MyveryrstthankyougoestoJesusChristforhisunconditionalloving.Withoutyour
passionandendlessblessing,Iwon’tbeabletostandstrongandaccomplishmanygreat
achievements.
I’dliketothankProf.ManfredGlesnerforhisguidanceandforgivingmetheop-
portunitytobeinvolvedinvariousprojects.AlsoI’dliketothankProf.NorbertFliege
whokindlyacceptedtoactasareviewerforthisthesis.FurtherI’dliketothankProf.
AbdelhakZoubir,Prof.Ju¨rgenAdamyandProf.GerdBalzerforactingasmembersof
theexaminationcommittee.
I’dliketoexpressmysincerelythankstoallcolleaguesattheinstituteforgivingme
suchawarmworkingatmosphere.ForthesupportandkindnessthatItastedduring
mywork,I’dliketoexpressmygratitudetoOanaMutihac,MassoudMomeni,Hans-
PeterKeil,TudorMurgan,AndreasSchmidt,PetruBacinschi,PingZhao,OliverSoffke
andHeikoHinkelmann.AlsoI’dliketothanktheolderandformercolleaguesLukusa
KabulepaandMatthiasRychetskyfortheiradvices.
Livinginaforeigncountryisfullofchallanges.That’swhyI’dliketospecically
thankAlvinKurnadi,EllisBong,ChristinaWibisono,NicoleIrwanto,ConnyMan,Susi
Schmidt,HendrinaPattiradjawaneandHennySchwo¨belforbeingthereforme.Espe-
cially,I’dliketothankSerenaSuprawotoforbeingagoodfriendsincetheolddaysand
forherexcellentEnglishexpertise.Forthewarmthwelcome,spiritualsupports,kind-
ness,friendshipandgoodfoodsofcourse,I’dliketoexpressmygratefulnesstoChristian
communityPERKIDarmstadt(nowJKI).AlsoI’dliketothankJochenSpringmannfor
givingmeadvicesandforsharingyourworries.MyspecialthankyougoestoThomas
Rinkforlisteningtomyproblemsandburdens,supportingmethroughtheyearsand
bringingthenewfelicityeveryday.
I’dliketodedicatethisthesistomylatefather.Thankyoufornotgivinghopeonme
andbelievinginme.I’dliketogreatlythankmymother,brothersandsistersfortheir
love,unconditionalsupports,care,trust,inspirationandencouragement.Thankyoufor
givingmethebestplacetogrowup.WithoutyouandyoureducationIdon’tknowwhat
Iwouldbe.

vii

Darmstadt,November2009

iiiv

ACKNOWLEDGMENTS

Abstract

Waveletshavebecomeahottopicinbothindustryandresearcheldsintherecentyears.
InthetransformblockofJPEG2000,twodifferentwaveletlterscanbeapplieddepend-
ingonthecompressionmethods:(5,3)forlosslessand(9,7)forlossycompression.Besides
theblocktransformofJPEG2000,wavelettransformsareappliedinmanyotherapplica-
tions,suchasfeaturedetection,voicesynthesis,statistic,etc.Themajorchallengeinthe
wavelettransformsisthatthereexistdifferentclassesofwaveletltersfordifferentkinds
ofapplications.
Inthisthesis,weproposegeneralizedlifting-basedwaveletprocessorsthatcanper-
formvariousDWTdecompositionsandreconstructions,aswellasDWPdecompositions
andreconstructionswithdifferenttypesofwaveletlters.Theprocessorsarebasedon
cross-chainedprocessingelementswhichperformpredictionandupdateatomfunctions
ofthelifting-basedtransforms.Twodifferentarithmeticsaredesignedinordertoadapt
withdiversitiesinapplications’demand:xed-pointandoating-pointwaveletproces-
sors.Oneachtypeofarithmetic,twoarchitecturesareproposed:resource-awarearchi-
tecturewhichexploitstime-sharingpropertyofthearithmeticunitsandhasprocessing
speedoff/2,andhigh-performancearchitecturewhichusesdedicatedarithmeticunits
andhasprocessingspeedoff.Thegeneralizationoftheproposedwaveletprocessorsex-
tendsinmanyways.TheproposedprocessorscancomputeN-dimensionaltransforms,
aswellasmultileveltransformsfor1Dsignal.Onsomeapplicationsthatrequireenergy
conservationduringthetransforms,wealsoconsiderthenormalizationstepwhichtakes
placeattheendofthedecompositionoratthebeginningofthereconstruction.Ourpro-
posedwaveletprocessorscanalsobeconguredtohavearbitrarydatawidth,including
thefractionsizeoftheoating-pointarchitectures.Becausedifferentapplicationsrequire
differentnumberofsamplesforthetransforms,weproposeaexiblememorysizethat
canbeimplementedinthedesign.Tocopewithdifferentwaveletlters,wefeaturea
multi-contextcongurationtoselectamongvarioustransforms.Thiscontextswitchis
furtherusedasacongurationtooltocomputewaveletlterswithlongerliftingsteps.
OurwaveletprocessorsaremodelledandsynthesizedwithaparameterizableVHDL
codewrittenattheRTLlevel.Theperformanceofourprocessorsvariesdependingonthe
datawidthselections,thearchitecturetypes,andthewaveletlters.For32-bitresource-
awareoating-pointarchitecture,theproposedprocessorcancomputelosslessJPEG2000
transformof512×512imagewith211fps.

xi

Kurzfassung

IndenletztenJahrenwurdenWaveletssowohlinForschungalsauchinderIndus-
triesehrumfassenduntersucht.ImTransformationsblockdesJPEG2000Algorithmus
ko¨nnenjenachKompressionsmethodezweiunterschiedlicheWaveletFiltereingesetzt
werden:(5,3)fu¨reineverlustfreieund(9,7)fu¨reineverlustbehafteteKompression.Außer
inderBlocktransformationvonJPEG2000ndenWavelet-FilterihrenEinsatzinvielen
weiterenAnwendungen,wiez.B.Mustererkennung,Sprachsynthese,Statistikusw.Die
gro¨ßteHerausforderungbestehtdarin,dassfu¨runterschiedlicheAnwendungenunter-
schiedlicheKlassenvonWavelet-Filterbestehen.
IndieserDissertationwerdenverallgemeinerteLifting-basierteWavelet-Prozessoren
vorgeschlagen,diesowohlverschiedeneDWT(DiscreteWaveletTransform)Dekompo-
sitionenundRekonstruktionenalsauchDWP(DiscreteWaveletPacket)Dekomposi-
tionenundRekonstruktionenmitverschiedenenTypenvonWavelet-Filterdurchfu¨hren
ko¨nnen.DieProzessorenbasierenaufverkettetenProzesselementen(PE)zurBerech-
nungundAktualisierungvonAtom-FunktionenindenLifting-basiertenTransforma-
tionen.ZweiunterschiedlicheArtenderArithmetikwurdenberu¨cksichtigt,umdie
großeFu¨llevonAnwendungenzuberu¨cksichtigen:Fixpunkt-undGleitkomma-Wavelet-
Prozessoren.Fu¨rbeideArtenderArithmetikwurdenzweiProzessorenentworfen:eine
Resourcen-sparsameArchitektur,diedasZeitteilverfahrenderarithmetischenEinheiten
ausnutztundbeieinerVerarbeitungs-Geschwindigkeitvonf/2betriebenwirdundeine
hochperformanteArchitektur,welchedediziertearithmetischeEinheiteneinsetztundbei
einerVerarbeitungs-Geschwindigkeitvonfbetriebenwird.DieVerallgemeinerungder
vorgeschlagenenWavelet-Prozessorenschla¨gtsichaufvieleArtennieder.DieProzes-
sorenko¨nnensowohlN-dimensionaleTransformationenalsauchMulti-LevelTransfor-
mationeneines1D-Signalsberechnen.Fu¨rmancheAnwendungen,dieeineEnergieer-
haltungwa¨hrendderTransformationdiktieren,betrachtenwirauchdieNormalisierung
amEndederDekompositionbzw.amAnfangderRekonstruktion.Dievorgeschlagenen
Prozessorenko¨nnenfu¨reinebeliebigeDatenbreitekonguriertwerden,auchdieAn-
zahlderMantissenzifferninderGleitkommadarstellungkannbeliebigeingestelltwer-
den.DaunterschiedlicheAnwendungeneineunterschiedlicheAnzahlvonSamplesfu¨r
dieTransformationbeno¨tigen,wirdeineexibleSpeichergro¨ßevorgeschlagen,dieim
Entwurfimplementiertwerdenkann.UmverschiedeneWavelet-FilterzurBerechnung
einerVielzahlvonTransformationenrealisierenzuko¨nnen,wirdeineMulti-KontextKon-

ix

iix

KURZAFSSUNGgurationvorgestellt.DieserKontext-SwitchwirdauchalseinKongurations-Toolzur
BerechnungvonWavelet-Filtermitla¨ngerenLiftingSchritteneingetzt.
DievorgestelltenWavelet-ProzessorenwurdeninparametrisierbaremVHDL-Code
aufRTL-Ebenemodelliertundsynthetisiert.DiePerformanzderProzessorenunter-
scheidensichjenachDatenbreite,ArchitekturtypundWavelet-Filter.Fu¨rdie32-
bitRessourcen-sparsameGleitkomma-ArchitekturkannderProzessoreineverluftfreie
JPEG2000Transformationeines512×512Bildesmit211fpsberechnen.

TableofContents

1

2

IntroductionandOverview
1.1Motivation......................................
1.2ResearchScopeandObjectives..........................
1.3ThesisOutline....................................

WaveletsandWaveletAlgorithms
2.1Time-FrequencyRepresentation..........................
2.1.1TheHeisenbergUncertaintyPrinciple..................
2.2Short-TimeFourierTransform...........................
2.2.1GaborTransform..............................
2.2.2PropertiesofShort-TimeFourierTransform...............
2.2.3DiscreteRepresentationofSTFT.....................
2.3ContinuousWaveletTransform..........................
2.4PropertiesofWavelets...............................
2.4.1AdmissibleCondition...........................
2.4.2Regularity..................................
2.4.3LocalizationAnalysis...........................
2.4.4WaveletTransformofBasicFunctions..................
2.5Time-FrequencyPlane...............................
2.6DiscreteWaveletTransform............................
2.7MultiresolutionSignalAnalysis..........................
2.8Two-ScaleandDecompositionRelations.....................
2.8.1RelationbetweenTwo-ScaleSequences.................
2.8.2RelationbetweenReconstructionandDecompositionSequences..
2.9FilterBanks.....................................
2.9.1DecimationandInterpolation.......................
2.9.2DecompositionandReconstructionAlgorithms............
2.9.3Two-ChannelPerfectReconstructionFilterBank............
2.10PolyphaseRepresentationforFilterBanks....................

ixii

1122

55790101112131416161717191325282920313234363

vix

3

4

TABLEOFCONTENTS

2.11LiftingScheme....................................37

State-of-the-ArtinDiscreteWaveletProcessors41
3.1FilterBanksSystolic-basedArchitectures....................43
3.1.1DWT-SAArchitecture...........................43
3.1.2ArcArchitecture..............................46
J3.2Lifting-BasedArchitectures............................48
3.2.1RecursiveArchitecture...........................49
3.2.21DFoldedArchitecture..........................51
3.2.3RowandColumnProcessorsArchitectures...............53
3.3ArchitecturesforComputingDiscreteWaveletPacket.............55
3.4ConcludingRemarks................................57

ArchitectureDesignConsideration59
4.1AlgorithmandApplicationMapping.......................59
4.2ObservationontheAlgorithmforDiscreteWaveletDecompositionandRe-
construction.....................................64
4.2.1ObservationontheLiftingScheme....................64
4.2.2WaveletTransformandWaveletPacket.................70
4.3DesignAnalysis...................................71
4.4Fixed-PointbasedPE................................72
4.4.1Resource-awareFixed-PointPE......................73
4.4.2High-PerformanceFixed-PointPE....................76
4.5TheNeedofFloating-Point............................79
4.5.1StandardIEEE754Format.........................81
4.5.2Floating-PointMultiplier.........................81
4.5.3Floating-PointAdditionAlgorithm...................84
4.5.44-StageFloating-PointAdderwithThreeInputs............85
4.5.53-StageFloating-PointAdderwithThreeInputs............89
4.5.6Resource-awareFloating-PointPE....................92
4.5.7High-PerformanceFloating-PointPE..................94
4.6ContextSwitchforPE...............................96
4.7CommonComponents...............................100
4.7.1MainFSM..................................101
4.7.2Cong....................................104
4.7.3Memory...................................105
4.7.4Arbiter....................................108
4.7.5SourceandSink...............................108

TABLEOFCONTENTS

vx

4.7.6LatencyCounter..............................110
4.8DetailsoftheTransformProcess.........................110
4.8.11DDiscreteWaveletDecompositionforDWT.............111
4.8.21DDiscreteWaveletReconstructionforDWT..............114
4.8.31DDiscreteWaveletDecompositionforDWP.............116
4.8.41DDiscreteWaveletReconstructionforDWP..............119
4.8.5N-DimensionalDWTDecompositionandReconstruction.......120
4.8.6N-DimensionalDWPDecompositionandReconstruction.......122
4.9ConcludingRemarks................................123

5AnalysisonPerformanceandBenchmarks125
5.1AnalysisonFloating-PointArithmeticCores..................127
5.1.12-StageFloating-PointMultiplier.....................127
5.1.24-StageFloating-PointAdder.......................128
5.1.33-StageFloating-PointAdder.......................130
5.1.4DiscussionontheFloating-PointCores.................131
5.2AnalysisonDifferentTypesofPEs........................132
5.3AnalysisonDifferentNumberofPEs.......................136
5.4AnalysisonDifferentMemoryOrganizations..................138
5.5AnalysisonSupportingWaveletPacket.....................140
5.6Performances....................................142
5.6.1Performanceson1DSignals........................142
5.6.2Performanceson2DSignals........................148
5.7Benchmarks.....................................151
5.8Comparisons.....................................155
5.9ConcludingRemarks................................157

6ConclusionsandFutureWorks159
6.1ContributionsoftheWork.............................160
6.2DirectionsforFutureWork.............................161

AFourierAnalysis163
A.1FourierSeriesandFourierTransform.......................163
A.2Discrete-TimeFourierTransform.........................166
A.3DiscreteFourierTransform.............................167

BOrthogonal,Biorthogonal,andSemiorthogonal

CFactoringWaveletFilterstoLiftingSteps

961

371

ivx

References

ListofPublications

Supervised

Theses

TABLEOFCONTENTS771

971

811

ListofAbbreviations

TWCTFDTFTDTWDPWDTOCBETFFOFIFPFAGMSFGEPJDOLPOLCAMARMFDPEPMDFODMISRNSTFTS

ContinuousWaveletTransform
DiscreteFourierTransform
Discrete-TimeFourierTransform
DiscreteWaveletTransform
DiscreteWaveletPacket
EmbeddedBlockCodingwithOptimizedTruncation
FastFourierTransform
FirstInFirstOut
FieldProgrammableGateArray
FiniteStateMachine
JointPhotographicExpertsGroup
Leading-OneDetector
Leading-OnePredictor
Multiply-and-Accumulate
MultirateSignalAnalysis
ProbabilityDensityFunction
ProcessingElement
OrthogonalFrequencyDivisionMultiplexing
SingleInstructionMultipleData
Signal-to-NoiseRatio
Short-TimeFourierTransform

iivx

ListofSymbols

b,a n,mhg˜hg˜VjWjPUP

oMhterufntcinoScalingfunction
Waveletexpansions
Discretewaveletexpansions
Low-passsynthesisfunction
High-passsynthesisfunction
Low-passanalysisfunction
High-passanalysisfunction
Scalingspaces
Waveletspaces
Predictionfunction
Updatefunction
Polyphasematrix

xix

ListofTables

4.1TheltercoefcientsofDaub-12forthecompactlysupportedwavelet....63
4.2Truthtableofpossibleresultingfractionaftertheunsignedmultiplication..83
4.3Descriptionoftheparametersstoredincongurationblock..........105
4.4Arbitrationofthememorybusownership....................108
4.5Initializationvalues.................................112

5.1Estimatedareaandfrequencyoftheoating-pointmultiplier.........128
5.2Estimatedareaandfrequencyofthe4-stageoating-pointadder.......129
5.3Estimatedareaandfrequencyofthe3-stageoating-pointadder.......130
5.4Fixed-pointmapping.................................132
5.5EstimatedareaandfrequencyofthenormalPEsandthePEswithnormal-
izerthatarebasedonxed-pointarithmetics...................133
5.6EstimatedareaandfrequencyofthenormalPEsandthePEswiththenor-
malizerthatarebasedonoating-pointarithmetics...............133
5.7Detailsofareausageofthexed-pointPEs(allvaluesareinm2).......135
5.8Detailsofareausageoftheoating-pointPEs(allvaluesareinm2).....135
5.9Estimatedareaandfrequencyofthexed-pointwaveletprocessorswith
differentnumbersofPEs..............................137
5.10Estimatedareaandfrequencyoftheoating-pointwaveletprocessorswith
differentnumbersofPEs..............................137
5.11Estimatedareaandfrequencyofthexed-pointwaveletprocessorswith
differentmemorycongurations..........................138
5.12Estimatedareaandfrequencyoftheoating-pointwaveletprocessorswith
differentmemorycongurations..........................139
5.13Detailsofareausageofthexed-pointwaveletprocessorswithdifferent
memorycongurations(allvaluesareinm2)..................139
5.14Detailsofareausageoftheoating-pointwaveletprocessorswithdifferent
memorycongurations(allvaluesareinm2)..................140

xxi

iixx

1.55

61.5

71.5

1.58

91.5

02.5

512.

22.5

LISTOFTABLESEstimatedareaandfrequencyofthexed-pointwaveletprocessorswith-
outandwithDWPsupport.............................141

Estimatedareaandfrequencyoftheoating-pointwaveletprocessorswith-
outandwithDWPsupport.............................141

Decompositionliftingcoefcientsof(9,7),Daub-4,Daub-6,Symlet-6,and
Coiet-2waveletlters...............................143

Benchmarksfor1Dsignalwith(5,3)lter.....................152

Benchmarksfor1Dsignalwith(9,7)lter.....................153

BenchmarksforJPEG2000with(5,3)lter.....................154

BenchmarksforJPEG2000with(9,7)lter.....................154

Comparisonwithotherlifting-basedarchitectures................156

ListofFigures

2.1Twoelementaryoperationsonabasisfunctionfandtheireffectsonthe
time-frequencyplane[?]...............................
2.2TimeshiftandfrequencyshiftoperationonSTFTandtheireffectontime-
frequencyplane[?]..................................
2.3Time-frequencyplaneofdifferentbases[?,?,?]..................
2.4Latticestructureoflocalizationofthediscretewaveletsintime-frequence
plane[?,?].......................................
2.5HierarchicalstructureofMRAsubspaces[?]...................
2.6Two-scalerelationsforHaarwavelet[?]......................
2.7DecompositionrelationsforHaarwavelet[?]...................
2.8Diagramofdecimatorandinterpolator[?]....................
2.9Decompositionprocessforaone-levelwaveletdecompositiontree[?]....
2.10Reconstructionprocessforaone-levelwaveletreconstructiontree[?].....
2.11Two-channellterbank[?].............................
2.12Polyphaserealizationofatwo-channellterbank[?]..............
2.13Basicliftingschemewithpredictionandupdatestep[?]............
2.14Waveletdecompositionusingliftingsteps[?]...................

3.1DWT-SAarchitectureproposedbyGrzeszczak[?]................
3.2Filterunitwithlow-passandhigh-passcoefcientsselector[?]........
3.3ArcJarchitectureforrstdecompositionlevel[?].................
3.4ArcJarchitectureforseconddecompositionlevel[?]...............
3.5RecursivearchitectureproposedbyLiao[?]....................
3.61DfoldedarchitectureproposedbyLian[?]...................
3.7Rowandcolumnarchitecture[?]..........................
3.8Dataowfor(5,3)and(9,7)ltermode[?]....................
3.9Basicarchitectureofeachprocessor[?]......................

iiixx

711810252728223334353739304

445464740515454555

vixx

LISTOFFIGURES

3.10FoldedarchitectureforDWP[?]..........................

4.1Liftingschemeofdiscretewaveletdecomposition................
4.2Liftingschemeofdiscretewaveletreconstruction................
4.3Discretewaveletdecompositionthatexerciseslongerwaveletlter......
4.4Stepbystepdiscretewaveletdecomposition...................
4.5LatticestructureliftingstepsofDaubechies-2waveletlter..........
4.6LatticestructureofliftingstepsofCoiet-2waveletlter............
4.7Wavelettransformsusinglterbanks.......................
4.8Waveletpacketsusinglterbanks.........................
4.9Blockdiagramoftheresource-awarexed-pointPEwithonemultiplier
andoneadder.....................................
4.10Multiply-And-Accumulateunit...........................
4.11Timingdiagramofthemultiplexerselectorsrelatedtotheinputsamples..
4.12Blockdiagramoftheresource-awarexed-pointPEwhichislocatedonthe
topandonthebottomofwaveletprocessor....................
4.13Blockdiagramofthehigh-performancexed-pointPEwithtwomultipli-
ersandtwoadders..................................
4.14Blockdiagramofthehigh-performancexed-pointPEwithtwomultipli-
ersandtwoaddersandanadditionalcapabilitytocomputethenormaliza-
tion...........................................
4.15Blockdiagramoftheoating-pointmultiplier..................
4.16Two-InputFloating-PointAdderwithLeading-OneDetector(LOD).....
4.17Two-InputFloating-PointAdderwithLeading-OnePredictor(LOP).....
4.18Thearchitectureof4-stage3-inputoating-pointadder.............
4.19Thearchitectureof3-stage3-inputoating-pointadder.............
4.20Blockdiagramoftheresource-awareoating-pointPEwithonemultiplier
and4-stageadder...................................
4.21Blockdiagramoftheresource-awareoating-pointPEwhichislocatedon
thetopandonthebottomofwaveletprocessor.................
4.22Blockdiagramofthehigh-performanceoating-pointPEwithtwomulti-
pliersand3-stageadder...............................
4.23Blockdiagramofthehigh-performanceoating-pointPEwhichislocated
onthetopandonthebottomofwaveletprocessor................
4.24ContextswitchforthePE..............................
4.25FunctionalunitthatconsistsofaPEanditscontextswitch...........

56

66667696960717173757677787082848586809495969798989

LISTOFFIGURES

vxx

4.26Cross-chainedPEs..................................99
4.27TheProposedWaveletProcessor..........................101
4.28MainFSMthatcontrolsthewaveletprocessor..................102
4.29Thecontentofthememoryusingonebankcongurationonly.........106
4.30Thecontentofthememoryusingtwobanksconguration...........106
4.31SourceFSM......................................109
4.324-level1DDWTwaveletdecomposition......................111
4.333-level1DDWTwaveletdecompositionwithmultipleliftingsteps......113
4.344-level1DDWTwaveletreconstruction......................114
4.353-level1DDWTwaveletreconstructionwithmultipleliftingsteps......115
4.364-level1DDWPwaveletdecomposition......................116
4.37Timingdiagramof1DDWPdecomposition...................117
4.383-level1DDWPwaveletdecompositionwithmultipleliftingsteps......119
4.39Timingdiagramof1DDWPdecompositionwithmultipleliftingsteps....119
4.404-level1DDWPwaveletreconstruction......................120
4.412-level2DDWTdecomposition...........................120
4.42ProcessofaN-level2DDWTdecomposition...................121
4.43Firstlevelandsecondlevel2DDWPdecomposition..............122

5.1Estimatedfrequencyandareaofoating-pointmultiplierforvariousdata
widths.........................................128
5.2Estimatedfrequencyandareaof4-stageoating-pointadderforvarious
datawidths......................................129
5.3Estimatedfrequencyandareaof3-stageoating-pointadderforvarious
datawidths......................................130
5.4Estimatedfrequencyofoating-pointarithmetics................131
5.5Estimatedareaandestimatedfrequencyofresource-awarexed-pointand
oating-pointPEs..................................134
5.6Estimatedareaandestimatedfrequencyofhigh-performancexed-point
andoating-pointPEs................................134
5.7MultilevelDWTusingxed-pointwaveletprocessorswithdifferentdata
widthimplementations...............................144
5.8MultilevelDWPusingxed-pointwaveletprocessorswithdifferentdata
widthimplementations...............................145

xivx

9.5

01.5

.511

521.

LISTOFFIGURESMultilevelDWTusingoating-pointwaveletprocessorswithdifferentdata
widthimplementations...............................147

MultilevelDWPusingoating-pointwaveletprocessorswithdifferentdata
widthimplementations...............................148

2Dimagesources...........

SNRvaluesofvarious2Dimages.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

941.

1.05

Chapter1

IntroductionandOverview

Contents
1.1Motivation.....................................1
1.2ResearchScopeandObjectives.........................2
1.3ThesisOutline..................................2

1.1Motivation

Forthelasttwodecadesthewavelettheoryhasbeenstudiedextensively[?,?,?,?,?]toan-
swerthedemandforbetterandmoreappropriatefunctionstorepresentsignalsthanthe
onesofferedbytheFourieranalysis.ContrarytotheFourieranalysis,whichdecomposes
signalsintosineandcosinefunctions,waveletsstudyeachcomponentofthesignalon
differentresolutionsandscales.Inanalogy,ifweobservethesignalwithalargewindow,
wewillgetacoarsefeatureofthesignal,andifweobservethesignalwithasmallwindow,
wewillextractthedetailsofthesignal.
Oneofthemostattractivefeaturesthatwavelettransformsprovideistheircapability
toanalyzethesignalswhichcontainsharpspikesanddiscontinuities.Thebetterenergy
compactingsupportthewavelettransformsofferandalsothelocalizingfeature[?]ofthe
signalinbothtimeandfrequencydomainsthesetransformssupporthavemadewavelet
outperformstheFouriertransforminsignalprocessingandhasmadeitselfintothenew
standardofJPEG2000[?,?].
Intherecentyears,waveletshavebecomeahottopicinbothindustryandresearch
eldsduetotheadoptionofthewavelettransformsbytheJPEGcommitteeintheirnew
JPEG2000standard.InthetransformblockofJPEG2000,twodifferentwaveletlters
canbeapplieddependingonthecompressionmethods.Forlosslesscompression,(5,3)
lterisusedbecauseithasintegercoefcientsandrequiresnoscaling,whereasforlossy
compression,(9,7)lterisusedbecauseitcanexploitthelocalitypropertyofthesignal

1

2

CHAPTER1INTRODUCTIONANDOVERVIEW

bettercomparedto(5,3)lter.Alongwithrecenttrendsandresearchfocusesinapplying
waveletsinimageprocessing,theapplicationofwaveletsisessentiallynotonlylimited
tothisarea.Thebenetsofwaveletshavebeenstudiedbymanyscientistsfromdifferent
eldssuchasmathematics,physics,andelectricalengineering.Intheeldofelectrical
engineeringwaveletshavebeenknownwiththenamemultiratesignalprocessing.Due
tonumerousinterchangingelds,waveletshavebeenusedinmanyapplicationssuchas
imagecompression,featuredetection,seismicgeology,humanvision,etc.
ContrarytotheFouriertransform,whichusesonebasisfunction(anditsinverse)
totransformbetweendomains,therearedifferentclassesofwaveletkernelswhichcan
beappliedonthesignaldependingontheapplication.Becausedifferentapplications
requiredifferenttreatments,researchershavetriedtocopewiththeirownissuesand
implementedonlyasubsetofwaveletswhicharesuitablefortheirownneedssuchas
onesthatcanbefoundinimagecompression[?,?,?,?]andspeechprocessing[?,?,?,?].
Thepowerofwavelettoolsisthenlimitedduetotheseapproaches.

1.2ResearchScopeandObjectives

Inthisthesisweproposeanovelarchitecturetocomputedecomposition(forwardtrans-
form)andreconstruction(inversetransform)ofnumerousDWTs(DiscreteWaveletTrans-
forms)andalsoDWPs(DiscreteWaveletPackets)basedontheirliftingschemerepresen-
tations.Mostlifting-basedwaveletprocessorsarededicatedtocomputewaveletlters
whichareusedonlyinJPEG2000imagecompressionwherethewaveletcoefcientscan
berepresentedasintegersandhavesimplepredictionandupdatefunctions.
Ournewproposedarchitecturetakesintoaccountthateachliftingsteprepresentation
ofanarbitrarywaveletltercanbefactoredtohavetwopredictionorupdatecoefcients,
inordertoreducethenumberofliftingsteps.Additionally,theproposedarchitecture
alsoconsidersthenormalizationstepwhichtakesplaceattheendoftheDWT/DWP
decompositionoratthebeginningoftheDWT/DWPreconstructionfortheapplications
thatrequiretoconservetheenergyduringthetransform.Inordertobeexible,the
proposedarchitectureprovidesamulti-contextcongurationtochoosebetweenvarious
DWT/DWPdecompositionandreconstruction.Becausewavelettransformsworkwith
largenumberofsamples,theproposedarchitecturecanbeconguredtohaveanarbitrary
memorysize(i.e.thepowersoftwo)tocopewiththeapplicationdemands.

1.3ThesisOutline

Therestofthethesisisorganizedasfollows.Thebasicknowledgeofwaveletsarede-
scribedinChap.2.Thischapteralsodiscussesthesecondgenerationofwavelettrans-
forms,whichismorepopularunderthenameofliftingscheme.Chap.3discussesseveral

1.3THESISOUTLINE

3

existingarchitecturestocomputebothDWTandDWPdecompositionandreconstruction.
Twodifferentapproachesaredescribedhere.Itstartsfromthetraditionalwavelettrans-
formsusinglterbanks,followedbythemorerecentlifting-basedapproaches.Chap.4
detailsthealgorithmandapplicationmappingthatmapsthewaveletltersintolifting
schemeinanefcientmanner.Basedonthemappingresults,fourdifferentprocessing
elements(PEs)areproposed.ThesePEsarethemainblockoftheproposedwaveletpro-
cessors.Additionalcomponentsthatmakeuptheprocessorsarealsodetailedhere.The
endofthischapterdescribesseveraltransformprocessesandhowtheyaresupported
andexecutedbyourwaveletprocessors.Chap.5detailstheanalysisofourwaveletpro-
cessors,includingtheperformancesandthebenchmarks.Chap.6concludesthethesis
andshowspossiblefuturedirections.

4

CHAPTER1INTRODUCTIONANDOVEVRIEW

Chapter2

WaveletsandWaveletAlgorithms

Contents
2.1Time-FrequencyRepresentation........................
2.1.1TheHeisenbergUncertaintyPrinciple.................
2.2Short-TimeFourierTransform.........................
2.2.1GaborTransform.............................
2.2.2PropertiesofShort-TimeFourierTransform..............
2.2.3DiscreteRepresentationofSTFT....................
2.3ContinuousWaveletTransform........................
2.4PropertiesofWavelets..............................
2.4.1AdmissibleCondition..........................
2.4.2Regularity.................................
2.4.3LocalizationAnalysis..........................
2.4.4WaveletTransformofBasicFunctions.................
2.5Time-FrequencyPlane..............................
2.6DiscreteWaveletTransform...........................
2.7MultiresolutionSignalAnalysis........................
2.8Two-ScaleandDecompositionRelations...................
2.8.1RelationbetweenTwo-ScaleSequences................
2.8.2RelationbetweenReconstructionandDecompositionSequences.
2.9FilterBanks....................................
2.9.1DecimationandInterpolation......................
2.9.2DecompositionandReconstructionAlgorithms...........
2.9.3Two-ChannelPerfectReconstructionFilterBank...........
2.10PolyphaseRepresentationforFilterBanks..................

5

5790101112131416161717191325282920313234363

6

CHAPTER2WAVELETSANDWAVELETALGORITHMS

2.11LiftingScheme..................................37

Thischapterdescribestheessentialbackgroundsofwavelets.BecauseFourieranaly-
sisisawellknownsignalanalysistool,thediscussionaboutwaveletsisalsopresented
usingthisapproach.Sec.2.1describesthetime-frequencyrepresentationofasignaland
twoelementaryoperationsthatinuencethetime-frequencyplane.Thesolutionofthe
Fourieranalysisintime-frequencyplaneisdetailedinSec.2.2.Sec.2.3startsthediscus-
sionaboutwaveletsinthecontinuous-timedomainandSec.2.4describestheirproper-
ties.Time-frequencyplaneofofthewavelets,alongwithseveralotherbases,aredetailed
inSec.2.5.Sec.2.6continuesthediscussionindiscrete-timedomain.Multiresolution
signalanalysisofthewaveletsiscoveredinSec.2.7andrelationstohaveaperfectrecon-
structionaredescribedinSec.2.8.Sec.2.9detailsthemethodstocomputethewavelet
transformsusinglterbanksandSec.2.10detailsthepolyphaserepresentationofl-
terbanks.Sec.2.11closesthediscussionwithliftingscheme.Somebasicknowledgeof
FourieranalysisareexplainedinApp.A.

2.1Time-FrequencyRepresentation

Time-frequencyanalysisisasubstantialtoolinthemodernsignalprocessing.Additional
insightintothenatureofsignalscanbeachievedoncetheinformationaboutthedistribu-
tionoftheenergyinthosesignalswithrespecttobothtimeandfrequencyareextracted.
Fourierseriesareanidealtooltoanalyzeperiodicsignalsbecausetheharmonicmodes
usedintheFourierexpansionsarethemselvesperiodic.Incontrary,theFouriertransform
isafarlessnaturaltool,becauseitusesperiodicfunctionstorepresentthenonperiodic
signals.CloselylooktoboundaryconditionoftheFouriertransform,itisobviousthat
thetransformcanonlybecarriedoutwhentheentiresignalinthewholeoftherealline
(1,1)isknown.Also,becausethefunctionsej!tareglobalfunctions[?],asmallchange
ofthefunctionatanypointinthetimedomaininuenceseverypointonthefrequency
domainandviceversa.AnotherstudyontheFouriertransformisthatthetransform
canbeevaluatedatonlyonefrequencyatatime.Albeitseveralalgorithmsexisttoper-
formthetransforminthedigitaldomain,suchasFFT,itisnecessarytostorethewhole
sampleddatainthememorybeforethecomputationtakesplace.
AlthoughFourieranalysisisapowerfultoolinsignalprocessing,itbecomesinad-
equatewhenthelocalfrequencycontentsofasignalareinthepointofinterest.Once
thesignalistransformedinthefrequencydomainwiththeFourieranalysis,thetimein-
formationaboutthesignalislost.Asanexample,locationsofthespikesthatoccuron
thepowerlineneedtobedetermined.TheFourieranalysisofthissignalwillgivethe
50/60Hzasthemajorfrequencyinthefrequencyspectrumandcontaininnitesmall
numberofsinusoidalfunctionsassidelobesthatmakeupthespikes(spikescanberep-
resentedasdeltafunctionwhichcontainssharpchanges).Themorethespikesoccur,the

8CHAPTER2WAVELETSANDWAVELETALGORITHMS
canbewrittenas
ft0(t)=f(tt0)(2.1)
Itisclearthatashiftingofafunctionfintimebyt0leadstoashiftingofthetilein
timeaxisbyt0.Likewise,amodulationbyej!0tonafunctionfleadstoashiftingofthe
tileby!0infrequencyaxis.Fig.2.1(a)depictstheschemeoftheeffectofshiftingona
time-frequencyplane.
Afunctionfscaledbyaiswrittenas
fa(t)=f(at)(2.2)
FollowingthescalingpropertyoftheFouriertransform,thescalingoperationleadsto
1It0=It(2.3)
aI!0=aI!(2.4)
whichaltersboththeshapeandthelocalizationofthetile,asdepictedinFig.2.1(b).Note
thatallelementaryoperationsconservethesurfaceofthetime-frequencytile.Inthecase
ofscalingoperation,thefrequencyresolutionistradedfortheresolutionintimeandvice
versa.
2.1.1TheHeisenbergUncertaintyPrinciple
Twoextremecasescanbedrawntoillustratethelocalizationtrade-off.Byhavingabasis
functionf(t)=ej!0t,itsFouriertransformwouldcontainexactlyonefrequency!0
f(t)=ej!0t !F(!)=2(!!0)(2.5)
whichtellsthatitsfrequencycontentiszeroeverywhere,exceptfor!=!0.Itindicates
aperfectlocalizationinthefrequencydomain.Nowifabasisfunctionisadeltafunction
f=(tt0),thetransformpairisgivenby
1f(t)=(tt0) !F(!)=ej!t0(2.6)
2Thefrequencycontentisnonzeroonthewhole!-axis.Thisindicatesaperfectlocaliza-
tioninthetimedomain,butnotinthefrequencydomain.Itisimpossibletogetperfect
localizationinbothtimeandfrequencydomainssimultaneously,asdetailedin[?,?,?].
Ingeneral,theweightedmeansinthetimedomainandinthefrequencydomaincan
beconsideredasprobabilitydensityfunctions(PDFs).Considerafunctionf(t)withits
correspondingFouriertransformF(!)whoseenergyiscenteredaroundat(t0,!0)inboth

2.1TIME-FREQUENCYREPRESENTATION9
timeandfrequencydomains
Rtf(t)2dt
t0=R2

  • Accueil Accueil
  • Univers Univers
  • Livres Livres
  • Livres audio Livres audio
  • Presse Presse
  • BD BD
  • Documents Documents