Discrete Fourier Transform (DFT) in Signal Processing - Step-by-Step Execution

Concept Flow - Discrete Fourier Transform (DFT)

Input: Time-domain signal x[n

↓

Compute DFT X[k

↓

For each frequency k: sum over n of x[n

↓

Output: Frequency-domain signal X[k

The DFT converts a time signal into its frequency components by summing weighted complex exponentials for each frequency.

Execution Sample

Signal Processing

import numpy as np
x = [1, 0, -1, 0]
N = 4
X = []
for k in range(N):
    s = sum(x[n]*np.exp(-2j*np.pi*k*n/N) for n in range(N))
    X.append(s)

This code computes the DFT of a simple 4-point signal step-by-step.

Execution Table

Step	k	n	x[n]	exp(-j*2*pi*k*n/N)	Product	Sum s for k
1	0	0	1	1.0+0.0j	1.0+0.0j	1.0+0.0j
2	0	1	0	1.0+0.0j	0.0+0.0j	1.0+0.0j
3	0	2	-1	1.0+0.0j	-1.0+0.0j	0.0+0.0j
4	0	3	0	1.0+0.0j	0.0+0.0j	0.0+0.0j
5	k=0 done					X[0] = 0.0+0.0j
6	1	0	1	1.0+0.0j	1.0+0.0j	1.0+0.0j
7	1	1	0	0.0-1.0j	0.0+0.0j	1.0+0.0j
8	1	2	-1	-1.0-0.0j	1.0+0.0j	2.0+0.0j
9	1	3	0	0.0+1.0j	0.0+0.0j	2.0+0.0j
10	k=1 done					X[1] = 2.0+0.0j
11	2	0	1	1.0+0.0j	1.0+0.0j	1.0+0.0j
12	2	1	0	-1.0+0.0j	0.0+0.0j	1.0+0.0j
13	2	2	-1	1.0+0.0j	-1.0+0.0j	0.0+0.0j
14	2	3	0	-1.0+0.0j	0.0+0.0j	0.0+0.0j
15	k=2 done					X[2] = 0.0+0.0j
16	3	0	1	1.0+0.0j	1.0+0.0j	1.0+0.0j
17	3	1	0	0.0+1.0j	0.0+0.0j	1.0+0.0j
18	3	2	-1	-1.0+0.0j	1.0+0.0j	2.0+0.0j
19	3	3	0	0.0-1.0j	0.0+0.0j	2.0+0.0j
20	k=3 done					X[3] = 2.0+0.0j

💡 All k from 0 to N-1 computed, DFT complete

Variable Tracker

Variable	Start	After k=0	After k=1	After k=2	After k=3	Final
k	0	0	1	2	3	3
s (sum)	0	0.0+0.0j	2.0+0.0j	0.0+0.0j	2.0+0.0j	2.0+0.0j
X (DFT output)	[]	[0.0+0.0j]	[0.0+0.0j, 2.0+0.0j]	[0.0+0.0j, 2.0+0.0j, 0.0+0.0j]	[0.0+0.0j, 2.0+0.0j, 0.0+0.0j, 2.0+0.0j]	[0.0+0.0j, 2.0+0.0j, 0.0+0.0j, 2.0+0.0j]

Key Moments - 3 Insights

Why do we multiply x[n] by a complex exponential in the sum?

Because each complex exponential represents a specific frequency component; multiplying and summing extracts how much of that frequency is in the signal (see execution_table rows 1-4 for k=0).

Why does the sum s reset for each new k?

Because each k corresponds to a different frequency; we calculate a separate sum for each frequency to find its coefficient (see execution_table rows 5, 10, 15, 20).

Why are some sums zero and others not?

Because the signal has certain frequency components; sums near zero mean little presence of that frequency, sums with larger magnitude mean strong presence (see sums at k=0 and k=2 are zero, k=1 and k=3 are 2.0).

Visual Quiz - 3 Questions

Look at the execution_table at step 9, what is the sum s for k=1 after n=3?

A 2.0+0.0j

B 1.0+0.0j

C 0.0+0.0j

D -1.0+0.0j

💡 Hint

Check the 'Sum s for k' column at step 9 in execution_table

At which iteration k does the DFT output X[k] equal 0.0+0.0j?

A k=1

B k=2

C k=3

D k=0

💡 Hint

Look at the 'X[k]' values in execution_table rows 5, 10, 15, 20

If the input x[n] was all zeros, how would the sums s change in the execution_table?

A Sums s would be complex numbers with magnitude 1

B Sums s would be equal to N for every k

C All sums s would be zero for every k

D Sums s would alternate between zero and one

💡 Hint

Recall that sum s is sum of x[n]*complex exponential; zero input means zero products

Concept Snapshot

Discrete Fourier Transform (DFT):
- Converts time signal x[n] into frequency components X[k]
- Formula: X[k] = sum_{n=0}^{N-1} x[n] * exp(-j*2*pi*k*n/N)
- k = frequency index, n = time index
- Output X[k] are complex numbers showing amplitude and phase
- Used to analyze signal frequencies in data science and engineering

Full Transcript

The Discrete Fourier Transform (DFT) takes a list of time-based signal values and changes them into frequency-based values. For each frequency index k, it sums all the time values multiplied by a complex exponential that represents that frequency. This sum shows how much of that frequency is in the signal. The code example computes this for a simple 4-point signal. The execution table shows each step: for each k and n, it calculates the product and adds it to the sum s. After all n for a k are done, s is stored as X[k]. The variable tracker shows how k, s, and the output list X change over time. Key moments explain why we multiply by complex exponentials, why sums reset for each k, and why some sums are zero. The quiz tests understanding of sums at specific steps, which frequencies have zero output, and what happens if the input is zero. The snapshot summarizes the DFT formula and purpose simply.

Practice

1. What does the Discrete Fourier Transform (DFT) primarily do to a signal?

easy

A. Converts the signal from time domain to frequency domain

B. Amplifies the signal amplitude

C. Filters out noise from the signal

D. Compresses the signal data size

Solution

1. Step 1: Understand signal domains

   The time domain shows how a signal changes over time, while the frequency domain shows the signal's frequency components.

2. Step 2: Role of DFT

   DFT transforms a signal from the time domain into the frequency domain, revealing hidden frequencies.

3. Final Answer:

   Converts the signal from time domain to frequency domain -> Option A

4. Quick Check:

   DFT = Time to Frequency [OK]

Hint: DFT = time to frequency conversion [OK]

Common Mistakes:

• Thinking DFT amplifies signals
• Confusing DFT with noise filtering
• Assuming DFT compresses data

2. Which of the following is the correct Python syntax to compute the DFT of a 1D array signal using numpy?

easy

A. numpy.dft(signal)

B. numpy.fft.fft(signal)

C. numpy.fft.dft(signal)

D. numpy.fft.transform(signal)

Solution

1. Step 1: Identify numpy FFT function

   In numpy, the function to compute the Discrete Fourier Transform is fft inside the fft module.

2. Step 2: Check correct syntax

   The correct call is numpy.fft.fft(signal). Other options are either non-existent or incorrect function names.

3. Final Answer:

   numpy.fft.fft(signal) -> Option B

4. Quick Check:

   Use numpy.fft.fft() for DFT [OK]

Hint: Use numpy.fft.fft() to compute DFT [OK]

Common Mistakes:

• Using nonexistent numpy.dft() function
• Confusing module and function names
• Typing transform instead of fft

3. Given the Python code:

import numpy as np
signal = np.array([1, 0, -1, 0])
dft_result = np.fft.fft(signal)
print(np.round(dft_result, 2))

What is the output?

medium

A. [0.+0.j 0.+2.j 0.+0.j 0.-2.j]

B. [0.+0.j 0.+0.j 0.+0.j 0.+0.j]

C. [0.+0.j 2.+0.j 0.+0.j 2.+0.j]

D. [0.+0.j 1.+0.j 0.+0.j 1.+0.j]

Solution

1. Step 1: Understand input signal

   The signal is [1, 0, -1, 0], a simple 4-point sequence alternating positive and negative values.

2. Step 2: Compute DFT manually or recall pattern

   DFT of this sequence results in complex values showing frequency components. The output is [0.+0.j, 0.+2.j, 0.+0.j, 0.-2.j] after rounding.

3. Final Answer:

   [0.+0.j 0.+2.j 0.+0.j 0.-2.j] -> Option A

4. Quick Check:

   DFT of alternating signal = complex freq components [OK]

Hint: Look for imaginary parts in DFT of alternating signals [OK]

Common Mistakes:

• Ignoring imaginary parts in output
• Confusing zero arrays with actual DFT
• Misreading numpy rounding output

4. Identify the error in this Python code snippet for computing DFT:

import numpy as np
signal = [1, 2, 3, 4]
dft = np.fft.fft(signal, n=2)
print(dft)

medium

A. np.fft.fft does not accept the parameter n

B. The signal must be a numpy array, not a list

C. The parameter n=2 truncates the DFT length incorrectly

D. The print statement syntax is incorrect

Solution

1. Step 1: Understand parameter n in np.fft.fft

   The parameter n sets the length of the DFT. If shorter than signal length, signal is truncated.

2. Step 2: Effect of n=2 on signal length 4

   Setting n=2 truncates the signal from length 4 to 2, losing data and changing the DFT result unexpectedly.

3. Final Answer:

   The parameter n=2 truncates the DFT length incorrectly -> Option C

4. Quick Check:

   n parameter truncates or pads signal [OK]

Hint: Check if n parameter matches signal length [OK]

Common Mistakes:

• Assuming n pads signal always
• Thinking signal must be numpy array
• Believing np.fft.fft disallows n parameter

5. You have a noisy signal sampled at 8 points: [1, 0, 1, 0, 1, 0, 1, 0]. You want to remove high-frequency noise by zeroing out the last 4 DFT coefficients and then reconstruct the signal using inverse DFT. Which Python code snippet correctly performs this?

hard

A. dft = np.fft.fft(signal)
dft[0:4] = 0
clean_signal = np.fft.ifft(dft).real

B. dft = np.fft.fft(signal)
dft[:4] = 0
clean_signal = np.fft.ifft(dft).real

C. dft = np.fft.fft(signal)
dft[2:] = 0
clean_signal = np.fft.ifft(dft).real

D. dft = np.fft.fft(signal)
dft[4:] = 0
clean_signal = np.fft.ifft(dft).real

Solution

1. Step 1: Compute DFT of signal

   Use np.fft.fft(signal) to get frequency components.

2. Step 2: Zero out last 4 coefficients to remove high frequencies

   Since signal length is 8, last 4 coefficients are dft[4:]. Setting them to zero removes high-frequency noise.

3. Step 3: Reconstruct signal with inverse DFT

   Use np.fft.ifft(dft).real to get cleaned time-domain signal.

4. Final Answer:

   dft = np.fft.fft(signal) dft[4:] = 0 clean_signal = np.fft.ifft(dft).real -> Option D

5. Quick Check:

   Zero last half DFT coefficients to filter high freq [OK]

Hint: Zero last half DFT coefficients to remove high frequencies [OK]

Common Mistakes:

• Zeroing first half instead of last half
• Zeroing wrong slice indices
• Forgetting to take real part after inverse DFT