An AT/sup 2/ lower bound for wavelet transforms in VLSI
Mohan Vishwanath, Robert Michael Owens · 1992
The lower bounds on the area and time complexity of computing the wavelet transforms in VLSI are derived. The discrete wavelet transform (DWT) is shown to have a lower bound that matches the lower bound for the DFT, while it is seen that the discrete short time Fourier transform (DSTFT) is, in general, more difficult to compute. It is shown that for the DWT, AT/sup 2/= Omega (N/sup 2/ log/sup 2/(N)) and for the DSTFT, AT/sup 2/= Omega (N/sup 2/M/sup 2/log/sup 2/(N/sub w/+N)).>