Sample rate conversion basics in Signal Processing - Time & Space Complexity

Time Complexity: Sample rate conversion basics

O(n * L * filter_len)

Understanding Time Complexity

When changing the sample rate of a signal, we want to know how the work grows as the signal length grows.

How does the time to convert a signal change when the input gets longer?

Scenario Under Consideration

Analyze the time complexity of the following sample rate conversion code.

# Upsample by factor L
upsampled = []
for sample in input_signal:
    upsampled.append(sample)
    for _ in range(L - 1):
        upsampled.append(0)

# Simple low-pass filter
filtered = []
for i in range(len(upsampled) - filter_len + 1):
    window = upsampled[i:i+filter_len]
    filtered.append(sum(window) / filter_len)
    

This code upsamples a signal by inserting zeros and then applies a simple moving average filter.

Identify Repeating Operations

Identify the loops and repeated work.

• Primary operation: Loop over input samples to insert zeros (upsampling).
• Secondary operation: Loop over upsampled signal to apply filter (moving average).
• How many times: Upsampling loop runs once per input sample; filtering loop runs once per upsampled sample.

How Execution Grows With Input

As input size grows, the upsampled signal grows by factor L, so filtering work grows with that larger size.

Input Size (n)	Approx. Operations
10	About 10 * L + (10 * L) * filter_len
100	About 100 * L + (100 * L) * filter_len
1000	About 1000 * L + (1000 * L) * filter_len

Pattern observation: Operations grow roughly linearly with input size multiplied by upsampling factor.

Final Time Complexity

Time Complexity: O(n * L * filter_len)

This means the time to convert grows roughly in direct proportion to the input length multiplied by the upsampling factor and filter length.

Common Mistake

[X] Wrong: "Upsampling always makes the process take much longer than input size because of inserted zeros."

[OK] Correct: While upsampling increases data length by factor L, the filtering step dominates and both scale linearly with input size times L and filter length, so overall time grows linearly, not exponentially.

Interview Connect

Understanding how signal length affects processing time helps you explain efficiency in real projects and shows you can think about scaling in data tasks.

Self-Check

"What if we replaced the simple moving average filter with a more complex filter that uses convolution with a large kernel? How would the time complexity change?"

Practice

1. What does sample rate conversion do in signal processing?

easy

A. Changes how often a signal is measured

B. Changes the signal's amplitude

C. Changes the signal's frequency content

D. Changes the signal's phase

Solution

1. Step 1: Understand sample rate meaning

   Sample rate is how many times per second a signal is measured or sampled.

2. Step 2: Define sample rate conversion

   Sample rate conversion changes this measurement rate, either increasing or decreasing it.

3. Final Answer:

   Changes how often a signal is measured -> Option A

4. Quick Check:

   Sample rate conversion = Changes measurement rate [OK]

Hint: Sample rate conversion changes measurement frequency [OK]

Common Mistakes:

• Confusing sample rate with signal amplitude
• Thinking it changes signal frequency content
• Mixing phase changes with sample rate changes

2. Which of the following is the correct Python syntax to upsample a signal by a factor of 2 using scipy.signal.resample_poly?

easy

A. resample_poly(signal, up=1, down=2)

B. resample_poly(signal, up=2, down=1)

C. resample_poly(signal, rate=2)

D. resample_poly(signal, down=2)

Solution

1. Step 1: Recall resample_poly parameters

   The function uses 'up' to increase sample rate and 'down' to decrease it.

2. Step 2: Identify upsampling by 2

   To upsample by 2, set up=2 and down=1 to keep original rate multiplied by 2.

3. Final Answer:

   resample_poly(signal, up=2, down=1) -> Option B

4. Quick Check:

   Upsample factor = up=2, down=1 [OK]

Hint: Upsample means up>down, so up=2, down=1 [OK]

Common Mistakes:

• Swapping up and down values
• Omitting required parameters
• Using only up or down without the other

3. Given a signal sampled at 1000 Hz, what will be the new sample rate after applying resample_poly(signal, up=3, down=2)?

medium

A. 1500 Hz

B. 2000 Hz

C. 500 Hz

D. 3000 Hz

Solution

1. Step 1: Understand resample_poly rate change

   The new sample rate = original rate * (up / down).

2. Step 2: Calculate new sample rate

   1000 Hz * (3 / 2) = 1500 Hz.

3. Final Answer:

   1500 Hz -> Option A

4. Quick Check:

   1000 * 3/2 = 1500 Hz [OK]

Hint: Multiply original rate by up/down ratio [OK]

Common Mistakes:

• Multiplying by down/up instead of up/down
• Forgetting to multiply by original rate
• Confusing sample rate with signal length

4. What is wrong with this code snippet for downsampling a signal by 4?

from scipy.signal import resample_poly
new_signal = resample_poly(signal, up=1, down=4)

medium

A. It will cause a syntax error due to missing import

B. The up parameter should be 4, not 1

C. It may cause aliasing without proper filtering

D. The down parameter should be 1, not 4

Solution

1. Step 1: Check code correctness

   The code syntax is correct and imports resample_poly properly.

2. Step 2: Understand downsampling risks

   Downsampling by 4 reduces sample rate, which can cause aliasing if signal is not filtered.

3. Final Answer:

   It may cause aliasing without proper filtering -> Option C

4. Quick Check:

   Downsampling needs filtering to avoid aliasing [OK]

Hint: Downsampling needs filtering to prevent aliasing [OK]

Common Mistakes:

• Assuming code syntax error
• Confusing up and down parameters
• Ignoring aliasing effects

5. You have a 44100 Hz audio signal and want to convert it to 16000 Hz for a speech recognition system. Which combination of up and down factors correctly resamples the signal using resample_poly?

hard

A. up=1600, down=441

B. up=44100, down=16000

C. up=160, down=4410

D. up=160, down=441

Solution

1. Step 1: Calculate ratio for resampling

   The ratio is new_rate / old_rate = 16000 / 44100 ≈ 0.3628.

2. Step 2: Find integer up/down factors

   Scaling both by 1000 gives up=160, down=441, which approximates the ratio well.

3. Final Answer:

   up=160, down=441 -> Option D

4. Quick Check:

   160/441 ≈ 0.3628 matches 16000/44100 [OK]

Hint: Simplify ratio new_rate/old_rate to small integers [OK]

Common Mistakes:

• Using raw sample rates as up/down without simplification
• Swapping up and down values
• Choosing factors that don't approximate ratio