10
$\begingroup$

I'm using a version of "KISS FFT" by Mark Borgerding. It accepts an array of 16-bit fixed-point input values and produces a 32-bit float result array.

I've discovered that if the input amplitudes are low many of the float result values come out zero, but if I simply scale the inputs (by, say, the factor 16) then fewer output values are zero and therefore the output seems to contain more detail. (Not that it matters much for my purposes, but for consistency I then divide the resulting float values by the same scaling factor.)

Anyway, this seems to work, in terms of producing a result when previously I'd have just gotten a buffer of virtually all zeros, but I'm wondering if there's some reason it might not be a valid approach.

(Note that this approach means that there's a lot more "coarsness"/granularity to the data, and, in particular, the low-level noise that would normally be present is not. I'm almost wondering if it would be wise to inject some low-level noise to replace the zero values in the input.)

$\endgroup$
  • $\begingroup$ "I'm almost wondering if it would be wise to inject some low-level noise to replace the zero values in the input." = en.wikipedia.org/wiki/Dither $\endgroup$ – endolith May 15 '12 at 0:16
7
$\begingroup$

This can be a valid approach. You're observing a very practical issue that arises often when using fixed-point (i.e. integer) arithmetic (although it can happen in floating-point also). When the numeric format that you're using to perform calculations doesn't have enough precision to express the full range of values that can arise from your calculations, some form of rounding is required (e.g. truncation, round-to-nearest, and so on). This is often modeled as an additive quantization error to your signal.

However, for some combinations of algorithm and rounding scheme, when the magnitude of the input signal is very low, it's possible to get what you observed: a large number of zero outputs. Basically, somewhere in the sequence of operations, the intermediate results are becoming small enough to not break the threshold required to quantize to a nonzero level. The value is then rounded to zero, which can often propagate forward to the output. The result is, as you noted, an algorithm that generates a lot of output zeros.

So can you get around this by scaling the data up? Sometimes (there are very few techniques that work all the time!). If your input signal is bounded in magnitude to a value below full-scale of the numeric format (16-bit signed integers run from -32768 to +32767), then you could scale the input signal up to more fully use the range available to it. This can help to mitigate the effects of roundoff error, as the magnitude of any roundoff error becomes smaller in comparison to the signal of interest. So, in the case where all of your outputs are getting rounded to zeros internally to the algorithm, this may help.

When can such a technique hurt you? Depending upon the structure of the algorithm's calculations, scaling the input signal up might expose you to numeric overflows. Also, if the signal contains background noise or interference that is larger in magnitude than the algorithm's roundoff error, then the quality of what you get at the output is going to be typically limited by the environment, not error introduced in the computation.

$\endgroup$
  • $\begingroup$ I'm using a dynamic technique for scaling that seems to work pretty well. And, as luck would have it, extreme transients are treated as noise and clipped anyway, so occasional clipping should not be an issue. Do you think it's valid to "descale" the output by dividing by the input's scale factor? $\endgroup$ – Daniel R Hicks May 15 '12 at 11:44
1
$\begingroup$

The easiest and most fool proof way to deal with this is to convert the data to floating point BEFORE the FFT and use a floating point FFT. The only downside to this approach would be that you may consume more processor and memory. Since your output is floating point anyway, there is probably little practical difference.

$\endgroup$
  • $\begingroup$ I was handed this project with the current FFT algorithm already in place, and I'm reluctant to muck with it at this point. And this is all going on on a phone, in real time, so performance is definitely an issue. $\endgroup$ – Daniel R Hicks May 15 '12 at 11:45
  • $\begingroup$ Understood. Do you know if the FFT internal is fixed or floating point? If it's fixed you need to worry about clipping, overflow and underflow $\endgroup$ – Hilmar May 15 '12 at 14:38
  • $\begingroup$ The documentation and commentary is exceptional in its absence, but I see lots of ints in the code and precious few floats and doubles. It appears to include the crude #ifdef framework for switching from 16-bit to 32-bit or float, but the framework has apparently been long disabled. $\endgroup$ – Daniel R Hicks May 15 '12 at 16:18
  • $\begingroup$ An iPhone (ARM+NEON CPU) can do a float FFT faster (via the Accelerate framework) than an integer FFT in C. $\endgroup$ – hotpaw2 May 17 '12 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.