1
$\begingroup$

We are performing a convolution of audio signal, with 511th order FIR filters, using fast convolution methods: overlap-add or overlap-save. Filters are being designed in frequency domain several thousand times per second. Filters need to be zeros padded to be used in order to be used in fast convolution algorithms, so to acquire appropriately padded filters we do:

  1. frequency domain filter design, filters of 511th order
  2. IFFT into time domain
  3. zeros padding to 2048 length (1536 zeros)
  4. FFT back into frequency domain (for multiplication with spectral representation of input audio signal)

Computational complexity of such operation occurred be to high for our needs. We're trying to figure out if there's a method to avoid IFFF->FFT steps and reduce the overall complexity from O(NlogN) to O(N). Any ideas if it is possible, and, if so, how can it be achieved?

Improve this question
$\endgroup$
3
  • $\begingroup$ Interesting idea. You asked for "any ideas" so ... Have you gone back to the defining equations (simplified by leaving out the overlap add) and tried rearranging computations to see if anything combines or drops out? The chirp z transform is presented as if it was discovered this way. Also you can look into alternate filter design approaches that may offer math that combines well with the other computations. Look at iterative FIR design approaches, for example Parks-McClellan which can be generalized for any response. Maybe the equations will play better together. $\endgroup$
    – user2718
    Mar 28, 2014 at 14:07
  • $\begingroup$ You're not going to get the general FIR filtering problem down to an $O(n)$ complexity; if there was such a technique, it would be widely used. For long filters like you're using, fast convolution techniques are much faster than direct discerete-time convolution, which has complexity $O(n^2)$. If you're not able to keep up with the required computations, then you may have to decrease the length of your filter. $\endgroup$
    – Jason R
    Mar 28, 2014 at 14:29
  • $\begingroup$ As I read the post it is the filter design problem that the OP seeks to optimize. Is there a reason you can't design a length 2048 frequency domain filter directly? $\endgroup$
    – John
    Mar 28, 2014 at 16:28

1 Answer 1

Reset to default
2
$\begingroup$

Zero-padding is one domain is equivalent to Sinc (or Dirichlet) convolution in the other, which is O(n^2), so that won't save you. For less computation, you might want to try different filter design methods (compositing existing FIR filters, IIRs, etc.) or finding a way to recompute your filter less often.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you very much for every idea! We've been taking everything into consideration :) $\endgroup$
    – Caudi
    Apr 8, 2014 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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