tom@skio.UUCP (Tom Gross) (08/04/88)
I need information about methods to do a Fast Fourier Transform with integer arithmetic. I have heard of a technique called a block integer FFT where the range of the integers is kept track of during the FFT so that the block can be rescaled to keep within integer ranges. I am programming an Hitachi HD6303 microcomputer for instrumentation control and real time data analysis. The type of data will be well known and ranges can be anticipated in advance. Speed is essential and error checking will be sacrificed. Can anyone suggest references or better yet supply sample programs? Thank You
yuval@taux02.UUCP (Gideon Yuval) (08/06/88)
In article <102@skio.UUCP> Tom Gross writes: >I need information about methods to do a Fast Fourier Transform with >integer arithmetic. I have heard of a technique called a block integer >FFT where the range of the integers is kept track of during the FFT so >that the block can be rescaled to keep within integer ranges. If (as you say below) ranges are known in advance, you don't need block-floating-point (which I presume is what "block integer" refers to). >ranges can be anticipated in advance. Speed is essential and error >checking will be sacrificed. The obvious way out is to work with FIXED-point numbers (so many bits integer, so many bits fraction), and then use integer math to fake them out. This is known as "poor man's floating-point", and a good deal of the algorithms are exactly those of (H/W or S/W) floating-point systems. If you can get hold of an Ada compiler, use Ada's fixed-point datatype, and look at the assembly-code expansion to find out how this faking-out is done. -- Gideon Yuval, yuval@taux01.nsc.com, +972-2-690992 (home) ,-52-522255(work) Paper-mail: National Semiconductor, 6 Maskit St., Herzliyah, Israel TWX: 33691, fax: +972-52-558322 (alternative E-mail address: decwrl!nsc!taux01!yuval@uunet.uu.net)