LTI Convolution Representation

Given a discrete-time input signal $x (n)$ , the output of a discrete-time LTI system $y (n)$ can be represented as a weighted combination of impulse responses $h [n]$ , such that
$y (n) = x (n) * h (n) = \sum_{k = - \infty}^{\infty} x (k) h (n - k) = \sum_{k = - \infty}^{\infty} x (n - k) h (k) .$
Similarly, given a continuous-time input signal $x (t)$ , the output of a continuous-time LTI system $y (t)$ can be represented as
$y (t) = x (t) * h (t) = \int_{- \infty}^{\infty} x (τ) h (t - τ) d τ = \int_{- \infty}^{\infty} x (t - τ) h (τ) d τ .$

Intuition

Properties

(Polynomialization) If for the polynomials $\overset{y}{^} (z) = \overset{x}{^} (z) \hat{h} (z)$ , then $y_{k} = (h * x)_{k}$ where $\overset{y}{^} (z) = \sum_{k = - \infty}^{\infty} y_{k} z^{k}$ .

We start by expanding with the fact that $\overset{y}{^} (z) = \sum_{i = - \infty}^{\infty} \sum_{j = - \infty}^{\infty} (x_{i} z^{i}) (h_{j} z^{j})$ . We can perform a change of variables for $k = i + j$ , such that
$\overset{y}{^} (z) = \sum_{k = - \infty}^{\infty} \sum_{j = - \infty}^{\infty} x_{k} h_{k - i} z^{k} .$
By definition, $\overset{y}{^} (z) = \sum_{k = - \infty}^{\infty} y_{k} z^{k}$ , and therefore $y_{k} = \sum_{j = - \infty}^{\infty} y_{k} z^{k} x_{k} h_{k - i}$ .

(Multiplication in Frequency) If $y (t) = (x * h) (t)$ , then $Y (ω) = X (ω) H (ω)$ .

Examples

Simple Convolution

Consider the following signal and impulse responses:

\begin{document}
 
\begin{tikzpicture}
   % Axes
   \draw[->] (-0.5,0) -- (3,0) node[right] {$n$};
   \draw[->] (0,-0.5) -- (0,4);
   
   % x(n) signal (black)
   \draw[thick, black] (0,0) -- (0,1);
   \draw[fill=black] (0,1) circle (2pt);
   
   \draw[thick, black] (1,0) -- (1,2);
   \draw[fill=black] (1,2) circle (2pt);
   
   \draw[thick, black] (2,0) -- (2,3);
   \draw[fill=black] (2,3) circle (2pt);
   
   % h(n) signal (red)
   \draw[thick, red] (0,0) -- (0,1);
   \draw[fill=red] (0,1) circle (2pt);
   
   \draw[thick, red] (1,0) -- (1,1);
   \draw[fill=red] (1,1) circle (2pt);
   
   % Labels
   \node[below] at (0,0) {0};
   \node[below] at (1,0) {1};
   \node[below] at (2,0) {2};
   
   \node[left] at (0,1) {1};
   \node[left] at (0,2) {2};
   \node[left] at (0,3) {3};
   
   % Label x(n) and h(n)
   \node[black, above] at (2.5,3) {$x(n)$};
   \node[red, above] at (1.5,1) {$h(n)$};
   
\end{tikzpicture}
 
\end{document}

We can express the convolution of these two signals using the three methods below.

Echo Method (Input Perspective) $y [n]$ as a sum of all the nonzero values of $x$ , such that, per the formula, $y [n] = x [0] h [n] + x [1] h [n - 1] + x [2] h [n - 2] = h [n] + 2 h [n - 1] + 3 h [n - 2] .$ Graphically, this can be expressed as:

The echo method expresses

\begin{document}
 
