A parallel algorithm for DWT and GFT
Zeng Yonghong · 2002
Discrete W transform (DWT) proposed by Wang (1985) has been used in digital signal processing and other fields. Its fast algorithm has been studied extensively when the number of points is a power of 2, but we have still known little about its fast algorithm in other cases. In this paper, it is shown that a DWT of length N=N/sub 1/N/sub 2/ (N/sub 1/ is odd) can be turned into N/sub 1/ DWT's of length N/sub 2/ and N/sub 2/ DHT's (discrete Hartley transform) of length N/sub 1/ with some very simple operations. Therefore, a unified parallel algorithm for all kinds of DWT is obtained. The complexity of the algorithm is discussed. Also, we have proved that the so-called generalized discrete Fourier transform (GFT) can be computed by DWT, so a unified parallel algorithm for all kinds of GFT is obtained. Finally, a "generalized convolution property" is given.>