5.1: Comparing systems as interacting signal processors

Cyber-physical systems are systems that involve tightly interacting physical and computational parts. An example is an autonomous car: sensors inform a decision system that controls a steering unit that drives a car, whose movement changes the sensory input. While such systems involve complex interactions of many different subsystems— both physical ones, such as the driving of a wheel by a motor, or a voltage placed across a wire, and computational ones, such as a program that takes a measured velocity and returns a desired acceleration—it is often useful to model the system behavior as simply the passing around and processing of signals. For this illustrative sketch, we will just think of signals as things which we can add and multiply, such as real numbers.

Interaction in cyber-physical systems can often be understood as variable sharing; i.e. when two systems are linked, certain variables become shared. For example, when we connect two train carriages by a physical coupling, the train carriages must have the same velocity, and their positions differ by a constant. Similarly, when we connect two electrical ports, the electric potentials at these two ports now must be the same, and the current flowing into one must equal the current flowing out of the other. Of course, the way the shared variable is actually used may be very different for the different subsystems using it, but sharing the variable serves to couple those systems nonetheless.

Note that both the above examples involve the physical joining of two systems; more figuratively, we might express the interconnection by drawing a line connecting the boxes that represent the systems. In its simplest form, this is captured by the formalism of signal flow graphs, due to Claude Shannon in the 1940s. Here is an example of a signal flow graph:

We consider the dangling wires on the left as inputs, and those on the right as outputs. In Eq. (5.1) we see three types of signal processing units, which we interpret as follows:

• Each unit labelled by a number a takes an input and multiplies it by a.
• Each black dot takes an input and produces two copies of it.
• Each white dot takes two inputs and produces their sum.

Thus the above signal flow graph takes in two input signals, say x (on the upper left wire) and y (on the lower left wire), and—going from left to right as described above produces two output signals: u = 15x (upper right) and v = 3x + 21y (lower right). Let’s show some steps from this computation (leaving others off to avoid clutter):

In words, the signal flow graph first multiplies y by 7, then splits x into two copies, adds the second copy of x to the lower signal to get x + 7y, and so on.

A signal flow graph might describe an existing system, or it might specify a system to be built. In either case, it is important to be able to analyze these diagrams to understand how the composite system converts inputs to outputs. This is reminiscent of a co-design problem from Chapter 4, which asks how to evaluate the composite feasibility relation from a diagram of simpler feasibility relations. We can use this process of evaluation to determine whether two different signal flow graphs in fact specify the same composite system, and hence to validate that a system meets a given specification.

In this chapter, however, we introduce categorical tools—props and their presentations for reasoning more directly with the diagrams. Recall from Chapter 2 that symmetric monoidal preorders are a type of symmetric monoidal category where the morphisms are constrained to be very simple: there can be at most one morphism between any two objects. Here shall see that signal flow graphs represent morphisms in a different, complementary simplification of the symmetric monoidal category concept, known as a prop.1 A prop is a symmetric monoidal category where the objects are constrained to be very simple: they are generated, using the monoidal product, by just a single object.

Just as the wiring diagrams for symmetric monoidal preorders did not require labels on the boxes, this means that wiring diagrams for props do not require labels on the wires. This makes props particularly suited for describing diagrammatic formalisms such as signal flow graphs, which only have wires of a single type.

Finally, many systems behave in what is called a linear way, and linear systems form a foundational part of control theory, a branch of engineering that works on cyber-physical systems. Similarly, linear algebra is a foundational part of modern mathematics, both pure and applied, which includes not only control theory, but also the practice of computing, physics, statistics, and many others. As we analyze signal flow graphs, we shall see that they are in fact a way of recasting linear algebra—more specifically, matrix operations—in graphical terms. More formally, we shall say that signal flow graphs have functorial semantics as matrices.