3
$\begingroup$

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.

$\endgroup$
0

3 Answers 3

6
$\begingroup$

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!)

$\endgroup$
4
$\begingroup$

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));

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

subplot(2,1,2);
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.

$\endgroup$
2
$\begingroup$

Today I read this in the documentation for FFTW (emphasis mine):

There is no sign parameter in fftw_plan_guru_split_dft. This function always plans for an FFTW_FORWARD transform. To plan for an FFTW_BACKWARD transform, you can exploit the identity that the backwards DFT is equal to the forwards DFT with the real and imaginary parts swapped.

This means that we must swap the real and imaginary parts of the input, and then also of the output.

We also need to take into account that the ifft typically normalizes by N.

For example, in MATLAB,

N = 8;
x = complex(randn(N, 1), randn(N, 1));

X = fft(x);

Y = complex(imag(X), real(X)); % swap real and imaginary components
y = fft(Y) / N;
y = complex(imag(y), real(y)); % swap real and imaginary components

all(x-y < 1e-15)
$\endgroup$

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.