4.7 Digital signal processing

Big idea

A digital signal is a list of numbers indexed by time: a sample every so often, running forward and backward as far as you like. Two signals add sample by sample, and a signal scales by multiplying every sample. Those are the vector space operations, so the set of signals is a vector space and everything from this chapter applies to it.

A filter takes a signal in and gives a signal out. The useful ones are local and repetitive: each output sample is a fixed weighted sum of a few nearby input samples, with the same weights used at every time. Smoothing a noisy reading by averaging neighbours is a filter. Taking successive differences to expose a change is a filter. Delaying a signal by one sample is a filter.

Every filter of that shape is a linear transformation, and on a finite stretch of samples it is a matrix. The weights appear as a band sliding down the rows, one step to the right each time. So “apply the filter” becomes “multiply by this matrix”, and the questions of the chapter become available: what does the filter destroy, which outputs can it produce, and can it be undone.

Decoder

A linear filter produces each output sample as a fixed linear combination of a window of input samples, with the same coefficients used at every index.

Two words carry the content. “Window” means the output at time $k$ looks only at input samples near time $k$, never at the whole signal. “Fixed” means the coefficients do not change as $k$ advances; the filter treats every moment the same way.

Together they force the matrix shape. Because the window is short, most entries of each row are zero. Because the coefficients are fixed, every row is the same pattern of numbers shifted one place right. A matrix like that is called banded, and it is the reason filtering a long signal is cheap.

Definitions and results

The space of signals. A discrete-time signal is a doubly infinite sequence of real numbers, one for each integer index. Write $\{x_k\}$ for a signal and $x_k$ for its sample at time $k$. Add two signals sample by sample and scale a signal by scaling every sample. With those operations the set of all signals is a vector space, and the zero signal has every sample $0$.

Finite signals. A signal recorded over $n$ sampling times is a vector in $\mathbb{R}^n$. Everything below is stated for a finite record, which is what a computer actually holds, and the matrix descriptions apply there.

Linear filter. Fix coefficients $a_0, a_1, \dots, a_p$ and define the output by

$$ y_k = a_0 x_k + a_1 x_{k-1} + \cdots + a_p x_{k-p} $$

The list of coefficients is the filter. The number of them is its length, and the output at each time depends on that many consecutive inputs. The offsets may run forward instead of backward, as in $y_k = x_k + x_{k+1}$; shifting them all by the same amount only relabels which time each output is stamped with, and changes nothing about the filter.

Filters are linear. Write $T$ for the map sending $\{x_k\}$ to $\{y_k\}$. Feeding in a sum gives $a_0(u_k + v_k) + a_1(u_{k-1} + v_{k-1}) + \cdots$, which regroups into the output for $\{u_k\}$ plus the output for $\{v_k\}$. Feeding in $c\{x_k\}$ pulls $c$ out of every term. So $T$ is a linear transformation, and kernel, range, rank and nullity all mean something for it.

Matrix of a filter. On a finite record, list the outputs you can form without running off the end of the input and write them as rows. Each row holds the coefficients in consecutive positions and zeros elsewhere, and each row is the previous one shifted one column right. Applying the filter is then a matrix-vector product $\mathbf{y} = A\mathbf{x}$, and the matrix is rectangular: a filter of length $p + 1$ applied to $n$ samples produces $n - p$ full outputs.

What the kernel means. A signal in the kernel is one the filter erases. If the kernel contains only the zero signal, no information is lost on that record and the filter can in principle be undone. A nonzero kernel means two different inputs produce the same output, so the filter is not reversible.

What the range means. The range is the set of signals the filter can produce. A target output is achievable exactly when it lies in the column space of the filter matrix, which is the consistency question for $A\mathbf{x} = \mathbf{y}$.

Composing filters. Applying one filter and then another is the composition of two linear transformations, so it is again linear and its matrix is the product of the two matrices, in the order the signals travel. Filters built this way are still filters, with a longer window.

Two families to recognise. A filter whose coefficients are all positive and sum to one is an averager: it passes a slowly varying signal almost unchanged and shrinks rapid wiggles. A filter whose coefficients sum to zero kills constant signals: the constant signal is in its kernel, so it reports change rather than level.

Worked examples

A moving sum as a matrix

