CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.

| Download
Views: 143
Tweet
Share
Share
Kernel: Python 3 (Ubuntu Linux)

Math 157: Intro to Mathematical Software

UC San Diego, Winter 2018

Fast Fourier Transforms

By: Anastasia Guanio

"4 E YAY"

Goals:

  • Understand the definition of Fast Fourier Transforms (FFT) (#Students will be able to have a foundation of the topic)

  • Know practical applications of FFT (#Students will understand why we are learning this/why it is useful)

  • Be able to apply knowledge of FFT to examples

Fast Fourier Transform (FTT)

What is FFT?

  • An algorithm that samples a signal over a period of time (or space) and divides it into its frequency components

  • Many different FFT algorithms based on a wide range of published theories like simple complex-number arithmetic, group theory, and number theory

  • FFT is a way to compute the same result more quickly (as opposed to Discrete Fourier Transformation (DFT))

Simply explaining FFT using a metaphor

  • What does the Fourier Transform do? Given a smoothie, it finds the recipe.

  • How? Run the smoothie through filters to extract each ingredient.

  • Why? Recipes are easier to analyze, compare, and modify than the smoothie itself.

  • How do we get the smoothie back? Blend the ingredients.

Why FFT?

  • Almost every imaginable signal can be broken down into a combination of simple waves. This fact is the central philosophy behind Fourier transforms

  • Fourier transforms (FT) take a signal and express it in terms of the frequencies of the waves that make up that signal

  • Sound is probably the easiest thing to think about when talking about Fourier transforms

Real Life Applications

  • Sound wave analysis

  • Image data analysis

  • Digital image processing

  • Computer-assisted image processing

  • Edge detection

Example with Sound Waves

import matplotlib.pyplot as plt
from scipy.io import wavfile as wav
from scipy.fftpack import fft
import numpy as np

rate, data = wav.read('whistle.wav')
fft_out = fft(data)
%matplotlib inline
plt.plot(data, np.abs(fft_out))
plt.axis([0,250,0,40000])
plt.show()
Image in a Jupyter notebook

Example with Discrete Cosine Transform

The DCT exhibits the “energy compaction property”, meaning that for many signals only the first few DCT coefficients have significant magnitude. Zeroing out the other coefficients leads to a small reconstruction error, a fact which is exploited in lossy signal compression (e.g. JPEG compression).

The example below shows a signal x and two reconstructions ( and )from the signal’s DCT coefficients. The signal is reconstructed from the first 20 DCT coefficients, is reconstructed from the first 15 DCT coefficients. It can be seen that the relative error of using 20 coefficients is still very small (~0.1%), but provides a five-fold compression rate.

>>> from scipy.fftpack import dct, idct
>>> import matplotlib.pyplot as plt
>>> N = 100
>>> t = np.linspace(0,20,N)
>>> x = np.exp(-t/3)*np.cos(2*t)
>>> y = dct(x, norm='ortho')
>>> window = np.zeros(N)
>>> window[:20] = 1
>>> yr = idct(y*window, norm='ortho')
>>> sum(abs(x-yr)**2) / sum(abs(x)**2)
0.0010901402257
>>> plt.plot(t, x, '-bx')
>>> plt.plot(t, yr, 'ro')
>>> window = np.zeros(N)
>>> window[:15] = 1
>>> yr = idct(y*window, norm='ortho')
>>> sum(abs(x-yr)**2) / sum(abs(x)**2)
0.0718818065008
>>> plt.plot(t, yr, 'g+')
>>> plt.legend(['x', '$x_{20}$', '$x_{15}$'])
>>> plt.grid()
>>> plt.show()
Image in a Jupyter notebook

This Worksheet: Exercises

  1. Create plot of sound waves that represent a dolphin squeak

  2. Perform a Fast Fourier Transform (FFT) on a sound file.

Through this problem set, use the Python 3 (Ubuntu Linux) kernel except as specified.

Exercise 1

Perform a Fast Fourier Transform (FFT) on a sound file.

For this example, use the sound files already found in this assignment's folder (titled 'whistle.wav and dolphin.wav').

To experiment with different sound wav files, find more here. (Note: wav files over 24KB are too large to analyze)

Solution:

import matplotlib.pyplot as plt
from scipy.io import wavfile as wav
from scipy.fftpack import fft
import numpy as np

rate, data = wav.read('dolphin.wav')
fft_out = fft(data)
%matplotlib inline
plt.plot(data,np.abs(fft_out))
plt.axis([0,250,0,10000])
plt.show()
Image in a Jupyter notebook
Exercise 2

Perform a Fast Fourier Transform (FFT) on a sound file.

For this example, use the sound files already found in this assignment's folder (titled 'whistle.wav and dolphin.wav').

To experiment with different sound wav files, find more here. (Note: wav files over 24KB are too large to analyze)

%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt
import scipy.fftpack

# Number of samplepoints
N = 600
# sample spacing
T = 1.0 / 800.0
x = np.linspace(0.0, N*T, N)
y = np.sin(50.0 * 2.0*np.pi*x) + 0.5*np.sin(80.0 * 2.0*np.pi*x)
yf = scipy.fftpack.fft(y)
xf = np.linspace(0.0, 1.0/(2.0*T), N/2)

fig, ax = plt.subplots()
ax.plot(xf, 2.0/N * np.abs(yf[:N//2]))
plt.show()
/usr/local/lib/python3.5/dist-packages/ipykernel/__main__.py:13: DeprecationWarning: object of type <class 'float'> cannot be safely interpreted as an integer.
Image in a Jupyter notebook