Re: FFT twiddle calculation and evaluation
- From: robert bristow-johnson <rbj@xxxxxxxxxxxxxxxxxxxx>
- Date: 23 May 2007 11:14:27 -0700
On May 23, 5:19 am, "mahesh_u2" <mahesh_susind...@xxxxxxxxxxx> wrote:
Thanks for the responses so far. While am aware of the formatm(complex)
and the values of the twiddles (after a good look around!) am looking for
some method of associating the various twiddle factors with the
butterflies in each stage.
e.g. For an 8 point DIF radix-2. We know there will be only 4 unique
weights: w0,w1,w2,w3.
from a POV of real numbers, there is really only 2, since w2=j*w0 and
w3=j*w1, the real and imaginary parts are just switched (and there's
one sign change which can be absorbed into the butterfly
implementation). that's one reason why an optimized radix-4 FFT can
save a lot (regarding memory accesses) over a radix-2. another reason
radix-4 might be neat is that you can always make it unary and put a 1/
sqrt(N) in both the forward and inverse. in fixed-point that would be
dividing by 2 for every other pass.
These can be derived from the FFT equation with
different values of k. The last stage (3rd) values would be multiplied by
1. Stage 1 and 2 remain with the interconnections between these being
predetermined from what i understand. So from literature twiddles:
w0,w1,w2,w3 are all used in the first stage. The second stage then
utilises twiddles: w0,w2 twice. What i'd like to be able to do is work out
what weights each stage utilises and which butterfly would use each weight.
do you want to generate these coefs in normal or in bit-reversed
order? there is a simple way to do it in normal order, but the errors
due to finite word size accumulate in a sorta bad way. doing it bit-
reversed order (w0,w2,w1,w3) is better numerically. you still need a
small table of two values, cos(delta) and sin(delta) (or, maybe 1-
cos() is better), for each N (power of 2), the FFT size if your FFT is
of a sorta general size.
.
- References:
- Re: FFT twiddle calculation and evaluation
- From: mahesh_u2
- Re: FFT twiddle calculation and evaluation
- Prev by Date: Any link for downloading sound files easier to localize
- Next by Date: Re: OT: US Immigration Legislation
- Previous by thread: Re: FFT twiddle calculation and evaluation
- Next by thread: Re: FFT twiddle calculation and evaluation
- Index(es):
Relevant Pages
|
