A parallel algorithm for DWT and GFT

Author

Zeng Yonghong

Author_Institution

7th Dept., Nat. Univ. of Defense Technol., Changsha, Singapore

Volume

3

fYear

1993

fDate

19-21 Oct. 1993

Firstpage

361

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;

fLanguage

English

Publisher

ieee

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

Type

conf

DOI

10.1109/TENCON.1993.327997

Filename

327997