FPGA Central

Hello,

I want to try using an fixed point based FFT routine instead of the current
floating point based routine. I have a user of my software that has a 800
Mhz VIA chipset motherboard, and the FPU on that thing is so bad, it can't
crunch an audio signal in real time (i.e. - while they are talking). On
non-VIA systems the computer is able to keep up in real time (it's a speech
recognition app.)

I found the KISS FFT project on SourceForge which is able to do fixed point
FFT as well as floating point

http://sourceforge.net/projects/kissfft/

However, when I use it compiled with fixed point data values, I get erratic
tiny values for the output complex data values. When compiled with floating
point values it matches closely the original FFT routine's outputs.

So it appears I don't know how to convert floating point values to fixed
point values. I found a post by the author of KISS FFT that said this:

"If you're not familiar with fixed point math, here's a crash course:

A common format for fixed point calculations is to use 15bits of a 16 bit
signed integer to represent the fractional part of a number from -1 to 1.

In other words, the range of a 16 bit integer (-32768:32767) is mapped to
(-1:.99997)

Note that 32768 cannot be represented as a 16 bit signed integer, thus
xfloat cannot equal 1.

So define xfix := round( xfloat * 32768) , where -1 <= xfloat < 1"

I want to be clear about what I don't understand about converting floating
point values to fixed point values.

Given the above and a floating point sample value such as 1000.4897 (as an
example), am I remapping 1000.4897 to a number between -1 and .99997?

Or am I just remapping the fractional portion (0.4897) to -1 and .99997?

If it's the latter case, am I supposed to create two fixed point values for
each floating point value, one for the integer portion of the floating point
number (1000) and one for the fractional portion (0.9997)?

Thanks,
Robert

"Robert Oschler" <[email protected]> writes:

> Hello,
>
> I want to try using an fixed point based FFT routine instead of the current
> floating point based routine. I have a user of my software that has a 800
> Mhz VIA chipset motherboard, and the FPU on that thing is so bad, it can't
> crunch an audio signal in real time (i.e. - while they are talking). On
> non-VIA systems the computer is able to keep up in real time (it's a speech
> recognition app.)
> [...]

Robert,

My gut feeling is that you're running off blindly in the wrong direction.
Firstly I don't think the FFT is the bottleneck, and even if it were, on
a machine like the Pentium, the floating point performance is probably
better than the fixed-point performance.

I'll bet that your speech recognition app was written sloppily in C and
needs to be profiled to see exactly where the major MIPS are being
wasted.

I could be wrong - this is all gut and hip. Besides, you can't really
convert just the FFT from floating-point to fixed-point - the input
dynamic range is undefined. You really need to analyze the entire
system from input to the FFT, and that is probably going to be very
involved (months, not hours).

--RY

--
Randy Yates
Sony Ericsson Mobile Communications
Research Triangle Park, NC, USA
[email protected], 919-472-1124

Randy Yates wrote:
> "Robert Oschler" <[email protected]> writes:
>
>
>>Hello,
>>
>>I want to try using an fixed point based FFT routine instead of the current
>>floating point based routine. I have a user of my software that has a 800
>>Mhz VIA chipset motherboard, and the FPU on that thing is so bad, it can't
>>crunch an audio signal in real time (i.e. - while they are talking). On
>>non-VIA systems the computer is able to keep up in real time (it's a speech
>>recognition app.)
>>[...]
>
>
> Robert,
>
> My gut feeling is that you're running off blindly in the wrong direction.
> Firstly I don't think the FFT is the bottleneck, and even if it were, on
> a machine like the Pentium, the floating point performance is probably
> better than the fixed-point performance.

I have experience both ways with Pentiums -- the best thing is to benchmark.
>
> I'll bet that your speech recognition app was written sloppily in C and
> needs to be profiled to see exactly where the major MIPS are being
> wasted.

No disagreement here.
>
> I could be wrong - this is all gut and hip. Besides, you can't really
> convert just the FFT from floating-point to fixed-point - the input
> dynamic range is undefined. You really need to analyze the entire
> system from input to the FFT, and that is probably going to be very
> involved (months, not hours).

Well, weeks, perhaps. Hours only if you are _very_ lucky. But
certainly not trivial.

--

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Robert Oschler wrote:

