1D DFT

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

Example:

Constraints:

Test Results