220 Pages
English

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

-

Gain access to the library to view online
Learn more

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.

Subjects

Informations

Published by
Published 01 January 2009
Reads 21
Language English
Document size 1 MB

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