> Hello,
>
> I want to try using an fixed point based FFT routine instead of the current
> floating point based routine. I have a user of my software that has a 800
> Mhz VIA chipset motherboard, and the FPU on that thing is so bad, it can't
> crunch an audio signal in real time (i.e. - while they are talking). On
> non-VIA systems the computer is able to keep up in real time (it's a speech
> recognition app.)
>
> I found the KISS FFT project on SourceForge which is able to do fixed point
> FFT as well as floating point
>
> http://sourceforge.net/projects/kissfft/
>
> However, when I use it compiled with fixed point data values, I get erratic
> tiny values for the output complex data values. When compiled with floating
> point values it matches closely the original FFT routine's outputs.
>
> So it appears I don't know how to convert floating point values to fixed
> point values. I found a post by the author of KISS FFT that said this:
>
> "If you're not familiar with fixed point math, here's a crash course:
>
> A common format for fixed point calculations is to use 15bits of a 16 bit
> signed integer to represent the fractional part of a number from -1 to 1.
>
> In other words, the range of a 16 bit integer (-32768:32767) is mapped to
> (-1:.99997)
>
> Note that 32768 cannot be represented as a 16 bit signed integer, thus
> xfloat cannot equal 1.
>
> So define xfix := round( xfloat * 32768) , where -1 <= xfloat < 1"
>
> I want to be clear about what I don't understand about converting floating
> point values to fixed point values.
>
> Given the above and a floating point sample value such as 1000.4897 (as an
> example), am I remapping 1000.4897 to a number between -1 and .99997?
>
> Or am I just remapping the fractional portion (0.4897) to -1 and .99997?
>
> If it's the latter case, am I supposed to create two fixed point values for
> each floating point value, one for the integer portion of the floating point
> number (1000) and one for the fractional portion (0.9997)?
>
> Thanks,
> Robert
>
You need to take your entire input signal and multiply it by some number
(call it A) so that it, the output of the FFT, and any intermediate
values of the FFT, all fit into the range (-max, max). Then you correct
things when you're done by multiplying by 1/A. You want to find the
biggest A that you can that will avoid overflow, because you'll
experience rounding errors that are more severe with smaller A. In your
case of 1000.4897 you could, for instance, choose A = 1 and get 1000 or
A = 32 (shift up by 5 bits) to get 32016.

As Randy mentioned finding A may not be trivial (but if you already have
a good idea of what you're doing it may not be months).

--

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

"Tim Wescott" <[email protected]> wrote in message
news:[email protected]..
>
> You need to take your entire input signal and multiply it by some number
> (call it A) so that it, the output of the FFT, and any intermediate
> values of the FFT, all fit into the range (-max, max). Then you correct
> things when you're done by multiplying by 1/A. You want to find the
> biggest A that you can that will avoid overflow, because you'll
> experience rounding errors that are more severe with smaller A. In your
> case of 1000.4897 you could, for instance, choose A = 1 and get 1000 or
> A = 32 (shift up by 5 bits) to get 32016.
>
> As Randy mentioned finding A may not be trivial (but if you already have
> a good idea of what you're doing it may not be months).
>
> --
>
> Tim Wescott
> Wescott Design Services
> http://www.wescottdesign.com

Tim,

Thanks, I'll give that a try. I believe you are both right about needing a
big overhaul rather than a symptom-fix. But it's worth a try. I've already
swapped the existing complex FFT for the KISS real-valued FFT. After trying
the fixed point stuff, if it's still too slow, then it's time to get serious
(tedious? ).

Thanks.

--
Thanks,
Robert
http://www.evosapien.com/
Robosapien Hacks & Tricks

Tim Wescott <[email protected]> writes:
> [...]
> You need to take your entire input signal and multiply it by some
> number (call it A) so that it, the output of the FFT, and any
> intermediate values of the FFT, all fit into the range (-max, max).
> Then you correct things when you're done by multiplying by 1/A. You
> want to find the biggest A that you can that will avoid overflow,
> because you'll experience rounding errors that are more severe with
> smaller A. In your case of 1000.4897 you could, for instance, choose
> A = 1 and get 1000 or A = 32 (shift up by 5 bits) to get 32016.
>
> As Randy mentioned finding A may not be trivial (but if you already
> have a good idea of what you're doing it may not be months).

Depending on what's before the FFT, the range of the input data could
be such that a value of A that prevents overflow for the largest
inputs also results in 1 LSB or less of wiggle in other scenarios.

Maybe I'm being pessimistic - real data probably won't vary THAT
much, but the floating-point format will allow this to be possible.
--
% Randy Yates % "Bird, on the wing,
%% Fuquay-Varina, NC % goes floating by
%%% 919-577-9882 % but there's a teardrop in his eye..."
%%%% <[email protected]> % 'One Summer Dream', *Face The Music*, ELO
http://home.earthlink.net/~yatescr

Randy Yates wrote:

> Tim Wescott <[email protected]> writes:
>
>>[...]
>>You need to take your entire input signal and multiply it by some
>>number (call it A) so that it, the output of the FFT, and any
>>intermediate values of the FFT, all fit into the range (-max, max).
>>Then you correct things when you're done by multiplying by 1/A. You
>>want to find the biggest A that you can that will avoid overflow,
>>because you'll experience rounding errors that are more severe with
>>smaller A. In your case of 1000.4897 you could, for instance, choose
>>A = 1 and get 1000 or A = 32 (shift up by 5 bits) to get 32016.
>>
>>As Randy mentioned finding A may not be trivial (but if you already
>>have a good idea of what you're doing it may not be months).
>
>
> Depending on what's before the FFT, the range of the input data could
> be such that a value of A that prevents overflow for the largest
> inputs also results in 1 LSB or less of wiggle in other scenarios.
>
> Maybe I'm being pessimistic - real data probably won't vary THAT
> much, but the floating-point format will allow this to be possible.

In which case you need to go to more precision. Generally if you're
using real input data then you have plenty of information to calculate
the necessary bit-depth and scaling of your internal variables. In
analyzing for bit-depth you'll find out if that "generally" is correct.

--

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com