The poorman's transform: approximating the Fourier transform without multiplication

A time-domain to frequency-domain transformation for sampled signals which is computed with only additions and trivial complex multiplications is described. This poorman's transform is an approximation to the usual Fourier transform, obtained by quantizing the Fourier coefficients to the four values (+or-1, +or-j), and is especially useful when multiplication is expensive. For the general case of an N-point quantization, an analytic formula is given for the error in the approximation, which involves only contributions from aliased harmonics. Continuous-time signals are considered; in this case the approximation is exact for bandlimited signals.>