DSP 1: The absolute fundamentals

In this short note, I recap the absolute minimum understanding to work with discrete-time signals and systems. These are by no mean complete, and might not be completely technically correct, as sometimes it’s easier to state a less precise statement for the sake of clarity. Now, for a very nice course on this topic have a look at [this MIT open courseware][1] or this [coursera course from EPFL][coursera]

Discrete-time signal

A discrete-time signal \(x[n]\) is essentially an array of floats. Though if you are familiar with thinking an array starts from 0, it’s important to notice that in DSP, a signal is consider from time negative infinity to infinity. That is

\[x[n], \text{where } -\infty < n < \infty.\]

Linear time-invariant discrete-time system

A discrete-time system is an abstract mapping that map a discrete-time signal to another, in mathematical notation we can write

\[y[n] = \mathcal{H}\{x[n]\}.\]

Most engineering marvels rest on simple, powerful mathematical structures. Linearity is perharps the most important characteristics. We restrict our attention to the class of linear discrete-time systems, which intuitively satisfies:

\[\mathcal{H}\{\alpha x[n] + \beta y[n]\} = \alpha \mathcal{H}\{x[n]\} + \beta \mathcal{H}\{y[n]\}\]

We even restrict further to time-invariant systems, which satisfies:

\[\mathcal{H}\{x[n - k]\} = y[n - k] \]

Convolution Operation and the Impulse Response

These previous two assumptions might seem to be relatively abstract. Though, the consequences of these two points are really cool! Now, recall that the impulse \(\delta[n]\) is filled with zero except at \(n=0\), the impulse response of a system is the output of the system given a impulse input. For Linear Time-Invariant (LTI) system, it is known that the output of a system given arbitrary input is the convolution of its impulse response with the given input, that is:

\[ y[n] = \mathcal{H}\{x[n]\} = \mathcal{H}\{\delta[n]\} * x[n] = h[n] * x[n] \]

This consequence has massive application. For instance, we can now represent arbitrary filter by an impulse response, then apply the convolution operation on the input signal to compute the output signal. In particular,

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

Notice that for all non-negative \(k\), \(x[n-k]\) is “in the past” and can be used. In fact, Finite Impulse Response filter is a very powerful concept that makes use of this exact property. In my own research, I have designed controller for discrete-time system by design the filter’s impulse response too.

The easiest way to implement a discrete-time system is to transform it into state-space form. Consider a filter that maps \(u[n]\) into an output signal \(y[n]\), there exist, potentially many, state space systems that realize the filter’s behavior:

\begin{align} x[n + 1] &= A x[n] + B u[n], \\\
y[n] &= C x[n] + D u[n]. \end{align}

where \(A,B,C,D\) are matrices.

In fact, the input and output signals are limitted to being scalar. Thus we can even combine several filters into a single state-space system, which greatly simplify the implementation. Indeed, we have a simple implementation below:

class StateSpaceController:
    """A statespace controller."""
    def __call__(self, u):
	xnext = np.dot(self.A, self.x) + np.dot(self.B, u)
	y     = np.dot(self.C, self.x) + np.dot(self.D, u)
	self.x = xnext
	return y

The difficult thing in working with discrete-time systems is usually deriving the coefficient matrices. For that, it’s useful to remember the following rules.

If these steps work for you, that’s great! Though sometimes it doesn’t. When this happens, I guess you just have to sit down and understand the math and try to resolve it. For example, [python-control] is unable to realize the state-space form of very long FIR filter without causing numerical issues.

Conclusion

This barely scratches the fundamental of Digital Signal Processing. There are many other potential venues to explore further. As examples, we could explore the z-transform, then go to the z-transform of Linear Constant Coefficient filters. From this we can go to the state-space representation of such filter, which is very useful for either analysis, design or simulation. The state-space form is ideal for some optimal control such as the Linear Quadratic Regulator, or concepts such as controllability or observability. This area of engineering is full of interesting ideas.

That said, until next time!

Dsp2Systems