Say you start out with $A=\left\{3,−1,0,0\right\}$, run fft() and end up with $B=\left\{2,3+j,4,3-j\right\}$.

What specific steps would need to be done to obtain $A=\left\{3,−1,0,0\right\}$ again using some pre-calculation on $B$, then fft(), then maybe post-calculation steps before obtaining $A$? I have heard that this is possible but have not been able to work out how.


We want to do inverse DFT: $$ x(k) = \frac{1}{\sqrt{N}}\sum_n y(n) e^{j 2\pi kn/N}, $$ but can only do forward DFT. So let's try to make it "look" like a forward DFT. Note that we want a minus sign in the complex exponential. We can introduce it via complex conjugation: $$ \overline{x(k)} = \frac{1}{\sqrt{N}}\sum_n \overline{y(n)} e^{-j 2\pi kn/N}, $$ That is starting to look like a forward DFT now! So the recipe is:

  1. Complex conjugate the given sequence that we want to inverse DFT
  2. Calculate its forward DFT
  3. Calculate complex conjugate of the result.

That gives you the inverse DFT of the original sequence.

(Note that I cheated a little bit on the scaling factor to make it easier!)


Alternatively to Atul's idea, you can also exploit the time-reversal property of the DFT:

N = 10;

x = randn(N, 1) + 1j*randn(N,1);

X = fft(x);

x2 = 1/N*fft(X);
x2 = x2(1+mod(-(0:N-1), N));

plot(real(x), 'ob')
hold on;
plot(real(x2), 'x-r');
hold off;

plot(imag(x), 'ob')
hold on;
plot(imag(x2), 'x-r');
hold off;

enter image description here

The inverse DFT is equal to the forward DFT, but the result is time-reversed. Note that in the discrete domain time-reversal accounts to not just a simple "read from the back to front" but it corresponds to reading the first element and then from back to front. See also here.


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