# Recursive filter with truncated polynomial impulse response

How can we recursively implement a causal discrete-time truncated infinite impulse response (TIIR) filter with an arbitrary truncated polynomial impulse response:

$$h[n] = \begin{cases}\displaystyle\sum_{k=0}^K c_k n^k&\text{if }0\le n

where real $$c_k$$ are the arbitrary coefficients of the polynomial, nonnegative integer $$K$$ is the degree of the polynomial, $$0^0 = 1$$, and positive integer $$N$$ is the length of the part of the impulse response that may be non-zero?

Perhaps a recursive form allows time complexity to be not dependent on $$N$$, giving an efficient implementation when $$K$$ is small, even when $$N$$ is large. Moving average can be implemented recursively as an integrator with tail cancellation. That's a $$K=0$$ degree truncated polynomial impulse response. Perhaps higher degree polynomials are also possible.

A cascade of identical moving average filters gives a B-spline impulse response, which is a piece-wise polynomial of any desired degree but lacking arbitrary control of the polynomial coefficients. Perhaps some form of tail cancellation allows to isolate a single piece of a higher degree B-spline impulse response and to linearly combine the piece with the same of lower degree B-splines to get arbitrary polynomials of any degree. Or maybe there is another approach.

Some promising literature I found: Oscar G. Ibarra-Manzano, Yuriy S. Shmaliy, "Implementation of Digital Unbiased FIR Filters with Polynomial Impulse Responses", Circuits Systems and Signal Processing, April 2012.

• it seems to me that the only TIIR you will get is of the form: $$h[n] = \begin{cases} \sum\limits_{k=1}^K c_k p_k^n &\text{if }0\le n<N,\\ 0&\text{otherwise,}\end{cases}$$ where $p_k$ are the $K$ poles (some might be complex conjugate pairs) of the parallel sections of the untruncated recursive filter that you get with partial fraction expansion. – robert bristow-johnson Apr 25 at 20:24
• did i send you my little TIIR pdf for how to define the delayed tap coefficients to exactly truncate the IIR tail for first and second-order sections? – robert bristow-johnson Apr 25 at 20:30
• @robertbristow-johnson that form is easy. I have read Martin Vicanek's paper on reverse IIR filters extending the original invention by cbbuntz. Martin handles each second-order section as a first-order section with complex coefs with the output a weighted sum of the real and imag outputs. But here I think we'll only need "marginally stable" integrator poles at 1 on z-plane. – Olli Niemitalo Apr 26 at 3:21
• BTW, the original reverse IIR thing is the Powell and Chau and the original TIIR is Wang and Smith. and more than a decade before Vicanek I was saying that the Wang and Smith TIIR thing should be combined with Powell and Chau block reversal processing thing to do linear-phase IIR-like responses and cheaper than 4000-tap FIR. – robert bristow-johnson Apr 26 at 3:35
• did i send you that TIIR document of mine? lemme look for it. – robert bristow-johnson Apr 26 at 3:36

I don't think you can, I don't see any special property of the truncated polynomial representation that would help here.

The impulse response coefficients are related to the polynomial coefficients through a set of linear equations, so we can simply write this as a matrix multiplication.

$$h = M \cdot c$$ where $$h$$ is the impulse response vector, $$c$$ the polynomial coefficient vector and $$M$$ a matrix that looks something like $$M = \begin{bmatrix} 1 & 0 & 0 & ... \\ 1 & 1 &1 & ... \\ 1 & 2 & 4 & ... \\ 1 & ... & ... & ... \end{bmatrix}$$

That matrix appears to be invertible, so we simply express the polynomial coefficients as

$$c = M^{-1} \cdot h$$

for any given impulse response. That means that every FIR impulse response can be represented in truncated polynomial form and there is really nothing special about it. If there were a way to implement this recursively, it would mean that every FIR filter can be implemented recursively which, to the best of my knowledge, is not the case.

• This is all correct. I'm thinking of the case $K \ll N$. I have clarified the question. – Olli Niemitalo Apr 25 at 13:11
• Sorry, I misunderstood. Will think some more. – Hilmar Apr 25 at 14:37
• Hi: This is probably not terribly helpful but, in econometrics, there is something called the koyck distributed lag. I'm not clear what your variables represent ( I'm a permanent DSP beginner ) but you might want to take a look at it because it's possibly related. There's so much literature on it that I'm just linking to the first one that popped up. It's on page 5 of the document at this link. fhi.sk/files/katedry/kove/predmety/Prognosticke_modely/…. – mark leeds Apr 26 at 6:19
• One more thing: Note that there are two different Koyck distributed lag models because of the different error term assumptions. This is why the discussion goes from page 5 to page 8. The error term assumption is more of an econometric issue so I'm not sure what it would imply for what you are doing. And, if this is totally not related, then my apologies for the noise. – mark leeds Apr 26 at 6:23

Consider transfer function of FIR filter with N-taps:

\begin{align} H(z) = \sum\limits_{n = 0}^{N - 1} h_n z^{-n} \end{align}

We can change it to IIR filter by adding pair of pole-zero with unity gain at $$-a_1$$:

\begin{align} H(z) &= \sum\limits_{n = 0}^{N - 1} h_n z^{-n} \\ &= \frac{(1 + a_1 z^{-1}) \sum\limits_{n = 0}^{N - 1} h_n z^{-n}}{1 + a_1 z^{-1}} \\ &= \frac{\sum\limits_{n = 0}^{N - 1} h_n z^{-n} + \sum\limits_{n = 0}^{N - 1} a_1 h_n z^{-(n + 1)}} {1 + a_1 z^{-1}} \\ &= \frac{\sum\limits_{n = 0}^{N - 1} h_n z^{-n} + \sum\limits_{n = 1}^{N} a_1 h_{n - 1} z^{-n}} {1 + a_1 z^{-1}} \\ &= \frac{h_0 + a_1 h_{N-1} z^{-N} + \sum\limits_{n = 1}^{N - 1} (h_n + a_1 h_{n-1}) z^{-n}} {1 + a_1 z^{-1}} \end{align}

So, the required condition is for $$1 \le n < N$$:

\begin{align} h_n + a_1 h_{n-1} &= 0 \\ h_n &= -a_1 h_{n-1} \\ h_n &= (-a_1)^n h_0 \end{align}

When $$a_1 = - 1$$, it is moving average filter. But it seems that the required condition of $$h_n$$ is unrelated with truncated polynomial impulse response definition.

We can also expand it with higher order polynomial denumerator $$1 + \sum\limits_{m=1}^{M} a_m z^{-m}$$. In that case, the required condition is:

\begin{align} h_n + \sum\limits_{m=1}^{M}a_m h_{n-m} &= 0 \\ h_n &= - \sum\limits_{m=1}^{M}a_m h_{n-m} \end{align}