# Implementing inverse FFT using forward FFT

I am trying to implement an inverse FFT using the forward FFT. For clarity:

Let S[t] be a signal in time, and S[w] the transformed signal. As per this site, it seems one can reverse S[w], use the forward FFT routine, then reverse the resulting signal again and this should give S[t]. I won't go into why should it work but it's all in the link provided.

I attempted to try this method, and it seems to recreate the signal when I use a high sample rate. However, it seems that even if I do not go over the niquist frequency, I encounter some weird effect. Here is my code in numpy:

# Generate a signal of s cosine with 200 [Hz]
f = 200
Fs = 10
t = np.linspace(-10,10,Fs*20)
s = cos(2*np.pi*f*t)

# Take fft
u = np.fft.fft(s)

# Reverse in time
u = u[::-1]

# Transform again
u_t = np.fft.fft(u)

# Reverse and normalize

s_new = np.divide(u_t[::-1],s.shape[-1])

# Finally slice for easier viewing
plt.plot(t[1:100],s_new[1:100])
plt.plot(t[1:100],s[1:100])


This code yields the following graph: I am a little confused, the theory looked sound and I can't think what I did wrong here.

Note: I tried calling np.fft.fft and then np.fft.ifft and the reconstruction goes as planned. Therefore I believe this problem is not due to aliasing.

Edit: I made way by simply taking the complex conjugation instead of reversing (using np.conj() where I reverse). This solves the problem, but I still do not understand why reversing in time does not accomplish a conjugation, so I'd love someone to explain it to me. I leave the modified code in case it helps someone else:

# Generate a signal
f = 200
Fs = 10
t = np.linspace(-10,10,Fs*20)
s = cos(2*np.pi*f*t)

# Take fft
u = np.fft.fft(s)

# Conjugate
u = np.conj(u)

# Transform again
u_t = np.fft.fft(u)

# conjugate and normalize

s_new = np.divide(np.conj(u_t),s.shape[-1])

# Finally slice for easier viewing
plt.plot(t[1:100],s_new[1:100])
plt.plot(t[1:100],s[1:100])

• 1) f=200;Fs=10 2) What is the purpose of the time reversal in your code? Try to spot the differences in the forward and inverse transforms here. Something is indeed flipped between the forward and inverse transforms but that is certainly not the time order of the samples (?).
– A_A
Nov 28 '16 at 21:24
• @A_A I think the link I provided explains the rational (-: Nov 28 '16 at 21:25

The time reversal $y(t)$ of a continuous signal $x(t)$ is given by $y(t)=x(-t)$. Similarly, for a discrete signal we have $y[n]=x[-n]$. However, here the delicate issue occurs that $n=0...N-1$, where $N$ is the signal length. Now, noting that in the finite discrete domain every signal is considered to be periodic with $N$, you get $$y[n] = x[-n] = x[(-n)_N]$$

where $(x)_N$ is the modulo operation of $x$ by $N$. Hence, time-reversal in the discrete domain is not just reading your vector from back to front. Instead, the first element remains the same ($n=0$) and the others are read from back to front.

Now coming to the time-reversal property wtih the Fourier Transform:

• $FFFF=I$ where $F$ is the (unitary) Fourier transform operator and $I$ is the identity. I.e. applying 4 times the (forward) Fourier transform yields the original signal.
• Hence, logically $FFF=F^H$, where $F^H$ is the inverse Fourier Transform (yes, it is also the Hermitian of the forward transform). However, calculating inverse FFT by 3 times forward FFT is not very efficient...
• Further, we know $FF=T$ where $T$ is the inflection operator $(Tx)[n]=x[-n]$, again read with the modulo interpretation.

Hence, we find $F^H=TF$, i.e. in order to caculate inverse FFT, you can do forward FFT and time-reverse the result:

f = 0.1
Fs = 10
t = np.linspace(-10,10,Fs*20)
s = np.cos(2*np.pi*f*t*(t+1))

# Take fft
U = np.fft.fft(s)

# Transform again
u_t = np.fft.fft(U)

# Reverse and normalize

s_new = np.divide(u_t[-np.arange(u_t.shape)],s.shape[-1])

# Finally slice for easier viewing
plt.figure(figsize=(12,4))
plt.plot(t,s_new)
plt.plot(t,s) In Short if $$X[k]$$ represents the $$N$$-point FFT of an $$N$$-point signal $$x(n)$$ , then $$N * x(n)$$ (sequence $$x(n)$$ scaled by $$N$$) can be obtained by performing FFT on the sequence $$X, X[N-1], X[N-2], \cdots ,X$$.

Explanation:

Consider the equation of IFFT

$$IFFT: x[n] = \frac{1}{N} ( \sum_{k=0}^{N−1}X[k]*e^{j2πnk/N} )$$

It can be split and written in the following way

$$x[n] = \frac{1}{N} ( X + \sum_{k=1}^{N−1}X[k]*e^{j2πnk/N} )$$

$$x[n] = \frac{1}{N} ( X + \sum_{k=1}^{N−1}X[N - k]*e^{j2πn(N-k)/N} )$$

$$x[n] = \frac{1}{N} ( X + \sum_{k=1}^{N−1}X[N - k]*e^{j2πn(N)/N}*e^{-j2πn(k)/N})$$

The term $$e^{j2πn(N)/N}$$ evaluates to one and hence the above can be re written as

$$x[n] = \frac{1}{N} ( X + \sum_{k=1}^{N−1}X[N - k]*e^{-j2πn(k)/N})$$

$$x[n] = \frac{1}{N} ( X * e^{-j2π(0)(k)/N} + \sum_{k=1}^{N−1}X[N - k]*e^{-j2πn(k)/N})$$

Consider a series $$Y[k]$$ defined as follows

$$Y = X$$ and

$$Y[k] = X[N-k]$$ $$for$$ $$k = 1,2,\cdots,N-1$$

Then the last of the above equation can be re written as

$$x[n] = \frac{1}{N} ( Y * e^{-j2π(0)(k)/N} + \sum_{k=1}^{N−1}Y[k]*e^{-j2πn(k)/N})$$

$$x[n] = \frac{1}{N} ( \sum_{k=0}^{N−1}Y[k]*e^{-j2πn(k)/N})$$

$$x[n] = \frac{1}{N} ( FFT(Y[k]))$$

Where $$Y[k]$$ is the series obtained from rearrangement of $$X[k]$$

$$X, X[N-1], X[N-2], \cdots, X$$