7
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ " 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. $\endgroup$ Commented Aug 10, 2016 at 4:43
  • 1
    $\begingroup$ 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. $\endgroup$
    – Matt L.
    Commented Aug 10, 2016 at 8:13
  • $\begingroup$ 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. $\endgroup$ Commented Aug 29, 2016 at 13:10

1 Answer 1

1
$\begingroup$

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 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|$$

$\endgroup$
8
  • 1
    $\begingroup$ There exist LTI systems with bounded memory and infinite-length impulse response. $\endgroup$ Commented Nov 13, 2016 at 21:22
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Nov 13, 2016 at 21:52
  • 1
    $\begingroup$ You said that H was LTI, so "H is LTI" and "H is not FIR" implies "H is IIR." $\endgroup$ Commented Nov 13, 2016 at 22:02
  • 1
    $\begingroup$ 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... $\endgroup$ Commented Jan 12, 2021 at 6:43
  • 1
    $\begingroup$ OK thanks, I think I get it. I will try to look at this all later... $\endgroup$ Commented Jan 31, 2021 at 10:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.