A linear-filtering transform algorithm based on permutations
Charles M. Rader, P. McKenzie · 2005
An algorithm is described which computes the discrete Fourier transform using only the following operations: multiplication by a term of constant frequency; multiplication by a sequence containing only the four numbers ± 1, ± j; permutation of the sequence; convolution with a fixed impulse response; permutation of the convolved sequence, multiplication by a sequence containing only ± 1, ± j, and multiplication by a term of constant frequency. Using charge-coupled devices, the fixed convolution and the multiplications by ± 1, ± j are relatively easy operations. The permutations are also believed to be reasonably easy. The multiplications by constant frequency terms can be ignored in many applications and the resulting "transform" still represents the spectrum and still has a straightforward convolution property.