Fast Algorithms for Discrete Wavelet TransformDWT and FWT: SignificanceFWT Algorithm: An OutlineFWT Algorithm: An Overview (I)Slide 5Slide 6Slide 7Fast Algorithms for Discrete Wavelet TransformReview and Implementationby Dan LiF2000DWT and FWT: Significance DWTDWTMulti-resolution mode to access the information Extensively (and intensively) used in information processingAdvantage over other transformse.g. (in JPEG 2000), DWT provides 20-30% improvement in compression efficiency as oppose to DCT. FWTFWTMulti-resolution mode to access the informationDWT: intensive computation and large memory requirement.FWT makes DWT practicable in real applicationsMain factors controlling the speed of DWT:–Filter length–Floating point operation vs. integer operationFWT Algorithm: An Outline“Regular” StructureMallat Straightfoward Filter Bank Mallat Straightfoward Filter Bank Polyphase Transversal Filters#Polyphase Transversal Filters#Polyphase Short-length Filters*Polyphase Short-length Filters*Classical Lattice Filters Classical Lattice Filters CORDIC Lattice Filters CORDIC Lattice Filters Lifting Scheme and Integer WTLifting Scheme and Integer WTBinomial QMF Filters Binomial QMF Filters (* also known as “fast-running FIR algo”)(* based on FFT for fast filtering)“Irregular” Structure“Irregular” Structure“Regular” Structure“Regular” StructureFWT Algorithm: An Overview (I)H(z)G(z)H(z)G(z)H(z)G(z)x[n]D1D2D3A3A2A1 2 2 2 2 2 2A1D1G0(z)x[n] 2 2H0(z)G1(z)H1(z)x0[n]x1[n-1]z-1x[n] 2 2-z-1z-1H0(z)H0(z)+H1(z)H1(z)-++-+-+D1A1Mallat Filter BankTransversal FiltersShort-length Filtersc0A1D1x[n] 2 2x0[n]x1[n-1]z-1(1+z-1)3(1-z-1)3(1+z-1)2(1+z-1)(1-z-1)(1-z-1)2(1+z-1)2(1+z-1)(1-z-1)(1-z-1)2c1c2-c0c1-c2A1D1112-2-2-2z-111 2 2z-1K’1-2-22-21 -11x[n]-2-42-8 2-16-0-22x[n] 2 2x0[n]x1[n-1]z-1...p1(z)q1(z)p2(z)q2(z)pM(z)qM(z)K1K2A1D1s(0)d(0)s(1)d(1)s(2)d(2)s(M)d(M)x[n] 2 2z-1K’cos 0cos 0 sin0 -sin0cos 1cos 1 sin1 -sin1...A1D1cos Lcos L sinL -sinLz-1z-1-1FWT Algorithm: An Overview (II)Binomial QMFClassical LatticeCORDIC LatticeLifting LadderComput. Complexity: A Comparison051015202530350 10 20 30 40Mallat FBTran.Filter (FFT)Tran.Filter(Short-length)# of multsFilter length L051015202530350 10 20 30 40Mallat FBTran.Filter (FFT)Tran.Filter(Short-length)# of addsFilter length L010203040505 10 15 20Tran.Filter (FFT)Tran.Filter(Short-length)Binomial QMF filtersClassical Lattice CORDIC LatticeWord length w (bits)# of addersneededArithmetic Complexity (per input point & per decomposition cell)Computational Structure Complexity (per filter coefficient)“Efficiency” in the sense of arithmetic complexity and computational structureStraightforward filter bank: classical and used in many commercial s/wPolyphase structure: more efficient than direct FB. (Worthy of further exploration!)FFT based filtering: efficient for medium or long filtersFast running FIR filter: good for short filtersBinomial QMF: reduces the # of mults with expense of additional adds Lattice: easier to implement with each relatively simpler stagesCORDIC: most suitable fore efficient VLSI implementation since only addition and shifts involved and least possible adders requiredLifting scheme: lead to IWT which is faster than floating-point DWT and ideal for lossless coding/compression. Implementation focused on the following:Fast filtering for short and long filters Various formats of polyphase structures Reformulation of polyphase transversal filter with the consideration of reduced inter-channel communicationInteger filter and IWT implementationsSimulations Comments, Implementations,
View Full Document
Unlocking...