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

Andre Guntoro

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.

Informations

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

Extrait

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.4Pr