dspdummy 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. >> >> >> >> > > 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)Zero padding doesn't change the returned values. The extra zeros are place holders and can be removed from the final result, which are otherwise bit exact. You should do a little reading (or use FFTW, reading the directions carefully and taking no steps for granted. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
N-pt DFT where n != power of 2
Started by ●August 12, 2009
Reply by ●August 13, 20092009-08-13
Reply by ●August 13, 20092009-08-13
>dspdummy 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. >>> >>> >>> >>> >> >> 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 framesize.>> The results have to be bit-exact with those of the 120 or 960 dft. Ilooked>> at that Wikipedia page but looks pretty complicated. I'll try to havea>> look at the other website with some useful programs (probably primefactor>> fft as was mentioned above). If there are any Matlab m files emulatingthis>> 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) > >Zero padding doesn't change the returned values. The extra zeros are >place holders and can be removed from the final result, which are >otherwise bit exact. You should do a little reading (or use FFTW, >reading the directions carefully and taking no steps for granted. > >Jerry >-- >Engineering is the art of making what you want from things you can get. >??????????????????????????????????????????????????????????????????????? >Hello More specifically, the input signal to my ifft is 960 frequency bins of an originally-transformed time-domain signal at fs=48kHz. From what I understand, padding 64(1024-960) zeros in the frequency domain will furnish 1024 samples in the time domain after executing the 1024-pt ifft. The extra samples will be the equivalent of interpolating the original time domain signal by a factor 1024/960 resulting in a higher sampling rate. I don't quite see how I can recover the equivalent 960 time-domain samples at fs=48kHz except for running the whole signal thru a sample rate converter. I suppose if we were doing simple things like padding by a factor of 2, then every 2nd output sample could maybe be removed as seen in the example: http://www.dspguru.com/howto/tech/zeropad.htm Thanks Bill
Reply by ●August 13, 20092009-08-13
Jerry Avins <jya@ieee.org> wrote: (big snip)> Zero padding doesn't change the returned values. The extra zeros are > place holders and can be removed from the final result, which are > otherwise bit exact. You should do a little reading (or use FFTW, > reading the directions carefully and taking no steps for granted.It seems to me that in some cases zero padding is right, and other times it is wrong. In this case, it would seem to me that you get the frequencies at different points in the zero padded case. You could interpolate them, assuming that it approximates a continuous spectrum. If you have 120 sample points over some time period, the FFT bins will be 0, 1, 2, up to 119 cycles over that time period. (or -60 to 59 if you like that better). If you zero pad, the frequency bins will be cycles over the now extended time period. If you want to graph the spectrum then that is probably fine. Also, if the samples represent one period of a periodic signal, zero padding will give a different result. -- glen
Reply by ●August 13, 20092009-08-13
"dspdummy" <chris.glass@orange.fr> wrote in news:3oqdnfJYDdfI- BnXnZ2dnUVZ_q2dnZ2d@giganews.com: <snip>> 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.<snip> If you want bit exact results, then you must stick with the DFT. Otherwise, you are doing a different number of operations (and the ones that remain are in a different order). Truncation and/or roundoff error is going to cause different results. Not greatly different, but not bit-exact. Are you certain that you want bit-exact? There is evidence that (other things being equal) FFT results are more "correct" than DFT because of the reduction in the number of operations where roundoff takes place.
Reply by ●August 13, 20092009-08-13
>"dspdummy" <chris.glass@orange.fr> wrote in news:3oqdnfJYDdfI- >BnXnZ2dnUVZ_q2dnZ2d@giganews.com: > > ><snip> >> The results have to be bit-exact with those of the 120 or 960 dft. Ilooked>> at that Wikipedia page but looks pretty complicated. ><snip> > >If you want bit exact results, then you must stick with the DFT.Otherwise,>you are doing a different number of operations (and the ones that remainare>in a different order). Truncation and/or roundoff error is going tocause>different results. Not greatly different, but not bit-exact. > >Are you certain that you want bit-exact? There is evidence that (other >things being equal) FFT results are more "correct" than DFT because ofthe>reduction in the number of operations where roundoff takes place. > >Hello Yes bit-exactness with the original 960-pt (i)dft is mandatory. Looks like I need to plunge into prime factor methods as we can't live with the number of operations required for the dft. (~48mips) Thanks Bill
Reply by ●August 13, 20092009-08-13
glen herrmannsfeldt wrote:> Jerry Avins <jya@ieee.org> wrote: > (big snip) > >> Zero padding doesn't change the returned values. The extra zeros are >> place holders and can be removed from the final result, which are >> otherwise bit exact. You should do a little reading (or use FFTW, >> reading the directions carefully and taking no steps for granted. > > It seems to me that in some cases zero padding is right, and other > times it is wrong. > > In this case, it would seem to me that you get the frequencies > at different points in the zero padded case. You could interpolate > them, assuming that it approximates a continuous spectrum. > > If you have 120 sample points over some time period, the FFT bins > will be 0, 1, 2, up to 119 cycles over that time period. > (or -60 to 59 if you like that better). > > If you zero pad, the frequency bins will be cycles over the > now extended time period. If you want to graph the spectrum > then that is probably fine. Also, if the samples represent one > period of a periodic signal, zero padding will give a different > result.I'm simply wrong. I was thinking FFT all along, not IFFT. Some days are like that. I owe apologies all around. Dspdummy should go with FFTW. I'm sure Gordon Sande will offer advice if that becomes necessary. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●August 13, 20092009-08-13
Ian Shef wrote:> Are you certain that you want bit-exact? There is evidence that (other > things being equal) FFT results are more "correct" than DFT because of the > reduction in the number of operations where roundoff takes place.Isn't there only one rounding point in a DFT? (At the end of the multiply-accumulate for each output bin.) This is versus log(N) rounding points in an FFT. -- Oli
Reply by ●August 14, 20092009-08-14
On Aug 12, 6:52�pm, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:> If N is not prime then it can be reduced depending on the factors of N. > If it is prime, then you are stuck.Not true; for at least 40 years, there have been O(N log N) FFT algorithms for prime N. (Google Rader's and Bluestein's FFT algorithms; both are implemented in FFTW.) Regards, Steven G. Johnson
Reply by ●August 14, 20092009-08-14
Oli Charlesworth <catch@olifilth.co.uk> wrote:> Isn't there only one rounding point in a DFT? (At the end of the > multiply-accumulate for each output bin.) This is versus log(N) > rounding points in an FFT.It gets more interesting in fixed point. If you can do it wide enough not to overflow without shifting, the results should be pretty good. Bit exact might be harder, though. -- glen
Reply by ●August 14, 20092009-08-14
>glen herrmannsfeldt wrote: >> Jerry Avins <jya@ieee.org> wrote: >> (big snip) >> >>> Zero padding doesn't change the returned values. The extra zeros are >>> place holders and can be removed from the final result, which are >>> otherwise bit exact. You should do a little reading (or use FFTW, >>> reading the directions carefully and taking no steps for granted. >> >> It seems to me that in some cases zero padding is right, and other >> times it is wrong. >> >> In this case, it would seem to me that you get the frequencies >> at different points in the zero padded case. You could interpolate >> them, assuming that it approximates a continuous spectrum. >> >> If you have 120 sample points over some time period, the FFT bins >> will be 0, 1, 2, up to 119 cycles over that time period. >> (or -60 to 59 if you like that better). >> >> If you zero pad, the frequency bins will be cycles over the >> now extended time period. If you want to graph the spectrum >> then that is probably fine. Also, if the samples represent one >> period of a periodic signal, zero padding will give a different >> result. > >I'm simply wrong. I was thinking FFT all along, not IFFT. Some days are >like that. I owe apologies all around. Dspdummy should go with FFTW. I'm>sure Gordon Sande will offer advice if that becomes necessary. > >Jerry >-- >Engineering is the art of making what you want from things you can get. >??????????????????????????????????????????????????????????????????????? >Hello Jerry, No pb. I was talking fft and not ifft at the beginning because of their mathematical similarites but I DO need an IFFT. I'll check out that FFTW but who is Gordon Sande? Thanks Bill
