Skip to content
Computational Lab.

Fourier Transform (DFT)

Mix frequencies in, read them out exactly.

Intermediate / approximation / frequency-domain

Compose a signal from harmonics plus noise, then compute its Discrete Fourier Transform by the textbook definition - no FFT shortcuts. The spectrum peaks at exactly the frequencies that were mixed in, which is the identity that makes everything from audio codecs to the convolution theorem work.

Tagged: DFT, spectrum, magnitude, superposition

Live simulation

The spectrum peaks at exactly the frequencies mixed into the signal.

Speed

The spectrum peaks at exactly the frequencies mixed into the signal.

Mathematics

The Discrete Fourier Transform rewrites a length-N signal as N complex exponentials: X(k) measures how much of frequency k lives in the signal. Computed here straight from the definition - N-squared operations, no FFT cleverness - so the spectrum is visibly the arithmetic it claims to be.

X(k) = sum_n x(n) e^{-2 pi i k n / N}

magnitude: |X(k)| = sqrt(Re^2 + Im^2)

linearity: DFT(x + y) = DFT(x) + DFT(y)

Linearity is why the spectrum reads honestly: each harmonic mixed into the signal produces exactly one peak at its own frequency, and noise spreads thinly across every bin. The two-peak structure in the default signal is the whole demonstration - what you mixed in is what you read out.

How it works

The signal buffer composes three harmonics (two slider-controlled) plus seeded noise, then the DFT runs per render: for each of the 64 output bins, sum the signal against a complex exponential. It is the O(n^2) textbook definition, which is precisely the point - the FFT is an optimization of exactly this sum.

The bottom panel plots |X(k)| for every bin; the peak bins are highlighted against the noise floor.

Implementation

src/engine/experiments/fourier-transform.ts · 141 lines · the module running above

TypeScript · fixed-timestep engine

