MPAE2: Fourier Transform

Prerequisites

To work on this exercise, you should first work through the Lecture on Fourier Analysis of Signals. The FMP Notebooks mentioned in the lecture overview will be particularly helpful!

Task 1: Complex Numbers

Work through the PCP notebook on Complex Numbers and complete exercises 1 and 2.

Discussion

• In which ways can we order a set of complex numbers?
• Which kind of polynomials have all their roots on the unit circle? Which kind has only real roots?

Task 2: Exponential Function

Work through the PCP notebook on the Exponential Function and complete exercise 1.

Discussion

• Can you find arguments for and against the idea that the complex exponential function is a "more basic oscillation function" than the sine/cosine?

Task 3: Sampling, Aliasing, Beating

Work through the PCP notebook on Signals and Sampling and complete exercises 1 and 2. Be sure that you understand the concepts of sampling, aliasing and beating.

Take an audio file (e.g. your favorite song) and listen to downsampled versions of it at different sampling rates. Can you find signals for which the effect is more pronounced? And can you find signals for which the original and the downsampled version sound (almost) identical? Hint: You can use ipd.Audio from the IPython library to play audio files in this notebook.

import numpy as np
import soundfile as sf
import IPython.display as ipd

# <your solution goes here>

Task 4: Quantization

Work through the FMP notebook on Quantization.

Take the audio signal from Task 3 and experiment with different quantization levels (you can copy the quantize_uniform function from the FMP notebook to use it here). At which quantization strength do you begin to hear quantization noise? What is the difference to non-uniform quantization from musical/perceptual perspective?

# <your solution goes here>

Task 5: Discrete Fourier Transform (DFT)

Work through the PCP notebook on the DFT and FFT (you may skip the part on the FFT for now) and complete exercises 1, 2 and 3. You can also consult the FMP notebook on DFT and FFT for more explanations of the concepts.

Discussion

• Explain in your own words: What happens to a signal $x$ when it is multiplied with the matrix $\mathrm{DFT}_N$? Check your understanding by looking at the visualizations of $\mathrm{Re}(\mathrm{DFT}_N)$ and $\mathrm{Im}(\mathrm{DFT}_N)$ and answering the following questions:
  • Why do both matrices show a 2-by-2 pattern?
  • Why are the quadrants of the 2-by-2 pattern in $\mathrm{Im}(\mathrm{DFT}_N)$ separated by white lines?
  • In $\mathrm{Re}(\mathrm{DFT}_N)$, you can see circles which are, alternatingly, blue-red-blue-red... Why do they appear?
  • In $\mathrm{Im}(\mathrm{DFT}_N)$, you can see colored circles, too. Observe, however, that the colors do not match between neighboring quadrants. Why does this happen?
• What is the Fourier transform from a polynomial perspective? Or from a linear algebra perspective? Or from a musical perspective?

Task 6: Fast Fourier Transform (FFT)

YouTube video: "The Most Important Algorithm Of All Time"

We want to compare the naive DFT and the FFT (the Cooley-Tukey algorithm in particular). For this, we first have to understand how the FFT works. Read the FMP notebook on DFT and FFT and Section 2.4.3 of the text book. If you prefer video content, this lecture may also be helpful. You should be able to answer the following questions:

• Which length should the input sequence have? What kind of sequences are possible?
• Why do we have $\sigma_M = \sigma_N^2$?
• Why do we say that the FFT algorithm is a recursive algorithm?
• Why does naive application of the DFT take operations in the order of $N^2$?

Finally, we want to see how much faster the FFT is in practice. First, implement both a DFT and an FFT for an arbitrary real input sequence below. Then we use the timeit module to compare your implementations. How does the speedup factor change for different sequence lengths? Can you relate this to the computational complexity?

If you want, it will not be difficult to find existing Python implementations of the DFT/FFT (even in the linked material) and you can use them for inspiration. It is however important that you understand the code in detail.

import timeit

def dft(x):
    # <your solution goes here>

def fft(x):
    # <your solution goes here>

N = 128
x = np.random.rand(N)
num_iterations = 1000

time_dft = timeit.timeit(stmt='dft(x)', globals=globals(), number=num_iterations)
time_fft = timeit.timeit(stmt='fft(x)', globals=globals(), number=num_iterations)
time_fft_np = timeit.timeit(stmt='np.fft.rfft(x)', globals=globals(), number=num_iterations)

print("Average execution time for...\nDFT: %.5fs\nFFT: %.5fs\nFFT (numpy): %.5fs" % (time_dft / num_iterations, time_fft / num_iterations, time_fft_np / num_iterations))
print("FFT is %.2f times faster than DFT." % (time_dft / time_fft))