murphy@pur-phy (William J. Murphy) (10/04/89)
I have a few questions for the dsp experts and amateurs.
I acquire data from two microphones and end up with a file that will
contain N 16-bit samples of the microphone voltages. Since the data is
real, I am considering crunching it with an FFT routine as described by
NUMERICAL Recipes for putting one sequence in the real part of the array and
the other sequence in the complex part. This should half the calculation
time of the FFT.
I have already copied/programmed the FFT routines in pascal/Turbo-Pascal
on a PC, but what I am wondering is if NR's procedure is particularly
fast or slow. I do know that there is a difference in speed between
Microsoft C and TP5.0 of about 2x for doing Mandelbrot calculations for
the same algorithm.
1.) Does anyone have some comparative ratings for the NR routine four1
and other routines in Pascal or C?
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?
Thanks,
--
Bill Murphy murphy@newton.physics.purdue.edumhorne@ka7axd.WV.TEK.COM (Michael T. Horne) (10/05/89)
> 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
harrison@sunny.DAB.GE.COM (Gregory Harrison) (10/12/89)
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.
jrc@hpdml93.HP.COM (Jim Conrad) (10/25/89)
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