# Method for modifying frequency-domain signal to produce predetermined time-domain signal

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?

• 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. Mar 28, 2014 at 14:07
• 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. Mar 28, 2014 at 14:29
• 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?
– John
Mar 28, 2014 at 16:28