📘

1D DFT

MediumSignal Processing 📚 CV: Image Processing

Implement a 1D Discrete Fourier Transform (DFT) to decompose a signal into its frequency components. This task involves computing the DFT of a given signal, which is a fundamental concept in signal processing and image analysis.

The DFT is a mathematical operation that transforms a discrete-time signal into a discrete-frequency representation, allowing us to analyze the signal in the frequency domain. The DFT is based on the idea of representing a signal as a sum of sinusoids with different frequencies, amplitudes, and phases. The DFT can be used to extract features from signals, such as the magnitude of each frequency component.

To compute the DFT, we can follow these steps:

Define the input signal $x[n]$ and its length $N$ .
Iterate over each frequency component $k$ .
For each $k$ , compute the sum of the products of the signal $x[n]$ and the complex exponential $e^{-2\pi i kn/N}$ over all $n$ .

X[k] = \sum_{n=0}^{N-1} x[n] \cdot e^{-2\pi i kn/N}

This technique is widely used in image and signal processing applications.

Example:

Input:

dft_magnitude([1, 0, 1, 0])

Output:

[2.0, 0.0, 2.0, 0.0]

Reasoning:

The input is $x = [1, 0, 1, 0]$ with $N = 4$ , and we compute $X[k] = \sum_{n=0}^{3} x[n] e^{-2\pi i kn/4}$ then take $|X[k]|$ for each $k = 0,1,2,3$ .
For $k = 0$ : $X = 1 + 0 + 1 + 0 = 2 \Rightarrow |X| = 2.0$ .
For $k = 1$ : $X[1] = 1 + 0 + 1\cdot e^{-2\pi i\cdot 2/4} + 0 = 1 + (-1) = 0 \Rightarrow |X[1]| = 0.0$ .
For $k = 2$ : $X[2] = 1 + 0 + 1\cdot e^{-2\pi i\cdot 4/4} + 0 = 1 + 1 = 2 \Rightarrow |X[2]| = 2.0$ ; for $k = 3$ the terms cancel similarly to $k=1$ , giving $|X[3]| = 0.0$ .
Collecting magnitudes gives the output: $[2.0, 0.0, 2.0, 0.0]$ .

Constraints:

Return magnitudes rounded to 4 decimal places

More from CV: Image Processing

Frequency Domain FilteringHard Separable Filter OptimizationHard Contrast Limited Adaptive Histogram EqualizationMedium Frequency Component EnergyEasy Low-Pass Filter (Frequency)Medium

Background Knowledge

The 1D Discrete Fourier Transform (DFT) takes a finite, discrete signal $x[n]$ of length $N$ (time or space domain) and expresses it as a sum of complex sinusoids at different discrete frequencies. Each output $X[k]$ is a complex coefficient that tells you “how much” of frequency $k$ (a particular sinusoid) is present in the signal. The formula

X[k] = \sum_{n=0}^{N-1} x[n] \, e^{-2\pi i kn/N}

is just a weighted sum of the input samples by complex exponentials, where $e^{-2$ \pi $i kn/N}$ encodes both cosine and sine components.

In many practical problems (including image and signal processing), we are often interested in the magnitude spectrum, i.e. $|X[k]|$ , which indicates the strength of each frequency, ignoring phase. For a complex number $X[k] = a + ib$ , the magnitude is $|X[k]| = \sqrt{a^2 + b^2}$ . Note that if the input signal is real-valued, the DFT output has a symmetry: high-frequency components mirror the low frequencies, but you don’t need that property to solve this problem directly.

Algorithm / General Approach

Since this is a basic implementation problem, you are expected to:

Implement the definition of the DFT directly (no FFT optimization).
For each frequency index $k$ , compute the sum over all time indices $n$ .
Use complex arithmetic to accumulate the real and imaginary parts.
After computing $X[k]$ , convert it to its magnitude and store that as the result.

This is effectively a double loop: outer loop over frequencies $k$ , inner loop over samples $n$ , plus a final magnitude computation.

Step-by-Step Strategy
Read input:

Get the signal length $N$ .
Read the sequence $x, x, \dots, x[N-1]$ (usually real numbers).

Initialize output container:

Create an array mag[0..N-1] (float/double) for magnitudes.

For each frequency index $k$ from 0 to $N-1$ :

Initialize:
real = 0.0
imag = 0.0
For each time index $n$ from 0 to $N-1$ :
Compute the angle:

\theta = \frac{2\pi k n}{N}

Compute cosine and sine:
cosθ = cos(θ)
sinθ = sin(θ)
Update using:

e^{-i\theta} = \cos\theta - i\sin\theta

So:

real += x[n] * cosθ
imag -= x[n] * sinθ (note the minus from the exponent)
After the inner loop, compute magnitude:
mag[k] = sqrt(realreal + imagimag)

Return / output:

Output the array mag as the final result.

Common Pitfalls

Sign in the exponent:
The DFT uses $e^{-2$ \pi $i kn/N}$ , not a plus sign; mixing this up will give a conjugated spectrum.
Using degrees vs radians:
sin and cos in most languages expect radians; ensure $\theta = 2 * pi * k * n / N$ is in radians.
Numeric type:
Use double (or equivalent) for better precision in angle, sin/cos, and sums.
Performance expectations:
The naive DFT is $O(N^2)$ . For coding problem constraints (often modest $N$ ), this is fine; just don’t try to over-optimize with FFT unless required.
Magnitude vs complex output:
The problem asks specifically for magnitude; don’t return real and imaginary parts separately unless specified.

Time & Space Complexity

Time Complexity:
Two nested loops: $k = 0 \dots N-1$ and $n = 0 \dots N-1$ .
Each iteration does $O(1)$ work (a few arithmetic ops and trig calls).
Overall: $O(N^2)$ .
Space Complexity:
Input array: $O(N)$ .
Output magnitudes: $O(N)$ .
A few scalar temporaries.
Overall additional space: $O(N)$ .

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.