Fast W transform. Algorithms and programs (Q1824374)

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.