The present paper can be seen as an exercise in the author's stream calculus [Rut01] and gives a new proof for an existing result about stream circuits. Such circuits are also known under the name of signal flow graphs, and are built from (scalar) multipliers, copiers (fan-out), adders (element-wise sum), and registers (here: one-element memory cells, aka delays). Because of the presence of memory, the input-output behaviour of these circuits is best described in terms of functions from streams to streams (of real numbers). The main statement of this paper (Theorem 6), gives a characterization of the input-output behaviour of finite stream circuits in terms of so-called rational streams. It is well-known in the world of signal processing, where it is formulated and proved in terms of the Z-transform (a discrete version of the Laplace transform) and transfer functions (see for instance [Lah98, p.6941). These transforms are used as representations of streams of (real or complex) numbers. As a consequence, one has to deal with two different worlds, and some care is required when moving from the one to the other. In contrast, we use stream calculus to formulate and obtain essentially the same result. What is somewhat different and new here is that we use only streams and nothing else. In particular, expressions for streams such as 1 (1-X) 2  = (1, 2, 3,...), are not mere representations but should be read as formal identities. Technically, the formalism of stream calculus is simple, because it uses the constant stream X = (0,1,0,0,0,...) as were it a formal variable (cf. work on formal power series such as [BR88]). We find it worthwhile to present this elementary treatment of signal flow graphs for a number of reasons: - It explains in very basic terms two fundamental phenomena in the theory of computation: memory (in the form of register or delay elements) and infinite behaviour (in the form of feedback). - Although Theorem 6 is well-known to electrical engineers, computer scientists do not seem to know it. Also, the result as such is not so easy to isolate in the relevant literature on (discrete-time, linear) system theory. Although not worked out here, there is a very close connection between Theorem 6, and a well-known result from theoretical computer science: Kleene's theorem on rational (regular) languages and deterministic finite state automata. The present methodology is relevant for the area of component-based software engineering: it has recently been generalised to model software composition by means of so-called component connectors, in terms of relations on the streams of ingoing and outgoing messages (or data elements) at the various communication ports [AR03]. A similar remark applies to our ongoing work on stream-based models of sequential digital circuits.
['Jan Rutten']
An application of stream calculus to signal flow graphs