Sampling and reconstruction in communication in Signal Processing - Time & Space Complexity

Time Complexity: Sampling and reconstruction in communication

O(n)

Understanding Time Complexity

We want to understand how the time to sample and reconstruct a signal changes as the signal length grows.

How does the work needed grow when we handle longer signals?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

# Assume signal is a list of length n
sampled_signal = []
for i in range(0, len(signal), sampling_rate):
    sampled_signal.append(signal[i])

reconstructed_signal = []
for i in range(len(sampled_signal) - 1):
    # simple linear interpolation
    start = sampled_signal[i]
    end = sampled_signal[i + 1]
    reconstructed_signal.append(start)
    reconstructed_signal.append((start + end) / 2)
reconstructed_signal.append(sampled_signal[-1])
    

This code samples the original signal at fixed steps, then reconstructs it by filling values between samples using linear interpolation.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the original signal to sample and looping through the sampled signal to reconstruct.
• How many times: Sampling loop runs about n / sampling_rate times; reconstruction loop runs about the same times.

How Execution Grows With Input

As the signal length n grows, the number of samples grows roughly proportional to n divided by the sampling rate.

Input Size (n)	Approx. Operations
10	About 10 operations for sampling and reconstruction combined
100	About 100 operations
1000	About 1000 operations

Pattern observation: The work grows roughly in direct proportion to the signal length.

Final Time Complexity

Time Complexity: O(n)

This means the time to sample and reconstruct grows linearly as the signal length increases.

Common Mistake

[X] Wrong: "Sampling and reconstruction take constant time regardless of signal length."

[OK] Correct: The loops must process more data as the signal gets longer, so time grows with input size.

Interview Connect

Understanding how processing time grows with signal size helps you explain efficiency clearly, a useful skill in real projects and interviews.

Self-Check

"What if we used a more complex interpolation method that looks at multiple neighboring samples? How would the time complexity change?"

Practice

1. What is the main purpose of sampling in communication systems?

easy

A. To convert a continuous signal into discrete values

B. To amplify the signal strength

C. To filter out noise from the signal

D. To encrypt the signal for security

Solution

1. Step 1: Understand the role of sampling

   Sampling takes a continuous-time signal and measures its amplitude at discrete time intervals.

2. Step 2: Identify the purpose in communication

   This process allows the signal to be represented digitally for processing and transmission.

3. Final Answer:

   To convert a continuous signal into discrete values -> Option A

4. Quick Check:

   Sampling = Continuous to discrete conversion [OK]

Hint: Sampling means turning smooth signals into numbers [OK]

Common Mistakes:

• Confusing sampling with filtering
• Thinking sampling increases signal strength
• Mixing sampling with encryption

2. Which of the following is the correct Nyquist sampling rate formula for a signal with maximum frequency f_max?

easy

A. f_s > f_max / 2

B. f_s > 2 * f_max

C. f_s = f_max

D. f_s < f_max / 2

Solution

1. Step 1: Recall Nyquist theorem

   The Nyquist rate states the sampling frequency must be greater than twice the highest frequency in the signal.

2. Step 2: Apply to formula

   So, f_s > 2 * f_max ensures no loss of information during sampling.

3. Final Answer:

   f_s > 2 * f_max -> Option B

4. Quick Check:

   Nyquist rate = 2 * max frequency [OK]

Hint: Sample faster than twice the highest frequency [OK]

Common Mistakes:

• Using sampling rate less than max frequency
• Confusing less than and greater than signs
• Ignoring the factor of 2 in Nyquist rate

3. Given a continuous signal with maximum frequency 3 kHz, what is the minimum sampling frequency to avoid aliasing? Choose the correct Python code output.

f_max = 3000
f_s = 2 * f_max
print(f_s)

medium

A. 6000

B. 1500

C. 3000

D. 9000

Solution

1. Step 1: Calculate minimum sampling frequency

   Using Nyquist, minimum sampling frequency is twice the max frequency: 2 * 3000 = 6000 Hz.

2. Step 2: Check Python code output

   The code multiplies 3000 by 2 and prints 6000, matching the calculation.

3. Final Answer:

   6000 -> Option A

4. Quick Check:

   2 * 3000 = 6000 [OK]

Hint: Double the max frequency to get sampling rate [OK]

Common Mistakes:

• Printing max frequency instead of double
• Dividing instead of multiplying
• Confusing units (Hz vs kHz)

4. Identify the error in the following Python code snippet for reconstructing a signal using sinc interpolation:

import numpy as np

def reconstruct_signal(samples, t, T):
    x_recon = 0
    for n in range(len(samples)):
        x_recon += samples[n] * np.sinc((t - n*T))
    return x_recon

# samples = [1, 2, 3], t = 1.5, T = 1
print(reconstruct_signal([1, 2, 3], 1.5, 1))

medium

A. np.sinc argument should be normalized by pi

B. Loop should iterate over t values, not samples

C. x_recon should be initialized as an array, not zero

D. The function should return samples instead of x_recon

Solution

1. Step 1: Understand np.sinc function

   In numpy, np.sinc(x) = sin(pi*x)/(pi*x), so input is already normalized by pi.

2. Step 2: Check argument passed to np.sinc

   The code passes (t - n*T) directly, which is correct because np.sinc expects normalized input.

3. Step 3: Identify error

   Actually, the argument is correct; the error is that x_recon is initialized as 0 (a scalar), but the function expects to handle array inputs for t for vectorized reconstruction.

4. Step 4: Correct error

   x_recon should be initialized as np.zeros_like(t) if t is an array, but since t is scalar here, initialization is fine.

5. Step 5: Reconsider options

   np.sinc argument should be normalized by pi says argument should be normalized by pi, but numpy's sinc already does that, so no need to normalize.

6. Step 6: Final conclusion

   No error in normalization; the code is correct for scalar t. The main issue is if t is array, initialization fails.

7. Final Answer:

   x_recon should be initialized as an array, not zero -> Option C

8. Quick Check:

   Accumulator initialization must match output type [OK]

Hint: Remember numpy sinc is normalized by pi already [OK]

Common Mistakes:

• Assuming np.sinc needs manual pi normalization
• Initializing accumulator incorrectly for arrays
• Confusing loop variable roles

5. You have a signal sampled at 8 kHz with maximum frequency 5 kHz. What problem will occur during reconstruction, and how can it be fixed?

hard

A. Signal will be noisy; fix by applying a low-pass filter after sampling

B. Signal will be delayed; fix by adjusting reconstruction timing

C. No problem; sampling rate is sufficient for reconstruction

D. Aliasing will occur; fix by increasing sampling rate above 10 kHz

Solution

1. Step 1: Compare sampling rate and Nyquist rate

   Nyquist rate = 2 * max frequency = 2 * 5 kHz = 10 kHz. Sampling rate is 8 kHz, which is less than Nyquist rate.

2. Step 2: Identify consequence of insufficient sampling

   Sampling below Nyquist rate causes aliasing, where higher frequencies appear as lower frequencies, distorting the signal.

3. Step 3: Determine solution

   To avoid aliasing, increase sampling rate above 10 kHz.

4. Final Answer:

   Aliasing will occur; fix by increasing sampling rate above 10 kHz -> Option D

5. Quick Check:

   Sampling rate < Nyquist rate causes aliasing [OK]

Hint: Sample above twice max frequency to avoid aliasing [OK]

Common Mistakes:

• Assuming 8 kHz is enough for 5 kHz max frequency
• Confusing noise with aliasing
• Ignoring Nyquist sampling theorem