Overview
The Discrete Fourier Transform maps samples from the time or spatial domain into frequency coefficients, revealing periodic components at discrete frequencies.
FoundationSource checked
Discrete Fourier Transform
Represents a finite sequence as weighted sums of discrete complex sinusoids.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Signal Processing
- Difficulty
- Intermediate
- Family
- Frequency Analysis
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 19
- Code example
- Not ready
- Visualization
- Ready
- Aliases
- DFT
Core Concepts
frequency bincomplex sinusoidsampled signalinverse transform
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n^2)
Average
O(n^2)
Worst
O(n^2)
Space
O(n)
When to Use
- Use it to analyze frequency content in finite sampled data.
- Use it when the exact transform definition matters more than algorithmic speed.
- Use it as the mathematical target computed by FFT algorithms.
When Not to Use
- Avoid direct DFT computation for large inputs when an FFT is available.
- Avoid interpreting bins without considering sampling rate and windowing.
- Avoid it when nonstationary signals need localized time-frequency analysis.
What It Does
- Analyzes frequency content
- Represents samples as sinusoidal components
Use Cases
- Frequency analysis
- Signal filtering
- Spectral visualization
Inputs
- Finite sequence of samples
Outputs
- Frequency-domain coefficients
Key Formulas (1)
DFT
X[k] = ∑(x[n] · exp(−2·π·i·k·n/N)) for n = 0…N−1
X[k] = sum(x[n] * exp(-2*pi*i*k*n/N)) for n = 0..N-1Projects samples onto each discrete frequency bin.
Pseudocode
- 1.For each output frequency:
- 2.Compare the input with that frequency's sinusoid
- 3.Sum the weighted sample contributions
- 4.Store the complex coefficient
- 5.Repeat for every frequency
Canonical Example
- Input
- samples = [1, 2, 3, 2, 1]
- Output
- transformed or filtered samples
- Explanation
- Discrete Fourier Transform: The algorithm reads local or frequency structure from the sample sequence.
Implementation Notes
- Document the sign convention and normalization factor.
- Map bin indices to frequencies using the sampling rate.
- Use complex arithmetic carefully and test inverse-transform recovery.
Common Pitfalls
- Forgetting normalization and inverse-transform conventions.
- Confusing bin index with physical frequency.
- Ignoring spectral leakage from finite windows.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow a waveform decomposing into frequency bars.
Step 1 of 5: For each output frequency:
time-to-frequencyNotes
The DFT is the transform definition; the FFT is a faster way to compute many DFTs.
Sources (1)
What each reference supports for this entry.
Discrete-Time Signal Processing
BookSignal-processing reference covering the discrete Fourier transform and spectral analysis.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Used bySpectral Subtraction
Signal Processing · Core
Spectral subtraction estimates and removes noise in the frequency domain.
Compare with thisUsed byCepstrum Analysis
Signal Processing · Extended
Cepstral analysis commonly uses Fourier transforms of log spectra.
Compare with thisOften paired withWindowing
Signal Processing · Core
Windowing controls spectral leakage before Fourier analysis.
Compare with thisOften paired withAutocorrelation
Signal Processing · Extended
Autocorrelation can be analyzed efficiently through frequency-domain methods.
Compare with thisRelationships
View full relationship pageGeneralizesFast Fourier Transform
FFT is an efficient algorithm for computing the DFT.
Prerequisite ofShort-Time Fourier Transform
STFT applies Fourier transforms to successive windows.
Related Algorithms
Tags
Signal ProcessingFrequency DomainNumerical Methods