Discrete-Time Systems

The convolution sum expresses the output of a discrete-time LTI system in terms of the input $x[n]$ and the impulse response $h[n]$ (the output when the input is $\delta[n]$).

Step 1: Any sequence as a sum of shifted impulses

Since $\delta[n-k] = 1$ only at $n = k$, each sample can be picked out:

$$x[n] = \sum_{k=-\infty}^{\infty} x[k]\,\delta[n-k]$$

For example, $x[n] = \{2, \underset{\uparrow}{1}, 3\}$ gives $x[n] = 2\delta[n+1] + \delta[n] + 3\delta[n-1]$.

Step 2: Apply the system properties

Let $T\{\cdot\}$ be the system and $h[n] = T\{\delta[n]\}$.

$$y[n] = T\{x[n]\} = T\left\{\sum_{k} x[k]\,\delta[n-k]\right\}$$

• Linearity (additivity and homogeneity): the $x[k]$ are just constants (weights), so

$$y[n] = \sum_{k=-\infty}^{\infty} x[k]\,T\{\delta[n-k]\}$$

• Time invariance: the response to $\delta[n-k]$ is $h[n-k]$.

Step 3: Result

$$y[n] = \sum_{k=-\infty}^{\infty} x[k]\,h[n-k] = x[n] * h[n]$$

This is the convolution sum. Putting $m = n-k$ gives the equivalent form

$$y[n] = \sum_{k=-\infty}^{\infty} h[k]\,x[n-k]$$

showing convolution is commutative.

Special cases:

• Causal system ($h[n] = 0$, $n < 0$) and causal input: $y[n] = \sum_{k=0}^{n} x[k]\,h[n-k]$.
• Lengths: if $x$ has $N_1$ samples and $h$ has $N_2$, $y$ has $N_1 + N_2 - 1$ samples.

Procedure: (1) fold $h[k]$ to $h[-k]$; (2) shift by $n$ to get $h[n-k]$; (3) multiply by $x[k]$ sample by sample; (4) sum the products to get $y[n]$; (5) repeat for every $n$.

Example: $x[n] = \{\underset{\uparrow}{1}, 2\}$, $h[n] = \{\underset{\uparrow}{1}, 1, 1\}$:

So $y[n] = \{\underset{\uparrow}{1}, 3, 3, 2\}$, with $2 + 3 - 1 = 4$ samples.

Given: $y[n] = 0.5\,y[n-1] + x[n]$, i.e. $y[n] - 0.5\,y[n-1] = x[n]$ (system initially at rest).

Frequency response

Take the DTFT of both sides, using the shift property $x[n-1] \leftrightarrow e^{-j\omega}X(e^{j\omega})$:

$$\begin{aligned} Y(e^{j\omega}) - 0.5\,e^{-j\omega}Y(e^{j\omega}) &= X(e^{j\omega}) \\ H(e^{j\omega}) = \frac{Y(e^{j\omega})}{X(e^{j\omega})} &= \frac{1}{1 - 0.5\,e^{-j\omega}} \end{aligned}$$

Writing $e^{-j\omega} = \cos\omega - j\sin\omega$, the denominator is $(1 - 0.5\cos\omega) + j\,0.5\sin\omega$.

Magnitude response:

$$|H(e^{j\omega})| = \frac{1}{\sqrt{(1-0.5\cos\omega)^2 + (0.5\sin\omega)^2}} = \frac{1}{\sqrt{1.25 - \cos\omega}}$$

Phase response:

$$\angle H(e^{j\omega}) = -\tan^{-1}\left(\frac{0.5\sin\omega}{1 - 0.5\cos\omega}\right)$$

The gain is largest at $\omega = 0$ and smallest at $\omega = \pi$, so the system is a low pass filter. $H(e^{j\omega})$ is periodic with period $2\pi$.

Impulse response

Using the DTFT pair $a^n u[n] \leftrightarrow \frac{1}{1 - a e^{-j\omega}}$ for $|a| < 1$, with $a = 0.5$:

$$h[n] = (0.5)^n\,u[n]$$

Check by recursion ($x[n] = \delta[n]$, $h[-1] = 0$):

