# How to implement the recursive FIR filtering of a signal with zero boundary condition?

Now I have a signal $$f(k)$$ with $$k=0,1,\ldots, N-1$$, and $$f(k)=0$$ if $$k<0$$ or $$k>N-1$$, that is, the signal satisfies the zero boundary condition. Then by convolving this signal with a symmetric FIR filter $$b^3(k)$$, I have $$f_0(k) = (f*b^3)(k),$$ in which $$b^3(k)$$ equals to $$1/6$$, $$4/6$$, $$1/6$$, for $$k=-1$$, $$0$$, $$1$$, respectively. Obviously, we can get $$f_0(-1) = f(0)/6 \\ f_0(N) = f(N-1)/6,$$ Therefore, the length of $$f_0$$ is extended to $$N+2$$, with $$f_0(k)=0$$ for $$k<-1$$ or $$k>N$$.

Using $$f_0$$ as initial settings, I want to compute $$f_i$$, which is defined as $$f_{i+1}(k) = (f_i*[h]_{\uparrow 2^i})(k),$$ where $$i=0,1,2,3,\ldots,7$$, and $$[h]_{\uparrow 2^i}$$ is $$h(k)$$ with $$2^i-1$$ zeros between each sample point: $$h(k) = 1/8, \ 1/2, \ 3/4, \ 1/2, \ 1/8, \ \text{for}\ k = -2, -1, 0, 1, 2 \\ [h]_{\uparrow 2^1} = 1/8, \ 0, \ 1/2, \ 0, \ 3/4, \ 0, \ 1/2, \ 0, 1/8, \ \text{for} \ k= -4, -3, -2, -1, 0, 1, 2, 3, 4 \\ [h]_{\uparrow 2^2} = 1/8, 0, 0, 0,1/2, 0, 0, 0,3/4, 0, 0, 0,1/2, 0, 0, 0,1/8, \ \text{for} \ k= -8,-7,-6,-5,-4, -3, -2, -1, 0, 1, 2, 3, 4, 5,6,7,8 \\ \ldots\ldots$$

If I want to obtain values of $$f_{i+1}(k)$$ for $$0\leq k\leq N-1$$, I have to know $$f_i(k)$$ for $$k<0$$ and $$k>N-1$$. However, these values of $$f_i(k<0)$$ or $$f_i(k>N-1)$$ are difficult to know. Can someone help me address this issue? Is there an explicit expression for $$f_i(k<0)$$ or $$f_i(k>N-1)$$?

I think there is a much easier and more general way to tackle this.

Let's assume we have a sequence of $$h[n]$$ that has finite support on $$[K,L]$$ where $$K$$ is the index of the first non-zero sample and $$L$$ is the index of the last non-zero sample, i.e.

$$h[n] = 0, n < K \lor n > L$$

Since that's awkward to write we will simply notate this as

$$\mathbb{S}(h) = [K,L]$$

Where $$\mathbb{S}(h)= ...$$ means "$$h$$ has finite support on $$...$$".

The length $$N$$ of the sequence is simply

$$N = L-K+1$$

Some quick examples: The unit impulse has support on $$[0,0]$$ with a length of 1. A causal sequence of length $$N$$ has support on $$[0,N-1]$$, a zero phase sequence is symmetric, i.e it has support on $$[-M,M]$$ with a length of $$2M+1$$

If we convolve two sequences $$h_1$$ and $$h_2$$ the supports just sum, i.e.

$$\mathbb{S}(h_1*h_2) = [K_1+K_2,L_1+L_2]$$

The length $$N_{1*2}$$ of the convolution comes out to be:

$$N_{1*2} = L_1+L_2 - K_1-K_2+1 = (L_1-K_1+1) + (L_2-K_2+1) - 1 = N_1+N_2 -1$$

as would be expected.

Armed with this formalism, it's easy to calculate the support of your recursive convolution. We look at the support of the impulse responses

