FFT resolution in fixed-point implementation

What is the effect of lowered resolution of intermediate results on an FFT?  I
am considering a number of implementation choices for a fixed-point FFT.  The
time-series data is inherently 16-bit integers (audio data).  I want to do a
8192-point FFT on this data.  Because of the need to explicitly handle overflows
(in the butterfly operations)  in a fixed-point implementation,  it is
convenient to limit the resolution of the intermediate results.  There is a
definite tradeoff between speed and how I check for overflow.  I am also limited
by the C language.  Ideally I would like to multiply two 32-bit numbers and
retain the high-order 32 bits of the 64-bit results.  In previous
implementations I have done this nicely in assembly language by changing the
register from the register pair used to save the result.  But this time my
development system does not have the option of compiling C-code to intermediate
assembly code and editing it before assembly.  (I am targeting the ARM processor
in Nokia/Symbian cell phones).  Even though this development system does support
64-bit integers, the performance penalty in promoting all operands to 64 bits
and then carrying out a full 64 x 64 multiply in software is prohibitive.
Another choice is to limit the intermediate results to 13 bits of resolution by
scaling the entire array when necessary.  This would allow me to do a full FFT
round without worrying about overflow.  (My trig tables are 16-bit.)  But I am
concerned about the effect on the resulting FFT if I limit the resolution of
intermediate results to 13 bits.  Since I am doing 13 rounds in my 8192-point
FFT, I wonder if the repeated limitation on the resolution is likely to produce
a power spectrum that has much less than 13 bits of resolution.  Does anyone
know for sure?



Robert Scott
Ypsilanti, Michigan

Robert Scott wrote:
> What is the effect of lowered resolution of intermediate results on an FFT?
> [...]
> Another choice is to limit the intermediate results to 13 bits of resolution by
> scaling the entire array when necessary.  This would allow me to do a full FFT
> round without worrying about overflow.  (My trig tables are 16-bit.)  But I am
> concerned about the effect on the resulting FFT if I limit the resolution of
> intermediate results to 13 bits.  Since I am doing 13 rounds in my 8192-point
> FFT, I wonder if the repeated limitation on the resolution is likely to produce
> a power spectrum that has much less than 13 bits of resolution.  Does anyone
> know for sure?

I don't work with fixed-point FFTs myself, but the number that I recall
is that you lose half a bit of precision, on average, per radix-2
stage, i.e. an error proportional to sqrt(N).  (Floating point is much,
much better, with errors that increase only as log(N) at worst, but
obviously that isn't an option for you.)  Thus, if my memory is
correct, you will lose about 6-7 bits of precision (out of 13) due to
the accumulated error in your 8192-point fixed-point FFT.

For more information, the classic reference seems to be: Peter D.
Welch, "A fixed-point fast Fourier transform error analysis," IEEE
Trans. Audio Electroacoustics, v. 17, p. 151-157 (1969).

Of course, it should be easy to check by just trying it and comparing
the answer to a floating-point FFT.

Regards,
Steven G. Johnson

Robert Scott wrote:
> I am also limited
> by the C language.  Ideally I would like to multiply two 32-bit numbers and
> retain the high-order 32 bits of the 64-bit results.  In previous
> implementations I have done this nicely in assembly language by changing the
> register from the register pair used to save the result.  But this time my
> development system does not have the option of compiling C-code to intermediate
> assembly code and editing it before assembly.  (I am targeting the ARM processor
> in Nokia/Symbian cell phones).

I am not familiar with the processor or its tools you might be able to
use
combinations of intrinsic functions (if your C compiler supports them)
for
performing this kind of arithmetic efficiently. However, you will have
to
mimic the processor operations in C if you want to maintain a bit-exact
model of your system.

C