Fast Floating-Point Format
in [DSP]
|
Prev: rahasia uang 250 ribu
Next: using FFT as a channelizer
From: _tomislav on 20 Oct 2009 10:05 Hi, I'm looking for an implementation of fast floating point FFT algorithm. I found application notes (http://tiny.cc/EE185, Analog Devices) describing addition and multiplication of fast floating point numbers. cftt function inside VisualDSP library performs N-point radix-2 complex input FFT using fract16 format. Could I find somewhere implementation for fastfloat16 format? I haven't used VisualDSP, so I'm not quite familiar with VisualDSP libraries
From: Tim Wescott on 20 Oct 2009 11:09 On Tue, 20 Oct 2009 09:05:47 -0500, _tomislav wrote: > Hi, > > I'm looking for an implementation of fast floating point FFT algorithm. > I found application notes (http://tiny.cc/EE185, Analog Devices) > describing addition and multiplication of fast floating point numbers. > cftt function inside VisualDSP library performs N-point radix-2 complex > input FFT using fract16 format. Could I find somewhere implementation > for fastfloat16 format? > > I haven't used VisualDSP, so I'm not quite familiar with VisualDSP > libraries If fastfloat16 really fits into 16 bits then you're probably just giving up too much precision to make an FFT worthwhile -- even a 16-bit fractional type is getting slim on precision unless your data isn't that wide and your number of bins isn't too great. I would assume that for a well-scaled fixed point algorithm you'd want at least your input precision, plus log2 of your number of bins, plus two or three bits for good measure -- that'll add up to 16 pretty darn quick, much less whatever is available for a mantissa in fastfloat16. -- www.wescottdesign.com
From: Vladimir Vassilevsky on 20 Oct 2009 11:27 _tomislav wrote: > Hi, > > I'm looking for an implementation of fast floating point FFT algorithm. Why would you need that? Why can't you use block floating point? > I > found application notes (http://tiny.cc/EE185, Analog Devices) describing > addition and multiplication of fast floating point numbers. cftt function > inside VisualDSP library performs N-point radix-2 complex input FFT using > fract16 format. Could I find somewhere implementation for fastfloat16 > format? Which VDSP? For what processor? > I haven't used VisualDSP, so I'm not quite familiar with VisualDSP > libraries Redefine a floating point FFT like that: template <class T> void FFT(T *data); Then define class float_16 and use it. This is definitely not the most efficient implementation; however it is going to be faster then the standard float if there is no FPU. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
From: _tomislav on 21 Oct 2009 04:11 >If fastfloat16 really fits into 16 bits then you're probably just giving >up too much precision to make an FFT worthwhile -- even a 16-bit >fractional type is getting slim on precision unless your data isn't that >wide and your number of bins isn't too great. > >I would assume that for a well-scaled fixed point algorithm you'd want at >least your input precision, plus log2 of your number of bins, plus two or >three bits for good measure -- that'll add up to 16 pretty darn quick, >much less whatever is available for a mantissa in fastfloat16. Fastfloat16 can't fit into 16 bits - format provides one 16-bit word for exponent and one 16-bit word for fraction. Signed twos-complement notation is used both for exponent and fraction. So, precision is equal to 2^-15. Fastfloat16 gives a good precision and range. Let's assume that well optimized FFT algorithm has a complexity of O(Nlog10). On a fixed point DSP like BF532 16-bit multiplication/addition is completed in one cycle. So, N is equal to cycle number. If fastfloat16 multiplication needs, lets say, 30 cycles in average for multiplication/addition I think this outperforms floating point format on fixed point machine.
From: Tim Wescott on 21 Oct 2009 12:06
On Wed, 21 Oct 2009 03:11:46 -0500, _tomislav wrote: >>If fastfloat16 really fits into 16 bits then you're probably just giving >>up too much precision to make an FFT worthwhile -- even a 16-bit >>fractional type is getting slim on precision unless your data isn't that > >>wide and your number of bins isn't too great. >> >>I would assume that for a well-scaled fixed point algorithm you'd want >>at > >>least your input precision, plus log2 of your number of bins, plus two >>or > >>three bits for good measure -- that'll add up to 16 pretty darn quick, >>much less whatever is available for a mantissa in fastfloat16. > > Fastfloat16 can't fit into 16 bits - format provides one 16-bit word > for exponent and one 16-bit word for fraction. Signed twos-complement > notation is used both for exponent and fraction. So, precision is equal > to 2^-15. > > Fastfloat16 gives a good precision and range. Let's assume that well > optimized FFT algorithm has a complexity of O(Nlog10). On a fixed point > DSP like BF532 16-bit multiplication/addition is completed in one cycle. > So, N is equal to cycle number. If fastfloat16 multiplication needs, > lets say, 30 cycles in average for multiplication/addition I think this > outperforms floating point format on fixed point machine. The gist of what I was trying to get across still stands -- floats use more memory for the precision they give, and they use time. Why use a data type that gives you less than 16 bits of precision and takes 30 clock ticks (at best) for a MAC when you can use the same amount of memory, get better than 30 bits precision, and use four clock ticks per MAC? -- www.wescottdesign.com |