$$\begin{array}{cl} \mathbb{S}(h_0) = [-2,2] \\ \mathbb{S}(h_1) = [-4,4] \\ \mathbb{S}(h_2) = [-8,8] \\ ... \\ \mathbb{S}(h_m) = [-2^{m+1},2^{m+1}] \end{array}$$

Let's now convolve a causal sequence $$f$$ with support $$[0,N-1]$$ with the first $$M+1$$ impulse response, i.e.

$$y_M = f * h_0 * h_1 * ... h_{M}$$

The support of the result will simply be the sum of the supports of all individual sequences that are being convolved, i.e we have

$$\mathbb{S}(y_M) = \left[ 0+\sum_{m=0}^M K_{hm},N-1+ \sum_{m=0}^M L_{hm}\right] = \\ \left[ -\sum_{m=0}^M 2^{m+1},N-1+ \sum_{m=0}^M 2^{m+1}\right]$$

With $$\sum_{m=0}^M 2^{m+1} = 2^{m+2}-2$$ we can simplify to

$$\mathbb{S}(y_M) = \left[ -(2^{m+2}-2), 2^{m+2} + N -3 \right]$$

This matches the result in the original answer but seems a lot easier (to me) and also doesn't make any assumptions about symmetry or alignment.

Let's break this down a little.

Let's define $$h_0$$ as $$h[n] = [1/8, \ 1/2, \ 3/4, \ 1/2, \ 1/8], n=[-2,-1,0,1,2]$$. We can than define the other impulse response in the series through upsampling as

$$h_m[n] = h_{m-1}[n] \uparrow 2 = h_0[n] \uparrow 2^m$$

The length $$L_m$$ of each impulse response is

$$L_m = 2^{m+2} + 1$$

with the time index spanning from $$-(L_m-1)/2 ... +(L_m-1)/2$$

We can now define a set of impulse responses $$g_k$$ that are cumulative convolutions of the base impulse responses, i.e.

$$g_0 = h_0, \hspace{1cm} g_k = g_{k-1} * h_{k}$$

where $$*$$ is the linear convolution operator. If you convolve two sequences of length $$N_1$$ and $$N_2$$ the result will have a length of $$N_1+N_2-1$$ and hence the length of the cumulative impulse response will simply be

$$R_k = \sum_{i = 0}^k (L_i)-(k-1) = 2^{k+3}-3$$

Since all individual impulse response are symmetric (zero phase), so will be the cumulative impulse response, i.e. the time index will go from

$$-(R_k-1)/2 = -(2^{k+2}-2) \leq n \leq +(R_k-1)/2 = +(2^{k+2}-2)$$

Now, finally we can convolve the cumulative impulse response with the input signal $$f[k]$$ which goes from $$[0,N-1]$$.

The length of the result, T_k, will be $$T_k = R_k + N -1$$ and the time span will be

$$-(R_k-1)/2 = -(2^{k+2}-2) \leq n \leq +(R_k-1)/2 + N - 1= 2^{k+2} + N -3$$

• $g_0=h_0,g_k$, $g_{k-1}*h_k$ means what ? Does that mean $g_0=h_0$ and $g_k=g_{k-1}*h_k$ Commented Aug 2, 2022 at 11:13
• yes. Good catch. Fixed Commented Aug 2, 2022 at 13:01
• Nice update!!!!
– Peter K.
Commented Aug 2, 2022 at 18:17
• @Hilmar In fact, all I care about are values of $y_M(k)$ for $0\leq k\leq N-1$. I want to search for a memory-efficient way to compute $y_M(k)$ in $0\leq k\leq N-1$. However, this is hindered by the expansion of the length of $y_M$. Commented Aug 3, 2022 at 9:20
• Sorry, I misunderstood your question. "Efficient" always depends on the details. Can you throw CPU at the problem? Do you have latency constraints? How accurate does it need to be ? What are rough numbers for $N$ and how many levels of recursion do you need? Commented Aug 3, 2022 at 12:27