\begin{tikzpicture}[scale=0.8]  % Reduce figure size
   % Set the style for the lines and points
   \tikzstyle{stem}=[thick, black]
   \tikzstyle{dot}=[fill=black,draw=black,thick]
   
   % Column 1: Original x(n) signal plots with more vertical space and x-axis labels
   \begin{scope}
       % First graph (0, 1)
       \node at (1.5, 2) {$x(0)$};  % Label above graph
       \draw[->] (-0.5,0) -- (3,0) node[right] {$n$};
       \draw[stem] (0,0) -- (0,1);
       \fill[dot] (0,1) circle (3pt);
       \node[above] at (0,1) {1};
       \node[below] at (0,0) {0};
       \node[below] at (1,0) {1};
       \node[below] at (2,0) {2};
       
       % Second graph (1, 2)
       \begin{scope}[yshift=-5cm]  % More vertical space
       \node at (1.5, 3) {$x(1)$};  % Label above graph
       \draw[->] (-0.5,0) -- (3,0) node[right] {$n$};
       \draw[stem] (1,0) -- (1,2);
       \fill[dot] (1,2) circle (3pt);
       \node[above] at (1,2) {2};
       \node[below] at (0,0) {0};
       \node[below] at (1,0) {1};
       \node[below] at (2,0) {2};
       \end{scope}
       
       % Third graph (2, 3)
       \begin{scope}[yshift=-10cm]  % More vertical space
       \node at (1.5, 4) {$x(2)$};  % Label above graph
       \draw[->] (-0.5,0) -- (3,0) node[right] {$n$};
       \draw[stem] (2,0) -- (2,3);
       \fill[dot] (2,3) circle (3pt);
       \node[above] at (2,3) {3};
       \node[below] at (0,0) {0};
       \node[below] at (1,0) {1};
       \node[below] at (2,0) {2};
       \end{scope}
   \end{scope}
   
   % Plus signs on the left of column 1
   \node at (-1.5, -2.5) {+};
   \node at (-1.5, -7.5) {+};
 
   % Equals sign after the first column
   \node at (4.5, -5) {$\to$};
   
   % Column 2: Convolution plots with more vertical space and x-axis labels
   \begin{scope}[xshift=7.5cm]  % Added more horizontal space
       % First convolution plot (0, 1), (1, 1)
       \node at (1.5, 2) {$x(0)h(n)$};  % Label above graph
       \draw[->] (-0.5,0) -- (3,0) node[right] {$n$};
       \draw[stem] (0,0) -- (0,1);
       \fill[dot] (0,1) circle (3pt);
       \draw[stem] (1,0) -- (1,1);
       \fill[dot] (1,1) circle (3pt);
       \node[above] at (0,1) {1};
       \node[above] at (1,1) {1};
       \node[below] at (0,0) {0};
       \node[below] at (1,0) {1};
       \node[below] at (2,0) {2};
       
       % Second convolution plot (1, 2), (2, 2)
       \begin{scope}[yshift=-5cm]
       \node at (1.5, 3) {$x(1)h(n-1)$};  % Label above graph
       \draw[->] (-0.5,0) -- (3,0) node[right] {$n$};
       \draw[stem] (1,0) -- (1,2);
       \fill[dot] (1,2) circle (3pt);
       \draw[stem] (2,0) -- (2,2);
       \fill[dot] (2,2) circle (3pt);
       \node[above] at (1,2) {2};
       \node[above] at (2,2) {2};
       \node[below] at (0,0) {0};
       \node[below] at (1,0) {1};
       \node[below] at (2,0) {2};
       \end{scope}
       
       % Third convolution plot (2, 3), (3, 3)
       \begin{scope}[yshift=-10cm]
       \node at (1.5, 4) {$x(2)h(n-2)$};  % Label above graph
       \draw[->] (-0.5,0) -- (3,0) node[right] {$n$};
       \draw[stem] (2,0) -- (2,3);
       \fill[dot] (2,3) circle (3pt);
       \draw[stem] (3,0) -- (3,3);
       \fill[dot] (3,3) circle (3pt);
       \node[above] at (2,3) {3};
       \node[above] at (3,3) {3};
       \node[below] at (0,0) {0};
       \node[below] at (1,0) {1};
       \node[below] at (2,0) {2};
       \node[below] at (3,0) {3};
       \end{scope}
   \end{scope}
   
   % Plus signs on the left of column 2
   \node at (6.5, -2.5) {+};
   \node at (6.5, -7.5) {+};
   
   % Equals sign after the second column
   \node at (11.5, -5) {=};
   
   % Column 3: Final result plot centered in the middle
   \begin{scope}[xshift=12.5cm, yshift=-7.5cm]  % Centered final plot in the middle
       \node at (1.5, 6) {$y(n)$};  % Label above graph
       \draw[->] (-0.5,0) -- (4,0) node[right] {$n$};
       \draw[stem] (0,0) -- (0,1);
       \fill[dot] (0,1) circle (3pt);
       \draw[stem] (1,0) -- (1,3);
       \fill[dot] (1,3) circle (3pt);
       \draw[stem] (2,0) -- (2,5);
       \fill[dot] (2,5) circle (3pt);
       \draw[stem] (3,0) -- (3,3);
       \fill[dot] (3,3) circle (3pt);
       \node[above] at (0,1) {1};
       \node[above] at (1,3) {3};
       \node[above] at (2,5) {5};
       \node[above] at (3,3) {3};
       \node[below] at (0,0) {0};
       \node[below] at (1,0) {1};
       \node[below] at (2,0) {2};
       \node[below] at (3,0) {3};
   \end{scope}
   
