zbMATH — the first resource for mathematics

Fast W transform. Algorithms and programs. (English) Zbl 0682.65087
The author proposes new algorithms for four special discrete W transforms (DWTs). In order to avoid confusion the W transform does not mean the Walsh-transform and was introduced by the author in earlier papers. Let x be a vector of length N, then the W transform X of x is obtained by \(X=W_{N,\alpha}\cdot x,\) where \(W_{N,\alpha}=(w_{jk})\) is the \(N\times N\) DWT-Matrix defined for an arbitrary real number \(\alpha\) by \(w_{jk}:=\sqrt{2/N}\cdot [\sin (\pi /4+(j+\alpha)k(2\pi /N))],\) \(j,k=- (N-1)/2\), -(N-3)/2,...,-1/2, 1/2,...,(N-1)/2 for N even and \(j,k=-(N- 1)/2\), -(N-3)/2,...,-1,0,1,...,(N-1)/2 for N odd. The four special transforms are defined \(as:\)
W\({}^ I_ N=\sqrt{2/N}[\sin (\pi /4+mn\) \(2\pi\) /N)], \(W_ N^{II}=\sqrt{2/N}[\sin (\pi /4+m(n+1/2)2\pi /N)],\)
W\({}_ N^{III}=\sqrt{2/N}[\sin (\pi /4+(m+1/2)n2\pi /N)]\), \(and\)
W\({}_ N^{IV}=\sqrt{2/N}[\sin (\pi /4+(m+1/2)(n+1/2)\) \(2\pi\) /N)], \(m,n=0,1,...,N-1.\)
These algorithms, which are different from those based on even-odd decomposition, are simple in structure and more efficient than other known algorithms. By utilizing the relationship of the four different types of the DWT the algorithms realize order reduction of the DWT matrices by decomposing the DWT-Matrix into submatrices. This is a well known technique from the decomposition of the DFT-Matrix and leads to a minimum number of additions and multiplications.
Reviewer: Th.Beth

65T40 Numerical methods for trigonometric approximation and interpolation
42A16 Fourier coefficients, Fourier series of functions with special properties, special Fourier series
42A15 Trigonometric interpolation