This matches $(0.5)^n$. The system is causal ($h[n] = 0$ for $n < 0$), stable ($\sum|h[n]| = \frac{1}{1-0.5} = 2 < \infty$), and IIR (infinite-length $h[n]$). Note $\sum h[n] = 2 = H(e^{j0})$, as expected.

A system is linear if it obeys superposition: $a_1x_1[n] + a_2x_2[n] \rightarrow a_1y_1[n] + a_2y_2[n]$.

Given: $y[n] = a\,x[n] + b$

Individual outputs: $y_1[n] = a\,x_1[n] + b$ and $y_2[n] = a\,x_2[n] + b$.

Weighted sum of outputs:

$$a_1y_1[n] + a_2y_2[n] = a\left(a_1x_1[n] + a_2x_2[n]\right) + (a_1 + a_2)\,b$$

Output for the combined input $x_3[n] = a_1x_1[n] + a_2x_2[n]$:

$$y_3[n] = a\left(a_1x_1[n] + a_2x_2[n]\right) + b$$

These are equal only if $(a_1 + a_2)b = b$ for all $a_1, a_2$, i.e. only if $b = 0$.

Zero-input check: $x[n] = 0$ gives $y[n] = b$. A linear system must give zero output for zero input.

Conclusion:

• For $b \ne 0$ the system is non-linear. It is incrementally linear: the difference between two outputs, $y_1 - y_2 = a(x_1 - x_2)$, is linear in the difference of inputs. It can be seen as a linear system $a\,x[n]$ plus a fixed zero-input response $b$.
• For $b = 0$, $y[n] = a\,x[n]$ is linear.

An LTI system is causal if and only if its impulse response is zero for negative time:

$$h[n] = 0 \quad \text{for } n < 0 \qquad \left(\text{CT: } h(t) = 0 \text{ for } t < 0\right)$$

Reason: the output of a DT LTI system is the convolution sum

$$y[n] = \sum_{k=-\infty}^{\infty} h[k]\,x[n-k] = \underbrace{\sum_{k=-\infty}^{-1} h[k]\,x[n-k]}_{\text{future inputs}} + \underbrace{\sum_{k=0}^{\infty} h[k]\,x[n-k]}_{\text{present and past}}$$

For $k < 0$, $x[n-k]$ is an input at a time later than $n$ (a future value). A causal system's output cannot depend on future inputs, so every weight $h[k]$ for $k < 0$ must be zero. Then

$$y[n] = \sum_{k=0}^{\infty} h[k]\,x[n-k] = \sum_{k=-\infty}^{n} x[k]\,h[n-k]$$

Physically: $h[n]$ is the response to $\delta[n]$ applied at $n = 0$, and a causal system cannot respond before the input arrives.

Examples:

• $h[n] = (0.5)^n u[n]$: causal.
• $h[n] = u[n] - u[n-4]$: causal.
• $h[n] = \delta[n+1] + \delta[n]$, i.e. $y[n] = x[n+1] + x[n]$: non-causal (uses the future input $x[n+1]$).
• $h[n] = (0.5)^{|n|}$: non-causal.

Related terms: a sequence that is zero for $n < 0$ is called a causal sequence. If $h[n] = 0$ for $n > 0$ instead, the system is anti-causal. Causality is needed for real-time operation; non-causal systems can still be used for stored data (e.g. image processing).

A system is time invariant if delaying the input by $k$ only delays the output by $k$: $x[n-k] \rightarrow y[n-k]$.

Given: $y[n] = n\,x[n] - x[n-1]$

Step 1 – Output for the delayed input $x_1[n] = x[n-k]$ (replace $x$ only, not the $n$ multiplying it):

$$y_1[n] = n\,x[n-k] - x[n-1-k]$$

Step 2 – Delayed output (replace every $n$ by $n-k$):

$$y[n-k] = (n-k)\,x[n-k] - x[n-k-1]$$

Step 3 – Compare:

$$y_1[n] - y[n-k] = n\,x[n-k] - (n-k)\,x[n-k] = k\,x[n-k] \ne 0$$

Since $y_1[n] \ne y[n-k]$ (for $k \ne 0$), the system is time variant.

Reason: the coefficient $n$ multiplying $x[n]$ changes with time, so the system's gain is different at different instants. The second term $-x[n-1]$ alone is time invariant, but the first term makes the whole system time variant.

