Discrete Fourier Transform & Frequency Decomposition
The Discrete Fourier Transform (DFT) decomposes time-domain signal amplitudes into constituent frequency sinusoids: $X_k = \sum_{n=0}^{N-1} x_n e^{-i 2\pi k n / N}$. It forms the backbone of digital audio processing and spectral analytics ⚡.
import cmath
def dft(signal):
N = len(signal)
return [
sum(x * cmath.exp(-2j * cmath.pi * k * n / N) for n, x in enumerate(signal))
for k in range(N)
]
signal = [1.0, 0.0, -1.0, 0.0] # 4-sample periodic wave
spectrum = dft(signal)
magnitudes = [round(abs(f), 1) for f in spectrum]
print(f"Magnitudes: {magnitudes} ⚡")
# 55. Discrete Fourier Transform & Frequency Decomposition The Discrete Fourier Transform (DFT) decomposes time-domain signal amplitudes into constituent frequency sinusoids: $X_k = \sum_{n=0}^{N-1} x_n e^{-i 2\pi k n / N}$. It forms the backbone of digital audio processing and spectral analytics ⚡. ```python import cmath def dft(signal): N = len(signal) return [ sum(x * cmath.exp(-2j * cmath.pi * k * n / N) for n, x in enumerate(signal)) for k in range(N) ] signal = [1.0, 0.0, -1.0, 0.0] # 4-sample periodic wave spectrum = dft(signal) magnitudes = [round(abs(f), 1) for f in spectrum] print(f"Magnitudes: {magnitudes} ⚡") ``` The Fast Fourier Transform (FFT, Cooley-Tukey algorithm) reduces standard DFT runtime from $O(N^2)$ to $O(N \log N)$ by recursively splitting even and odd sample indices 🏎️. --- ### Question What domain transformation does the Discrete Fourier Transform (DFT) execute on an input sequence? 🧠 - [ ] a. It converts time-domain amplitude samples into frequency-domain spectral coefficients ⚡ - [ ] b. It maps discrete integers into continuous floating-point RGB color channels - [ ] c. It parses natural language text into executable abstract syntax tree nodes - [ ] d. It compresses binary byte arrays by replacing repeated zero sequences --- ### Challenge Implement `dft(signal)` using `cmath.exp`. Compute frequency magnitudes (`abs()`) for `[1.0, 0.0, -1.0, 0.0]` and print them rounded to 1 decimal place. 🎯 <details> <summary>Solution</summary> ```python import cmath def dft(signal): N = len(signal) return [ sum(x * cmath.exp(-2j * cmath.pi * k * n / N) for n, x in enumerate(signal)) for k in range(N) ] spectrum = dft([1.0, 0.0, -1.0, 0.0]) print([round(abs(f), 1) for f in spectrum]) ``` </details>