# 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. 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. 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. Aug 29 '16 at 13:10

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 $$|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 is nothing more than a polynomial that can be factorized, being this condition applicable in a recurrent way.

Hence our definitions:

ALL $$\leftrightarrow$$ FIR $$\lor$$ IIR

IIR $$\leftrightarrow$$ TF $$\lor$$ IS

IS $$\leftrightarrow$$ KIS $$\lor$$ UIS

And our known relations: FIR $$\rightarrow$$ BIM (By construction)

TF $$\rightarrow$$ BIM (By construction)

KIS $$\rightarrow$$ BIM (Counter-Example 1)

UIS $$\rightarrow$$ not BIM (Infinite Terms)

And finally, a Bounded in Memory System is a FIR, a TF or a Known Expansion Infinite Series.

BIM $$\leftrightarrow$$ FIR $$\land$$ TF $$\land$$ KIS

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. 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. Nov 13 '16 at 21:52
• You said that H was LTI, so "H is LTI" and "H is not FIR" implies "H is IIR." Nov 13 '16 at 22:02
• It has been many years but I still don't get it - how is the $log(1 + az^{-1})$ example BIM? How would you actually implement that transfer function in a BIM way? That $.../t$ term in the denominator is where I'm stuck... Jan 12 '21 at 6:43
• OK thanks, I think I get it. I will try to look at this all later... Jan 31 '21 at 10:18