Numerical check: take $x[n] = \delta[n]$: $y[n] = 0\cdot\delta[n] - \delta[n-1] = -\delta[n-1]$. For $x[n] = \delta[n-1]$: $y_1[n] = n\,\delta[n-1] - \delta[n-2] = \delta[n-1] - \delta[n-2]$, which is not $y[n-1] = -\delta[n-2]$.

Convolution

Convolution is the operation that gives the output of an LTI system from its input and its impulse response. For discrete time, the output is a weighted sum of the present and past (and possibly future) inputs, with the impulse response values as weights:

$$y[n] = x[n] * h[n]$$

Here $h[n]$ is the impulse response, the output when the input is the unit impulse $\delta[n]$.

Expression for the convolution sum

Step 1: Represent the input with impulses. Using the sifting property, any sequence is a sum of scaled, shifted impulses:

$$x[n] = \sum_{k=-\infty}^{\infty} x[k]\,\delta[n-k]$$

e.g. $\{\underset{\uparrow}{3}, 1\} = 3\delta[n] + \delta[n-1]$.

Step 2: Response to one impulse. By definition $\delta[n] \rightarrow h[n]$.

Step 3: Time invariance. $\delta[n-k] \rightarrow h[n-k]$.

Step 4: Homogeneity. $x[k]\,\delta[n-k] \rightarrow x[k]\,h[n-k]$ ($x[k]$ is a constant for each $k$).

Step 5: Additivity. The output for the sum of all these inputs is the sum of their outputs:

$$y[n] = \sum_{k=-\infty}^{\infty} x[k]\,h[n-k]$$

This is the convolution sum. With $m = n - k$ it can also be written $y[n] = \sum_{k} h[k]\,x[n-k]$ (commutative property).

For a causal system with a causal input: $y[n] = \sum_{k=0}^{n} x[k]\,h[n-k]$.

Steps to evaluate: fold $h[k] \rightarrow h[-k]$; shift to $h[n-k]$; multiply with $x[k]$; add all products; repeat for each $n$. If the lengths are $N_1$ and $N_2$, the output length is $N_1 + N_2 - 1$, starting at (start of $x$) + (start of $h$).

Example: $x[n] = \{\underset{\uparrow}{1}, 1\}$, $h[n] = \{\underset{\uparrow}{2}, 3\}$:

• $y[0] = 1\cdot2 = 2$
• $y[1] = 1\cdot3 + 1\cdot2 = 5$
• $y[2] = 1\cdot3 = 3$

So $y[n] = \{\underset{\uparrow}{2}, 5, 3\}$.

Given: $y[n] - \frac{3}{4}y[n-1] + \frac{1}{8}y[n-2] = 2x[n]$, system initially at rest.

Step 1: Frequency response

Take the DTFT ($x[n-k] \leftrightarrow e^{-j\omega k}X(e^{j\omega})$):

$$\left(1 - \tfrac{3}{4}e^{-j\omega} + \tfrac{1}{8}e^{-j2\omega}\right)Y(e^{j\omega}) = 2X(e^{j\omega})$$ $$H(e^{j\omega}) = \frac{2}{1 - \frac{3}{4}e^{-j\omega} + \frac{1}{8}e^{-j2\omega}}$$

Step 2: Factorise the denominator

Let $v = e^{-j\omega}$. The roots of $1 - \frac{3}{4}v + \frac{1}{8}v^2$ come from $p^2 - \frac{3}{4}p + \frac{1}{8} = 0$, giving $p = \frac{1}{2}, \frac{1}{4}$. So

$$H(e^{j\omega}) = \frac{2}{\left(1 - \frac{1}{2}e^{-j\omega}\right)\left(1 - \frac{1}{4}e^{-j\omega}\right)}$$

Step 3: Partial fractions

$$H = \frac{A}{1 - \frac{1}{2}v} + \frac{B}{1 - \frac{1}{4}v}$$ $$\begin{aligned} A &= \left.\frac{2}{1 - \frac{1}{4}v}\right|_{v=2} = \frac{2}{1 - \frac{1}{2}} = 4 \\ B &= \left.\frac{2}{1 - \frac{1}{2}v}\right|_{v=4} = \frac{2}{1 - 2} = -2 \end{aligned}$$ $$H(e^{j\omega}) = \frac{4}{1 - \frac{1}{2}e^{-j\omega}} - \frac{2}{1 - \frac{1}{4}e^{-j\omega}}$$

