Fixed point FFT scaling

Hi,

I am making a fixed point FFT in an FPGA. My architecture will use 1
'buttterfly' processor that will be reused
in every stage. However I can have a different scaling in each stage. I am
using a radix-2 decimation in time structure.

The 'problem' is finding out the scaling to use in each stage. Note that I 
am not interested in keeping the
'rms' of the input and output the same, but Ijust want to use my fixed point 
operations as good as possible.

After browsing a bit the web...I found several ties that each radix-2 stage
can scale the input by 1+sqrt(2).
I think this comes from the butterfly operation doing

X'= X + TW*Y
Y'= Y -TW*Y

Hence if for example Y = 1 + i, and TW is at pi/4 ----> Imag(X') will be
scaled with 1+sqrt(2) wrt X and Y (assuming X and Y equal).

However to me assuming a scaling of 1+sqrt(2) for each stage looks a bit
pessimistic because:
- obviously not every butterfly will always pi/4 for the twiddle. E.g. the
first FFT stage will just use 1 or so as twiddle, hence I think the gain on
a branch would maximally be 2 in stead of 2.414
- when there is a large 'gain'  on the imaginary branch, there is a small
gain on the real branch and the other way around. For example in the above
example Real(X') will be scaled with 1 only I think. The twiddle as such has
no complex gain, so TW*Y has the same amplitude as Y, just that it can shift
from I to Q and so...

Now my question: does my reasoning make sense...and if so, does someone know
how I could calculate some more realistic scaling factors to apply (I want
to have some fixed scalings, not using some kind of dynamic floating point
like things) ? I tried to find this myself, but it isn't that simple, and I
guess a lot of people have had the same problem. Although I have not found
anything on the internet, so I might be completely wrong as well.


My 2nd question is about how to test my FFT scaling, i.e. what should I use
as input to my FFT to test if no overflow will occur. I was thinking to use
full scale DC inputs for my FFT so that what should come out is 1 value at
DC and zeros everywhere else. Is this OK for testing ?


Thanks,

NL

NewLine wrote:
...
> After browsing a bit the web...I found several ties that each radix-2
stage
> can scale the input by 1+sqrt(2).
> I think this comes from the butterfly operation doing
>
> X'= X + TW*Y
> Y'= Y -TW*Y
>
> Hence if for example Y = 1 + i, and TW is at pi/4 ----> Imag(X') will
be
> scaled with 1+sqrt(2) wrt X and Y (assuming X and Y equal).
>
> However to me assuming a scaling of 1+sqrt(2) for each stage looks a
bit
> pessimistic because:
> - obviously not every butterfly will always pi/4 for the twiddle.
E.g. the
> first FFT stage will just use 1 or so as twiddle, hence I think the
gain on
> a branch would maximally be 2 in stead of 2.414
...
>
> Now my question: does my reasoning make sense...

i didn't see how you were discounting the conventional wisdom regarding
the absolute worst-case scaling.  you *could* have an X = +1, a Y = 1 +
i, and a twiddle (operating on Y) of exp(-i*pi/4) and that would grow
to 1 + sqrt(2) over your previous full scale.  that is the worst case.

now, *if* you are doing some saturation or more graceful overflow than
wrapping around, maybe you could get away with dividing by 2 each pass,
or ever sqrt(2) which would preserve r.m.s.  but neither would
absolutely, positively guarantee that overflow would never happen
unless your input signal was sufficiently scaled down.

>
> My 2nd question is about how to test my FFT scaling, i.e. what should
I use
> as input to my FFT to test if no overflow will occur. I was thinking
to use
> full scale DC inputs for my FFT so that what should come out is 1
value at
> DC and zeros everywhere else. Is this OK for testing ?

also try full scale sinusoids at a variety of frequencies as input to
either the FFT or iFFT.

r b-j

testing...

sheesh, this new Google Groups is weird....

r b-j

:
> ...
>> After browsing a bit the web...I found several ties that each radix-2
> stage
>> can scale the input by 1+sqrt(2).
>> I think this comes from the butterfly operation doing
>>
>> X'= X + TW*Y
>> Y'= Y -TW*Y
>>
>> Hence if for example Y = 1 + i, and TW is at pi/4 ----> Imag(X') will
> be
>> scaled with 1+sqrt(2) wrt X and Y (assuming X and Y equal).
>>
>> However to me assuming a scaling of 1+sqrt(2) for each stage looks a
> bit
>> pessimistic because:
>> - obviously not every butterfly will always pi/4 for the twiddle.
> E.g. the
>> first FFT stage will just use 1 or so as twiddle, hence I think the
> gain on
>> a branch would maximally be 2 in stead of 2.414
> ...
>>
>> Now my question: does my reasoning make sense...
>
> i didn't see how you were discounting the conventional wisdom regarding
> the absolute worst-case scaling.  you *could* have an X = +1, a Y = 1 +
> i, and a twiddle (operating on Y) of exp(-i*pi/4) and that would grow
> to 1 + sqrt(2) over your previous full scale.  that is the worst case.
>
> now, *if* you are doing some saturation or more graceful overflow than
> wrapping around, maybe you could get away with dividing by 2 each pass,
> or ever sqrt(2) which would preserve r.m.s.  but neither would
> absolutely, positively guarantee that overflow would never happen
> unless your input signal was sufficiently scaled down.
>

I guess our two examples (and I think there are more), both show that the 
maximum ratio between a real or imag branch butterfly output and input value 
can be 1+sqrt(2), ok ?

However my main question was if there is a path through the FFT so that in 
EACH stage this worst case scaling is present ? I think (but this is not 
proven) that such a path (over all FFT stages) should have pi/4 like (3pi/4, 
5pi/4, 9pi/4) twiddles and the incoming X and Y of each butterfly should 
continuously be the worst case outputs of the previous stages. I am just 
wondering if such a path exists. But if I am correct, the first FFT stage 
has no twiddles at pi/4, so already for the first stage this worst case gain 
of 1+sqrt(2) is not present.

NL 

Hi Newline,

 unless you have some knowledge on the input signal, you will have to
protect against the worst case that could overflow your FFT; if your
input signal is completely unknow, you may consider using a
block-floating point FFT, i.e each stage adjust the scaling depending
on the output of the previous stage.

on the other hand, if you have some information about the input signal
(for ex: OFDM modulator), just run a lot of simulation with the input
signal to see the scaling you need at 1st stage then at 2nd stage,
etc...

Julien

>Hi Newline,
>
> unless you have some knowledge on the input signal, you will have to
>protect against the worst case that could overflow your FFT; if your
>input signal is completely unknow, you may consider using a
>block-floating point FFT, i.e each stage adjust the scaling depending
>on the output of the previous stage.
>
>on the other hand, if you have some information about the input signal
>(for ex: OFDM modulator), just run a lot of simulation with the input
>signal to see the scaling you need at 1st stage then at 2nd stage,
>etc...
>
>Julien
>
>

Thanks for the response. 
I want to make a general purpose FFT, hence I know nothing of my input
signal. I agree I need to protect versus the worst case for overflow.

However my problem is exactly to find out what is the worst case.
The 1+sqrt(2) I have found a couple of times looks to me to be worser than
worst case. I think this because the 1+sqrt(2) comes from a pi/4 like
twiddle, but already in the first DIT FFT stage I have never a twiddle of
pi/4. So already at the output of my first stage I would have a bit too
much headroom. (and hence non optimal use of my bits)
Now if this is only valid in stage 1, probably there is not much to gain,
but I find it hard to figure this out for the next stages.






		
This message was sent using the Comp.DSP web interface on
www.DSPRelated.com

OK,

regarding fixe point scaling, here is some answer coming from a Texas
Instrument Application Note that I have .
I think they have some serious background in the domain of fixed point
fft :-)

  TI SPRA948 :
Thus, the input data must be
prescaled to allow for one bit of growth in the first two stages and
two bits of growth in
each stage thereafter if overflow is to be averted.

Julien

>OK,
>
>regarding fixe point scaling, here is some answer coming from a Texas
>Instrument Application Note that I have .
>I think they have some serious background in the domain of fixed point
>fft :-)
>
>  TI SPRA948 :
>Thus, the input data must be
>prescaled to allow for one bit of growth in the first two stages and
>two bits of growth in
>each stage thereafter if overflow is to be averted.
>
>Julien
>
>

Thanks, this is truly an interesting app note. If I read it carefully,
what it is saying is that in the first 2 stages you can get a growth of 2,
and all the next stages a growth of 2.414.
However I still do not belive that you need to compensate for 2.414 in
every last N-2 stages, simply because this 2.414 growth will not be
encountered in consecutive stages through 1 path.

Another way of reasoning:
Suppose a 256 point FFT. According to the paper this would have a growth
of 
2^2 * 2.414^6 = 792

However I think that a worst case input to my FFT would be when all output
would be on one FFT output point --> hence if my input is a pure sin/cos at
a certain frequency. For example a DC input (sin/cos of 0Hz). Obviously the
FFT output is just the sum of all the inputs. Hence I would conclude that
my maximum gain is 256 and not 792.


		
This message was sent using the Comp.DSP web interface on
www.DSPRelated.com

robert bristow-johnson wrote:

> testing...
> 
> sheesh, this new Google Groups is weird....
> 
> r b-j
> 

My ISP charges *more* than industry minimum.
For that I get:
1. PORTAL-less WEB access
2. Email with improving spam blocking and rock solid virus blocking
3. access to newsgroups via supernews.com

#3 is a biggee.
I don't see any of the problems many complain about.
I doubt that supernews.com is *ONLY* service that provides this advantage.

*YOU DO GET WHAT YOU PAY FOR*  ;)

PS. Haven't checked Google's privacy policy, But YAHOO's *STINKS*

"Richard Owlett" <rowlett@atlascomm.net> wrote in message
news:1156a5c444l73bd@corp.supernews.com...
> robert bristow-johnson wrote:
>
> > testing...
> >
> > sheesh, this new Google Groups is weird....
> >
> > r b-j
> >
>
> My ISP charges *more* than industry minimum.
> For that I get:
> 1. PORTAL-less WEB access
> 2. Email with improving spam blocking and rock solid virus blocking
> 3. access to newsgroups via supernews.com
>
> #3 is a biggee.
> I don't see any of the problems many complain about.
> I doubt that supernews.com is *ONLY* service that provides this advantage.
>
> *YOU DO GET WHAT YOU PAY FOR*  ;)

On the topic of news service, I used to use and recommend news.individual.net,
but just a week ago, they switched from being free to being a paid service.  Are
there any good free news servers out there?  My ISP offers one so I'm back to
using that.  It wasn't quite as good as news.individual.net, hence my switch,
but it is decent.  News servers/readers are vastly superior to web access, IMHO.