6
$\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$
  • $\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$ – robert bristow-johnson Aug 10 '16 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. Aug 10 '16 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$ – Mike Battaglia Aug 29 '16 at 13:10
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 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|$$

$\endgroup$
  • 1
    $\begingroup$ There exist LTI systems with bounded memory and infinite-length impulse response. $\endgroup$ – Mike Battaglia Nov 13 '16 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$ – Mike Battaglia Nov 13 '16 at 21:52
  • $\begingroup$ I think i could figure a counterexample. I will put the answer in stasis.... $\endgroup$ – Brethlosze Nov 13 '16 at 21:59
  • $\begingroup$ You said that H was LTI, so "H is LTI" and "H is not FIR" implies "H is IIR." $\endgroup$ – Mike Battaglia Nov 13 '16 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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