Simultaneous convolution and downsample
1. Problem statement
We are given a signal of interest \(a\) characterized by its sample period and number of samples \(s_a: (T_a, N_a)\) and a filter signal \(b\) with sampling \(s_b: (T_b, N_b)\). We restrict the problem to the case where the ratio of sample periods, \(R=T_a/T_b = L/M,\ \{L,M\} \in \mathbb{N}\) can be expressed as an integer fraction. With no loss of generality we take the case where \(T_a \le T_b,\ R < 1\). That is, we give mere semantics in defining “the filter” as being the signal that is sampled more slowly than the defined “signal of interest”. We then wish to apply the filter to the signal of interest such that the result is sampled with the slower period \(T_b\).
2. Common sampling period
In the special case that \(T \equiv T_a = T_b\) there is of course no downsampling required. The problem reduces to performing only the filtering through convolution. As we do not know the extent over which each signal is nonzero we should apply linear convolution to avoid any “wrap-around” effects that a cyclic convolution may cause. This requires extending both signals with zero-valued interval domain samples to a length at least \(N_a + N_b - 1\). We will choose to add an additional sample and extend by \(N_c = N_a + N_b\) and recognize that this is equivalent to extending the signals by the sum of their durations.
\begin{align} s^e_a: (T,N_c) &= extend(s_a, N_c) \\ s^e_b: (T,N_c) &= extend(s_b, N_c) \end{align}The convolution is most efficiently performed as a multiplication in the frequency domain through application of discrete Fourier transform (DFT) \(S\equiv\mathcal{F}\{s\}\) according to:
\begin{align} c = a \circledast b & \leftrightarrow C = A B \\ A = \mathcal{F}\{a\} & \leftrightarrow a = \mathcal{F}^{-1}\{A\} \end{align}Where we denote a signal in the (time) interval domain with a lower case letter and in the frequency domain with an upper case letter. Multiplication of two signals such as \(AB\) is understood to be performed in a sample-wise basis.
To apply this isometry requires the two signals to have equal frequency sample bandwidth \(\delta F = \frac{1}{NT}\). By construction, they have the same sample period and after extension the same size and thus the same sample bandwidth.
The procedure now applies the convolution
\begin{equation} s^e_c = conv(s^e_a, s^e_b) \end{equation}Where the \(conv(a,b)\) function is assumed to be implemented as
\begin{align} S_a &= \mathcal{F}\{s_a\} \\ S_b &= \mathcal{F}\{s_b\} \\ S_c &= S_aS_b \\ s_c &= \mathcal{F}^{-1}\{S_c\} \end{align}At this point the signal \(s^e_c: (T, N_c)\) may be truncated to size \(N_a\) or \(N_b\) or etc as required by downstream algorithms.
3. Upsample-filter-downsample
When \(T_a \ne T_b\), the above procedure can not be applied. We may resample one (or in principle both) signals in order that they have common sample bandwidth \(\delta F_a = \delta F_b\). We should not downsample the “faster” signal \(s_a\) as there is no available anti-alias filter (after all, that is what \(s_b\) is for). On the other hand, we may safely upsample the \(s_b\) to sample period \(T_a\).
\begin{equation} s^{u}_b:(T_a, N_b/R) = interp(s_b, 1/R) \end{equation}We assume the \(interp(s,r)\) function interpolates \(s:(T,N) \to s^u:(T/r,rN)\) and is implemented according to the procedure:
\begin{align} S:(T,N) &= \mathcal{F}\{s\} \\ S^u:(T/r,rN) &= resize(S, r) \\ s^u:(T/r,rN) &= \mathcal{F}^{-1}\{S^u\} \end{align}Where the \(resize(S, r)\) function will remove samples from or insert samples to signal \(S:(T,N)\) so that the new signal \(S^u\) is sampled as \((T/r, rN)\), keeping \(\delta F = \frac{1}{NT}\) constant. When upsampling \(r>1\), zero-valued samples are inserted above the original Nyquist frequency \(\frac{1}{2NT}\). When downsampling \(r<1\), all existing samples above the new, downsampled Nyquist frequency \(\frac{r}{2NT}\) are removed.
The frequency sample bandwidth of the upsampled filter signal now matches that of the original signal of interest. The previously described common sampling period procedure may now be applied to the original signal of interest \(s_a:(T_a,N_a)\) and the upsampled filter signal \(s^u_b:(T_a,N_b/R)\). This results in a signal \(s^u_c:(T_a,N_c = N_a + N_b/R)\). To complete the problem, this signal is downsampled
\begin{equation} s_c:(T_b, N=RN_a + N_b) = interp(s^u_c, R) \end{equation}In summary, the high level procedure is
\begin{align} s^u_b &= interp(s_b, 1/R) \\ N_c &= N_a + N_b/R \\ s^e_a &= extend(s_a, N_c) \\ s^{eu}_b &= extend(s^u_b, N_c) \\ s^{eu}_c &= conv(s^e_a, S^{eu}_b) \\ s^{e}_c &= interp(s^{eu}_c, R) \end{align}4. Single-step
In the high-level procedure summary of the upsample-filter-downsample it is obvious that the final two steps can be rewritten as the function composition \(interp(conv(a,b),r) \to (interp \cdot conv)(a,b,r)\). This allows the \(resize()\) function that makes up the payload of \(interp\) to be applied directly to the intermediate spectrum calculated after the multiplication inside \(conv\).
The two earlier calls to \(extend()\) do not fall to such simple optimization as they operate in the interval domain, by construction. However, we may perform the extension required for the eventual \(conv()\) prior to the interpolation by extending the original signals by suitable amount.
Recalling how the extension in size for signals of common sample period is equivalent to extension in duration, we extend each signal of differing sample period based on their duration.
\begin{align} d_c &= d_a + d_b = T_aN_a + T_bN_b \\ s^e_a &= extend(s_a, d_c / T_a) \\ s^e_b &= extend(s_b, d_c / T_b) \end{align}The extend signals \(s^e_a:(T_a, N_a + N_b/R)\) and \(s^e_b:(T_b, N_aR + N_b)\) may each be transformed to the frequency domain. As they have the same duration, they have the same sample bandwith and the order of the frequency domain multiplication and \(resize()\) are commutative.
\begin{align} S^{ed}_a &= resize(S^{e}_a, R) \\ S^{ed}_c &= S^{ed}_a S^e_b \\ s^{ed}_c &= \mathcal{F}^{-1}\{S^{ed}_c\} \end{align}This final signal is \(s^{ed}_c:(T_b, N_aR+N_b)\). A total of one forward \(\mathcal{F}\) for each original, extended signal and one inverse \(\mathcal{F}^{-1}\) for the final signal has been applied.
5. Prime factoring constraint
With the two applications of \(extend()\) performed on the initial interval-domain signals the problem is reduced to one application of \(\mathcal{F}\) at size \(N_a + N_b/R\) and another at size \(N_aR+N_b\) followed by \(\mathcal{F}^{-1}\) also at size \(N_aR+N_b\). For a DFT to be implemented as via FFT the size must consist of small prime factors. Any prime factors larger than, typically 5 or 7 will incur performance penalties worse than \(\mathcal{O}(n\log n)\).
For a given DFT size \(N\) one may always find a size \(N+n\) that satisfies this small-prime-factor requirement. In many cases the extra computation cost of a somewhat larger size is offset by the speed provided by FFT.
When applied in the context of the above procedure, care is needed to assure that the additional extension retains a common total duration for the signal of interest and the filter signal. Simplifying notation, after initial extension we have \(s_a:(T_a, N_a)\) and \(s_b:(T_b, N_b)\) and wish to further extend to \(s^t_a:(T_a, N_a+n_a)\) and \(s^t_b:(T_b, N_b+n_b)\) such that \(N_a + n_a\) and \(N_b + n_b\) are factored by (in general, a different) set of small primes. For any \(n_a\) and \(n_b\) the common total duration requires \(\frac{N_b+n_b}{N_a+n_a} = R = \frac{N_b}{N_a}\) or \(n_a/n_b = N_a/N_b\). In general it may not be easy to guarantee a simultaneously satisfying \(n_a\) and \(n_b\). Though, in some practical cases, the size \(N_b + n_a\) will see multiple downstream uses. In such cases, optimizing on this number and leaving the signal in the frequency domain can bring additional optimization.