🚀 go-pugleaf

> 2.)  ...Is there
>      any acceleration available for strictly integer data input versus
>      real input to the FFT routine? i.e. is there an optimization available
>      for integer data?  I assume that regardless of input you will return
>      a real complex spectrum instead of an integer complex spectrum?

You can implement an all-integer FFT by storing your data and sin/cos terms
as scaled integers (i.e. scale all data up some number of bits to preserve
`fractional' results).  I've implemented just such an algorithm, and as long
as you take care in avoiding overflow, it works fine.  One suggestion, however;
Use as many bits as possible to store your data and sin/cos values
so you have sufficient dynamic range.  Using 32-bit integers will provide
reasonable results (depending, of course, on the number of bits of resolution
your original data has).  16-bit integers probably won't provide you with
sufficient dynamic range.  If you're using an 80x86 based box with only 16-bit
registers, you'll have to 1) accept the small word size in exchange for speed,
or 2) do 32-bit math with < 1/2 the speed of 16-bit math.  If you're using a
32-bit processor, then you're in good shape.

>--
>  Bill Murphy        murphy@newton.physics.purdue.edu

Mike

In article <2620@pur-phy> murphy@newton.physics.purdue.edu.UUCP (William J. Murphy) writes:
>
>2.)  Though this shows my naivety about the details of the FFT, Is there
>     any acceleration available for strictly integer data input versus
>     real input to the FFT routine? i.e. is there an optimization available
>     for integer data?  I assume that regardless of input you will return
>     a real complex spectrum instead of an integer complex spectrum?
>
Due to the nature of integer processing on a computer (native units), 
operating on integers will normally be much faster than operating
on floating-point numbers, especially without a floating point
coprocessor chip.  An integer FFT will return integer spectral data.
An integer FFT will lose approximately 1/2 bit of precision for each
level of butterflys in the algorithm.  Thus a 1024 point integer FFT
will lose approximately 5 bits of precision in the conversion from
time-domain to frequency domain.

Thus floating point processing (which does not have the precision loss
problem in this manner) is preferable for larger FFTs.   

Greg Harrison
My opinions are not intended to reflect those of GE.

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