Step 4: Inverse DTFT

Using $a^n u[n] \leftrightarrow \frac{1}{1 - a e^{-j\omega}}$ ($|a| < 1$):

$$h[n] = \left[4\left(\tfrac{1}{2}\right)^n - 2\left(\tfrac{1}{4}\right)^n\right]u[n]$$

Check by recursion

$h[n] = 2\delta[n] + \frac{3}{4}h[n-1] - \frac{1}{8}h[n-2]$, with $h[-1] = h[-2] = 0$:

Both agree. Both poles ($0.5$, $0.25$) are inside the unit circle, so the system is causal and stable; $h[n]$ decays to zero. Also $H(e^{j0}) = \frac{2}{1 - 0.75 + 0.125} = 5.333 = \sum h[n] = \frac{4}{0.5} - \frac{2}{0.75}$.

Answer: $h[n] = \left[4(0.5)^n - 2(0.25)^n\right]u[n]$

Given: $y[n] = 0.5\,y[n-1] + x[n]$, initially at rest.

Frequency response

DTFT of both sides:

$$\begin{aligned} Y(e^{j\omega})\left(1 - 0.5e^{-j\omega}\right) &= X(e^{j\omega}) \\ H(e^{j\omega}) &= \frac{1}{1 - 0.5e^{-j\omega}} = \frac{1}{(1 - 0.5\cos\omega) + j0.5\sin\omega} \end{aligned}$$

Magnitude:

$$|H(e^{j\omega})| = \frac{1}{\sqrt{(1 - 0.5\cos\omega)^2 + 0.25\sin^2\omega}} = \frac{1}{\sqrt{1.25 - \cos\omega}}$$

Phase:

$$\theta(\omega) = -\tan^{-1}\frac{0.5\sin\omega}{1 - 0.5\cos\omega}$$

Magnitude plot

 |H|
 2.0 |          *
     |        .' '.
 1.36|      *       *
     |    .'         '.
 0.89|  *               *
 0.67|*                   *
     +--+---+---+---+---+--> w
     -pi   -pi/2  0  pi/2  pi

The magnitude is even in $\omega$, has its maximum 2 at $\omega = 0$ and its minimum $2/3$ at $\omega = \pm\pi$, and repeats every $2\pi$. So the system is a low pass filter. The phase is odd in $\omega$ (maximum lag 30° at $\omega = \pm\pi/3$).

Impulse response

Using $a^n u[n] \leftrightarrow \frac{1}{1 - ae^{-j\omega}}$ with $a = 0.5$:

$$h[n] = (0.5)^n\,u[n]$$

 h[n]
 1.0 |   o
     |   |
 0.5 |   |  o
0.25 |   |  |  o
     |   |  |  |  o  o  .
   0 +-o-+--+--+--+--+--+--> n
      -1  0  1  2  3  4  5

The system is causal, stable ($\sum h[n] = 2$) and IIR.

Given: $y[n] = 0.5\,x[n] - 0.5\,x[n-1]$, so $h[n] = 0.5\,\delta[n] - 0.5\,\delta[n-1] = \{\underset{\uparrow}{0.5}, -0.5\}$ (a two-tap FIR system: a scaled first difference).

Frequency response

$$H(e^{j\omega}) = \sum_n h[n]e^{-j\omega n} = 0.5 - 0.5e^{-j\omega}$$

Factor out $e^{-j\omega/2}$:

$$\begin{aligned} H(e^{j\omega}) &= 0.5\,e^{-j\omega/2}\left(e^{j\omega/2} - e^{-j\omega/2}\right) \\ &= 0.5\,e^{-j\omega/2}\,(2j\sin\tfrac{\omega}{2}) \\ &= j\sin\left(\tfrac{\omega}{2}\right)e^{-j\omega/2} = \sin\left(\tfrac{\omega}{2}\right)e^{j\left(\frac{\pi}{2} - \frac{\omega}{2}\right)} \end{aligned}$$

Magnitude: $|H(e^{j\omega})| = \left|\sin\frac{\omega}{2}\right|$

