# Fast fourirer transform - Even and odd numbered elements

I'm trying to understand some optimizations on DFT. So in this step, there is a note like the following:

The next step involves the mathematical observation that the even-numbered elements can be computed separately from the odd ones. In cases where n is even, this will reduce the number of multiplications by half.

And this is the formula for even part:

odd part:

Sorry for this newbie question but I have watched several videos, read a number of papers but still don't get how the "sum[k]" is generated.

btw: m is N/2

how the "sum[k]" is generated.

Add the first and the second half or your input. If you have a buffer of 16 samples, you can from a sequence of 8 samples by taking samples 0 to 7 and add samples 8 to 15.

The 8 point FFT over your 8 sample sequence equals the even indexed values of the FFT over your original 16 sample sequence.

The factor of 0.5 is wrong (I think) and the notation isn't great, so perhaps you want to look for a better source of information.

In cases where n is even, this will reduce the number of multiplications by half.

Not really.

• I added the odd part maybe it will make sense. there is a code snippet for this equation and its working well, so I think it's not wrong but I'm burnout. Aug 28, 2021 at 12:32
• Well this really just the first stage of any decimation-in-frequency FFT. Aug 28, 2021 at 12:35