I know that an N-pt DFT can be replaced by an FFT to save operations if N is a power of 2. What can I do if N is NOT a power of 2 to avoid the DFT? I need, nevertheless, the exact result. Thanks
N-pt DFT where n != power of 2
Started by ●August 12, 2009
Reply by ●August 12, 20092009-08-12
dspdummy <chris.glass@orange.fr> wrote:> I know that an N-pt DFT can be replaced by an FFT to save operations if N > is a power of 2. What can I do if N is NOT a power of 2 to avoid the DFT? I > need, nevertheless, the exact result.If N is not prime then it can be reduced depending on the factors of N. If it is prime, then you are stuck. The advantage of the FFT is that an N point DFT can be reduced to two N/2 point transforms, plus a little math. Repeat that log2(N) times and you have the FFT. There are routines around that have this all coded for you, for reasonable factors of N. -- glen
Reply by ●August 12, 20092009-08-12
"dspdummy" <chris.glass@orange.fr> wrote in news:w_ydndU_wYNjoh7XnZ2dnUVZ_sydnZ2d@giganews.com:> I know that an N-pt DFT can be replaced by an FFT to save operations if N > is a power of 2. What can I do if N is NOT a power of 2 to avoid the DFT? I > need, nevertheless, the exact result.<snip> The FFT is not limited to powers of 2. Assuming that by "FFT" you mean "a DFT algorithm that can be performed in O(N log N) operations" (naive DFT is O(N^2), then there are FFT solutions for any N (composite or prime). See http://en.wikipedia.org/wiki/Fft
Reply by ●August 12, 20092009-08-12
Check it out "We expect that most users will be best served by the basic interface, whereas the guru interface requires careful attention to the documentation to avoid problems. Besides the automatic performance adaptation performed by the planner, it is also possible for advanced users to customize FFTW manually. For example, if code space is a concern, we provide a tool that links only the subset of FFTW needed by your application. Conversely, you may need to extend FFTW because the standard distribution is not sufficient for your needs. For example, the standard FFTW distribution works most efficiently for arrays whose size can be factored into small primes (2, 3, 5, and 7), and otherwise it uses a slower general-purpose routine. If you need efficient transforms of other sizes, you can use FFTW's code generator, which produces fast C programs (=93codelets=94) for any particular array size you may care about. For example, if you need transforms of size 513 =3D 19*33,you can customize FFTW to support the factor 19 efficiently." So you should have a look at the fftw library. Is a really good one! www.fftw.org Take care! On 12 ago, 20:14, Ian Shef <inva...@avoiding.spam> wrote:> "dspdummy" <chris.gl...@orange.fr> wrote innews:w_ydndU_wYNjoh7XnZ2dnUVZ_=sydnZ2d@giganews.com:> > > I know that an N-pt DFT can be replaced by an FFT to save operations if=N> > is a power of 2. What can I do if N is NOT a power of 2 to avoid the DF=T? I> > need, nevertheless, the exact result. > > <snip> > > The FFT is not limited to powers of 2. > > Assuming that by "FFT" you mean "a DFT algorithm that can be performed in=O(N> log N) operations" (naive DFT is O(N^2), then there are FFT solutions for=any> N (composite or prime). > > See > > http://en.wikipedia.org/wiki/Fft
Reply by ●August 13, 20092009-08-13
>dspdummy <chris.glass@orange.fr> wrote: > >> I know that an N-pt DFT can be replaced by an FFT to save operations ifN>> is a power of 2. What can I do if N is NOT a power of 2 to avoid theDFT? I>> need, nevertheless, the exact result. > >If N is not prime then it can be reduced depending on the factors of N. >If it is prime, then you are stuck. > >The advantage of the FFT is that an N point DFT can be reduced to >two N/2 point transforms, plus a little math. Repeat that >log2(N) times and you have the FFT. > >There are routines around that have this all coded for you, >for reasonable factors of N. > >-- glen >N is 960 or 120. It would be useful for me to get ahold of one of these routines. thanks, Bill
Reply by ●August 13, 20092009-08-13
dspdummy wrote:>> dspdummy <chris.glass@orange.fr> wrote: >> >>> I know that an N-pt DFT can be replaced by an FFT to save operations if > N >>> is a power of 2. What can I do if N is NOT a power of 2 to avoid the > DFT? I >>> need, nevertheless, the exact result. >> If N is not prime then it can be reduced depending on the factors of N. >> If it is prime, then you are stuck. >> >> The advantage of the FFT is that an N point DFT can be reduced to >> two N/2 point transforms, plus a little math. Repeat that >> log2(N) times and you have the FFT. >> >> There are routines around that have this all coded for you, >> for reasonable factors of N. >> >> -- glen >> > N is 960 or 120. It would be useful for me to get ahold of one of these > routines. > > thanks, BillFFTW will do these for you very nicely. They both have only small prime factors. If you don't want to have to learn something new, append enough zeroes to bring the larger up to 1024 and the smaller to 120. Any window that you use should be sized for the original, not the augmented, data. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●August 13, 20092009-08-13
Jerry Avins wrote: ...> zeroes to bring the larger up to 1024 and the smaller to 120.128! Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●August 13, 20092009-08-13
On 2009-08-13 12:53:55 -0300, Jerry Avins <jya@ieee.org> said:> Jerry Avins wrote: > > ... > >> zeroes to bring the larger up to 1024 and the smaller to 120. > > 128! > > Jerry120 = 3 * 5 * 8 and 960 = 8 * 120 = 3 * 5 * 64 so both are in the small primes of 2, 3 or 5 range.
Reply by ●August 13, 20092009-08-13
Gordon Sande wrote:> On 2009-08-13 12:53:55 -0300, Jerry Avins <jya@ieee.org> said: > >> Jerry Avins wrote: >> >> ... >> >>> zeroes to bring the larger up to 1024 and the smaller to 120. >> >> 128! >> >> Jerry > > 120 = 3 * 5 * 8 and 960 = 8 * 120 = 3 * 5 * 64 so both are in the > small primes of 2, 3 or 5 range.I wrote "FFTW will do these for you very nicely. They both have only small prime factors." Thanks for naming the factors. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●August 13, 20092009-08-13
>On 2009-08-13 12:53:55 -0300, Jerry Avins <jya@ieee.org> said: > >> Jerry Avins wrote: >> >> ... >> >>> zeroes to bring the larger up to 1024 and the smaller to 120. >> >> 128! >> >> Jerry > >120 = 3 * 5 * 8 and 960 = 8 * 120 = 3 * 5 * 64 so both are in the >small primes of 2, 3 or 5 range. > > > >Can't pad zeros and do the 1024 or 128 fft(it's really an ifft that I need) as the output time samples must respect the 960 or 120 frame size. The results have to be bit-exact with those of the 120 or 960 dft. I looked at that Wikipedia page but looks pretty complicated. I'll try to have a look at the other website with some useful programs (probably prime factor fft as was mentioned above). If there are any Matlab m files emulating this I would be grateful to get my hands on them as it's quite helpful for understanding the theory (I mostly speak C,Matlab,and block diagrams, and not too much formulas) Thanks Bill
