# FFT overflow

Started by July 5, 2007
Hi,

This is my first post so please be patient.
I am trying to implement an 8pt FFT. However i only have a 16bit adder.
When i add 2 large numbers together the result is 17bits. I can remove the
LSB but what is the best way to make the result 16bits again. Assume the
FFT size will be 1024pts eventually.

Thanks

>Hi, > >This is my first post so please be patient. >I am trying to implement an 8pt FFT. However i only have a 16bit adder. >When i add 2 large numbers together the result is 17bits. I can remove
the
>LSB but what is the best way to make the result 16bits again. Assume the >FFT size will be 1024pts eventually. > >Thanks > > >
any replies :-(
On Jul 5, 11:29 am, "malikos" <omar.ma...@nxp.com> wrote:
> >Hi, > > >This is my first post so please be patient. > >I am trying to implement an 8pt FFT. However i only have a 16bit adder. > >When i add 2 large numbers together the result is 17bits. I can remove > the > >LSB but what is the best way to make the result 16bits again. Assume the > >FFT size will be 1024pts eventually. > > >Thanks > > any replies :-(
my, you're patient. :-\ i would add (or subtract) and divide by 2 (shift left) for each butterfly addition (or subtraction). for an 8-point FFT, then your result would be scaled by 1/8, but you would know it and could deal with it in the use or interpretation of the FFT results. a fixed 8-point FFT is so specialized and small that it seems reasonable that your code could be highly optimized for speed/ efficiency by trading generality for tricks. take a look at your twiddle factors (the FFT coefficients) for the 8-point FFT to see what i mean by this. r b-j
>On Jul 5, 11:29 am, "malikos" <omar.ma...@nxp.com> wrote: >> >Hi, >> >> >This is my first post so please be patient. >> >I am trying to implement an 8pt FFT. However i only have a 16bit
>> >When i add 2 large numbers together the result is 17bits. I can
remove
>> the >> >LSB but what is the best way to make the result 16bits again. Assume
the
>> >FFT size will be 1024pts eventually. >> >> >Thanks >> >> any replies :-( > >my, you're patient. :-\ > >i would add (or subtract) and divide by 2 (shift left) for each >butterfly addition (or subtraction). for an 8-point FFT, then your >result would be scaled by 1/8, but you would know it and could deal >with it in the use or interpretation of the FFT results. > >a fixed 8-point FFT is so specialized and small that it seems >reasonable that your code could be highly optimized for speed/ >efficiency by trading generality for tricks. take a look at your >twiddle factors (the FFT coefficients) for the 8-point FFT to see what >i mean by this. > >r b-j > >
Thanks for your reply. The problem is i would also like to build an 1024pt FFT, however if i divide by 2 each time the last butterflies i get 0. Any ideas here ?? I can use floating point unit as it is not build into my DSP.
any ideas ????
malikos wrote:
> any ideas ????
Sure. Use double precision. In most cases, dividing by two on every second pass is sufficient. There are many fifed-point FFT implementations around; study some. Jerry -- Engineering is the art of making what you want from things you can get. &macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;
On Jul 6, 12:39 pm, Jerry Avins <j...@ieee.org> wrote:
> malikos wrote: > > any ideas ???? > > Sure. Use double precision.
16 bits just ain't enough for a 1024 pt FFT
> In most cases, dividing by two on every > second pass is sufficient.
doing this (dividing by 2 every other pass) will preserve energy, or the mean-square of the signal data. it will neither grow or decline in r.m.s. amplitude.
> There are many fifed-point FFT > implementations around; study some.