-1
$\begingroup$

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:

enter image description here

odd part:

enter image description here

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

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – badcode
    Aug 28, 2021 at 12:32
  • $\begingroup$ Well this really just the first stage of any decimation-in-frequency FFT. $\endgroup$
    – Hilmar
    Aug 28, 2021 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.