So I was flipping through my news feed and hit https://www.adafruit.com/blog/2014/08/29/using-gpu-fft-with-your-raspberry-pi-raspberry_pi-piday-raspberrypi/ Which is neat and all, but reminds me of something I've always wondered about, since I've never had anything resembling an application for one. I keep seeing people going on about algorithms for performing 256 point FFTs. Or 16-point FFTs. Or 4-point FFTs. Any time I've ever needed an FFT, I needed tens of kilopoints or higher. What sorts of practical applications do teensy FFTs have? Clearly I'm missing something, because I'm drawing a complete blank. Or is this just one of those things that marketers and academics get all in a tizzy about off in the corner by themselves? -- Rob Gaddi, Highland Technology -- www.highlandtechnology.com Email address domain is currently out of order. See above to fix.
Short FFTs
Started by ●August 29, 2014
Reply by ●August 29, 20142014-08-29
Rob Gaddi <rgaddi@technologyhighland.invalid> writes:> So I was flipping through my news feed and hit > > https://www.adafruit.com/blog/2014/08/29/using-gpu-fft-with-your-raspberry-pi-raspberry_pi-piday-raspberrypi/ > > Which is neat and all, but reminds me of something I've always > wondered about, since I've never had anything resembling an application > for one. I keep seeing people going on about algorithms for performing > 256 point FFTs. Or 16-point FFTs. Or 4-point FFTs. Any time I've > ever needed an FFT, I needed tens of kilopoints or higher. > > What sorts of practical applications do teensy FFTs have? Clearly I'm > missing something, because I'm drawing a complete blank. Or is this > just one of those things that marketers and academics get all in a > tizzy about off in the corner by themselves?I don't think so. I can see a 256-point FFT being useful for smallish-order frequency domain filtering. -- Randy Yates Digital Signal Labs http://www.digitalsignallabs.com
Reply by ●August 29, 20142014-08-29
On Fri, 29 Aug 2014 16:21:06 -0700, Rob Gaddi wrote:> So I was flipping through my news feed and hit > > https://www.adafruit.com/blog/2014/08/29/using-gpu-fft-with-your-raspberry-pi-raspberry_pi-piday-raspberrypi/> > Which is neat and all, but reminds me of something I've always wondered > about, since I've never had anything resembling an application for one. > I keep seeing people going on about algorithms for performing 256 point > FFTs. Or 16-point FFTs. Or 4-point FFTs. Any time I've ever needed an > FFT, I needed tens of kilopoints or higher. > > What sorts of practical applications do teensy FFTs have? Clearly I'm > missing something, because I'm drawing a complete blank. Or is this > just one of those things that marketers and academics get all in a tizzy > about off in the corner by themselves?In OFDM or DMT, each point in the FFT represents a carrier in the channel, so these tend to be smaller than the FFTs you use for spectral analysis. IEEE 802.11a OFDM has 48 data and 4 pilot subcarriers and may use a 64 point FFT. Most other OFDM schemes use much larger FFTs though e.g. DVB- T uses a whopping 8k. Regards, Allan
Reply by ●August 30, 20142014-08-30
On Saturday, August 30, 2014 11:21:06 AM UTC+12, Rob Gaddi wrote:> So I was flipping through my news feed and hit > > > > https://www.adafruit.com/blog/2014/08/29/using-gpu-fft-with-your-raspberry-pi-raspberry_pi-piday-raspberrypi/ > > > > Which is neat and all, but reminds me of something I've always > > wondered about, since I've never had anything resembling an application > > for one. I keep seeing people going on about algorithms for performing > > 256 point FFTs. Or 16-point FFTs. Or 4-point FFTs. Any time I've > > ever needed an FFT, I needed tens of kilopoints or higher. > > > > What sorts of practical applications do teensy FFTs have? Clearly I'm > > missing something, because I'm drawing a complete blank. Or is this > > just one of those things that marketers and academics get all in a > > tizzy about off in the corner by themselves? > > > > -- > > Rob Gaddi, Highland Technology -- www.highlandtechnology.com > > Email address domain is currently out of order. See above to fix.When a stochastic process is non-stationary we use small quasi stationary FFTs to model the process. eg in LPC coding, speech enhancement - spectral subtraction maybe. Also, for a smooth spectrum, take short interval FFTs and average the result (works better for stationary time-series)
Reply by ●August 30, 20142014-08-30
On 30.08.14 01.21, Rob Gaddi wrote:> So I was flipping through my news feed and hit > > https://www.adafruit.com/blog/2014/08/29/using-gpu-fft-with-your-raspberry-pi-raspberry_pi-piday-raspberrypi/ > > Which is neat and all, but reminds me of something I've always > wondered about, since I've never had anything resembling an application > for one. I keep seeing people going on about algorithms for performing > 256 point FFTs. Or 16-point FFTs. Or 4-point FFTs. Any time I've > ever needed an FFT, I needed tens of kilopoints or higher. > > What sorts of practical applications do teensy FFTs have?Well, look at the gpufft implementation on Raspi. The short FFTs can be cascaded. The current implementation provides support for 10^17 points based on at most 32 point FFTs, and it is still fast enough for real time audio processing. Of course, up to 10^20 points would be nice for some applications. Unfortunately the gpu_fft library is not really usable as library. It requires exclusive root access to a kernel device. So you can use it only once per Raspi. And it leaves many orphaned resources around, when the program stops unexpectedly or if you are debugging. You need to reboot to get your memory back. Iv have done some kernel patches to come around this issue, but they are still alpha.> Clearly I'm > missing something, because I'm drawing a complete blank. Or is this > just one of those things that marketers and academics get all in a > tizzy about off in the corner by themselves?No, it is part of a bigger solution. Marcel
Reply by ●August 30, 20142014-08-30
Rob Gaddi <rgaddi@technologyhighland.invalid> wrote: (snip)> Which is neat and all, but reminds me of something I've always > wondered about, since I've never had anything resembling an application > for one. I keep seeing people going on about algorithms for performing > 256 point FFTs. Or 16-point FFTs. Or 4-point FFTs. Any time I've > ever needed an FFT, I needed tens of kilopoints or higher.> What sorts of practical applications do teensy FFTs have?Some image compression algorithms are based on 8 point DCTs. Well, actually 8x8 in 2D, but DCT (and Fourier transforms in general) are separable in rectangular coordinates, so an 8x8 transform uses 16 eight point transforms. -- glen
Reply by ●August 30, 20142014-08-30
On 30/08/2014 00:21, Rob Gaddi wrote:> So I was flipping through my news feed and hit > > https://www.adafruit.com/blog/2014/08/29/using-gpu-fft-with-your-raspberry-pi-raspberry_pi-piday-raspberrypi/ > > Which is neat and all, but reminds me of something I've always > wondered about, since I've never had anything resembling an > application for one. I keep seeing people going on about algorithms > for performing 256 point FFTs. Or 16-point FFTs. Or 4-point FFTs. > Any time I've ever needed an FFT, I needed tens of kilopoints or > higher. > > What sorts of practical applications do teensy FFTs have? Clearly > I'm missing something, because I'm drawing a complete blank. Or is > this just one of those things that marketers and academics get all in > a tizzy about off in the corner by themselves? >overlapping FFTs around 1024 points are at the heart of the phase vocoder (pvoc), and also (using various block sizes) of convolution reverb. "When I get around to it" I will be hoping/trying to get a real time version of at least pvoc going on the Pi. Unfortunately the FFT is not the only compute-intensive component in pvoc (atan2, hypot also needed per frequency bin), so it still remains to be seen etc. Richard Dobson
Reply by ●August 30, 20142014-08-30
On Fri, 29 Aug 2014 16:21:06 -0700, Rob Gaddi <rgaddi@technologyhighland.invalid> wrote:>So I was flipping through my news feed and hit > >https://www.adafruit.com/blog/2014/08/29/using-gpu-fft-with-your-raspberry-pi-raspberry_pi-piday-raspberrypi/ > >Which is neat and all, but reminds me of something I've always >wondered about, since I've never had anything resembling an application >for one. I keep seeing people going on about algorithms for performing >256 point FFTs. Or 16-point FFTs. Or 4-point FFTs. Any time I've >ever needed an FFT, I needed tens of kilopoints or higher.Hi Rob, You ask a good question. While working with some Lockheed aerospace guys I once saw an algorithm that, as a first step, needed to determine if the majority of a signal's spectral energy was between zero and Fs/4 Hz, or between Fs/4 and Fs/2 Hz. They used a 4-point FFT for that step. (You can compute 4-point FFT magnitude results without needing to perform any multiplications!) But the value of small FFTs goes beyond the above oddball example.> >What sorts of practical applications do teensy FFTs have? Clearly I'm >missing something, because I'm drawing a complete blank. Or is this >just one of those things that marketers and academics get all in a >tizzy about off in the corner by themselves?Think about computing FFTs using fixed-point hardware having signal data and FFT twiddle factors restricted to B bits. An N-point FFT breaks up a circle into N slices where its dealing with N angles whose angular granularity is 2pi/N radians. As N increases the angles inside an FFT become smaller and smaller. Using B-bit arithmetic, the binary numerical representation of those small angles becomes more and more incorrect (percentage-wise) due to numerical quantization. That numerical quantization affect shows up in FFT results as random noise. Thanks to dead mathematicians and DSP pioneers we know that if all quantization is performed by rounding (not truncation), the maximum achievable N-point FFT output signal-to-quantization-noise power ratio decreases by a factor of two when N increases by a factor of two. What this means is that, in fixed-point hardware, larger sized FFTs produce results containing larger amounts of random error. From this viewpoint smaller-sized FFTs are superior to larger-sized FFTs. [-Rick-]
Reply by ●August 30, 20142014-08-30
On Fri, 29 Aug 2014 16:21:06 -0700, Rob Gaddi <rgaddi@technologyhighland.invalid> wrote:>So I was flipping through my news feed and hit > >https://www.adafruit.com/blog/2014/08/29/using-gpu-fft-with-your-raspberry-pi-raspberry_pi-piday-raspberrypi/ > >Which is neat and all, but reminds me of something I've always >wondered about, since I've never had anything resembling an application >for one. I keep seeing people going on about algorithms for performing >256 point FFTs. Or 16-point FFTs. Or 4-point FFTs. Any time I've >ever needed an FFT, I needed tens of kilopoints or higher. > >What sorts of practical applications do teensy FFTs have? Clearly I'm >missing something, because I'm drawing a complete blank. Or is this >just one of those things that marketers and academics get all in a >tizzy about off in the corner by themselves? > >-- >Rob Gaddi, Highland Technology -- www.highlandtechnology.com >Email address domain is currently out of order. See above to fix.My personal experience is mostly with short DFT/FFTs, where the computational complexity needs to be kept low. For comm applications, a short DFT can often be used to estimate initial frequency offset for synchronization, etc. Many sensing applications, e.g., radar, use short DFTs in various parts of the receiver for Doppler, etc. Some touch-screen technologies yield touch position via a signal with the frequency proportional to the touch position on an axis. Lots of funky little applications like that use short DFTs because they're adequate to the task and complexity needs to be managed. It's kinda cool that you only use long ones! Eric Jacobsen Anchor Hill Communications http://www.anchorhill.com
Reply by ●August 30, 20142014-08-30
Rick Lyons <R.Lyons@_bogus_ieee.org> wrote: (snip on small FFTs) (snip)> Think about computing FFTs using fixed-point hardware > having signal data and FFT twiddle factors > restricted to B bits. An N-point FFT breaks up > a circle into N slices where its dealing with > N angles whose angular granularity is 2pi/N radians. > As N increases the angles inside an FFT become > smaller and smaller. Using B-bit arithmetic, the > binary numerical representation of those small angles > becomes more and more incorrect (percentage-wise) > due to numerical quantization.> That numerical quantization affect shows up in > FFT results as random noise. Thanks to dead mathematicians > and DSP pioneers we know that if all quantization is > performed by rounding (not truncation), the maximum > achievable N-point FFT output signal-to-quantization-noise > power ratio decreases by a factor of two when N increases > by a factor of two.They show up as random noise, but they aren't so random? I have commented on the ICT (Integer Cosine Transform): http://ipnpr.jpl.nasa.gov/progress_report/42-119/119M.pdf before, which is similar to, but with the coefficients not exactly what you would choose for the DCT, but optimized for faster computation on small processors, such as the CDP1802.> What this means is that, in fixed-point hardware, > larger sized FFTs produce results containing > larger amounts of random error. From this viewpoint > smaller-sized FFTs are superior to larger-sized FFTs.If you do the right inverse transform, that takes into account the coefficient errors, you find that it isn't noise after all. The assumption of the ICT is that the inverse is done on a faster processor, with hardware multiply. -- glen
