# Faster Fourier Transform Without Multiplication

Original Publication Date: 1983-Apr-01

Included in the Prior Art Database: 2005-Feb-07

## Publishing Venue

IBM

## Related People

## Abstract

A faster technique for obtaining the discrete Fourier Transform of a signal is described where multiplications are avoided by cross-correlating the input signal with square or ladder-like waves rather than with conventional sinusoidal waves. The implementation of the technique consists of an integrator, a sampler and a serial buffer from which partial sums of consecutive samples are obtained and upon which a Fast Fourier Transform-like butterfly operation is applied. This scheme gives directly only the upper 4/5ths of a bandpass signal, but renders an order of magnitude reduction in hardware complexity or calculation time. The rest of the spectrum is obtained by adding to the lower 20 percent a correction factor which is proportional to the upper 80 percent of the band.

**This text was extracted from a PDF file.**

**At least one non-text object (such as an image or picture) has been suppressed.**

**This is the abbreviated version, containing approximately 27% of the total text.**

__Page 1 of 6__**Faster Fourier Transform Without Multiplication **

A faster technique for obtaining the discrete Fourier Transform of a signal is described where multiplications are avoided by cross-correlating the input signal with square or ladder-like waves rather than with conventional sinusoidal waves. The implementation of the technique consists of an integrator, a sampler and a serial buffer from which partial sums of consecutive samples are obtained and upon which a Fast Fourier Transform-like butterfly operation is applied. This scheme gives directly only the upper 4/5ths of a bandpass signal, but renders an order of magnitude reduction in hardware complexity or calculation time. The rest of the spectrum is obtained by adding to the lower 20 percent a correction factor which is proportional to the upper 80 percent of the band. The appropriate choice of parameters provides samples of the spectrum at logarithmic intervals in frequency. Compared to the conventional Fast Fourier Transform (FFT) which requires 4NlogN real additions, 2NlogN real multiplications, and N input buffer locations for a signal spectrum with N samples, the new method uses approximately 10NlogN additions, which may be eliminated altogether in hardware using a delta modulator instead of a sampler and counters in exchange for adders and registers.

Definition of the Square Wave Transform Let sgn(x) be the signum function defined as

1 if x>0

sgn(x)= 0 if x=0

-1 if x<0 and let C(s)(wt),S(s)(wt) be the cosine and sine square-wave functions shown in Fig. 1 and defined by C(s) (wt)D/=sgn(cos(wt)) = (odd) Sigma (-1)/n-1/2/ cos (nwt)/n S(s) (wt)D/=sgn(sin(wt))= (odd) Sigma sin (nwt)/1 n which are written herein in their Fourier series form.

Now, define the square-wave transform to be the function F(s) (jw) = f(t)C(s) (wt)dt + j f(t)S(s) (wt)dt where f(t) is the input function whose spectrum defined as F(jw) = f(t) cos (wt)dt + j f (t) sin (wt)dt = R(Omega) + j1(Omega) is to be determined wherein R(Omega) and I(Omega) are the real and imaginary parts of the spectrum respectively. After substitution of the expressions for the square functions, we obtain F(s) (jw)= Sigma(( - 1)/n-1/2/ f(t) cos (nwt)dt + j f(t) sin (nwt)dt odd 1 wherefrom the expression

F(s)(jw)= Sigma (( - 1) /n-1/2/ R(nw) + j1(nw)) odd 1 or the series

F(s) (jw) = - F(jw)-F*(3jw)/3 + F(j5w) /5 - F*(7jw)/7 + F(j9w)/9 - .....

Suppose that f (t) is bandlimited to have zero components outside

1

__Page 2 of 6__the band w<W. Then we see that the contribution of the third and higher harmonics of the square wave will be zero whenever the fundamental of the square wave is in the range 1/3 W<w>W and thus F(s)(jw) = F(jw) for the latter band of frequencies.

To get the spectrum in the rest of the band, say in the interval 1/5W<w>1/3W, we observe that the square wave spectrum is given by the expression F(jw) = F(jw)-1/3F/*/ (j3w) and thus the true spectrum in this band can be obtained by subtracting from the square spectrum the added...