Transfer function H(z) in Signal Processing - Time & Space Complexity

Time Complexity: Transfer function H(z)

O(n * m)

Understanding Time Complexity

We want to understand how the time to compute the transfer function H(z) changes as the input size grows.

How does the number of calculations grow when we increase the length of the input signal or filter coefficients?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

# Compute output y[n] using transfer function H(z)
for n in range(len(x)):
    y[n] = 0
    for k in range(len(h)):
        if n - k >= 0:
            y[n] += h[k] * x[n - k]

This code calculates the output signal y by applying the filter coefficients h to the input signal x using convolution.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops performing multiplications and additions for convolution.
• How many times: Outer loop runs for each input sample (n times), inner loop runs for each filter coefficient (m times).

How Execution Grows With Input

As the input size or filter length grows, the total operations increase by multiplying these sizes.

Input Size (n)	Filter Length (m)	Approx. Operations
10	5	50
100	5	500
1000	5	5000

Pattern observation: Operations grow proportionally to the product of input size and filter length.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to compute grows in direct proportion to both the input length and the filter size.

Common Mistake

[X] Wrong: "The time to compute H(z) depends only on the input size n."

[OK] Correct: The filter length m also affects the total work because each input sample is combined with all filter coefficients.

Interview Connect

Understanding how nested loops affect time helps you explain performance in signal processing tasks clearly and confidently.

Self-Check

"What if the filter length m is fixed and very small? How would the time complexity change as input size n grows?"

Practice

1. What does the transfer function H(z) represent in signal processing?

easy

A. The amplitude of the output signal

B. The time delay of a signal

C. The frequency of the input signal

D. The ratio of output to input signals in the z-domain

Solution

1. Step 1: Understand the definition of transfer function

   The transfer function H(z) is defined as the ratio of the output signal to the input signal in the z-domain.

2. Step 2: Identify the correct description

   Among the options, only The ratio of output to input signals in the z-domain correctly describes H(z) as this ratio.

3. Final Answer:

   The ratio of output to input signals in the z-domain -> Option D

4. Quick Check:

   Transfer function = output/input ratio [OK]

Hint: Remember: H(z) = output signal ÷ input signal [OK]

Common Mistakes:

• Confusing H(z) with time delay
• Thinking H(z) is just frequency
• Mixing amplitude with transfer function

2. Which of the following is the correct general form of a digital filter transfer function H(z)?

easy

A. H(z) = (b0 + b1z + b2z^2) / (1 + a1z + a2z^2)

B. H(z) = (b0 + b1z^{-1} + b2z^{-2}) * (1 + a1z^{-1} + a2z^{-2})

C. H(z) = (b0 + b1z^{-1} + b2z^{-2}) / (1 + a1z^{-1} + a2z^{-2})

D. H(z) = (b0z + b1z^2 + b2z^3) / (1 + a1z + a2z^2)

Solution

1. Step 1: Recall the standard form of digital filter transfer function

   The transfer function is usually expressed with negative powers of z, representing delays: numerator and denominator polynomials in z^{-1}.

2. Step 2: Compare options with the standard form

   H(z) = (b0 + b1z^{-1} + b2z^{-2}) / (1 + a1z^{-1} + a2z^{-2}) correctly shows numerator and denominator with negative powers of z, matching the standard form.

3. Final Answer:

   H(z) = (b0 + b1z^{-1} + b2z^{-2}) / (1 + a1z^{-1} + a2z^{-2}) -> Option C

4. Quick Check:

   Negative powers of z indicate delays [OK]

Hint: Look for negative powers of z in numerator and denominator [OK]

Common Mistakes:

• Using positive powers of z incorrectly
• Multiplying numerator and denominator instead of dividing
• Forgetting the leading 1 in denominator

3. Given the transfer function H(z) = (1 - 0.5z^{-1}) / (1 - 0.9z^{-1} + 0.15z^{-2}), what is the value of H(z) at z = 1?

