The discrete Fourier transform (DFT) converts finite samples of a signal, such as a sound wave, into numerical frequency components. Its inverse reconstructs the signal from those components, supporting digital audio encoding and analysis. section 7.0
The DFT compares a discrete signal with sinusoidal Fourier bases of different frequencies. Each output is a complex number whose magnitude and phase describe that frequency component; together, the outputs decompose the signal into frequency bins. section 7.3.1
A direct Python implementation follows the correlation-based definition:
- Build Fourier bases from complex rotations, using a sequence length N and frequency index l. section 7.3.1
- Compute each coefficient as the inner product between the samples and its corresponding basis. section 7.3.1
- Apply the same calculation across all frequency indices to produce the complete DFT sequence. section 7.3.1
- Check the result with NumPy's FFT, a high-performance classical algorithm for computing the DFT. section 7.3.1
Recovering frequencies from sampled data
For N = 8, sample a cosine wave with frequency 1.7, normalize the samples, and correlate them with eight Fourier bases. The resulting complex sequence contains conjugate-symmetric components, with large values near the signal's dominant frequency. NumPy's FFT produces the same values as the explicit inner-product implementation. section 7.3.1
N = 4 omega = cis(2*pi/N) F_0 = [omega**(0*k) for k in range(N)] F_1 = [omega**(1*k) for k in range(N)] F_2 = [omega**(2*k) for k in range(N)] F_3 = [omega**(3*k) for k in range(N)]
Inspect the explicit Python construction of four Fourier bases for N = 4 before calculating signal correlations. section 7.3.1
