2
$\begingroup$

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: enter image description here

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])
$\endgroup$
  • $\begingroup$ 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 (?). $\endgroup$ – A_A Nov 28 '16 at 21:24
  • $\begingroup$ @A_A I think the link I provided explains the rational (-: $\endgroup$ – Bloodworth Nov 28 '16 at 21:25
4
$\begingroup$

In your link I cannot find a reference to the time-reversal. However, here are some additions:

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[0])],s.shape[-1])

# Finally slice for easier viewing
plt.figure(figsize=(12,4))
plt.plot(t,s_new)
plt.plot(t,s)

enter image description here

$\endgroup$

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.