{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Unit 9: Discrete Fourier Transform (DFT)\n", "\n", "np.dot
. Since the number of operations for computing a DFT via a simple matrix–vector product is quadratic in the input length, the runtime of this approach becomes problematic with increasing length. This issue is exactly where the fast Fourier transform (FFT) comes into the game. We present this famous divide-and-conquer algorithm and provide a Python implementation. Furthermore, we compare the runtime behavior between the FFT implementation and the naive DFT implementation. We will further deepen your understanding of the Fourier transform by considering further examples and visualization in the exercises. In Exercise 1, you will learn how to interpret and plot frequency indices in a physically meaningful way. In Exercise 2, we discuss the issue of loosing time information when applying the Fourier transform, which is the main motivation for the short-time Fourier transform. In Exercise 3, you will apply the DFT to a chirp signal, which yields another illustrative example of the DFT's properties. Finally, in Exercise 4, we will invite you to explore the relationship between the DFT and its inverse. Again, an overarching goal of this unit is to apply and deepen your Python programming skills within the context of a central topic for signal processing. \n",
" \n",
"np.vdot
to compute the inner product. However, opposed to the mathematical convention that conjugates the second argument, this function applies complex conjugation on the first argument. Therefore, for computing $\\langle x | y \\rangle$ as defined above, one has to call np.vdot(y, x)
.\n",
"dft
and fft
implementations do not yield the same result (due to numerical issues). However, the results are numerically very close, which is verified by the test using np.allclose
. \n",
"np.fft.fft
."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import timeit\n",
"\n",
"rep = 3\n",
"for N in [256, 512, 1024, 2048, 4096]:\n",
" time_index = np.arange(N)\n",
" x = np.sin(2 * np.pi * time_index / N )\n",
" t_DFT = 1000 * timeit.timeit(lambda: dft(x), number=rep)/rep\n",
" t_FFT = timeit.timeit(lambda: fft(x), number=rep*5)/(rep*5)\n",
" t_FFT_np = timeit.timeit(lambda: np.fft.fft(x), number=rep*100)/(rep*100)\n",
" print(f'Runtime (ms) for N = {N:4d} : DFT {t_DFT:10.2f}, FFT {t_FFT:.5f}, FFT_np {t_FFT_np:.8f}')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercises and Results"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import libpcp.dft\n",
"show_result = True"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"plot_signal_dft
uses these properties to convert and visualize the time and frequency axes.x, t = libpcp.signal.generate_example_signal(Fs=64, dur=2)
, plot the signal and its magnitude Fourier transform once using axes given in indices and once using axes given in physical units (seconds, Hertz). Discuss the results.x, t = libpcp.signal.generate_example_signal(Fs=32, dur=2)
. What is going wrong and why?np.linspace
), with $N\\in\\mathbb{N}$ being power of two (e.g., $N=256$). Define DT-signals of the superposition and the concatenation and compute the DFT for each of the signals. Plot the signals as well as the resulting magnitude Fourier transforms and discuss the result.\n",
"x
over the interval $[t_0,t_1]$ with $N$ samples (use np.linspace
).x
for various input parameters $t_0$, $t_1$, and $N$. Plot the chirp signal as well as the resulting magnitude Fourier transform. Discuss the result.generate_matrix_dft_inv
that explicitly generates $\\mathrm{DFT}_N^{-1}$. \n",
"np.matmul
) and comparing these products with the identity matrix (using np.eye
and np.allclose
).np.linalg.inv
. Compare the result with your function using np.allclose
.\n",
"fft
, implement a fast inverse Fourier transform fft_inv