-1
$\begingroup$

I would like your help on a theoretical question regarding convolution.

The point is to design a faster discrete-time convolution operator functioning on one-dimensional space so that y[n] = x[n] * h[n] where * is the traditional convolution operation and both x[n] and h[n] are finite-length sequences. Lets assume that we have infinite storage or memory but we have finite time. What strategy or algorithm can we use for a faster discrete-time convolution operation.

And also shown the algorithm or the strategy please.

Thank you in advance.

$\endgroup$
  • 3
    $\begingroup$ If I had an algorithm for faster convolution, I'd publish it in a journal (before posting it here). This is a problem that has been worked on for decades; I'd wager that you won't get many answers. Let us know if you make progress, though :) $\endgroup$ – MBaz Oct 21 '18 at 23:14
  • $\begingroup$ Bless you mate :D. I sure will. $\endgroup$ – Shkodrani Oct 21 '18 at 23:30
  • 2
    $\begingroup$ Please consider also in your comparison of optimized approaches the well understood relationship using fft's: $conv = ifft(fft(a)*fft(b))$. Also note that cross correlation is also solved with a similar fft relationship: $xcorr = ifft(fft(a)*conj(fft(b))$, where "conj" is the complex conjugate. $\endgroup$ – Dan Boschen Oct 22 '18 at 0:23
  • $\begingroup$ @DanBoschen Indeed, AFAIK for non-short sequences that approach is the fastest known. Since we don't know that current FFT algorithms are the fastest possible, the implication is that we don't know if there are faster algorithms for convolution either :) $\endgroup$ – MBaz Oct 22 '18 at 0:31
  • 2
    $\begingroup$ @MBaz Yes indeed. That's why I am rooting for Shkodrani and look forward to his FCATW implementation! $\endgroup$ – Dan Boschen Oct 22 '18 at 0:42
0
$\begingroup$

It's not very clear whether you ask for :

  • a more efficient definition of the standard convolution operator between two sequences $x[n]$ and $h[n]$ given as:

$$ y[n] = x[n] \star h[n] = \sum_{k=-\infty}^{\infty} h[k] x[n-k] $$ which would yield the same $y[n]$ per given $n$, but with a different formulation which would require less number of arithmetic operations and hence will be more efficient to compute.

or:

  • a more efficient implementation of the standard convolution operator, (instead of using the direct sum approach) which would produce the same $y[n]$ per given $n$, based on the same formula above but using an architecture that lends the same result with less number of operations.

Note that whether these two approaches are indeed distinct or just the same thing stated differently is also a matter of debate.

Neverthless, for the second approach, as Dan Boschen has already stated, the Fast Fourier Transform (FFT) algorithm, which is indeed a fast compuation of DFT (discrete Fourier transform) can be used to implement the standard convolution operator at a much faster rate (due to less number of MACs) when sequences are long enough.

Furthermore, again for the second approach, based on your statement that you have infinite memory (and I would add that also an infinite (very large) number of FPU ALUs) then you can implement the direct sum approach using a massively parallel architecture. You would still be performing the same number of MACs but since they are in parallel, the execution steps will be much shorter, and therefore faster.

For example, assume those two sequences above are defined in $0 \leq n \leq N_x$ and $0\leq n\leq N_h$ respectively. The standard convolution will produce $y[n]$ which is defined for $0\leq n \leq N_y = N_x + N_h -1$.

Then a direct sum approach performed on a single core (single ALU) serial execution architecture would compute about $\min\{N_h,N_x\}$ MACs per each output sample of $y[n]$, totalling a $\min\{N_h,N_x\}\times N_y$ MACs. (The exact number should take the partially overlapping edge cases in detail and is less than this upper bound.) Due to serial processing, each output time is added onto.

Now if all those $N_y$ output samples are computed in parallel, then $N_y \times$ times faster execution is possible (still doing the same number of MACs though).

Furthermore, computation of each output sample would normally take $\min\{N_h,N_x\}$ MACs and in a serial computation that would also require $\min\{N_h,N_x\}$ steps (apprx CPU cycles). But a parallel computation of that dot product would also yield substantial execution (step) time reduction.

As a result, the parallel execution time of a direct sum approach of the standard convolution operator reduces into that of a single dot product time between two vectors of length $\min\{N_h,N_x\}$, which can be done (again in parallely) in $\log_2 \min\{N_h,N_x\}$ MAC steps. Quite fast compared to serial $N_y \times \min\{N_h,N_x\}$ steps.

Note that we have ignored any kind of overhead; data movement, memory management, synchronization, etc. These can very easily overwhelm any gains you would expect from a parallel execution.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.