# For a discrete LTI system, does “bounded memory” imply “rational transfer function?”

Every LTI system with a $\mathcal Z$-domain transfer function that is a rational function - aka a quotient of two polynomials in $z$ - can be implemented using a bounded amount of memory.

Is the converse true? That is, are there any LTI systems that can be implemented using finite memory that do not have a transfer function that is a rational function?

Proving rational transfer function $\rightarrow$ finite memory is easy - any such system can be rewritten in the time domain as a linear constant-coefficient difference (LCCD) equation, so you end up needing only a finite number of delay lines to provide an implementation of the system.

Proving finite memory $\rightarrow$ rational transfer function seems less easy.

One way to look at it is, does finite memory $\rightarrow$ LCCD equation? That is, are there any finite memory LTI systems that cannot be expressed as an LCCD equation?

• " are there any LTI systems that can be implemented using finite memory that do not have a transfer function that is a rational function?" --- i think theanswer is no. – robert bristow-johnson Aug 10 '16 at 4:43
• Have you seen this question (with no answer, maybe for a reason)? It refers to this paper, which describes the implementation of irrational transfer functions with so-called "mapping functions". I'm not sure if it describes what you're looking for. – Matt L. Aug 10 '16 at 8:13
• Thanks, had not seen that. Apparently those require an unbounded amount of computation in the size of the input, so it isn't physically realizable in a different sense. – Mike Battaglia Aug 29 '16 at 13:10

## 1 Answer

Non-trivially, the answer is no, a Bounded In Memory (BIM) LTI system do not imply the system has a rational Transfer Function (TF).

Proof (TL;DR):

Every discrete LTI system $H$ has an Impulse Response (by definition), and hence have a TF in the z-domain (by construction), which could be infinite (IIR) or finite (FIR).

A FIR LTI is trivially BIM, requiring a bounded number of operation for implement every convolution.

A IIR LTI could have a Rational TF (RTF) -such as most ARMA systems- or could have an not rational -an infinite series (IS)- TF -such as the counter-example 1 below.

If the system has an IS TF which can be decomposed as a rational TF -such as the counter-example 2-, then the system is bounded in memory, because the rational TF can be decomposed into a pair of finite series, which can be implemented and evaluated with finite memory and finite CPU.

Similarly, if the system has an IS TF with an known algebraic expansion (KIS), -such as the counter-example 1-, then again the system is BIM, because, the general term is computed in each step, consuming an increasing amount of CPU -this is, an unbounded CPU system- but still BIM.

If this is not the case, that is, if the system has an IS TF without an unknown algebraic expansion (UIS) -which is indeed real for most LTIs- then is not BIM in practice.

The condition here for an IS to be not rational is having no poles and no zeros, that is, being bounded: $$0<H(z)=\sum_0^\infty c_nz^{-1}<\infty$$ $|z|>z_0$ for some $z_0$.

If the series crosses by zero through $z_i$, or diverges for some $p_i$, then it has a rational set of component $(1-z_iz^{-1})$ or $(1-p_iz^{-1})$, which can be factorized, and the condition is applied again to the residual series.

Hence:

LTI $\rightarrow$ FIR $\vee$ IIR LTI

FIR LTI $\rightarrow$ BIM LTI

IIR $\rightarrow$ TF $\vee$ IS

TF LTI $\rightarrow$ BIM LTI

IS $\rightarrow$ Known IS $\vee$ Unknown IS

Known IS LTI $\rightarrow$ BIM LTI (Counter-example 1)

Unknown IS LTI $\rightarrow$ not BIM LTI

Counter Example 1: The LTI system, with IIR defined by its Z-transform, is BIM, but has not rational TF:

$$H(z)=log(1+az^{-1}), h(t)=\frac{(-1)^{t+1}a^t}{t}\Gamma(t), t>0$$

We are using the exploit that: $$log(1+x)=\sum_{n=1}^\infty \frac{(-1)^{n+1}x^n}{n}, x<1$$

which in general is not valid, thus this procedure will produce unbounded LTI systems except for the trivial power series functions $sin(x)$, $cos(x)$,$e^x$...

We are also assuming that our TF must be finite in terms, which is the purpose of having a TF, provided that all Impulse Responses can be converted into series in Z space.

http://www.comm.utoronto.ca/~dkundur/course_info/362/6_Kundur_Rationalz-Transf_handouts.pdf

Counter Example 2: The IIR AR System has both a rational and an infinite series transfer function: $$H(z)=\frac{1}{1-az^{-1}}=\sum_{n=0}^{\infty}a^nz^{-n}, |a|<|z|$$

• There exist LTI systems with bounded memory and infinite-length impulse response. – Mike Battaglia Nov 13 '16 at 21:22
• I get that you are claiming no, but your proof sketch on step 1 claims finite memory <-> FIR, and assuming <-> means "if and only if," the proof falls apart. – Mike Battaglia Nov 13 '16 at 21:52
• I think i could figure a counterexample. I will put the answer in stasis.... – Brethlosze Nov 13 '16 at 21:59
• You said that H was LTI, so "H is LTI" and "H is not FIR" implies "H is IIR." – Mike Battaglia Nov 13 '16 at 22:02