1import { BaseExperiment } from "../core/base-experiment";
2import type { ParameterDef, ThemeColors } from "../core/types";
3
4const SAMPLES = 128;
5
6/**
7 * The Discrete Fourier Transform, computed by definition (O(n^2), no FFT
8 * trickery) so the spectrum is transparently real: a composed signal goes
9 * in, its exact frequency components come out.
10 */
11export class FourierTransformExperiment extends BaseExperiment {
12 readonly id = "fourier-transform";
13
14 private harmonics = [
15 { freq: 5, amp: 1, phase: 0 },
16 { freq: 12, amp: 0.6, phase: 1.2 },
17 { freq: 30, amp: 0.35, phase: -0.7 },
18 ];
19 private spectrum: { re: number; im: number }[] = [];
20 private signal = new Float64Array(SAMPLES);
21
22 protected params(): ParameterDef[] {
23 return [
24 { key: "h1", label: "Harmonic 1 frequency", min: 1, max: 40, step: 1, defaultValue: 5 },
25 { key: "h2", label: "Harmonic 2 frequency", min: 1, max: 60, step: 1, defaultValue: 12 },
26 { key: "h2amp", label: "Harmonic 2 amplitude", min: 0, max: 1, step: 0.05, defaultValue: 0.6 },
27 { key: "noise", label: "Noise", min: 0, max: 0.5, step: 0.02, defaultValue: 0.1 },
28 ];
29 }
30
31 protected onReset(): void {
32 this.compose();
33 }
34
35 private compose(): void {
36 this.harmonics[1].freq = this.num("h2");
37 this.harmonics[1].amp = this.num("h2amp");
38 this.harmonics[0].freq = this.num("h1");
39 const noise = this.num("noise");
40 for (let i = 0; i < SAMPLES; i++) {
41 const t = i / SAMPLES;
42 let value = 0;
43 for (const h of this.harmonics) {
44 if (h.amp <= 0) continue;
45 value += h.amp * Math.sin(2 * Math.PI * h.freq * t + h.phase);
46 }
47 value += (this.rng() - 0.5) * 2 * noise;
48 this.signal[i] = value;
49 }
50 this.transform();
51 }
52
53 protected onParameterChange(): void {
54 this.compose();
55 }
56
57 protected onUpdate(): void {}
58
59 /** DFT by definition: X_k = sum_n x_n e^{-2 pi i k n / N}. */
60 private transform(): void {
61 this.spectrum = [];
62 for (let k = 0; k < SAMPLES / 2; k++) {
63 let re = 0;
64 let im = 0;
65 for (let n = 0; n < SAMPLES; n++) {
66 const angle = (-2 * Math.PI * k * n) / SAMPLES;
67 re += this.signal[n] * Math.cos(angle);
68 im += this.signal[n] * Math.sin(angle);
69 }
70 this.spectrum.push({ re: re / SAMPLES, im: im / SAMPLES });
71 }
72 }
73
74 render(ctx: CanvasRenderingContext2D, theme: ThemeColors): void {
75 ctx.fillStyle = theme.bg;
76 ctx.fillRect(0, 0, this.width, this.height);
77 const half = this.height / 2 - 12;
78 // Signal (top)
79 ctx.strokeStyle = theme.line;
80 ctx.beginPath();
81 ctx.moveTo(0, half);
82 ctx.lineTo(this.width, half);
83 ctx.stroke();
84 ctx.strokeStyle = theme.fgSecondary;
85 ctx.lineWidth = 1.4;
86 ctx.beginPath();
87 for (let i = 0; i < SAMPLES; i++) {
88 const x = (i / (SAMPLES - 1)) * this.width;
89 const y = half - this.signal[i] * half * 0.42;
90 if (i === 0) ctx.moveTo(x, y);
91 else ctx.lineTo(x, y);
92 }
93 ctx.stroke();
94 // Spectrum (bottom): magnitude per bin
95 const baseY = this.height - 24;
96 let maxMag = 1e-6;
97 for (const bin of this.spectrum) {
98 maxMag = Math.max(maxMag, Math.hypot(bin.re, bin.im) * 2);
99 }
100 const barW = this.width / this.spectrum.length;
101 for (let k = 0; k < this.spectrum.length; k++) {
102 const mag = Math.hypot(this.spectrum[k].re, this.spectrum[k].im) * 2;
103 const h = (mag / maxMag) * (half - 30);
104 ctx.fillStyle = k === 0 ? theme.line : mag > maxMag * 0.12 ? theme.accent : theme.fgTertiary;
105 ctx.fillRect(k * barW + 0.5, baseY - h, Math.max(1, barW - 1.5), h);
106 }
107 ctx.strokeStyle = theme.line;
108 ctx.beginPath();
109 ctx.moveTo(0, baseY);
110 ctx.lineTo(this.width, baseY);
111 ctx.stroke();
112 ctx.font = "11px ui-monospace, monospace";
113 ctx.fillStyle = theme.fgTertiary;
114 ctx.fillText("SIGNAL (TIME)", 10, 14);
115 ctx.fillStyle = theme.accent;
116 ctx.fillText("SPECTRUM |X(k)| (FREQUENCY)", 10, half + 16);
117 ctx.lineWidth = 1;
118 }
119
120 getMetrics() {
121 // Peak detection: the two largest bins above DC.
122 const mags = this.spectrum.map((bin, k) => ({ k, mag: Math.hypot(bin.re, bin.im) }));
123 const sorted = [...mags].sort((a, b) => b.mag - a.mag).slice(0, 2);
124 return {
125 peak1: `k=${sorted[0]?.k ?? 0}`,
126 peak2: `k=${sorted[1]?.k ?? 0}`,
127 samples: SAMPLES,
128 noise: this.num("noise").toFixed(2),
129 };
130 }
131
132 describe(): string {
133 const m = this.getMetrics();
134 return `A composed signal decomposed by its DFT: the spectrum peaks at bins ${m.peak1} and ${m.peak2}, the exact frequencies that were mixed in.`;
135 }
136
137 entities(): number {
138 return SAMPLES;
139 }
140}
141

Performance

Time per tick
O(N^2) per render - the definition, unoptimized on purpose
Space
One signal buffer plus the spectrum
Notes
The FFT achieves the same result in O(N log N) by exploiting the symmetry this page makes visible.

Live numbers (FPS, frame time, steps per second, microseconds per step, entity count) are in the performance overlay on the simulation above: the pulse icon in its top-right corner.