Fast Fourier Transform (FFT) examples

The Discrete Fourier Transform(DFT) is defined by X_k = \sum_{n=0}^{N-1} x_n \cdot e^{-i 2 \pi \frac{k}{N} n} latex and the inverse fourier transform is defined as x_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k \cdot e^{+i 2 \pi \frac{k}{N} n} latex

In [2]:
from __future__ import division
import numpy as np
import matplotlib.pyplot as plt
import time

'''
	Define two functions to compute fourier transforms using two different methods
	1.	dft(x,inverse=False,timer=False): for INVERSE: inverse=true
						  for timed: timer=true
	2.	timedfft(x,inverse=False,timer):for INVERSE: inverse=true
						  for timed: timer=true
	3.	func(x): defines function at x
'''

def func(x):
    f=10.0 
    val=np.sin(2*np.pi*f*x)
    return val

'''
   	Computes the discrete fourier transform /inverse fourier transform
	using basic summation convention.
	OPTIONS:
		inverse: computes inverse fourier transform
		timer:	 prints time required for computation
'''
def dft(x, inverse = False, timer = False) :

    t = time.clock()							#get current time to calculate the computation time
    N = len(x)
    if inverse:
        inv=1
    else:
        inv=-1

    X =[0] * N								#make an array of size N

    for k in xrange(N) :						#compute the required sum
        for n in xrange(N) :
            X[k] += x[n] * np.e**(inv * 2j * np.pi * k * n / N)
        if inverse :
            X[k] /= N

    t = time.clock() - t						#get delta time
    if timer :
        print "Computed DFT of size",N,"in",t,"sec."
    return X

'''
	fourier transform using built in fast fourier method
'''

def timedfft(x,inverse=False,timer=False):

	t=time.clock()
	if not inverse:X=np.fft.fft(x)
	else:	X=np.fft.ifft(x)
	t=time.clock()-t
	if timer: print "Computed DFT using fft of size",len(x),"in",t,"sec."
	return X

'''
	Computing part: 1. Define a function over a interval
			2. Compute fourier transform using the two methods
			3. Compare time
'''

#fix sample size, this gives the the rate of sampling of the function
sample_size=2**8
L=5.0
x=np.linspace(0,L,sample_size)

#there are four plots 1.original signal 2.fourier transformed signal 3.fast fourier transformed signal 4.Reconstructed signal

plt.subplot(411)
plt.xlabel('t')
plt.ylabel('f($t$)')
plt.xlim([0,L/10])
signal=func(x)
plt.plot(x,signal,label='original signal')

'''
				In [20]: run fourier_basic.py
				Computed DFT using fft of size 256 in 0.0 sec.
				Computed DFT of size 256 in 0.48 sec.
				Computed DFT of size 256 in 0.16 sec.

				In [21]: run fourier_basic.py
				Computed DFT using fft of size 4096 in 0.0 sec.
				Computed DFT of size 4096 in 123.94 sec.
				Computed DFT of size 4096 in 43.18 sec.
'''
#compute timed fft
fourierfft=timedfft(signal,timer=True)

#caluclate discrete fourier transform using normal method
fourier =dft(signal,timer=True)

#get the frequencies
n=x.size
d=x[1]-x[0]
freqsfft=np.fft.fftfreq(n,d)

#get positive index
indices=np.where(freqsfft>=0)

#plot
plt.subplot(412)
plt.xlabel('freq')
plt.ylabel('f($\omega$)')
plt.plot(freqsfft,fourierfft,label='FFT')

plt.subplot(413)
plt.xlabel('freq')
plt.ylabel('f($\omega$)')
plt.plot(freqsfft,fourier,color='green',label='Without FFT')

#inverse fourier transform using dft
invfourier=(dft(fourier,inverse=True,timer=True))

plt.subplot(414)
plt.xlabel('t')
plt.ylabel('f($t$)')
plt.xlim([0,L/10])
plt.plot(x,invfourier,'+-',color='red')
display(gcf())
Computed DFT using fft of size 256 in 0.0 sec.
Computed DFT of size 256 in 0.48 sec.
Computed DFT of size 256 in 0.16 sec.

/numpy/core/numeric.py:235: ComplexWarning: Casting complex values to real discards the imaginary part
  return array(a, dtype, copy=False, order=order)

N.B.: The fourier transform of the function is symmertric about 0.
Thus it suffices to display only the positive half,
as the negetive half gives us no more information

In [3]:
clf()
plt.subplot(111)
pi=np.pi
sampled=5*np.sin(2*pi*x)+np.sin(2*pi*10*x)
fourier=np.fft.fft(sampled)
#if you want to print only the positive frequencies
index=np.where(freqsfft>=0)
plt.plot(freqsfft[index],fourier[index])
display(gcf())

In [39]:
clf()
sampled=np.exp(-x**2)
fourier=np.fft.fft(sampled)
plt.plot(freqsfft,fourier)
display(gcf())

In [40]:
clf()
from scipy.special import jn
sampled=jn(2,x)
fourier=np.fft.fft(sampled)
plt.plot(freqsfft,fourier)
display(gcf())

Advertisements

Any thoughts?

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s