Given a discrete-time LTI system with an impulse response $h[n]$, it is a common operation to find the system's output $y[n]$ for some input $x[n]$. There are several ways this can be done, including finding the system matrix $H$ and then using it to find the output via matrix multiplication: $y=Hx$. Recalling the circulant structure of that matrix, the output can be expressed in formula form: $y[n]~=~ x[n] \circledast h[n]~=~ \sum_{m=0}^{N-1} \: h[(n-m)_N] \, x[m]$. This operation is known as
circular convolution (or
finite-length convolution ).
Computing circular convolution
The circular convolution $x[n]\circledast h[n]$ can be computed using the following seven step procedure:
--First, decide which of $x$ or $h$ you will flip and shift. Since circular convolution is commutative, either choice will result in the same output.--Second, plot the values of $x[m]$ on a circular "clock," beginning at "midnight" (for $m=0$), and continuing clockwise for a total number of "hours" that is equal to the length of the signal.--Third, plot $h[(-m)_N]$ on another clock. This simply amounts to plotting the values, starting at midnight, in a counter-clockwise direction.For a given value of $n$, $y[n]$ will be the dot product of the two "clocks." Your original plots of $x$ and $h$ correspond to $n=0$. For $n=1$, first rotate the values of $h$ in a clockwise manner, i.e., delay them one "hour" time unit. Rotating $h$ in this way is what creates $h[(n-m)_N]$. So:
--Fourth, rotate the $h$ clock accordingly and,--Fifth, perform the inner product.
--Sixth, repeat this for $n$ ranging from $0$ to $N-1$.--Seventh, plot your final answer and do a "reality check" to see if it seems reasonable.
Let's see the circular convolution process in action. Consider the two finite-length ($N=8$) signals below:
Discrete-time finite-length signals $x[m]$ and $h[m]$. Since $N=8$, our "clock" will have have 8 "hours." We will place the "zero hour" at the top of the clock, as if it were midnight, but the starting place is arbitrary, so long as you are consistent (you can also choose to have your time run counter-clockwise, if you prefer).
For the purposes of computing circular convolution by hand, the values of the signals may be plotted on a "clock" with a number of hours equal to the length of the signals. The time values progress clockwise.
The second step is to plot $x[m]$ and $h[(-m)_8]$. For $x$, this means starting at the zero our and then writing the values clockwise. For $h$, this means starting at zero and then writing the values counter-clockwise:
The values of $x[m]$ are plotted clockwise, starting at "midnight."To plot $h[(-m)_8]$, the values of $h[m]$ are simply plotted counter-clockwise, i.e., backwards in time, starting at "midnight."Plots of $x[m]$ and $h[(n-m)_8]$.
Having plotted $x[m]$ and $h[(-m)_8]$, we can now begin to find our output values corresponding to each $n$. We'll start with $n=0$, which for $h[(n-m)_8]$ is of course what we have originally plotted:
The plot of $x[m]$ will remain constant for each of the inner products.The to plot $h[(n-m)_8]$, the $h[(-m)_8]$ signal is rotated $n$ "hour" time units clockwise. Here it is plotted for $n=0$.Plots of $x[m]$ and $h[(0-m)_8]$, the inner products of which is $y[0]$. We'll move around clockwise, starting at zero hour, to find the inner product. The value of the inner product for $n=0$ is $y[0]=1\cdot 0 +0\cdot 0+ -1\cdot0 +0 \cdot 0+1\cdot 4 +0\cdot 3 + -1 \cdot 2 + 0 \cdot 1=4-2=2$.
Now, for each successive value of $n$, starting with $n=1$ and going up to $n=7$, we will rotate the $h$ plot clockwise an "hour," and then find the inner product with the (unchanged) $x$.
$x[m]$ and $h[(n-m)_8]$ for $n=1$. The value of the inner product for $n=1$ is $y[1]=1\cdot 1 +0\cdot 0+ -1\cdot0 +0 \cdot0+1\cdot 0 +0\cdot 4 + -1 \cdot 3 + 0 \cdot 2=1-3=-2$.
Below are the plots for $n=2$. $x$ remains unchanged, and $h$ is shifted one hour clockwise from where it was at $n=1$:
$x[m]$ and $h[(n-m)_8]$ for $n=2$.
Now for $n=3$:
$x[m]$ and $h[(n-m)_8]$ for $n=3$. The value of the inner product for $n=3$ is $y[3]=1\cdot 3 +0\cdot 2+ -1\cdot 1 +0 \cdot 0+1\cdot 0 +0\cdot 0 + -1 \cdot 0 + 0 \cdot 4=3-1=2$.
Next, $n=4:
$x[m]$ and $h[(n-m)_8]$ for $n=4$. The value of the inner product for $n=4$ is $y[4]=1\cdot 4 +0\cdot 3+ -1\cdot 2 +0 \cdot 1+1\cdot 0 +0\cdot 0 + -1 \cdot 0 + 0 \cdot 0=4-2=2$.
$n=5$:
$x[m]$ and $h[(n-m)_8]$ for $n=5$. The value of the inner product for $n=5$ is $y[5]=1\cdot 0 +0\cdot 4+ -1\cdot 3 +0 \cdot 2+1\cdot 1 +0\cdot 0 + -1 \cdot 0 + 0 \cdot 0=-3+1=-2$.
$n=6$:
$x[m]$ and $h[(n-m)_8]$ for $n=6$. The value of the inner product for $n=6$ is $y[6]=1\cdot 0 +0\cdot 0+ -1\cdot 4 +0 \cdot 3+1\cdot 2 +0\cdot 1 + -1 \cdot 0 + 0 \cdot 0=-4+2=-2$.
And finally, $n=7$:
$x[m]$ and $h[(n-m)_8]$ for $n=7$. The value of the inner product for $n=7$ is $y[7]=1\cdot 0 +0\cdot 0+ -1\cdot 0 +0 \cdot 4+1\cdot 3 +0\cdot 2 + -1 \cdot 1 + 0 \cdot 0=3-1=2$. Now that we have found the output for each $n$ from $0$ to $7$, we may plot $y[n]$
The final plot of $y[n]$.