Phase: $\theta(\omega) = \frac{\pi}{2} - \frac{\omega}{2}$ for $0 < \omega < \pi$ (and $-\frac{\pi}{2} - \frac{\omega}{2}$ for $-\pi < \omega < 0$): linear phase apart from the $\pi/2$ jump.

 |H|
  1 |*                   *
    | '.               .'
0.7 |   *             *
    |     '.       .'
  0 +--------'-*-'--------> w
   -pi         0         pi

Interpretation: DC ($\omega = 0$) is blocked completely and the highest frequency ($\omega = \pi$) passes with gain 1, so this is a simple high pass filter (a difference/differentiator-like system). Being FIR, it is always stable.

No origin is marked, so take the first sample of each sequence at $n = 0$: $x[n] = \{\underset{\uparrow}{1}, 2, 0, -1\}$ for $0 \le n \le 3$ and $h[n] = \{\underset{\uparrow}{2}, 0, 2\}$ for $0 \le n \le 2$.

Convolution sum:

$$y[n] = \sum_{k} x[k]\,h[n-k]$$

Output range: starts at $0 + 0 = 0$; length $= 4 + 3 - 1 = 6$, so $0 \le n \le 5$.

Tabular method

Each row is one input sample times the shifted $h[n]$; add the columns:

Check by direct calculation

• $y[0] = x[0]h[0] = 1\times2 = 2$
• $y[1] = x[0]h[1] + x[1]h[0] = 0 + 4 = 4$
• $y[2] = x[0]h[2] + x[1]h[1] + x[2]h[0] = 2 + 0 + 0 = 2$
• $y[3] = x[1]h[2] + x[2]h[1] + x[3]h[0] = 4 + 0 - 2 = 2$
• $y[4] = x[2]h[2] + x[3]h[1] = 0 + 0 = 0$
• $y[5] = x[3]h[2] = -1\times2 = -2$

Sum check: $\sum y = (\sum x)(\sum h) = 2 \times 4 = 8$, and $2 + 4 + 2 + 2 + 0 - 2 = 8$.

Answer:

$$y[n] = \{\underset{\uparrow}{2},\ 4,\ 2,\ 2,\ 0,\ -2\}$$

i.e. $y[n] = 2\delta[n] + 4\delta[n-1] + 2\delta[n-2] + 2\delta[n-3] - 2\delta[n-5]$.

(If $x$ and $h$ had different origins, the values stay the same and only the starting index shifts: start of $y$ = start of $x$ + start of $h$.)

Given:

• $x[n] = \delta[n] + 2\delta[n-1] - \delta[n-3] = \{\underset{\uparrow}{1}, 2, 0, -1\}$, for $0 \le n \le 3$.
• $h[n] = 2\delta[n+1] + 2\delta[n-1] = \{2, \underset{\uparrow}{0}, 2\}$, for $-1 \le n \le 1$.

Method 1: Using $x[n] * \delta[n-k] = x[n-k]$

Convolution with a shifted impulse just shifts the signal, and convolution is distributive:

$$\begin{aligned} y[n] &= x[n] * \left(2\delta[n+1] + 2\delta[n-1]\right) = 2x[n+1] + 2x[n-1] \end{aligned}$$ $$\begin{aligned} 2x[n+1] &= 2\delta[n+1] + 4\delta[n] - 2\delta[n-2] \\ 2x[n-1] &= 2\delta[n-1] + 4\delta[n-2] - 2\delta[n-4] \end{aligned}$$

Adding:

$$y[n] = 2\delta[n+1] + 4\delta[n] + 2\delta[n-1] + 2\delta[n-2] - 2\delta[n-4]$$

Method 2: Tabular check

Output starts at $0 + (-1) = -1$; length $4 + 3 - 1 = 6$, so $-1 \le n \le 4$.

Both methods agree. Sum check: $(\sum x)(\sum h) = 2 \times 4 = 8 = 2 + 4 + 2 + 2 + 0 - 2$.

Answer:

$$y[n] = \{2,\ \underset{\uparrow}{4},\ 2,\ 2,\ 0,\ -2\}$$

with $y[-1] = 2$, $y[0] = 4$, $y[1] = 2$, $y[2] = 2$, $y[3] = 0$, $y[4] = -2$.

 y[n]
  4 |       o
    |       |
  2 |   o   |   o   o
    |   |   |   |   |
  0 +---+---+---+---+---o---+--> n
    |  -1   0   1   2   3   4
 -2 |                       o