medium

A. 2.0

B. 1.0

C. 0.5

D. 0.0

Solution

1. Step 1: Substitute z = 1 into H(z)

   Calculate numerator: 1 - 0.5 * 1^{-1} = 1 - 0.5 = 0.5
   Calculate denominator: 1 - 0.9 * 1^{-1} + 0.15 * 1^{-2} = 1 - 0.9 + 0.15 = 0.25

2. Step 2: Compute H(1) = numerator / denominator

   H(1) = 0.5 / 0.25 = 2.0 exactly.

3. Final Answer:

   2.0 -> Option A

4. Quick Check:

   H(1) = 2.0 [OK]

Hint: Plug z=1, compute numerator and denominator separately [OK]

Common Mistakes:

• Forgetting to use z^{-1} as 1/z
• Incorrect arithmetic in numerator or denominator
• Choosing zero instead of computed value

4. Identify the error in the following transfer function expression:
H(z) = (1 + 0.3z^{-1} - 0.2z^{-2}) / (1 + 0.5z + 0.1z^{-2})

medium

A. Numerator has negative powers of z which is invalid

B. Denominator has a positive power of z which is incorrect

C. Transfer function must not have more than two terms in numerator

D. Denominator should be multiplied, not divided

Solution

1. Step 1: Examine powers of z in numerator and denominator

   The numerator has negative powers of z, which is correct for delays.
   The denominator has a positive power term 0.5z, which is not standard and incorrect.

2. Step 2: Confirm correct form of denominator

   The denominator should have terms with negative powers of z (delays), not positive powers (advances). So the positive power term is an error.

3. Final Answer:

   Denominator has a positive power of z which is incorrect -> Option B

4. Quick Check:

   Denominator powers must be negative [OK]

Hint: Check denominator powers: must be negative or zero [OK]

Common Mistakes:

• Allowing positive powers of z in denominator
• Confusing numerator and denominator powers
• Thinking number of terms limits validity

5. You have a transfer function H(z) = (1 - 0.7z^{-1}) / (1 - 1.2z^{-1} + 0.45z^{-2}). Which statement best describes the system's stability based on the poles of H(z)?

hard

A. The system is stable because all poles lie inside the unit circle

B. The system is unstable because at least one pole lies outside the unit circle

C. The system is marginally stable because poles lie on the unit circle

D. Stability cannot be determined without zeros

Solution

1. Step 1: Find the poles by solving denominator polynomial

   The denominator is 1 - 1.2z^{-1} + 0.45z^{-2} = 0.
   Rewrite as z^2 - 1.2z + 0.45 = 0 (multiply both sides by z^2).

2. Step 2: Calculate roots of the quadratic

   Using quadratic formula:
   z = [1.2 ± sqrt(1.44 - 1.8)] / 2
   Discriminant = 1.44 - 1.8 = -0.36 (complex roots)
   Roots: z = 0.6 ± 0.3i

3. Step 3: Calculate magnitude of poles

   Magnitude = sqrt(0.6^2 + 0.3^2) = sqrt(0.36 + 0.09) = sqrt(0.45) ≈ 0.67 < 1

4. Step 4: Re-examine coefficients for stability

   Actually, the denominator polynomial is in z^{-1}, so poles are roots of denominator polynomial in z.
   But the coefficients suggest poles inside unit circle, so system is stable.

5. Step 5: Check option correctness

   Options say system is unstable if poles outside unit circle.
   Our calculation shows poles inside unit circle, so system is stable.

6. Final Answer:

   The system is stable because all poles lie inside the unit circle -> Option A

7. Quick Check:

   Poles magnitude < 1 means stable [OK]

Hint: Calculate pole magnitudes; inside unit circle means stable [OK]

Common Mistakes:

• Confusing zeros with poles for stability
• Ignoring complex roots magnitude
• Assuming zeros affect stability