Title :
A parallel algorithm for DWT and GFT
Author_Institution :
7th Dept., Nat. Univ. of Defense Technol., Changsha, Singapore
Abstract :
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.<>
Keywords :
Fourier transforms; computational complexity; parallel algorithms; transforms; algorithm complexity; digital signal processing; discrete Hartley transform; discrete W transform; fast algorithm; generalized convolution property; generalized discrete Fourier transform; parallel algorithm; unified parallel algorithm; Concurrent computing; Convolution; Discrete Fourier transforms; Discrete transforms; Discrete wavelet transforms; Image processing; Parallel algorithms; Signal processing; Turning;
Conference_Titel :
TENCON '93. Proceedings. Computer, Communication, Control and Power Engineering.1993 IEEE Region 10 Conference on
Conference_Location :
Beijing, China
Print_ISBN :
0-7803-1233-3
DOI :
10.1109/TENCON.1993.327997
