Finite realization of irrational transfer functions

Question

In the field of digital signal processing, linear time-invariant systems play a distinguished role. These are the systems for which there exists an impulse response, a function $h:\mathbb{Z}\to\mathbb{C}$ such that for any input $x:\mathbb{Z}\to\mathbb{C}$ the output is just the convolution $x\ast h$ given by $(x\ast h)(n) = \sum_{m=-\infty}^\infty x(n-m)h(m)$. We restrict to cases where such sums converge, e.g. square-summable sequences.

Typically we focus on causal systems, those for which $h(n)=0$ when $n<0$, so future inputs do not affect the present output. The tools for analyzing these systems are equivalent to tools used in non-engineering math, but often known by different names, e.g. $z$-transforms instead of generating functions.

There are two subclasses of causal linear time-invariant systems which are commonly implemented in practice.

1) Finite impulse response systems are those for which $h$ has finite support. Each output value is a finite linear combination of input values, which can be computed directly.

2) Infinite impulse response systems with rational transfer functions are those for which $H(z) := \sum_{-\infty}^\infty z^{-n}h(n)$ is a rational function of the complex number $z$ (and which do not have finite impulse responses). This rationality is often implicit in the phrase "infinite impulse response". The input-output relations of these systems can be expressed in terms of difference equations of finite order. These give a way of computing the present output in terms of past outputs as well as present and past inputs such that the amount of computation, the requisite memory, and the delay are all bounded.

Question: Are there other causal linear time-invariant systems which can be implemented?

I fully expect that the answer is no -- just because engineers never talk about other kinds of systems -- but I've never seen such a statement proven or even formalized. I would be happy with any "reasonable" model of computation such that the computational load of computing the output at index $n$ does not grow with $n$. In particular the number of arithmetic operations, the amount of memory needed, and the delay from the time a new input is available to the time the corresponding output is available should all be bounded independent of how much of the input sequence has been processed so far.

Schmidlin's 2013 paper Realization of Irrational Transfer Functions, from which I took the title of this question, shows an implementation for which I believe the amount of computation is quadratic in the length of the input sequence (number of nonzeros), and so violates the delay constraint imposed here.

Answer 1

There is at least one (rather trivial) way to formalize "implementability" that has the property that the only implementable functions are rational. Suppose that the implementation is defined as a continuous mapping $f:\mathbb R^{N+1}\to \mathbb R^N$ such that the last coordinate of the image of the current state concatenated with the next input produces the next output. This model makes a reasonable (IMHO) compromise between allowing the infinite computation precision and disallowing some clever encoding of the entire past into a single number. The proof of the rationality of the implementable functions is then very simple. Since there is no continuous injection from $\mathbb R^{N+1}$ to $\mathbb R^N$, there are two beginnings of length $N+1$ that result in the same state of the computer. If we continue with $0$ input after that, we will have equal outputs from there on, resulting in a finite recurrence relation for $h$.

Answer 2

Causal discrete-time signals that are linear combinations of real or complex exponentials do have rational transfer functions. However, not all causal discrete-time signals are linear combinations of real or complex exponentials.

For example, consider the causal LTI system whose (infinite) impulse response is

$$h (n) = \begin{cases} \frac{1}{1+n} & \text{ if } n \geq 0\\ \,\,\,0 & \text{ if } n < 0\end{cases}$$

Taking the Z-transform, we obtain the following non-rational transfer function

$$H (z) = \sum_{n=0}^{\infty} \frac{z^{-n}}{1+n} = - z \ln \left(\frac{z-1}{z}\right)$$

when $|z| \geq 1$ and $z \neq 1$. When $z=1$, we have the (divergent) harmonic series.

Can this LTI system be implemented? Using finite-precision arithmetic, $h (n)$ will eventually underflow at some very large $n$. Hence, we can truncate the infinite impulse response $h$, which produces an FIR filter that requires an astronomically long cascade of delays.

Of course, the same underflow would happen if we had the causal infinite impulse response $2^{-n}$. However, $2^{-n}$ is a real exponential and can be produced by the 1st order difference equation

$$y (n) - \frac 12 y (n-1) = x (n)$$

which requires only $1$ adder, $1$ multiplier and $1$ delay.

Exponentials — whether real or complex — have low complexity, i.e., they can be generated using few adders, multipliers and delays. Do note that discrete-time exponentials are eigenfunctions of the delay operator.

Answer 3

A non-integer delay is infinite-dimensional. It can be implemented in an apparatus with a different sampling time. Also, continuous-time transfer functions can be implemented with analog devices, and may not have finite implementations with a fixed sample time.