I do not specialize in signal processing so I wonder if there is any references to the following procedure.

Let $[n]=\{0,1,\ldots,n\}$.

Consider the function $f:[n] \to \mathbb{R}$ and $g:[kr] \to \mathbb{R}$, such that $\operatorname{supp} g = \{0,r,2r,3r,\ldots,kr\}$. Assume for simplicity, $n/r$ is a integer.

We are interested in computing the linear convolution $f*g$.

If $r$ is large, one way to do the computation is partition $f$ into $r$ functions $f_0,\ldots,f_{r-1}$, such that $f_i(t) = f(tr+i)$, and $f_i:[n/r]\to \mathbb{R}$.

We also define $\bar{g}:[k]\to \mathbb{R}$ as $\bar{g}(t) = g(rt)$.

Find $f_i*\bar{g}$ to each $i$, then we can read off $(f*g)(tr+i) = (f_i*\bar{g})(t)$.

This make sure we apply $r$ convolutions on sequence of length $n/r$ and $k$. Instead of $1$ convolution on sequence of length $n$ and $kr$.


This is known as polyphase decomposition. It is often used as en efficient implementation of filtering combined with decimation or interpolation.

| improve this answer | |

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.