I need to take FFT for 160 points. Of course zero padding it to 256 points will allow me to take radix 2 fft. But I need to do redundant computation for 96 points. Will split radix help? If so give me links regarding theory behind and implementation of it. If you feel any other method efficient in this case kindly let me know.
FFT for Non 2^N points
Started by ●November 9, 2007
Reply by ●November 9, 20072007-11-09
You can use powers of 3, too, in combination with powers of 2. Any small prime will help. For example, 162 point fft takes shorter than 256 point in my computer.> If you feel any other method efficient in this case kindly let me know.
Reply by ●November 9, 20072007-11-09
dsper <h.emreguven@gmail.com> wrote in news:1194617832.359790.304450 @q5g2000prf.googlegroups.com:> You can use powers of 3, too, in combination with powers of 2. Any > small prime will help. > > For example, 162 point fft takes shorter than 256 point in my > computer. > >> If you feel any other method efficient in this case kindly let me know. > > >I suppose how it's being implemented is the key. If you're using a full computing environment, just use FFTW and use whatever N is convenient. If you're coding on a dsp or microcontroller, than options become more limited -- Scott Reverse name to reply
Reply by ●November 9, 20072007-11-09
Satish Prabu wrote:> I need to take FFT for 160 points. Of course zero padding it to 256 > points will allow me to take radix 2 fft. But I need to do redundant > computation for 96 points.160 = 2^5 * 5 There should be pretty darn efficient FFT for that. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
Reply by ●November 9, 20072007-11-09
Im implementing it on a DSPs. So no library can be used. I have to develop from scratch. Can you give some more details or links regarding it. -Satish Prabu On Nov 9, 7:27 pm, Scott Seidman <namdiestt...@mindspring.com> wrote:> dsper <h.emregu...@gmail.com> wrote in news:1194617832.359790.304450 > @q5g2000prf.googlegroups.com: > > > You can use powers of 3, too, in combination with powers of 2. Any > > small prime will help. > > > For example, 162 point fft takes shorter than 256 point in my > > computer. > > >> If you feel any other method efficient in this case kindly let me know. > > I suppose how it's being implemented is the key. If you're using a full > computing environment, just use FFTW and use whatever N is convenient. If > you're coding on a dsp or microcontroller, than options become more limited > > -- > Scott > Reverse name to reply
Reply by ●November 9, 20072007-11-09
Satish Prabu <satishprabu@gmail.com> wrote in news:1194622925.764510.41350 @s15g2000prm.googlegroups.com:> > Im implementing it on a DSPs. So no library can be used. I have to > develop from scratch. Can you give some more details or links > regarding it. >I haven't had to do it, but I'd have a hard time believing that with enough searching you couldn't dig up some user-contributed FFT algorithm for the common dsp families. -- Scott Reverse name to reply
Reply by ●November 9, 20072007-11-09
Satish Prabu wrote:> Im implementing it on a DSPs. So no library can be used. I have to > develop from scratch. Can you give some more details or links > regarding it. > > -Satish Prabuhttp://en.wikipedia.org/wiki/Cooley-Tukey_FFT_algorithm VLV
Reply by ●November 9, 20072007-11-09
Satish Prabu wrote:> I need to take FFT for 160 points. Of course zero padding it to 256 > points will allow me to take radix 2 fft. But I need to do redundant > computation for 96 points. > > Will split radix help? If so give me links regarding theory behind and > implementation of it. > > If you feel any other method efficient in this case kindly let me know. >You can use a 5 point and 32 point kernel, combined using the mixed radix algorithm. See Smith & Smith's Handbook of real-time FFTs ( http://www.amazon.com/exec/obidos/ASIN/0780310918/andraka ) for a detailed description of both the mixed radix algorithm and several different 5 point algorithms.
Reply by ●November 9, 20072007-11-09
Ray Andraka wrote:> Satish Prabu wrote: > >> I need to take FFT for 160 points.> You can use a 5 point and 32 point kernel, combined using the mixed > radix algorithm. See Smith & Smith's Handbook of real-time FFTs ( > http://www.amazon.com/exec/obidos/ASIN/0780310918/andraka ) for a > detailed description of both the mixed radix algorithm and several > different 5 point algorithms.A very nice classic book: R. Blahut "Fast Algorithms for Digital Signal Processing" Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
Reply by ●November 9, 20072007-11-09
Vladimir Vassilevsky wrote:> > A very nice classic book: > > R. Blahut "Fast Algorithms for Digital Signal Processing" > >Yes, another very good source...if you can find it. it can be difficult to find a copy either in the library or for sale. It took me over two years to find a replacement for my personal copy when it disappeared from my bookshelf at a prior place of employment. The usual used book places sometimes list it, but then when you go to buy it they reply that they'll notify you when they find it. The local state university library showed one in their inventory, but it could not be found when I tried to check it out about 10 years ago.
