2
$\begingroup$

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

$\endgroup$

1 Answer 1

4
+50
$\begingroup$

New Answer

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.

Original Answer

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

$\endgroup$
5
  • $\begingroup$ $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$ $\endgroup$
    – Wang Yun
    Aug 2, 2022 at 11:13
  • $\begingroup$ yes. Good catch. Fixed $\endgroup$
    – Hilmar
    Aug 2, 2022 at 13:01
  • $\begingroup$ Nice update!!!! $\endgroup$
    – Peter K.
    Aug 2, 2022 at 18:17
  • $\begingroup$ @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$. $\endgroup$
    – Wang Yun
    Aug 3, 2022 at 9:20
  • $\begingroup$ 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? $\endgroup$
    – Hilmar
    Aug 3, 2022 at 12:27

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.