Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!wuarchive!brutus.cs.uiuc.edu!apple!sun-barr!decwrl!hplabs!hpda!hpcuhb!hp-ses!hpdml93!jrc
From: jrc@hpdml93.HP.COM (Jim Conrad)
Newsgroups: comp.dsp
Subject: Re: FFT for integer data
Message-ID: <13650001@hpdml93.HP.COM>
Date: 24 Oct 89 20:40:58 GMT
References: <2620@pur-phy>
Organization: Hewlett Packard - Boise, ID
Lines: 28

I worked on an FFT for the Data General NOVA (slow by today's personal
computer standards) in 1972/3.  It was capable of finding the magnitudes
of a 1024 pt buffer in 1.03 seconds.  Key points of the algorithm were:

	1) Two transform buffers (real and imag) of 16 bit integers.

	2) One 16-bit scale factor for an entire buffer (I believe that one
	scale factor served both the real and the imag buffers).  The
	actual value of a datum in the buffer was X*(2**S) where X was
	a datum and S was the scale factor.

	3) Whenever an operation was about to overflow, the entire
	buffer was scaled (shifted left or right one bit) and the scale
	factor modified accordingly.  Then the operation was retried.

	3) Trig values were scaled such that 010000 (octal) was PI.

	4) Table lookup (based upon the retrieval sequence) for trig values.

The algorithm was capable of maintaining three significant digits from the time
domain into the frequency domain.

This work was never published to the best of my knowledge, but was done under
the direction of Dr. Donald Hagen of the Cloud Physics Research Center at
the Univ of Mo - Rolla.

Jim Conrad
jrc@hpbsrl