\end{tikzpicture}
 
\end{document}

Flip & Drag Method (Impulse Perspecive) $y (n) =$

The flip & drag method reverses the input. In our case,

Polynomial Multiplication Method $f (x) = 1 + 2 x + 3 x^{2}$ $g (x) = 1 + (1) x .$ Multiplying these two functions, we get $h (x) = f (x) \cdot g (x) = 1 + 3 x + 5 x^{2} + 3 x^{3},$ which is equal to the convolution of the two signals as found above.

We can convolve the two signals based on their polynomials. For our example, we have two polynomials based on the input and impulse signals:

Cascade

Suppose we have two FIR filters, $a (n)$ and $b (n)$ , such that their impulse response is given by
$a(n) &= a_0\delta(n) + a_1\delta(n-1)+ \ldots + a_N\delta(n-N) && (\text{where } N \in \mathbb{N}), \\ &\text{and} \\ b(n) &= b_0\delta(n) + b_1\delta(n-1)+ \ldots + b_M\delta(n-M) && (\text{where } M \in \mathbb{N}). \end{align}$$ The two filters are placed in a cascade $C$, such that the final system is $$x \rightarrow \boxed{\boxed{A} \rightarrow \boxed{B}}^C \rightarrow y.$$ We can find the cascade by setting $x(n) = \delta(n)$. Then, $$\begin{align} y(n) &= [(x * a) * b]. \end{align}$$ Since the impulse response of any system is its filter, we can simplify this into $$\begin{align} c(n) &= (a * b) \\ &= \sum^{\infty}_{k=-\infty} a(k)b(n-k) \\ \end{align}$$ Here, we can see that $a(k)b(n-k)$ is equal to $$a_0b_0\delta(k)\delta(n-k) + a_0b_1\delta(k)\delta(n-k-1) + a_1b_0\delta(k-1)\delta(n-k) + a_1b_1\delta(k-1)\delta(n-k-1) + \ldots,$$ and therefore $$\begin{align} c(n) &= a_0b_0\delta(n) + (a_0b_1 + a_1b_0)\delta(n-1) + (a_0b_2 + a_1b_1 + a_2b_0)\delta(n-2) + \ldots \end{align}$$ This means that we can model any coefficient $c_n$ of the cascade ($n \leq N$) as $$c_n = \sum^{n}_{k=\max(0, n - M)}a_kb_{n-k},$$ where $k=\max(0, n-M),$ as the two systems are of different sizes, and we need to account for cases where $M < N$. Finally, we can express $c$ as $$c(n) = c_0\delta(n) + c_1\delta(n-1) + \ldots + c_{N+M}\delta(n-N-M).$$$

Project Alexandria

Explorer

2.2b LTI Convolution

Intuition

Properties

(Polynomialization) If for the polynomials $\overset{y}{^} (z) = \overset{x}{^} (z) \hat{h} (z)$ , then $y_{k} = (h * x)_{k}$ where $\overset{y}{^} (z) = \sum_{k = - \infty}^{\infty} y_{k} z^{k}$ .

(Multiplication in Frequency) If $y (t) = (x * h) (t)$ , then $Y (ω) = X (ω) H (ω)$ .

Examples

Graph View

Table of Contents

Backlinks

Project Alexandria

Explorer

2.2b LTI Convolution

Intuition

Properties

(Polynomialization) If for the polynomials y^​(z)=x^(z)h^(z), then yk​=(h∗x)k​ where y^​(z)=∑k=−∞∞​yk​zk.

(Multiplication in Frequency) If y(t)=(x∗h)(t), then Y(ω)=X(ω)H(ω).

Examples

Graph View

Table of Contents

Backlinks

(Polynomialization) If for the polynomials $\overset{y}{^} (z) = \overset{x}{^} (z) \hat{h} (z)$ , then $y_{k} = (h * x)_{k}$ where $\overset{y}{^} (z) = \sum_{k = - \infty}^{\infty} y_{k} z^{k}$ .

(Multiplication in Frequency) If $y (t) = (x * h) (t)$ , then $Y (ω) = X (ω) H (ω)$ .