DSP System Toolbox blocks in Simulink - Time & Space Complexity

Time Complexity: DSP System Toolbox blocks

O(n * m)

Understanding Time Complexity

When using DSP System Toolbox blocks in Simulink, it's important to understand how the time to process signals grows as the input size increases.

We want to know how the processing time changes when the signal length or sample rate changes.

Scenario Under Consideration

Analyze the time complexity of the following DSP filter block setup.

% Simulink DSP filter block example
% Input: signal vector x of length n
% Filter: FIR filter with coefficients b
% Output: filtered signal y

for k = 1:n
    y(k) = 0;
    for j = 1:length(b)
        if k-j+1 >= 1
            y(k) = y(k) + b(j)*x(k-j+1);
        end
    end
end
    

This code applies an FIR filter to an input signal by sliding the filter coefficients over the signal samples.

Identify Repeating Operations

Look at the loops that repeat work:

• Primary operation: Multiplying and adding filter coefficients to signal samples.
• How many times: The outer loop runs once per input sample (n times), and the inner loop runs once per filter coefficient (m times).

How Execution Grows With Input

As the input signal length grows, the total work grows by the number of samples times the number of filter coefficients.

Input Size (n)	Approx. Operations (n * m)
10	10 * m
100	100 * m
1000	1000 * m

Pattern observation: The total operations grow linearly with the input size and linearly with the filter length.

Final Time Complexity

Time Complexity: O(n * m)

This means the processing time grows proportionally to the input length times the filter size.

Common Mistake

[X] Wrong: "The filter processing time only depends on the input length n."

[OK] Correct: The filter length m also affects the time because each output sample requires m multiplications and additions.

Interview Connect

Understanding how DSP blocks scale helps you explain performance in signal processing tasks and design efficient systems.

Self-Check

What if we replaced the FIR filter with an IIR filter that uses feedback? How would the time complexity change?