A discrete-time LTI system is linear and time invariant. It is completely described by its impulse response $h[n]$, and its output is the convolution sum $y[n] = \sum_k x[k]\,h[n-k] = x[n]*h[n]$. Its main properties are listed below, with the test in terms of $h[n]$.

1. Commutative property

$x[n]*h[n] = h[n]*x[n]$: input and impulse response can be interchanged. Example: $\{1,1\}*\{1,2\} = \{1,2\}*\{1,1\} = \{1,3,2\}$.

2. Associative property (cascade)

$\left(x*h_1\right)*h_2 = x*\left(h_1*h_2\right)$. Two systems in cascade equal one system with $h[n] = h_1[n]*h_2[n]$, and the order of the cascade does not matter.

x -->[h1]-->[h2]--> y  ==  x -->[h1*h2]--> y

3. Distributive property (parallel)

$x*(h_1 + h_2) = x*h_1 + x*h_2$. Two systems in parallel equal one system with $h[n] = h_1[n] + h_2[n]$.

4. Memory

The system is memoryless only if $h[n] = K\delta[n]$, i.e. $y[n] = Kx[n]$. Otherwise it has memory. Example: $h[n] = \delta[n] + \delta[n-1]$ ($y[n] = x[n] + x[n-1]$) has memory.

5. Causality

Causal if $h[n] = 0$ for $n < 0$, so the output uses no future inputs. Example: $h[n] = (0.5)^n u[n]$ is causal; $h[n] = \delta[n+1]$ ($y[n] = x[n+1]$) is not.

6. Stability (BIBO)

Stable if the impulse response is absolutely summable:

$$\sum_{n=-\infty}^{\infty} |h[n]| < \infty$$

Example: $h[n] = (0.5)^n u[n]$ gives $\sum = 2$, stable; $h[n] = u[n]$ (accumulator) gives an infinite sum, unstable. Every FIR system is stable.

7. Invertibility

Invertible if an inverse system $h_i[n]$ exists with $h[n]*h_i[n] = \delta[n]$. Example: the accumulator $h[n] = u[n]$ has inverse $h_i[n] = \delta[n] - \delta[n-1]$ (first difference).

8. Identity and unit step response

$x[n]*\delta[n] = x[n]$ and $x[n]*\delta[n-k] = x[n-k]$. The step response is the running sum of $h[n]$: $s[n] = \sum_{k=-\infty}^{n} h[k]$.

Given (origin marked):

• $x_1[n] = \{1, \underset{\uparrow}{2}, 1, -1\}$, so $x_1[-1] = 1$, $x_1[0] = 2$, $x_1[1] = 1$, $x_1[2] = -1$ ($-1 \le n \le 2$).
• $x_2[n] = \{\underset{\uparrow}{1}, 2, 3, 1\}$, so $0 \le n \le 3$.

$$y[n] = x_1[n]*x_2[n] = \sum_k x_1[k]\,x_2[n-k]$$

Output range: start $= -1 + 0 = -1$; length $= 4 + 4 - 1 = 7$; so $-1 \le n \le 5$.

Tabular method

Each row is one sample of $x_1$ times $x_2$ shifted to that sample's position:

Direct check of some values

• $y[-1] = x_1[-1]x_2[0] = 1$
• $y[0] = x_1[-1]x_2[1] + x_1[0]x_2[0] = 2 + 2 = 4$
• $y[1] = 1(3) + 2(2) + 1(1) = 8$
• $y[2] = 1(1) + 2(3) + 1(2) + (-1)(1) = 8$
• $y[3] = 2(1) + 1(3) + (-1)(2) = 3$
• $y[4] = 1(1) + (-1)(3) = -2$
• $y[5] = (-1)(1) = -1$

Sum check: $(\sum x_1)(\sum x_2) = 3 \times 7 = 21$, and $1 + 4 + 8 + 8 + 3 - 2 - 1 = 21$.

Answer:

$$y[n] = \{1,\ \underset{\uparrow}{4},\ 8,\ 8,\ 3,\ -2,\ -1\}$$

for $-1 \le n \le 5$ (the arrow marks $n = 0$, so $y[0] = 4$).