Decompose any discrete signal into its hidden frequencies — from a chord's individual notes to the radio waves encoding mobile data. The DFT is the mathematical prism at the heart of every digital signal processing pipeline.
Core Paradigm Shift
Every signal can be described in two complementary ways: as amplitude values evolving over time, or as a collection of frequency components each with its own strength and phase. The DFT is the mathematical bridge that converts between these two equivalent representations.
Imagine trying to identify a musical chord just by reading pressure numbers off an oscilloscope — you'd see a jagged, seemingly random wave. But the moment you pass that same audio through an equalizer, each frequency band lights up independently, instantly revealing the individual notes. Why does this transformation feel like magic, and how does it work mathematically?
The DFT is like a glass prism separating white light into a rainbow. A complex audio chord (the "white light") passes through the DFT (the "prism") and emerges as separate, identifiable pure sinusoidal components (the "colors"). Just as you can reconstruct white light by recombining all the colors, you can perfectly reconstruct the original signal by recombining all the DFT bins.
DFT maps N time samples → N complex frequency bins. Each bin $X[k]$ reports the amplitude and phase of the sinusoid at frequency $k \cdot \Delta f$ Hz. Tall bars indicate strong frequency components in the signal.
A signal exists simultaneously in both domains. Neither is more "real" — each is more useful for different tasks.
| Dimension | Time Domain | Frequency Domain |
|---|---|---|
| Horizontal axis | Sample index $n$ | Bin index $k$ (= $k \cdot f_s/N$ Hz) |
| Vertical axis | Amplitude $x[n]$ | Magnitude $|X[k]|$ and phase $\angle X[k]$ |
| Best for | Detecting events, onsets, transients | Identifying pitch, tone, spectral content |
| Notation | $x[n]$ — real discrete samples | $X[k]$ — complex DFT coefficients |
The magnitude spectrum $|X[k]|$ shows amplitude per frequency bin. A tall spike at bin $k$ means a strong sinusoidal component at frequency $f_k = k \cdot f_s / N$ Hz. Silent bins (near zero) mean no energy at that frequency.
Problem: Signal is a pure 3 Hz cosine, sampled at $f_s = 16$ Hz, $N = 16$ samples. Which DFT bin contains the energy?
If $f_s = 8000$ Hz and $N = 256$, what is the frequency resolution $\Delta f$? Which bin contains a 1000 Hz tone?
The frequency domain unlocks operations that are impossible or prohibitively expensive in the time domain.
Confusing bin index with Hz. Bin $k$ does NOT equal $k$ Hz unless $\Delta f = 1$ Hz. Always compute $f_k = k \cdot f_s / N$ to find the physical frequency. With $f_s = 44100$ Hz and $N = 1024$, bin $k = 10$ represents $10 \times 44100/1024 \approx 430$ Hz — not 10 Hz.
Below is an interactive decomposer. Before pressing play, predict: a square wave is built from sine waves at what frequencies? (Hint: it starts at frequency $f_0$ and includes harmonics at $3f_0$, $5f_0$, $7f_0$, …)
After predicting, try the "Square Wave" button and verify your prediction against the magnitude spectrum.
The DFT is a domain switch — the same signal viewed through a prism that separates it into its constituent frequencies, each bin reporting exactly how much of one sinusoid is present.
The animated frequency bars bouncing to music in any streaming app are computed by running a DFT repeatedly over short overlapping windows of audio — typically 1024 or 2048 samples. The height of each bar equals $|X[k]|$ for that frequency bin: low-$k$ bins on the left represent deep bass, high-$k$ bins represent treble. This runs on a smartphone at 60 frames per second, processing millions of DFT operations per second in real time.
Q1 A signal has $f_s = 100$ Hz and $N = 100$ samples. What is the frequency resolution $\Delta f$, and which bin number contains a 25 Hz tone?
Q2 Why does a unit impulse $x[n]=\delta[n]$ have a flat magnitude spectrum where all $|X[k]|$ are equal?
Q3 Name two tasks that become computationally feasible in the frequency domain that are impractical in the time domain.
Theoretical Foundations
The DFT maps $N$ time-domain samples to $N$ complex frequency coefficients. At its core, it multiplies the signal by a rotating complex sinusoid at each target frequency and sums the result — a clever inner-product test for "how much of this frequency is present?"
Have you ever wondered why complex numbers appear in a formula about real audio signals? The trick is that a single complex exponential $e^{j\theta}$ simultaneously encodes both a cosine and a sine in one compact object — giving us two orthogonal "frequency detectors" for the price of one symbol.
Each DFT output $X[k]$ is like asking the signal: "Are you friends with a 440 Hz tone?" You play a 440 Hz test tone, multiply it sample-by-sample with the signal, then sum everything up. If the signal contains 440 Hz, the products add up constructively (large $|X[k]|$). If it doesn't, they cancel to zero. That "multiply-and-sum" is exactly what $\sum x[n]\cdot e^{-j2\pi kn/N}$ does for each bin $k$.
Given $N$ samples $x[0], \ldots, x[N-1]$, the DFT produces $N$ complex coefficients $X[0], \ldots, X[N-1]$:
$$X[k] = \sum_{n=0}^{N-1} x[n]\cdot e^{-j\frac{2\pi}{N}kn}, \quad k = 0, 1, \ldots, N-1$$
Problem: Compute $X[0]$ and $X[1]$ for the signal $x = [1, 0, -1, 0]$ with $N = 4$.
Using the same signal $x = [1,0,-1,0]$ with $N=4$, compute $X[2]$ by hand. What do you expect physically?
The complex exponential $e^{j\theta}$ is the key to why the DFT uses complex numbers. Euler's formula unpacks it:
$$e^{j\theta} = \cos\theta + j\sin\theta$$
In the DFT, the probe is $e^{-j2\pi kn/N}$, which expands to:
$\cos\!\left(\tfrac{2\pi kn}{N}\right) - j\sin\!\left(\tfrac{2\pi kn}{N}\right)$
The real part (cosine) detects even-symmetric frequency content. The imaginary part (−sine) detects odd-symmetric content. Together they capture both amplitude and phase of any sinusoidal component.
Problem: Expand the probe $e^{-j\pi n/2}$ at each $n$ using Euler's formula.
What is $|e^{j\theta}|$ for any $\theta$? Why does this matter for the DFT probe?
Twiddle factor shorthand: The probe $W_N^{kn} = e^{-j2\pi kn/N}$ is often called the twiddle factor in DSP literature. You will see this notation in FFT algorithm descriptions (Week 5). For now, remember $W_N = e^{-j2\pi/N}$ is just Euler's formula with a fixed angular step.
The widget below lets you choose $N$ and watch $X[1]$ computed step by step. Before using it, predict: for $x = [1,0,-1,0]$ with $N=4$, what is $|X[1]|$? (You just computed it by hand above.)
Then try $N = 8$ with the same pattern and predict how the spectrum changes.
The DFT is a set of N inner products — each bin $X[k]$ asks "how correlated is this signal with a pure sinusoid at frequency $k \cdot f_s/N$ Hz?" and the complex answer encodes both the amplitude and the phase of that correlation.
A radar system transmits a known chirp signal. When the echo returns, it runs a DFT-based matched filter — multiplying the received signal's spectrum $X[k]$ by the conjugate of the transmitted chirp's spectrum $H^*[k]$ and taking the IDFT. The result is a sharp peak at the time delay proportional to distance. This is exactly the "multiply probe and sum" operation of the DFT applied across all frequency bins simultaneously — turning a noisy return signal into a precise range estimate.
Q1 Expand $e^{-j\pi/2}$ using Euler's formula. Give the real and imaginary parts.
Q2 For the signal $x = [2, 2, 2, 2]$ and $N = 4$, what is $X[0]$? What does this value represent physically?
Q3 What is $|e^{-j\theta}|$ for any real angle $\theta$? Why is this property important for the DFT?
Geometric Intuition
The DFT's inner product can be visualised geometrically: wrap the signal around a circle at a chosen frequency and look at where the centre of mass lands. A strong frequency component makes all wrapped points cluster on one side — the centre of mass moves far from the origin, producing a large $|X[k]|$.
Why does multiplying a signal by a complex exponential and summing detect frequency? The answer becomes obvious once you see it geometrically: imagine winding the signal like a spring around a circle. If the signal oscillates at exactly the winding frequency, all the spring's mass lands on the same side of the circle — its centre of mass is far from the origin. If the frequencies don't match, the mass cancels out and the centre of mass collapses to zero.
Imagine you spin a bucket of water at a certain rate. If the water is sloshing at the same frequency as your spin, the water builds up on one wall — you feel a strong net force. If the frequencies don't match, the sloshes cancel around the bucket and you feel no net force. The DFT "spin rate" is $k/N$ cycles per sample; the "felt force" is $|X[k]|$.
The DFT phasor-wrap: wind x[n] onto a circle at frequency k/N, plot each scaled point, then take the vector sum. A strong frequency component causes the points to cluster, giving a large magnitude $|X[k]|$.
Each DFT output is the cross-correlation of the signal with a pure sinusoid. For real $x[n]$ the signal's energy is entirely in bins $k = 0$ to $N/2$:
The DFT inner product $X[k] = \langle x, \phi_k \rangle$ measures how well the signal $x[n]$ overlaps with the probe $\phi_k[n] = e^{j2\pi kn/N}$. Large $|X[k]|$ = high correlation = signal contains frequency $k \cdot f_s / N$.
Goal: Verify that $|X[1]|$ is large by tracing the phasor-wrap mentally.
For the same signal, explain geometrically why $|X[2]| = 0$. Where do the non-zero contributions land on the unit circle when using the k=2 probe?
When the input $x[n]$ is real-valued (as it almost always is for physical signals), the DFT has a mirror property:
$$X[N-k] = X^*[k] \quad \text{(for real } x[n]\text{)}$$
Consequence: Bins $k = 0$ to $k = N/2$ contain all unique frequency information. Bins $k = N/2 + 1$ to $k = N-1$ are redundant (complex conjugates of bins $k = N/2 - 1$ down to $k = 1$).
One-sided spectrum: When plotting real signals, only show bins $k = 0$ to $k = N/2$, and double the magnitudes of bins $1$ to $N/2 - 1$ to conserve total energy.
Signal: $x = [1, 0, -1, 0]$. We computed $X = [0, 2, 0, 2]$.
For a real signal with $N = 256$ samples, how many unique (non-redundant) DFT bins are there?
The phasor wrap is why DFT needs complex numbers. A real-only probe (cosine) can only tell you the amplitude, not the phase. The complex probe simultaneously rotates through all phase angles, detecting both the magnitude AND the phase offset of each frequency component in a single pass. Using only a cosine probe would require two separate passes.
The widget below animates the phasor wrap for different signals and probe frequencies. Before adjusting the slider, predict: if you set the probe frequency equal to the signal frequency, what shape will the wrapped points form?
Prediction: all points cluster on one side of the circle (not spread evenly). Verify with the widget.
The DFT is a geometric correlation test: a large $|X[k]|$ means the signal's phasor-wrapped points cluster on one side of the circle, revealing that frequency $k \cdot f_s/N$ is present with that strength and phase.
In Magnetic Resonance Imaging, hydrogen nuclei in the body precess (spin) at frequencies proportional to the local magnetic field strength. The MRI scanner records the combined radio-frequency signal from millions of spinning protons. Applying a Fourier transform to the received signal — exactly the phasor-wrap correlation we studied — separates the signal by frequency, and since frequency encodes spatial position (via a field gradient), the result is a spatial image of tissue density. The DFT turns a time-domain radio signal into an anatomical cross-section image.
Q1 In the phasor-wrap model, what does it mean when all the wrapped points cluster tightly on one side of the circle?
Q2 State the conjugate symmetry property for a real signal $x[n]$ and explain its practical consequence for plotting spectra.
Q3 Why does the DFT use a complex probe $e^{-j2\pi kn/N}$ rather than just a cosine $\cos(2\pi kn/N)$?
Synthesis & Energy
The Inverse DFT reconstructs the original signal from its frequency coefficients — proving the DFT is perfectly reversible. Parseval's Theorem then guarantees that the total energy computed in the time domain exactly equals the total energy computed in the frequency domain, confirming no information is created or destroyed.
After the DFT converts your signal into frequency coefficients, how do you get back to the original waveform? And when you modify those coefficients — say, zeroing out noisy frequency bins — are you guaranteed to get a valid signal back? The IDFT answers the first question, and Parseval's Theorem provides the energy accounting that makes frequency-domain editing trustworthy.
The DFT is like disassembling a LEGO model into sorted bins (blue bricks here, red bricks there). The IDFT is the instruction sheet that reassembles exactly the same model from those bins. Parseval's Theorem says: the total weight of all the bricks in the bins equals the total weight of the assembled model — nothing was lost in sorting or reassembly.
The IDFT reconstructs $x[n]$ from $X[k]$ by summing all $N$ complex sinusoidal components:
$$x[n] = \frac{1}{N}\sum_{k=0}^{N-1} X[k]\cdot e^{+j\frac{2\pi}{N}kn}, \quad n = 0, 1, \ldots, N-1$$
Problem: Given $X = [0, 2, 0, 2]$ with $N=4$, compute $x[0]$ and $x[1]$ using the IDFT.
Compute $x[2]$ for $X=[0,2,0,2]$ with $N=4$ using the IDFT formula. What do you expect?
The total signal energy computed in the time domain equals the total energy computed in the frequency domain:
$$\sum_{n=0}^{N-1}|x[n]|^2 = \frac{1}{N}\sum_{k=0}^{N-1}|X[k]|^2$$
The left side is the total energy of all $N$ time samples. The right side is the total energy of all $N$ frequency bins (divided by $N$ for normalization). They must always be equal.
Why it matters: When you zero out frequency bins (noise removal), you can directly compute how much energy you removed — before inverting. This lets you predict the signal-to-noise ratio improvement before performing the IDFT.
Signal: $x=[1,0,-1,0]$, DFT $X=[0,2,0,2]$, $N=4$.
For signal $x = [2, 0, 0, 0]$ with $N=4$: (a) compute the time-domain energy $E_t$; (b) verify that $E_f = E_t$ by computing all $|X[k]|$ first.
Noise removal arithmetic: If signal energy is $E_s = 10$ and you zero out 30% of the bins, the energy removed is approximately $0.3 \times E_f = 0.3 \times E_t$. The residual energy after denoising is approximately $0.7 \times E_t$ — computable before you even run the IDFT.
The widget below lets you modify frequency bins and see the IDFT reconstruction. Before experimenting, predict: if you zero out all bins except bin $k=3$, what will the reconstructed signal look like?
A single non-zero bin = a pure sinusoid at frequency $3 \cdot f_s/N$ Hz. Predict the frequency and amplitude before pressing.
The DFT and IDFT form a perfect inverse pair: modify frequency bins to engineer the signal, then reconstruct with the IDFT — and Parseval's Theorem guarantees exact energy accounting throughout.
Every digital audio equalizer — from studio mixing consoles to smartphone earphone apps — works by taking the DFT of an audio block, multiplying each bin by a gain factor (the EQ curve), and applying the IDFT. A noise gate zeros out bins below a threshold (similar to our denoising code above). Parseval's Theorem means the audio engineer can directly read energy removed from the frequency display and predict exactly how much quieter the noise floor will become — a direct link between the frequency-domain operation and the audible result.
Q1 Write the IDFT formula. How does it differ from the DFT formula? (Name both differences.)
Q2 For signal $x = [3, 0, 0, 0]$ with $N=4$: compute the time-domain energy $E_t$ and verify Parseval's Theorem (all bins of this signal have $|X[k]| = 3$).
Q3 A denoising algorithm zeros out 80% of the DFT bins of a signal with total energy $E = 100$. Approximately how much energy remains after the IDFT reconstruction?
Practical Limitations
In practice, you rarely have exactly an integer number of signal cycles in your analysis window. When the signal frequency falls between DFT bins, energy "leaks" from the true frequency into neighboring bins — producing a smeared spectrum. Window functions reduce this leakage by smoothly tapering the signal at the edges of the analysis window.
You have a 3.7 Hz tone and you record exactly 1 second at 16 Hz — giving 16 samples. But the DFT has bins only at integer Hz: 3 Hz, 4 Hz. The 3.7 Hz tone doesn't land on any bin. So where does its energy go? It smears across all bins, polluting the spectrum with spurious "ghost" peaks. This is spectral leakage, and it is the single most common artifact beginners encounter when working with real signals.
Abruptly cropping an audio recording is like slamming a door shut mid-sentence. The sharp cut introduces a click that spreads energy across all frequencies — just like the rectangular window introduces spectral leakage. A window function is like politely fading the recording in and out: the smooth edges eliminate the click and keep the spectrum clean.
Before/after windowing: applying a Hann window eliminates spectral leakage sidebands and concentrates energy near the true frequency bin. The table shows the main-lobe/side-lobe trade-off for common windows.
The DFT implicitly assumes the $N$-sample window is one period of an infinitely repeating signal. When the signal frequency doesn't align with a bin, the "stitched" signal has a discontinuity at the block boundary:
Multiplying the signal by the implicit rectangular window $w[n] = 1$ for all $n$ is equivalent to abruptly cutting the signal at both ends. In the frequency domain, the DFT of a rectangular window has high sidelobes (the "Gibbs phenomenon"), and these sidelobes add energy to every bin, creating spectral leakage.
Condition for zero leakage: The signal frequency must fall exactly on a DFT bin: $f = k \cdot f_s / N$ for some integer $k$. In practice this rarely holds for real-world signals.
Problem: You record $N = 16$ samples at $f_s = 16$ Hz. Which signal frequencies produce zero leakage?
You want to analyze a 440 Hz tone with zero leakage using $f_s = 8000$ Hz. What value of $N$ would guarantee this? (Hint: $N$ must be a multiple of $f_s / f$.) Is this practical?
Multiply $x[n]$ by a window $w[n]$ that tapers smoothly to zero at both ends before computing the DFT:
Rectangular (default, implicit): $w[n] = 1$ — no tapering, maximum leakage
Hann window: $w[n] = 0.5\left(1 - \cos\!\left(\tfrac{2\pi n}{N-1}\right)\right)$
Hamming window: $w[n] = 0.54 - 0.46\cos\!\left(\tfrac{2\pi n}{N-1}\right)$
Blackman window: more complex; best side-lobe suppression (−57 dB)
Trade-off: Wider windows suppress leakage better but widen the main lobe (reducing frequency resolution). Choose the window based on whether resolution or dynamic range matters more for your task.
Problem: Compute the Hann window $w[n]$ for $N=8$ at $n=0,1,2,3,4$.
Why is $w[0] = 0$ for a Hann window? What does this mean for the first sample of the windowed signal?
Forgetting to compensate for window energy loss. Windowing reduces signal amplitude — the Hann window reduces total power by roughly 50%. After windowing, multiply the DFT magnitudes by $2/\text{sum}(w)$ to restore correct amplitude scale. NumPy's np.hanning(N) gives the window; divide by np.sum(w) for the compensation factor.
The widget below shows the same off-bin frequency with and without a Hann window. Before toggling, predict: will the windowed spectrum have a narrower peak or a wider peak than the unwindowed spectrum?
Prediction: wider peak (main lobe is broader) but cleaner — the side lobes disappear. Verify this trade-off with the widget.
Spectral leakage is caused by the implicit rectangular window whenever the signal frequency doesn't land on a DFT bin; applying a smooth window (Hann, Hamming, Blackman) suppresses this leakage at the cost of slightly reduced frequency resolution.
Every spectrum analyzer — from a $100 USB dongle to a $100,000 lab instrument — applies windowing before computing each DFT block. In radio frequency monitoring, a weak signal at 100.1 MHz might be completely buried under the sidelobes of a strong adjacent station at 100.0 MHz if a rectangular window is used. A Blackman window with −57 dB sidelobe suppression keeps the weak signal visible. The choice of window directly determines whether a frequency-hopping transmitter can be detected — a critical factor in spectrum management, electronic warfare, and interference diagnosis.
Q1 You analyze a 440 Hz signal with $f_s = 8000$ Hz and $N = 512$. Does this signal fall exactly on a DFT bin, or does it cause spectral leakage? Show your calculation.
Q2 Write the Hann window formula and explain what value $w[0]$ takes and why this matters.
Q3 The Hann window is said to have a "wider main lobe" than the rectangular window. Is this a bug or a feature? Explain the trade-off.
Interactive Dashboard
Build a composite signal from two frequency components, apply a window function, compute the DFT in real time, and observe the magnitude spectrum, phase spectrum, and Parseval energy balance — all in one dashboard.
Every parameter you adjust — frequencies, amplitudes, window size, and window type — has a direct visible consequence in the magnitude spectrum, phase spectrum, and Parseval energy balance, making all five DFT concepts from this week tangible and interactive.
Week 4 Summary
The DFT converts N time-domain samples into N complex frequency coefficients — each encoding the amplitude and phase of one frequency in the signal.
$X[k] = \sum x[n]e^{-j2\pi kn/N}$ (DFT) and $x[n] = \frac{1}{N}\sum X[k]e^{+j2\pi kn/N}$ (IDFT). The only differences are the sign of the exponent and the $1/N$ factor. Zero information is lost.
Bin $k$ represents frequency $f_k = k \cdot f_s / N$ Hz. Always use this formula — never assume bin index equals Hz. Frequency resolution $\Delta f = f_s/N$ improves (shrinks) as $N$ increases.
$\sum|x[n]|^2 = \frac{1}{N}\sum|X[k]|^2$. Time-domain energy equals frequency-domain energy. Modifying bins changes the reconstructed signal's energy by exactly the amount you removed — no surprises.
Whenever the signal frequency falls between DFT bins, spectral leakage occurs. Multiply by a Hann or Hamming window before the DFT to suppress sidelobes — at the cost of slightly wider main-lobe width (reduced frequency resolution).
Coming up — Week 5
The naive DFT you implemented this week runs in $O(N^2)$ — unusable for $N = 16{,}384$. The FFT reduces this to $O(N\log N)$ by exploiting the periodicity and symmetry of the twiddle factors $W_N^{kn}$. You will implement the radix-2 Cooley-Tukey butterfly, see why $N = 2^p$ is preferred, and use numpy.fft.fft() as a production-grade FFT.
Further Reading
Curated resources to strengthen your DFT intuition — from interactive visualisations to the textbook chapter that every DSP engineer has bookmarked.
The definitive visual explanation of the phasor-wrap model. Watch this video to build rock-solid geometric intuition for why the DFT detects frequencies.
→ YouTube (20 min) TextbookFree online textbook with Python examples. Chapter 7 walks through the DFT formula with hands-on code — perfect companion to this week's exercises.
→ greenteapress.com (free PDF) Deep DiveSmith's freely available reference explains the DFT's derivation, normalization conventions, and the exact relationship between the DFT and the continuous Fourier transform.
→ dspguide.com (free) ToolNumPy's FFT module documentation with complete function references, normalization conventions, and frequency-bin ordering explained — essential reference for all coding exercises.
→ numpy.org/docPractice
12 exercises across theory and code — two per topic plus two synthesis tasks. Work through them in order; each builds on the concepts from the matching section.
You record a signal at $f_s = 44100$ Hz using $N = 2048$ samples. (a) Compute the frequency resolution $\Delta f$. (b) Which DFT bin contains a 1 kHz tone? (c) How many unique (non-redundant) bins does this real-signal DFT produce?
Generate a signal $x[n] = \cos(2\pi \cdot 3 \cdot n/f_s) + 0.5\cos(2\pi \cdot 7 \cdot n/f_s)$ with $f_s = 16$ Hz and $N = 32$ samples. Compute and plot the one-sided magnitude spectrum using np.fft.fft and np.fft.fftfreq. Label the two frequency peaks.
freqs = np.fft.fftfreq(N, 1/fs) for the frequency axis. Plot only the first N//2 bins (one-sided). Use np.abs(X) for magnitudes.Compute the full DFT $X[k]$ for $k = 0, 1, 2, 3$ of the signal $x = [0, 1, 0, -1]$ with $N = 4$ using the definition $X[k] = \sum_{n=0}^{3} x[n]\, e^{-j\pi kn/2}$. Express each $X[k]$ in the form $a + jb$. What physical signal does this $x[n]$ represent?
Write a Python function dft(x) that implements the DFT definition using two nested for loops (no NumPy FFT). Test it on $x = [1, 0, -1, 0]$ and verify against np.fft.fft(x) using np.allclose. Then measure the runtime for $N = 256$ using time.perf_counter and compare to np.fft.fft.
X = np.zeros(N, dtype=complex). The inner loop multiplies x[n] * np.exp(-1j * 2 * np.pi * k * n / N). Expect the naive DFT to be ~100–1000× slower than NumPy's FFT for N=256.A real signal has $N = 8$ samples and DFT $X = [8, 3-2j, 0, 1+j, 0, 1-j, 0, 3+2j]$. (a) Verify the conjugate symmetry property $X[N-k] = X^*[k]$ for $k = 1$ and $k = 3$. (b) How many unique bins are there? (c) What is $|X[1]|$ and $|X[7]|$? Are they equal?
Generate a random real signal $x = \text{np.random.randn}(32)$. Compute $X = \text{np.fft.fft}(x)$. Plot $|X[k]|$ for all $k = 0$ to $31$ and add a vertical dashed line at $k = N/2$. Numerically verify that $|X[k]| = |X[N-k]|$ for all $k$. Print the maximum difference.
np.max(np.abs(np.abs(X[1:N//2]) - np.abs(X[N//2+1:][::-1]))) to compare the two halves. This should be near machine epsilon (~1e-14).Given $X = [4, 0, 0, 0]$ (a scaled impulse in the frequency domain) with $N = 4$, compute $x[0], x[1], x[2], x[3]$ using the IDFT formula. Then verify Parseval's Theorem: compute $\sum|x[n]|^2$ and $\frac{1}{N}\sum|X[k]|^2$ and confirm they are equal.
Generate $x[n] = \sin(2\pi \cdot 5 \cdot n/64) + \text{noise}$ with $N=64$, $f_s=64$, and Gaussian noise of std = 0.4. Apply DFT, zero out all bins where $|X[k]| < 5$, apply IDFT to reconstruct. Report: (a) number of bins zeroed, (b) fraction of energy removed (using Parseval), (c) plot original vs. reconstructed signal.
X_clean = X.copy(); X_clean[np.abs(X_clean) < 5] = 0 for zeroing. Energy before: sum(|X|²)/N. Energy after: sum(|X_clean|²)/N. The difference is the noise energy removed.You want to analyze a 250 Hz tone using $f_s = 8000$ Hz and $N = 512$. (a) Does this frequency fall exactly on a DFT bin? Show the calculation. (b) Write the Hann window formula and compute $w[0]$, $w[128]$, and $w[511]$ for $N = 512$. (c) What is the worst-case sidelobe level (in dB) for the rectangular window and the Hann window?
Generate $x[n] = \cos(2\pi \cdot 5.3 \cdot n/64)$ with $N=64$, $f_s=64$. Compute and plot (on the same axes) the dB magnitude spectrum using (a) rectangular window, (b) Hann window, (c) Blackman window (np.blackman(N)). For each, report the peak bin and the magnitude at bin $k = 3$ (a bin far from the true frequency — pure leakage).
np.sum(w) before taking dB. Plot in dB: 20*np.log10(mag + 1e-10). The Blackman window should give the cleanest spectrum (most leakage suppression) but the broadest main lobe.Record (or synthesize) a 0.5-second chord of A4 (440 Hz) + C5 (523 Hz) + E5 (659 Hz) at $f_s = 22050$ Hz. (a) Apply a Hann window and compute the DFT. (b) Identify the three dominant frequency bins and convert them to Hz. (c) Verify that the detected frequencies match A4, C5, E5 within $\pm 5$ Hz. (d) What is the minimum $N$ needed to resolve 440 Hz and 523 Hz as two separate peaks (resolution must be $< 83$ Hz)?
Generate a noisy signal: $x = \sin(2\pi\cdot 3\cdot n/32) + \sin(2\pi\cdot 7\cdot n/32) + 0.3\cdot\text{randn}(N)$ with $N=32$, $f_s=32$. (a) Compute the DFT. (b) Build $X_{\text{clean}}$ by keeping only the 4 highest-magnitude bins (set all others to 0). (c) Reconstruct via IDFT and plot original vs. reconstructed. (d) Compute the Signal-to-Noise Ratio improvement: $\text{SNR} = 10\log_{10}(E_{\text{signal}}/E_{\text{noise removed}})$. (e) Verify Parseval's Theorem before and after denoising.
idx = np.argsort(np.abs(X))[-4:] to find top 4 bins. For (d): E_noise_removed = (sum(|X|²) − sum(|X_clean|²))/N. SNR is in dB. For (e): check that time-energy and freq-energy/N are equal for both the noisy and clean signals.