DISCRETE WAVELET TRANSFORM - DATA DEPENDENCE ANALYSIS AND SYNTHESIS OF DISTRIBUTED-MEMORY AND CONTROL ARRAY ARCHITECTURES

In this paper, we perform a thorough data dependence and localization analysis for the discrete wavelet transform algorithm and then use it to synthesize distributed memory and control architectures for its par allel computation, The discrete wavelet transform (DWT) is characteriz ed by a nonuniform data dependence structure owing to the decimation o peration (it is neither a uniform recurrence equation (URE) nor an aff ine recurrence equation (ARE) and consequently cannot be transformed d irectly using linear space-time mapping methods into efficient array a rchitectures, Our approach is to apply first appropriate nonlinear tra nsformations operating on the algorithm's index space, leading to a ne w DWT formulation on which application of Linear space-time mapping ca n become effective, The first transformation of the algorithm achieves regularization of interoctave dependencies but alone does not lead to efficient array solutions after the mapping due to limitations associ ated with transforming three-dimensional (3-D) algorithm onto one-dime nsional (1-D) arrays, which is also known as multiprojection, The seco nd transformation is introduced to remove the need for multiprojection by formulating the regularized DWT algorithm in a two-dimensional (2- D) index space, Using this DWT formulation,,ve have synthesized two VL SI-amenable linear arrays of L PE's computing a J-octave DWT decomposi tion with latencies of M and 2M-1, respectively, where L is the wavele t filter length, and M is the number of samples in the data sequence, The arrays are modular, regular, use simple control, and can be easily extended to larger L and J. The latency of both arrays is independent of the highest octave J, and the efficiency is nearly 100% for any M with one design achieving the lowest possible latency of M.