## 4 Educational Guide
### Fourier Analysis of Signals (Part 2)
The real (imaginary) part of a Fourier coefficient \(X(k)\) can be interpreted as the inner product of the input signal \(x\) and a sampled version of the cosine (sine) function of frequency \(k/N\). In our notebook, we provide a concrete example that illustrates how this inner product can be interpreted as the correlation between a signal \(x\) and the cosine (sine) function. We recommend that students experiment with different signals and frequency parameters \(k\) to deepen the intuition of these correlations. From a computational view, the vector \(X\) can be expressed by the product of the matrix \(\text{DFT}_{N}\) with the vector \(x\). Defining the complex number \(\sigma_{N}:=\exp(-2\pi i/N)\) (which is a specific root of unity), one can express the DFT matrix in a very compact form given by \(\text{DFT}_{N}(n,k)=\sigma_{N}^{nk}\) for \(n,k\in[0:N-1]\). Visualizing the real and imaginary parts of the DFT matrix reveals its structural properties (see Figure 7). In particular, one can observe that the rows of the DFT matrix correspond to sampled cosine (real part) and sine (imaginary part) functions. The specific structure of the matrix \(\text{DFT}_{N}\) (with its relation to \(\text{DFT}_{M}\) for \(M=N/2\)) can be exploited in a recursive fashion, yielding the famous fast Fourier transform (FFT). In our notebook, we provide an explicit implementation of the FFT algorithm and present some experiments, where we compare the running time of a naive implementation with the FFT-based one. We think that implementing and experimenting with the FFT--an algorithm of great beauty and high practical relevance--is a computational eye opener and a must in every signal processing curriculum. Computing a DFT results in complex-valued Fourier coefficients, where each such coefficient can be represented by a magnitude and a phase component. In the FMP Notebook _DFT: Phase_, we provide a Python code example that highlights the optimality property of the phase. Studying this property is the core of understanding the role of the phase--a concept that is often difficult to access for students new to the field. Another central topic of signal processing is the short-time Fourier transform (STFT), which is covered in ([1], Section 2.5) for the analog and discrete case. In the FMP Notebook Discrete Short-Time Fourier Transform (STFT), we implement a discrete version of the STFT from scratch and discuss various options for visualizing the resulting spectrogram. While the main idea of the STFT, where one applies a sliding window technique and computes for each windowed section a DFT, seems simple, computing the discrete STFT in practice can be tricky. In an applied signal processing course, it is essential to make students aware of the different parameters and conventions when applying windowing. Our notebooks provide Python implementations that allow students to experiment with the STFT (applied to synthetic signals and real music recordings) and to gain an understanding on how to physically interpret discrete objects such as samples, frames, and spectral coefficients. In the FMP Notebook STFT: Influence of Window Function, we explore the role of the window type and window size. Furthermore, in the FMP Notebook STFT: Padding, we discuss various padding conventions that become crucial to correctly interpret and visualize feature representations. This important topic, which is a typical source of inaccuracies and errors in music processing pipelines, is illustrated by simple examples as a basis for further exploration (see also Figure 8). One main limitation of the discrete STFT is the linear frequency grid whose resolution is determined by the signal's sampling rate and the STFT window size. In the FMP Notebook STFT: Frequency Grid Density, we deepen the understanding on the connection between the different parameters involved. In particular, we discuss how to make the frequency grid denser by suitably padding the windowed sections in the STFT computation. Often, one loosely says that this procedure increases the frequency resolution.