How to Compute DFT: Discrete Fourier Transform Explained

To compute the Discrete Fourier Transform (DFT) of a sequence, apply the formula X[k] = Σ (x[n] * e^(-j2πkn/N)) where x[n] is the input signal, N is the number of points, and k is the frequency index. This transforms the time-domain signal into its frequency components.

Syntax

The DFT formula is:

X[k] = Σn=0N-1 x[n] * e-j2πkn/N

• x[n]: input signal at time index n
• N: total number of samples
• k: frequency index (0 to N-1)
• e: Euler's number, j is imaginary unit

This sums the input multiplied by complex exponentials to find frequency components.

python

def dft(x):
    import cmath
    N = len(x)
    X = []
    for k in range(N):
        s = 0
        for n in range(N):
            angle = -2j * cmath.pi * k * n / N
            s += x[n] * cmath.exp(angle)
        X.append(s)
    return X

Example

This example computes the DFT of a simple 4-point signal [1, 2, 3, 4] and prints the frequency components.

python

def dft(x):
    import cmath
    N = len(x)
    X = []
    for k in range(N):
        s = 0
        for n in range(N):
            angle = -2j * cmath.pi * k * n / N
            s += x[n] * cmath.exp(angle)
        X.append(s)
    return X

signal = [1, 2, 3, 4]
result = dft(signal)
for i, val in enumerate(result):
    print(f"X[{i}] = {val}")

Output

X[0] = (10+0j)
X[1] = (-2+2j)
X[2] = (-2+0j)
X[3] = (-2-2j)

Common Pitfalls

• Not using complex numbers correctly causes wrong results.
• Mixing up the sign in the exponent (should be negative).
• Forgetting to sum over all n from 0 to N-1.
• Using DFT on very large signals without Fast Fourier Transform (FFT) can be slow.

python

import cmath

# Wrong: positive sign in exponent
# s += x[n] * cmath.exp(2j * cmath.pi * k * n / N)

# Right: negative sign in exponent
s += x[n] * cmath.exp(-2j * cmath.pi * k * n / N)

Quick Reference

Remember these key points when computing DFT:

• Input length N defines frequency resolution.
• Output X[k] are complex numbers representing amplitude and phase.
• Use negative sign in exponent for forward DFT.
• For large data, use FFT for efficiency.

Key Takeaways

The DFT converts a time signal into frequency components using a sum of complex exponentials.

Use the negative sign in the exponent to correctly compute the forward DFT.

DFT outputs complex numbers representing amplitude and phase of frequencies.

Computing DFT directly is slow for large signals; use FFT for faster results.

Always sum over all input points from 0 to N-1 for accurate transformation.