Parallel Schemes of Certain Discrete Orthogonal Transformations
Y. E. Romm, V. V. Zabeglov
Keywords: discrete orthogonal transformations, Walsh transform, Haar transform, wavelet transform, parallel schemes, time complexity
Pages: 54-70
Abstract
The paper describes parallel transformations of the Walsh and Haar transforms with a time complexity O(log2N), as well as the fast wavelet and saw-tooth transforms. The parallel calculation of the basis of the discrete Fourier transform is performed with a time complexity O(1); the parallel algorithm of the fast wavelet transform is estimated as having a time complexity O(log2log2N × log2N).
|