Take the filter $y_k = x_k + x_{k+1} + x_{k+2}$, a three-sample running total, applied to a record of five samples. Three full outputs fit, so the matrix is $3 \times 5$:

$$ A = \begin{bmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \end{bmatrix} $$

Each row is the previous one shifted one place right; that is the “same coefficients at every time” condition in matrix form.

Apply it to $\mathbf{x} = (2, 4, 6, 1, 3)$:

$$ A\mathbf{x} = \begin{bmatrix} 2 + 4 + 6 \\ 4 + 6 + 1 \\ 6 + 1 + 3 \end{bmatrix} = \begin{bmatrix} 12 \\ 11 \\ 10 \end{bmatrix} $$

Check the third entry against the definition: $y$ at the last usable time is $x_3 + x_4 + x_5 = 6 + 1 + 3 = 10$, matching. The input swung between $1$ and $6$; the output sits between $10$ and $12$, which is the smoothing the filter was built to do.

A difference filter and the signals it erases

Take $y_k = x_{k+1} - x_k$ on a record of four samples. Three outputs fit, so the matrix is $3 \times 4$:

$$ D = \begin{bmatrix} -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ 0 & 0 & -1 & 1 \end{bmatrix} $$

Apply it to $\mathbf{x} = (3, 3, 7, 2)$:

$$ D\mathbf{x} = \begin{bmatrix} 3 - 3 \\ 7 - 3 \\ 2 - 7 \end{bmatrix} = \begin{bmatrix} 0 \\ 4 \\ -5 \end{bmatrix} $$

The output is zero where the signal held steady and large where it jumped, which is what a difference filter is for.

Now find the kernel. The coefficients $-1$ and $1$ sum to zero, so any constant signal should be erased. Check: $D(1,1,1,1) = (1 - 1,\; 1 - 1,\; 1 - 1) = (0, 0, 0)$. Conversely, $D\mathbf{x} = \mathbf{0}$ forces $x_2 = x_1$, $x_3 = x_2$, $x_4 = x_3$, so every kernel member is constant. The kernel is $\text{Span}\{(1,1,1,1)\}$, of dimension one.

Read off the rank from that. The matrix has four columns and nullity one, so its rank is $4 - 1 = 3$. Three pivots in three rows means the range is all of $\mathbb{R}^3$: every three-sample output is achievable. What you cannot recover is the overall level of the input, which is exactly the information the kernel represents.

A weighted smoother on a ramp

Take the filter with coefficients $1, 2, 1$, so $y_k = x_{k-1} + 2x_k + x_{k+1}$, on five samples. Its matrix is

$$ W = \begin{bmatrix} 1 & 2 & 1 & 0 & 0 \\ 0 & 1 & 2 & 1 & 0 \\ 0 & 0 & 1 & 2 & 1 \end{bmatrix} $$

Apply it to the ramp $\mathbf{x} = (1, 2, 3, 4, 5)$:

$$ W\mathbf{x} = \begin{bmatrix} 1 + 4 + 3 \\ 2 + 6 + 4 \\ 3 + 8 + 5 \end{bmatrix} = \begin{bmatrix} 8 \\ 12 \\ 16 \end{bmatrix} $$

Check what happened. The coefficients sum to $4$, and the output values $8$, $12$, $16$ are exactly $4$ times the middle input sample in each window, which was $2$, $3$, $4$. A straight-line signal comes out as the same straight line scaled by the coefficient sum, so this filter passes a trend untouched apart from a known gain.

Test the linearity claim on this matrix rather than trusting it. Take $\mathbf{u} = (1,0,0,0,0)$ and $\mathbf{v} = (0,1,0,0,0)$. Then $W\mathbf{u} = (1,0,0)$ and $W\mathbf{v} = (2,1,0)$, and $W(\mathbf{u} + \mathbf{v}) = W(1,1,0,0,0) = (1 + 2,\; 0 + 1,\; 0) = (3, 1, 0)$, which is the sum of the two outputs. Scaling behaves the same way, since $W(3\mathbf{u}) = (3, 0, 0)$.

Practice

First the mechanics: apply a filter matrix to a signal, and build the matrix from stated coefficients.

Then the structural questions: check that a stated rule is linear, and find what a filter erases.

Quiz

Five items on filter matrices, filtered outputs, and linearity.