Inverse DFT

Inverse Discrete Fourier Transform

The Inverse DFT (IDFT) reconstructs the original time-domain signal from its frequency-domain representation. It is defined as:

$x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] \cdot e^{2\pi j k n / N}, \quad n = 0, 1, \ldots, N-1$

Notice:

• The exponent is positive (versus negative for DFT)
• There is a $1/N$ normalization factor

DFT–IDFT Round Trip

The DFT and IDFT are exact inverses (up to floating-point precision):

$\text{IDFT}(\text{DFT}(x)) = x$

This round-trip property is essential for signal reconstruction after frequency-domain processing.

Example

Given $X = [4, 0, 0, 0]$:

$x[n] = \frac{1}{4} \sum_{k=0}^{3} X[k] \cdot e^{2\pi j k n/4} = \frac{1}{4} \cdot 4 = 1 \quad \text{for all } n$

Result: $[1, 1, 1, 1]$ — a DC signal.

Your Task

Implement:

• idft(X) — returns a list of $N$ real floats (take .real of each result)

import math

def idft(X):
    N = len(X)
    x = []
    for n in range(N):
        val = 0 + 0j
        for k in range(N):
            val += X[k] * math.e ** (2j * math.pi * k * n / N)
        x.append((val / N).real)
    return x

Verify the round trip: define dft from the previous lesson and check idft(dft([1,2,3,4])) ≈ [1,2,3,4].