0
$\begingroup$

I'm trying to implement IDFT using multiple smaller forward DFTs but am confused as to how to do so.

So, I know that the N-point IDFT can be expressed in terms of the forward DFT by: $$ IDFT = \frac{1}{N}[DFT(X_n^*)]^* $$

Also, an N-point DFT can be implemented with two N/2-point DFTs by performing a DFT on the even-indexed samples and another on the odd-indexed samples.

How would I go about combining these concepts?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Just follow your recipe as written

  1. Conjugate your frequency domain vector
  2. Apply DFT on even samples
  3. Apply DFT on odd samples
  4. Recombine the two $N/2$ DFTs to create the $N$ point DFT result
  5. Conjugate the DFT result and divide by N.

You can swap the last two steps, if you want.

Keep in mind that there is rarely a good reason to split an $N$ point DFT into two $N/2$ point DFTs. Because of the recombination it's typically more as expensive a single full size DFT. In essence you just take one stage out of the FFT algorithm and compute it manually. The only reason to go there if you have severe memory constraints or cache management issues.

That's different from using a $N/2$ point complex FFTs to compute an $N$ point FFT on real value data. That's generally a considerable savings.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Many thanks for your reply. I have tried implementing those steps in MATLAB using fft() but cannot reach the same result as one would get from the in-built ifft() function.My main goal is to be able to process a signal by splitting it up, processing individual portions, and recombining. To give an example, say you had 1024-samples from a DFT but were limited by hardware that could only process 32-samples at a time. $\endgroup$
    – larry_lasers
    Commented May 6, 2020 at 11:42
  • $\begingroup$ You are probably looking a the wrong solution then. Please post details on what exactly your application/requirements and what your constraints are. $\endgroup$
    – Hilmar
    Commented May 6, 2020 at 13:21
  • $\begingroup$ I haven't an application per se, more trying to wrap my head around DSP theory. After reading about the Cooley-Tukey FFT algorithm I was wondering if it would be possible to apply it in reverse to achieve a decomposed IFFT. $\endgroup$
    – larry_lasers
    Commented May 6, 2020 at 14:57
  • $\begingroup$ Nice answer Hilmar. What might not be clear although is assumed is that the recombination must be done with the linear phase $W_n^k$ term? $\endgroup$
    – Dan Boschen
    Commented May 6, 2020 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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