Real-time DSP processing pipeline in Signal Processing - Time & Space Complexity

Time Complexity: Real-time DSP processing pipeline

O(n log k)

Understanding Time Complexity

When working with real-time digital signal processing (DSP), it is important to know how the processing time changes as the input signal length grows.

We want to understand how the time to process each signal frame scales with the size of the input data.

Scenario Under Consideration

Analyze the time complexity of the following DSP pipeline code.

for sample in input_signal:
    filtered = apply_filter(sample)
    transformed = fft(filtered)
    output.append(transformed)
    

This code processes each sample by filtering it, then applying a fast Fourier transform (FFT), and stores the result.

Identify Repeating Operations

Look at what repeats as the input grows.

• Primary operation: Loop over each sample in the input signal.
• How many times: Once for every sample in the input (n times).
• Inside the loop: Each sample is filtered (constant time) and then transformed using FFT.
• FFT operation: Runs on the filtered data, which size depends on the frame size, often fixed and not proportional to n.

How Execution Grows With Input

As the input signal length grows, the number of samples to process grows linearly.

Input Size (n)	Approx. Operations
10	About 10 FFTs and filters
100	About 100 FFTs and filters
1000	About 1000 FFTs and filters

Each FFT itself takes more time as its input size grows, so the total time grows faster than just the number of samples if the FFT input size grows with n.

Final Time Complexity

Time Complexity: O(n log k) where k is the FFT input size per sample.

This means the processing time grows linearly with the number of samples and logarithmically with the FFT input size, which is often fixed, making the overall complexity close to linear.

Common Mistake

[X] Wrong: "The processing time grows exactly linearly with input size because we just loop over samples."

[OK] Correct: Each sample's FFT step depends on the size of the data it processes, which adds a logarithmic factor if the FFT input size grows with n.

Interview Connect

Understanding how signal processing steps scale with input size helps you explain and design efficient real-time systems, a valuable skill in many technical roles.

Self-Check

"What if we replaced the FFT with a simpler transform that runs in linear time? How would the time complexity change?"

Practice

1. What is the main purpose of a real-time DSP processing pipeline?

easy

A. To process signals step-by-step as data arrives

B. To store large amounts of data for later analysis

C. To generate random signals for testing

D. To visualize signals after processing is complete

Solution

1. Step 1: Understand real-time processing

   Real-time DSP means processing data immediately as it comes in, not storing for later.

2. Step 2: Identify pipeline purpose

   The pipeline processes signals step-by-step to analyze or clean them on the fly.

3. Final Answer:

   To process signals step-by-step as data arrives -> Option A

4. Quick Check:

   Real-time DSP = step-by-step processing [OK]

Hint: Real-time means processing data immediately as it arrives [OK]

Common Mistakes:

• Confusing real-time with batch processing
• Thinking pipeline stores data only
• Assuming visualization is the main goal

2. Which of the following is the correct syntax to apply a moving average filter on a signal array data in Python using a window size of 3?

easy

A. filtered = [sum(data[i:i+3])*3 for i in range(len(data)-2)]

B. filtered = [sum(data[i:i+3])/3 for i in range(len(data)-2)]

C. filtered = [sum(data[i:i+3])/3 for i in range(len(data)+2)]

D. filtered = sum(data[i:i+3])/3 for i in range(len(data)-2)

Solution

1. Step 1: Understand moving average filter

   It averages each group of 3 consecutive elements in the data.

2. Step 2: Check syntax correctness

   filtered = [sum(data[i:i+3])/3 for i in range(len(data)-2)] correctly uses list comprehension with range(len(data)-2) and divides sum by 3.

3. Final Answer:

   filtered = [sum(data[i:i+3])/3 for i in range(len(data)-2)] -> Option B

4. Quick Check:

   Correct list comprehension with proper range and division [OK]

Hint: Use range(len(data)-window+1) for correct slicing [OK]

Common Mistakes:

• Missing brackets for list comprehension
• Using wrong range length causing index errors
• Multiplying instead of dividing for average

3. Given the Python code below for a simple real-time DSP pipeline, what is the output of print(filtered_signal)?

signal = [1, 3, 5, 7, 9]
window_size = 2
filtered_signal = [ (signal[i] + signal[i+1]) / 2 for i in range(len(signal)-1) ]
print(filtered_signal)

medium

A. [1.0, 4.0, 6.0, 8.0]

B. [1.0, 3.0, 5.0, 7.0, 9.0]

C. [2.0, 4.0, 6.0, 8.0]

D. [3.0, 5.0, 7.0, 9.0]

Solution

1. Step 1: Understand the list comprehension

   It averages each pair of consecutive elements: (signal[i] + signal[i+1]) / 2.

2. Step 2: Calculate each average

   Pairs: (1+3)/2=2.0, (3+5)/2=4.0, (5+7)/2=6.0, (7+9)/2=8.0.

3. Final Answer:

   [2.0, 4.0, 6.0, 8.0] -> Option C

4. Quick Check:

   Pairwise averages = [2.0, 4.0, 6.0, 8.0] [OK]

Hint: Calculate pair averages step-by-step [OK]

Common Mistakes:

• Including last element without pair
• Confusing sum with average
• Wrong range causing index error

4. The following code attempts to implement a moving average filter but raises an error. What is the error and how to fix it?

data = [2, 4, 6, 8]
window = 3
filtered = []
for i in range(len(data)):
    avg = (data[i] + data[i+1] + data[i+2]) / window
    filtered.append(avg)
print(filtered)

medium

A. IndexError because indexing goes beyond list end; fix by using range(len(data)-window+1)

B. ZeroDivisionError because window is zero; fix by setting window to 1

C. TypeError because sum cannot add list slices; fix by converting slice to list

D. No error; code runs correctly

Solution

1. Step 1: Identify the error cause

   Loop runs till len(data), but indexing data[i+2] exceeds list length at end.

2. Step 2: Fix the loop range

   Change loop to range(len(data)-window+1) to avoid out-of-range indexing.

3. Final Answer:

   IndexError because indexing goes beyond list end; fix by using range(len(data)-window+1) -> Option A

4. Quick Check:

   Loop range must prevent out-of-bound indexing [OK]

Hint: Loop till len(data)-window+1 for safe indexing [OK]

Common Mistakes:

• Ignoring index bounds causing IndexError
• Changing window size incorrectly
• Assuming no error occurs

5. You want to build a real-time DSP pipeline that filters noise from a sensor signal using a moving average filter of window size 4, but the sensor sometimes sends fewer than 4 samples at once. How should you adapt your pipeline to handle this situation correctly?

hard

A. Use a fixed window size of 1 to avoid buffering

B. Apply the filter on whatever samples arrive, even if fewer than 4, without buffering

C. Discard any samples fewer than 4 and wait for a full batch

D. Process only when at least 4 samples are available; buffer incoming data until then

Solution

1. Step 1: Understand window size requirement

   Moving average with window 4 needs 4 samples to compute an average.

2. Step 2: Handle fewer samples in real-time

   Buffer incoming samples until at least 4 are collected, then apply filter.

3. Step 3: Avoid incorrect averages

   Processing fewer samples without buffering gives wrong results; discarding loses data.

4. Final Answer:

   Process only when at least 4 samples are available; buffer incoming data until then -> Option D

5. Quick Check:

   Buffering ensures correct window size for filtering [OK]

Hint: Buffer data until window size reached before filtering [OK]

Common Mistakes:

• Filtering with incomplete windows causing errors
• Discarding useful data
• Using window size 1 losing noise reduction benefits