Radix-2 FFT equations

[Maverickmax]

radix 2 fft

Hi

As I am learning to implement FFT algorithm in C. I am aware some of these equations are related to buttefly calculation such as
a+bW^k and a-bW^k and cos(2PI/N)-jsin(2PI/N).

But I am struggling to understand why sin(x)*Im2 are needed in equation 1 and 2. Also cos(x)*Im2 in the equation 3 and 4.

Please help me to understand this concept

Re1 = Re1 + (cos(x)xRe2 + sin(x)*Im2) -> equation 1
Re2 = Re1 - (cos(x)xRe2 + sin(x)*Im2) -> equation 2

Im1 =Im1 + (cos(x)xIm2 - sin(x)*Re2) -> equatio 3
Im1 =Im1 + (cos(x)xIm2 - sin(x)*Re2) -> equation 4

Where

Re1 = Array[index_a]
Re2 = Array[index_b]

Im1 = Array[Index_a]
Im2 = Array[Index_b]

mm

 

[Maverickmax]

radix-2 fft

Any explaination?

MM

 

[doraemon]

fft equation

Hello!

The extensive explanation would be quite some pain, and on top of that, the
explanation exists in books and also probably on wikipedia, but let's make it
simple.
Let's say that it simply comes from the way the DFT is simplified in order to reduce
the calculations:
Suppose you have a number N of samples x(k) (N being a power of 2, 0<=k<n).
Now you calculate its fourier transform f(k).
Then, divide the input sample set into 2 sets, Ne and No (e & o, for even and odd).
Similarily calculate their fourier transforms f(ke) and f(ko).
You can therefore say that f(k) is the sum of f(ke) and f(ko)... but f(ko) is shifted
by a unit phase since your second set doesn't start at 0. This phase can be
modeled as cos(2*pi/N) + i sin((2*pi/N), usually written as W(2*pi/N) (or W1)
and this yields: F(k) = F(ke) + W1 F(ko).

Using the same method, you can further simplify each FFT until the size of the
sets is 2. At this point you get what is called a buttefly. But let's stop at this
first step.

From this first step, is is evident that the calculation of the FFT as a sum of 2
FFTs will involve the multiplication by the phase vector W1 (which is a complex
number). Therefore all the real part and also imaginary part individual calculation
will involve both real parts and imaginary parts. For all the further steps, there
will also composed phases coming from the first step phase W1, which gets
composed with phases of the further seps W2, W4, W8 and so on, generating
all the possible phases between W0 and WN/2.

By the way (off topic, but worth mentioning):
Another further simplification. If the signal is purely real, then the spectrum will
be symmetric. But calculating a symmetric spectrum is a waste of CPU, so you
can feed the imaginary part with another real signal to calculate 2 FFTs at once.

For further info you may be interested in reading "Digital processing of signals,
Theory and practice", from Maurice Bellanger. Maybe not the pope of signal
processing but at least a bishop. The explanations are extremely clear, but
that's not the proper kind of book for bedtime.

Dora.

Any explaination?

MM

 

[Communications_Engineer]

radix2 fft

Hi, in the Radix-2 algorithm Decimation in time for 2 iteration for 8-point DFT, why do we keep the twiddle factor to W(0,8.0) and W(2,8.0) where normally we go in the series W(0,Cool, W(1,Cool...

If I'm not clear, please read my question and look at the implementation of 8-point DFT using 2-point DFT by FFT DIT method

Added after 51 seconds:


the smiley represents eight, for some reason numerically writing eight and bracket coverts it into a smiley