An efficient algorithm for cyclic convolution based on fast-polynomial and fast-\(W\) transforms (Q5957034)

If \((x(n))^{N- 1}_{n= 0}\) is an arbitrary real vector, then by \[ X(k):= {2\over N} \sum^{N-1}_{n=0} x(n)\sin\Biggl({\pi\over 4}+ {(n+\alpha)(k+ \beta)2\pi\over N}\Biggr),\qquad k= 0,\dots, N-1 \] the discrete-\(W\) transform (DWT) is defined, where \((\alpha,\beta)\in \{(0,0), ({1\over 2},0), (0,{1\over 2}), ({1\over 2},{1\over 2})\}\). Let \(N\) be a power of 2. Using a fast DWT algorithm, polynomial products modulo \(z^N\pm 1\) and cyclic/skew-cyclic convolutions can be computed. Applying a fast DWT algorithm and a fast polynomial transform, the two-dimensional cyclic convolution is calculated. A comparison with other algorithms for two-dimensional cyclic convolution shows a lower arithmetic complexity of the proposed method.